Adaptation des métaheuristiques pour l'optimisation continue

31/08/2017
Auteurs : Patrick Siarry
Publication REE REE 2006-5
OAI : oai:www.see.asso.fr:1301:2006-5:19716
DOI :

Résumé

Adaptation des métaheuristiques pour l'optimisation continue

Métriques

36
4
2.12 Mo
 application/pdf
bitcache://dcdcccb6ef2027f816d98d66d81698e4fced83b7

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2006-5/19716</identifier><creators><creator><creatorName>Patrick Siarry</creatorName></creator></creators><titles>
            <title>Adaptation des métaheuristiques pour l'optimisation continue</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Thu 31 Aug 2017</date>
	    <date dateType="Updated">Thu 31 Aug 2017</date>
            <date dateType="Submitted">Mon 15 Oct 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">dcdcccb6ef2027f816d98d66d81698e4fced83b7</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33490</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Dossier MÉTHODOLOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS Adaptation des métaheuristiques m m pour l'optimisation continue ) ? Ir ! n ? r=S Métaheuristiques, Optimisationcombinatoire, Optimisationcontinue Patrick SIARRY Université de Paris 12 Val-de-Marne Laboratoire Images, Signaux et Systèmes Intelligents (LISSI, EA 3956) 1. Cadre général de l'optimisation continue " difficile " 1.1. Quelques problèmes-types On peut classer en trois familles les problèmes " diffi- ciles " couramment rencontrés en variables continues : . les problèmes d'optimisation proprement dits ; . les problèmes d'identification ou de caractérisation ; . les problèmes d'apprentissage. Nous illustrons chacune de ces familles par un exemple d'application. 1. 1. 1. Exemple de problème d'optimisation propre- ment dit : l'optimisation des performances d'un circuit électronique Nous supposons connu le schéma électrique du circuit, qui réalise une fonction donnée : par exemple, un généra- teur de courant constant, ou un amplificateur à large bande passante. Ce circuit comporte n " paramètres " : par exem- ple, les valeurs des résistances, les géométries des transis- tors, etc. Pour chacun d'entre eux, nous connaissons généralement la plage des valeurs physiquement admissi- bles. Le problème de l' " optimisation des performances du circuit " consiste à chercher la valeur numérique qu'il faut attribuer à chacun des n paramètres disponibles pour que le circuit réalise, au mieux, un objectif donné. Exemple : optimisation d'un générateur de courant constant : Le circuit considéré est représenté sur la figure 1. Il s'agit d'un générateur de courant constant, comportant 4 transistors MOS, notés MI à M,. Les 8 inconnues du problème sont les dimensions 5 v M. (.L) (w.. t) M, Il 1l w,.f f +5 v .. M2 (W')," ) Figure 1. Géiiéi-atelii- de colii-tiiit t'oiistaiit problèiiie d'optiniisatioii ii 8 vcii-iables. (largeur W et longueur L) du canal de chaque transistor. Les spécifications imposées pour le circuit sont les suivantes : le courant i délivré doit être constant et égal à 50 tA, quelle que soit la valeur, entre - 3 V et - 2 V, de la tension continue de sortie V,. La fonction objectif f est formée en exploitant un simulateur de circuits, tel que SPICE. En mode " simula- tion continue ", le simulateur évalue le courant i délivré par le générateur, lorsque la tension d'utilisation V, prend une valeur donnée. Dans cette application, réalisée au CEA, Centre de Bruyères- le-Châtel, f est formée à partir des résultats de 6 simulations continues, correspondant aux 6 ESSENTIEL SYNOPSIS Danscet article,nousprésentonsd'abordle cadregénéralde l'op- timisation continue "diffici ! e " ;aprèsavoirdécrit quelquesapplica- tions typiques, noussoulignonsles difficultés spécifiquesauxpro- blèmes continus. Puisnous décrivonsquelquesécueilsde l'adap- tation des métaheuristiquesaux problèmesà variablescontinues. Dansune secondepartie, nous exposons,à titre d'illustration,les méthodes que nous avons proposées pour adapter quelques métaheuristiques: le recuit simulé, la recherchetabou et les algo- rithmes génétiques. In that paper,we present first the generalframe of "hard" conti- nuous optimization: we describe some typical applications,then difficulties peculiar to continuous variable problems are pointed out. Afterwards we describea few pitfallsof the adaptationof dis- crete metaheuristicsto continuousvariableproblems. ln a second part,we present,as an illustration,the methods that we havepro- posed to adapt some metaheuristics: simulated annealing,tabu searchand genetic algorithms. REE No 5 Mai2006 Dossier MÉTHODOEOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS valeurs suivantes de V, : - 3, - 2,8 ; - 2,6, - 2,4 ; - 2,2 et - 2 V. Les simulations donnent les courants cor- respondants : il,..., if, (en ! -tA). On pose alors : F - 1,-,, (i, - 50)' Pour un jeu fixé de dimensions des canaux des tran- sistors, 6 simulations continues sont ainsi nécessaires pour aboutir à une évaluation de la fonction objectif. Notons que le choix du nombre de simulations résulte d'un compromis entre le temps de calcul (proportionnel à ce nombre) et la recherche d'une meilleure adéquation du circuit électronique avec l'objectif fixé. 1. 1.2. Exemple de problème d'identification ou de caractérisation : le "calage " d'un modèle de moteur électrique synchrone Dans une application réalisée avec le Centre de Génie Electrique de Lyon (CEGELY) [Clerc et aL 02], l'objectif était de faire coïncider au mieux les courbes calculées (sorties du modèle) et les courbes expérimentales (mesu- res relevées sur le moteur). Le banc expérimental permet- tant d'effectuer les mesures sur le moteur synchrone (MS) est représenté sur la figure 2. Les 19 inconnues de ce pro- blème d'optimisation sont tous les paramètres du modèle numérique. La fonction objectif à minimiser traduit l'écart (valeur absolue ou moindres carrés) entre les données expérimentales et les grandeurs calculées par le modèle. 1 1.. -1, Figure 2. Banc expérimental pour le relevé de mesures sur un inoteiir synchrone (MS). 1. 1.3. Exemple de problème d'apprentissage Ce type de problème se rencontre avec les réseaux de neurones, ou les bases de règles floues. Nous l'illustrons avec le " réseau de neurones analogique " de la figure 3, utilisé par le CEA pour reproduire au mieux la fonction sinus sous forme câblée [Berthiau et al. 94]. Ce réseau de neurones multi-couches, de type " icedfbrward ", est uti- lisé pour calculer : y - 0,8 sinX, pour - JI <_ X <_ + Le réseau admet deux entrées : l'argument X de la fonction sinus et l'entrée constante Xo (qui permet d'ajus- ter la fonction d'activation de chacun des neurones du !: y \ -L-' "____<''* - M- ---L.'----. 'r-- +. ----t ---..'-. , .S' cl'eii,eiiible Élit " ré.eciii de iieiii-oiie, cii7tilo (ritlliL,". 1 1 11 " --. 1 - : " 1 &&si . 1- 1 i ,-,,- \1 F/1 1 1 (b) Sc-liéiiïticléiciillé cle -liciclite iieiii-oiie. Figure 3. Schémaétecti-iqtte dit " i-éseiti de iieiii-ones analogiqlte " litili,é poiti- l'appro-) iiiiation de la fonction.inifs. réseau). Le réseau comporte deux couches : une couche d'entrée formée de 5 neurones, recevant chacun deux entrées ; une couche de sortie formée d'un seul neurone, qui reçoit 6 entrées. Chaque " coefficient synaptique " du réseau de neurones est matérialisé par une résistance du circuit de la figure 3a. L'apprentissage du réseau de neu- rones se traduit ainsi par un problème d'optimisation à 16 variables : les 16 résistances synaptiques, dont le domaine de variation est fixé à [1 kQ, 1MQ]. On devine, à travers les quelques exemples qui précè- dent, le foisonnement des applications continues, dans tous les domaines de l'ingénierie : en particulier, l'élec- tronique et la mécanique. Il existe en outre de nombreux problèmes " mixtes ", à la fois discrets et continus, tel celui de la recherche d'un schéma équivalent en électronique. 1.2. Difficultés spécifiques aux problèmes continus Pour dégager ces difficultés, nous nous plaçons dans le cas suivant : . problème mono-objectif ; . fonction objectif !, à minimiser ; REE N 5 Mai2006 Adaptation des métaheuristiques pour 1optimisation continue . variables de décision rassemblées dans un vecteur x ; . seules contraintes : " contraintes de boîte " : X.%li i .,< X. < X Les problèmes d'optimisation continus, tels que ceux cités plus haut, présentent souvent des difficultés spécifi- ques. On parle alors aussi de " problèmes difficiles ", même si ce terme ne fait pas référence, ici, à la théorie de la complexité invoquée dans le cas discret. Les principales sources de ces difficultés sont les suivantes : (1) il n'existe pas d'expression analytique der; (2) f est " bruitée ". Ce bruit peut être de nature expéri- mentale, si le calcul de f passe par l'exploitation de mesures. Il peut s'agir aussi d'un " bruit de calcul " numérique, par exemple lorsque f est évaluée via un simulateur de circuits électroniques (qui a recours, en particulier, à des méthodes d'intégra- tion numérique) ; (3) f comporte des non-linéarités ; (4) il existe des corrélations - non précisément loca- lisées - entre certaines variables du problème. Les difficultés (1) et (2) condamnent l'accès aux gra- dients de f Quant aux difficultés (3) et (4), elles entraî- nent l'existence d'un " paysage d'énergie " tourmenté, comportant de nombreux minimums locaux. En conséquence, les méthodes qui s'attachent à résou- dre efficacement de tels problèmes continus difficiles doi- vent posséder deux propriétés : < elles doivent être "directes ", c'est-à-dire sans calcul de gradients : cette condition interdit l'emploi de méthodes classiques puissantes, de " type Newton " ; w elles doivent être "globales ", dans le sens suivant : méthodes non piégées, en principe, dans un mini- mum local. Remarque : Il est à noter que les termes " global " et " local " ci-dessus ne caractérisent pas le type de " mouvement " utilisé : il s'ensuit que, par exemple, le recuit simulé peut être qua- lifié de local, par son mécanisme, mais aussi de global, par sa finalité... Cette double exigence motive le recours aux métaheu- ristiques, qui sont tout à la fois " directes " et " globales ". On peut souligner que l'aspect " direct " des métaheu- ristiques - qui est lié à leur origine combinatoire - n'a pas d'attrait particulier dans le cas discret. Il s'agit, au contraire, d'un avantage déterminant, dans le cas continu difficile. Les considérations précédentes expliquent l'intérêt important suscité par les métaheuristiques dans le contexte de l'optimisation continue. Le revers de la médaille est que la plupart des métaheuristiques ont été conçues dans un cadre discret (à l'exception notable de la méthode des " essaims particulaires ") : d'où la nécessité d'une " adaptation " aux problèmes continus. 1.3. Quelques écueils de l'adaptation des métaheu- ristiques aux problèmes à variables continues Ces écueils sont d'abord d'ordre " culturel " : les appli- cations continues sont en effet le plus souvent du ressort de l'ingénieur, électronicien ou mécanicien par exemple ; en revanche, le savoir-faire concernant les métaheuristi- ques est plutôt du côté des informaticiens, qui sont moins intéressés par les problèmes continus, peu standardisés. Ce décalage explique sans doute la pauvreté des résultats théoriques dans ce domaine. Il existe aussi des écueils d'ordre " technique ", comme : . l'hétérogénéité des domaines de définition des diffé- rentes variables ; . la présence de variables de gammes de définition très étendues (parfois plus de 10 décades). Par ailleurs, la confrontation entre les études empiri- ques concurrentes est périlleuse ; en effet : . les codes concurrents sont rarement publics ; < il est délicat de programmer soi-même toutes les méthodes concurrentes ; . les résultats publiés sont difficilement comparables, du fait de : .jeux différents de fonctions de test, et de domai- nes d'évolution des variables ; . choix différents du mode de sélection du point initial, et du nombre d'exécutions moyennées par résultat ; . définitions différentes du " succès" (approche de l'optimum global x), de l' " erreur finale " (en f ? en x ?), du temps de calcul. E. Taillard préconise une confrontation objective des travaux concurrents, via l'utilisation de tests statistiques [Taillard 02] : cette démarche pourrait régler le problème de la comparaison, si les auteurs de travaux concurrents acceptent de jouer le jeu. De nombreuses méthodes ont été proposées dans la littérature pour adapter les métaheuristiques au cas continu [Dréo et al. 03]. Il n'est pas possible d'en déga- ger des considérations générales, autres que celles-ci : . la plupart des techniques développées pour adapter une métaheuristique ne sont pas applicables aux autres métaheuristiques... . en continu, comme en discret, aucune métaheuristi- que ne semble surpasser ses concurrentes... Pour préciser le domaine, et présenter au lecteur quel- REE No 5 Mai2006 ossîer MÉTHODOLOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS ques exemples de méthodes opérationnelles, nous décri- vons maintenant les techniques que nous avons proposées pour adapter au cas continu quelques métaheuristiques. 2. Quelques métaheuristiques continues 2.1. Recuit simulé Le principal problème concerne la gestion de la " dis- crétisation " de l'espace de recherche. Il faut " maintenir à peu près constante l'efficacité " du processus d'optimisa- tion, tout au long de la descente en température. A cet effet, il faut utiliser la longueur du pas de discrétisation comme un paramètre de contrôle supplémentaire, qui s'adapte automatiquement, par exemple en fonction du taux d'acceptation des modifications tentées, ou de la lon- gueur moyenne des déplacements déjà effectués (cette longueur constituant, en quelque sorte, une mesure de la topographie locale de l'espace des configurations). En pratique, pour la mise au point du recuit simulé continu, on peut procéder comme suit : (1) Le pas de discrétisation, a priori différent pour chaque variable Xi du problème, est noté STEP. 11 représente la variation maximale que peut subir x, en un seul " mouvement ". (2) Pour un pas STEP ; fixé, nous devons préciser la loi F de calcul du mouvement d'une variable, pas- sant de la valeur x, à la valeur x F (x,,STEP,). (3) Comme nous l'avons souligné plus haut, STEP ; doit être ajusté périodiquement, pour maintenir constante l'efficacité de l'optimisation lorsque T diminue ; il est donc nécessaire de choisir : . le mode d'évaluation de cette efficacité : . à l'aide du taux d'acceptation des mouvements tentés ? .à l'aide de l'amplitude moyenne des mouve- ments déjà effectués ? . la fréquence d'ajustement du pas ; . la loi d'ajustement du pas. (4) Nous devons décider quelles variables x, sont concernées par un mouvement donné : . toutes les variables du problème ? . une seule à la fois ? . un sous-ensemble de variables ? Peu de résultats théoriques sont disponibles pour vali- der cette procédure intuitive, et pour préciser ses diverses options. En conséquence, nombre d'auteurs justifient leurs choix en suivant une approche empirique systéma- tique : le programme est évalué et réglé en utilisant, comme fonctions objectifs, diverses fonctions analyti- ques de test publiées, comportant jusqu'à 100 variables. La connaissance a priori des minimums globaux et locaux du problème permet alors d'étudier l'influence des principaux paramètres de la méthode sur sa vitesse de convergence. A titre d'illustration, nous avons représenté trois fonctions de test classiques sur la figure 4. Le réglage que nous avons retenu [Siarry et al. 97] est le suivant : . STEP, initial :'/,, du domaine de variation de x,../4 . STEP, modifié à l'issue de chaque palier de tem- r pérature . On exploite le taux d'acceptation A, des mouve- ments tentés, au cours du palier, pour x, : . si Ai > 20 %, STEP, est doublé . si A, < 5 %, STEP, est divisé par 2 . Si le domaine de variation de xi est " peu étendu " : Xi'= Xi + y. STEP, où y désigne un nombre réel aléatoire, tiré dans [0, 1]. Sinon (cas de plusieurs décades), la perturbation est opérée selon une loi logarithmique. . Les n variables du problème sont modifiées par groupes dep, fonnés aléatoirement : typiquement, p : : :n/3. Les fréquences de mouvement des différentes variables sont égalisées. . Plusieurs critères complémentaires sont utilisés pour l'arrêt automatique du programme. Remarque : Le déplacement simultané de plusieurs variables peut per- mettre, dans le cas où celles-ci sont fortement corrélées, d'approcher davantage l'optimum que des déplacements individuels. Une estimation des gradients et du " hessien " de la fonction objectiffpermettrait de déterminer les varia- bles les plus " sensibles " (c'est-à-dire celles dont la varia- tion produit l'effet le plus important surf), et d'analyser les corrélations entre les variables. Cependant, comme nous l'avons indiqué plus haut, l'évaluation, par différences finies, des gradients et du hessien de f aboutit fréquem- ment à de sévères instabilités numériques. Il faut donc renoncer à un partitionnement du problème fondé sur le regroupement a priori des variables les plus corrélées. REE No 5 Mai2006 Adaptation des métaheuristiques pour l'optimisation continue Il -i-ÙOM 1 1 ; t-.'t. çr:_ ·,'ï M ,. i i I, r Figtire 4, Exeiiiples de@fonctioiis de lesi classiqzies. 2.2. Recherche tabou 1 Nous décrivons, à titre d'illustration, l'algorithme que nous avons proposé : ECTS (" Enhanced Continuous Tabu Search ") [Chelouah et al. OOa], qui se veut une transposi- tion fidèle de la méthode combinatoire. Les différents éléments d'ECTS sont les suivants : . La liste tabou est formée de " boules " centrées sur les dernières solutions retenues ; . La notion de voisinage est précisée dans la figure 5 : l'espace autour d'une solution courante est découpé sous forme de " couronnes " concentriques hyper-rec- tangulaires. La liste des voisins de cette solution courante est formée en sélectionnant au hasard une solution à l'intérieur de chaque " couronne " ; . La structure générale de l'algorithme est représentée sur la figure 6. Le coeur de la méthode tabou, non 1r t1 \ 1 11 1 /, /,/, 1 1 , Figiire 5. Notion d ( voisin (,ige d'tine soliilion courante dans la recherche tabou continue. décrit dans cette figure, est classique : . on engendre N voisins, non tabous, de la solu- tion courante, . le meilleur de ces voisins devient la nouvelle solution courante, . l'ancienne solution courante prend place dans la liste tabou. . ECTS comporte deux phases successives : de paramètres T détection de « zones prometteuses » -- parmi celles de l liste prometteuse à l'intétieur de la meillcurc zonc prometteuse l Figure 6. Structure générale de l'algorithme tabou continu ECTS. REE NO 5 Mai2006 MÉTHODOLOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS . une phase de diversification, destinée à repérer les " zones prometteuses " de l'espace des solutions, susceptibles d'abriter le minimum global de f. Le statut " prometteur " est d'abord attribué à des solutions : la solution x est déclarée prometteuse, si elle surpasse " nettement " (au sens d'un seuil fixé dynamiquement par ECTS) ses N voisins, évalués tour à tour au coeur de la recherche tabou. La liste prometteuse est alors formée de " boules " centrées sur les solutions prometteuses. . une phase d'intensification : une nouvelle recherche tabou est lancée à l'intérieur de la meilleure zone prometteuse. Elle opère plus finement (réductions de la dimension de l'es- pace de recherche, et de la taille de la liste tabou). Pour illustrer ce mécanisme, nous avons représenté en figure 7 le trajet suivi par ECTS lors de l'optimisation d'une fonction de test : ECTS a repéré 6 zones promet- teuses, dont celle abritant l'optimum global (0, 0). B2 (x,, xj x, + 2 x - 0,3 cos (31ux,) - 0,4 cos(4ix,) + 0,7 domaine de recherche : - 1 : g xi : 5 + 1, j E 1, 21 minimum global : (x x,) * = (0, 0) et B2 (0, 0) - 0 oa 06 oa 02 I 1 4 weillcucronenomeua.< opbmm^loh,-.. VY D4 f -r\-i ! 04 1 - 2 -1 -3 8 -0 6 -04 -02 D 02 04 0 6 08 1 Figure 7. Ti-ajet siiivi pai- l'algor-ithiîie ECTS (divei-sification) loi-s de l'optiiiiisatioi de lafoiietioi7 de test B2. Le principal écueil de cette approche réside dans le nom- bre élevé de paramètres de réglage : . tailles des listes tabou et prometteuse, . rayons des boules tabou et prometteuse, . dimensions du voisinage d'une solution courante, . nombre de voisins d'une solution courante,... etc. La plupart des paramètres d'ECTS sont calculés automa- tiquement, ou ont été figés " au mieux " empiriquement. La validation expérimentale détaillée d'ECTS, expo- sée dans [Chelouah et al. OOa], montre que le temps de calcul croît lentement (quasi linéairement) en fonction du nombre de variables de f La convergence peut encore être accélérée, en hybridant ECTS avec l'algorithme du polytope de Nelder & Mead. Ce dernier est un algorithme de " descente locale ", qui présente l'avantage - tout comme les métaheuristiques - de ne pas recourir aux gra- dients de la fonction objectif ; la descente s'effectue par déformations successives d'un " polytope ", via des trans- formations géométriques. Dans la variante hybride d'ECTS, les phases de diversification et d'intensification K---* Dï\ ï : Rsn-''K'ynoN détection d'une solution prometteuse i affinage de cette solution via l'aigvo. du pot'tope actualisation de la liste nrometteuse Figure 8. Principe de la variante hybride de l'algorithme ECTS. sont alternées, comme le montre la figure 8. 2.3. Algorithmes génétiques 1 Nous décrivons, à titre d'illustration, l'algorithme que nous avons proposé : CGA (" Continuous Genetic Algorihm ") [Chelouah et al. OOb]. Les particularités de CGA sont les suivantes : . alternance de phases de diversification et d'intensi- fication, précisée plus loin ; . réductions dynamiques de la taille de la population, et de l'espace de recherche ; . codage réel des individus ; l'affiliation d'un AG exploitant ce type de codage est parfois débattue : RCGA (" Real Coded Genetic Algorithm ") ou EA ( " Evolutionary Algorithm ") ; . opérateurs de croisement et de mutation spécifiques, décrits plus loin ; . réduction dynamique de la probabilité de mutation. L'alternance entre diversification et intensification dans CGA est illustrée par la figure 9 : REE NQS Mai2006 eyaueoles,ointions - nlomim· nlc rechemhe - u C-) - ! 111 0 0 - %1.1,n 0 fflo 1- iiicilicili 11 (l ! u % 1.1,Ullle l tiii ilicil l'lit iiicilicili 11 (ilit ll'IR Il I (Il Ili Il [ (Il nouceleçpnce effet de " zooms " successifs Figure 9.- Alternaice eiiti-e divei-sfication et intensification dans CGA. < la phase de diversification est réalisée à l'aide d'un AG classique, manipulant des individus " opulents ". Elle aboutit à l'identification d'une " solution pro- metteuse " x ; . la phase d'intensification est menée dans un nouvel espace de recherche restreint, autour de x* ; elle est réalisée à l'aide d'un nouvel AG, comportant une population réduite, formée d'individus amaigris. L'opérateur de croisement, dénommé " recombinaison " en codage réel, s'inspire, dans CGA, du croisement mono- point en binaire : . chaque individu est un vecteur x de dimension n ; la i " " ` composante de x est la i "' " variable d'optimisation ; la position/du croisement est sélectionnée au hasard ; . les composantes d'indice supérieur à i sont échan- gées entre les deux parents ; . les composantes d'indice i subissent des variations opposées, comme l'indique, sur un exemple (n 2, i = 2), la figure 10. C. le à Individu après recombinaison Individu avant recombinaison : Il=,. " 1-) L'opérateur de mutation affecte la valeur d'une seule variable. L'amplitude maximale de la perturbation, et la probabilité de mutation, sont progressivement diminuées : ce second point, plus délicat, est discuté dans [Chelouah etal.OOb]. Un exemple typique de résultat est présenté en figure ! 1 ; dans le cas de l'optimisation de la fonction de Goldstein- Price, nous comparons les évolutions vers l'optimum pro- curées par deux algorithmes : l'algorithme CGA et l'algo- rithme tabou continu ECTS décrit auparavant. Nous observons que CGA est gagnant au début, mais qu'il " s'essouffle " ensuite, ce qui suggère le recours à une hybridation avec une méthode de descente locale. Nous avons proposé d'effectuer l'intensification via l'algo- g (i /o -- t XX A e-, ( 11,) x eë t 3 (l ----------- 10 () 1 ( AO O 0 0 SCI 11 $aaDa ? Qa0070QO 1 CI () 1 ,j l () 1 i : v ; i Ll'it,n 2513 Figtire Il. Exeiiiple typiqite de résiillat (optiiiii.atioiq de la .fonction de Goldstein-Pt-ice) pi-ociii-é pai- les algoi-ithiiie, CGA et ECTS. 1 CGA 08 CGA08 - SS \ - CGA ,HA avec iiiterisificat on ilrélllatl,rëe 07 CHA biet- réglê 06 . 04- as-0.3 01 - t 0 1 + J 1 2 4 5 6 7 8 9 10 Xombt'c de ocncrations1 Figure 10. variations opposées des composantes des deux pai-eiits sititées ati poiiit de ci-oisei ; ient. Figzrre 12. Effet de l'kybridation de CGA avec l'algoi-ithiiie du polviope de Nelder & Mead. rithme du polytope de Nelder & Mead [Chelouah et al. 03]. Nous illustrons l'effet de cette transformation à l'aide de la figure 12 ; on constate sur l'exemple présenté REE No 5 Mai 2006 MÉTHODOLOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS (optimisation de la fonction B2) que : . l'algorithme CGA ne converge que lentement au bout de quelques générations ; . l'algorithme du polytope seul (SS) conduit à un opti- mum local ; . la méthode hybride (CHA), obtenue par hybridation de CGA et de SS, est très efficace, à condition que le passage de relais entre les deux approches ne soit pas prématuré. Nous discutons l'automatisation de ce passage de relais dans [Chelouah et al. 03]. La variante hybride a été exploitée avec succès, au CEA, pour la conception optimale d'un capteur à cou- rants de Foucault destiné au contrôle non destructif de tubes métalliques [Chelouah et al. OOc]. L'algorithme a notamment permis de retrouver un capteur, de forme plate, très répandu : le " pancake ". Conclusion Nous avons présenté dans cet article quelques répon- ses à une question de haute importance posée par de nom- breux problèmes d'optimisation en ingénierie : comment adapter les métaheuristiques, souvent d'origine discrète, aux problèmes à variables continues ? Une autre voie peut consister à recourir à l'une des rares métaheuristi- ques conçues d'emblée pour le cas continu, comme la méthode d'Optimisation par Essaiz Particulaire. Références [BERTHIAU et al. 94] G. BERTHIAU, F. DURBIN, J. HAUSSY, P SIARRY, "Learning of Neural Networks Approximating Continuous Functions Through Circuit Simulator SP/CF-R4C Driven by Simulated Annealing ", International Journal of Electronics, Vo. 76, p. 437-441, 1994. [CHELOUAH et al. OOa] R. CHELOUAH, P SIARRY, "Tabu Search Applied to Global Optimization ", European Journal of Operational Research, Vol. 123, p. 256-270, 2000. [CHELOUAH et a !. OOb] R. CHELOUAH, P SIARRY,'A Continuous Genetic Algorithm Designed for the Global Optimization of Mmoda/Funcf/ons ", Journal of Heuristics, Vol. 6, p. 191-213, 2000. [CHELOUAH et al. Oücl R. CHELOUAH, P SIARRY, G. BERTHIAU, B. DE BARMON, " An optimlzation method fitted for model inver- sion in non desiructive control by eddy currents ", The European Physical Journal, Applied Physics, Vol. 12, p. 231-238, 2000. [CHELOUAH et al. 03] R. CHELOUAH, P SIARRY, "Genetic and Nelder-Mead Algonthms Hybridized for a More Accurate Global Optimizatlon of Continuous Multiminima Functions ", European Journal of Operational Research, Vol. 148, p. 335-348, 2003. [CLERC et ai. 02] G. CLERC, M. BESSAOU, P SIARRY, P BAS- TIANI, " Identification des machmes synchrones par algorithme génétique ; prinCipe et application ", Revue Internationale de Génie Electrique, Vol 5, p. 485-515, 2002. [DREO et al. 03] J. DRÉO, A. PETROWSKI, P SIARRY, E TAIL- LARD (ouvrage coordonné par P Siarry), " Métaheuristiques pour l'optimisation difficile " Eyrolles, 2003. [SIARRY et al 97] P SIARRY, G. BERTHIAU, F DURBIN, J. HAUSSY, "Enhanced Simulated Annealing for Globally Minimizin_q Functions of Many Continuous Variables' ACM Trans. on Mathematical Software, Vol 23, p. 209-228, 1997 [TAILLARD 021 E.D. TALLARD,'A Statistical Test for Comparing Rates of Success ", INA technical report, INA, Yverdon-les-Bains, 2002. L'a u t e u r Patrick Siarry est ingénieur de Su pélec (1977, litu lai ne du Doctorat de l'université de Paris 6 (1986) et de l'habilitation à diriger les recherches de l'université de Pans 11 (1994) Il a commencé sa car- rière comme ingénieur-chercheur à EDF :Chatou, où il a développé des modèles analogiques et numériques d'organes de centrales nucléaires. Depuis 1995, il est professeur des universités, et depuis 1999 il est en poste à l'université de Paris 12 (Créteil), Il est actuellement directeur du laboratoire Images, Signaux et Systèmes Intelligents (LiSSi, EA 3956) Il s'intéresse depuis 1982 aux métho- des d'optimisation heuristiques, inspirées de la physique, de la bio- logie ou de l'éthologie Ces méthodes, qui s'adressent plus parti- culièrement aux problèmes d'optimisation dits « {difficiles », sont désormais regroupées sous le terme de « métaheuristiques ». Ses principales contributions portent sur l'adaptation de ces méthodes discrètes aux problèmes d'optimisation à variables continues, auxquels sont le plus souvent confrontés les ingénieurs. Les applications qu'il a traitées sont variées : identification des paramètres de modèles de composants électroniques, apprentis- sage d'une base de règles floues ou d'un réseau de neurones, conception optimale d'un moteur électrique, recalage d'images d'angiographie rétinienne, etc. REE N05 Mai 2006