Recombinaison et auto adaptation dans les

De
Publié par

Chapitre 3 Recombinaison et auto-adaptation dans les d'élitism iner l'influence des opérateurs d'évolution ait été largement souligné [Lau99], il n'y a eu à notre connaissance que très peu d'investigations sur cette problématique [Co Dans c élitistes (à savoir le SPEA2 et le NSGA-II) en fonction de différentes méthodes de recomb perf nous proposons et validons une technique de recomb robuste 3.1 Dans cette partie, nous présentons les différentes procédures de recombinaison et d'auto- adaptation que nous allons employer pour tester le SPEA2 et le NSGA-II. 3.1.1 Méthodes de croisement de variables réelles algorithmes évolutionnaires multicritères La plupart des travaux sur les méthodes évolutionnaires multicritères se sont focalisés jusqu'à présent sur les techniques de sélection, d'affectation de l'adaptation, e ou de nichage. Bien que le besoin d'exam s02][Lau01]. e chapitre, nous allons donc examiner l'efficacité de deux algorithmes multicritères inaison, croisement et/ou mutation pour 3 problèmes tests standards. Des critères de ormance usuels et complémentaires sont pris pour réaliser les comparaisons. Par ailleurs, inaison auto-adaptative afin d'améliorer la sse des algorithmes. Procédures de recombinaison et d'auto-adaptation 3.1.1.1 Le croisement arithmétique étendu (BLX-? ) Le croisement arithmétique étendu (Blind Crossover) permet de générer un enfant )(ic à partir de deux parents )(1 ip et )(2 ip de la manière suivante [Esh93] : ( ) ] )()( [ )( 121 ipipipic ?+

  • fronts locaux de pareto

  • procédure de mutation gaussienne anisotrope

  • auto-adaptation dans les algorithmes évolutionnaires

  • variable aléatoire

  • mutations adaptatives

  • croisement

  • résolution de problèmes tests

  • auto- adaptation


Publié le : lundi 18 juin 2012
Lecture(s) : 73
Source : ethesis.inp-toulouse.fr
Nombre de pages : 80
Voir plus Voir moins
 
Chapitre 3
 
Recombinaison et auto-adaptation dans les algorithmes évolutionnaires multicritères
La plupart des travaux sur les méthodes évolutionnaires multicritères se sont focalisés jusqu'à présent sur les techniques de sélection, d'affectation de l'adaptation, d'élitisme ou de nichage. Bien que le besoin d'examiner l'influence des opérateurs d'évolution ait été largement souligné [Lau99], il n'y a eu à notre connaissance que très peu d’investigations sur cette problématique [Cos02][Lau01].  Dans ce chapitre, nous allons donc examiner l'efficacité de deux algorithmes multicritères élitistes (à savoir le SPEA2 et le NSGA-II) en fonction de différentes méthodes de recombinaison, croisement et/ou mutation pour 3 problèmes tests standards. Des critères de performance usuels et complémentaires sont pris pour réaliser les comparaisons. Par ailleurs, nous proposons et validons une technique de recombinaison auto-adaptative afin d'améliorer la robustesse des algorithmes.
3.1 Procédures de recombinaison et d'auto-adaptation
Dans cette partie, nous présentons les différentes procédures de recombinaison et d’auto-adaptation que nous allons employer pour tester le SPEA2 et le NSGA-II.
3.1.1 Méthodes de croisement de variables réelles
3.1.1.1 Le croisement arithmétique étendu (BLX- )
Le croisement arithmétique étendu (Blind Crossover) permet de générer un enfantc(i) à partir de deux parentsp1(i) etp2(i la manière suivante [Esh93] :) de
c i=p1(i)+[p2(i)p1(i) ]
(3.1)
où est une variable aléatoire uniforme comprise dans l’intervalle [, 1+], eti correspond, pour l’enfant et les parents, à l’indice de la variable de conception à croiser.
 
69
Chapitre 3
Si=0 , ce croisement engendre un enfant, qui sera obligatoirement situé à l’intérieur de l’intervalle défini par les deux parents. Dans ces conditions, cet opérateur est équivalent au croisement arithmétique classique [Mic96].EshelmanetSchafferont montré, sur des problèmes tests, que la valeur= garantissait les meilleurs performances [Esh93].0.5 (BLX-0.5) 3.1.1.2 Le croisement binaire simulé (SBX) Le croisement binaire simulé (Simulated Binary Crossover) reproduit les mécanismes du croisement standard à un point utilisé lorsque les variables objets sont représentées sous la forme de chaînes binaires [Deb99a]. A partir de deux parentsp1(i) etp2(i ce croisement génère deux) , enfantsc1(i) etc2(i) , par l’intermédiaire de la relation suivante. c1(i))=(1 [05.0+ β)p11(i)+(1− β)p2((ii) ] )] c2(i=.5[ (1− β)p(i)+(1+ β)p2(3.2)
où représente un facteur de dispersion défini par :
  (2u)1+1 siu<0.5  η β = ⎨ ⎛   12(1-u) η1+1 ailleurs
(3.3)
uune variable aléatoire uniformément répartie dans l’intervalle [0est  et , 1] paramètre un réel non négatif qui caractérise la forme de la distribution des enfants par rapport aux parents. De fortes valeurs de engendrent de fortes probabilités de retrouver un enfant dans le voisinage local des parents. Tout comme les stratégies d’évolution, le croisement SBX possède des propriétés intéressantes d’auto-adaptation9[Deb99a]. 3.1.1.3 Le croisement génétique reproducteur (BGX) A partir de deux parentsp1(i) etp2(i) , le croisement génétique reproducteur (Breeder Genetic Crossover) crée un enfantc1(i) de la manière suivante [Schl94] : c(i)=p1(i)±(pp22((ii))pp11((ii)))iδ (3.4)
imoitié du domaine de définition du paramètreest généralement égal à la i. La norme représente la distance euclidienne dans l’espace des paramètres. est calculé en utilisant une distribution définie par l’équation (3.5), qui favorise les faibles valeurs :                                                  9précisément le concept d’auto-adaptation dans la section suivanteNous expliquerons plus
70
 
Recombinaison et auto-adaptation dans les algorithmes évolutionnaires multicritères
=2ku(3.5)  u une variable aléatoire uniformément distribuée dans l’intervalle [ est et 0,1 ],k une constante de précision habituellement égale à 16. Notons que, dans [Schl94], les enfants sont le plus souvent situés au voisinage des meilleurs parents,p1(i le parent qui possède la) étant meilleure adaptation. De même, le signe –de l’équation (3.4) est choisi avec une probabilité de 0.9. Dans notre travail, nous avons décidé de ne favoriser aucun parent (le choix dep1(i) et du signe dans l’équation (3.4) sont fait avec une probabilité de 0.5).  A la figure 3.1, nous pouvons observer, pour les différents croisements précédemment décrits, l’allure de la densité de répartition d’un enfant par rapport à ses parents. Elle traduit la probabilité de trouver un enfant dans le voisinage de ses deux parentsp1(i) etp2(i symbolisés) , par les cercles noirs pleins. Remarquons que le croisement BGX aveck= la16 renforce probabilité de générer un enfant situé dans le voisinage local des parents. 1
0.8 SBX (η= 1) BGX (k= 16) BLX-0.5 0.6
0.4
0.2
0 0p1p210  figure 3.1 : Densité de répartition des enfants en fonction des différents types de croisement
3.1.2 Auto-adaptation
Le concept d'auto-adaptation a été introduit pour désensibiliser les algorithmes évolutionnaires de leurs paramètres de contrôle et tirer profit de l'adaptation induite par la sélection. L'auto-adaptation consiste à permettre à l'algorithme évolutionnaire d'adapter automatiquement les valeurs de ses paramètres de contrôle au cours de la recherche, soit de façon explicite, à l'aide d'une heuristique prédéfinie, soit de façon implicite, en codant celles-ci directement dans les
 
71
Chapitre 3
individus. Il existe par exemple dans la littérature plusieurs techniques de mutations adaptatives, utilisant des taux de mutation variant au cours des générations [Sar99], ou directement intégrés aux chromosomes des individus [Bäc92a][Bäc92b]. Toutefois, les méthodes auto-adaptatives les plus connues restent celles employées dans les stratégies d'évolution [Bäc96][Sch95][Deb99c]. Nous précisons en particulier dans ce qui suit la procédure de mutation gaussienne anisotrope et une technique de croisement auto-adaptative, que nous avons développée pour caractériser la performance des opérateurs de variation dans les algorithmes multicritères.
3.1.2.1 Mutations auto-adaptatives anisotropes
Dans les stratégies d’évolution, chaque individu est caractérisé par ses variables objetsx iet un ensemble d’écarts-typesi Lorsque l’on emploie la procédure de mutation associés. gaussienne anisotrope, les enfants (c(i) ,c(i)) sont créés à partir des parents (p(i) ,p(i)) , en utilisant les équations (3.6) et (3.7).
ci=piexp( 'N(0,1)+Ni(0,1))
c i=p i+ci Ni(0,1)
(3.6)
(3.7)
N une distribution normale aléatoire de moyenne nulle et d’écart-type 1.(0,1) représente Ni que le nombre aléatoire est généré pour chaque nouvelle valeur de(0,1) indiquei. Les  facteurs et ' sont habituellement fixés à 2Nam12arp1 2et 2Nparam1 2[Bäc96].  
3.1.2.2 Proposition d’une méthode de croisement auto-adaptatif
 Il est très difficile de savoira priori quel type de croisement sera le plus efficace pour un problème donné. Pour réduire la sensibilité des algorithmes vis-à-vis des opérateurs de recombinaison, nous proposons d’implémenter une procédure de croisement auto-adaptatif, similaire à celle utilisée parSpearsles algorithmes génétiques à codage binaire [Spe95]. dans Pour cela, nous associons au chromosome de chaque individu, un gène supplémentaire (que nous qualifierons ici de gène de croisement ou X-gene) qui code le type de croisement à employer au cours du processus de recombinaison [Sar03]. Lors de la création d’un enfant, le croisement utilisé est choisi aléatoirement parmi les deux valeurs des X-genedes parents. Avec cette procédure, l’algorithme évolutionnaire favorise, par l’intermédiaire de la sélection, le croisement qui produit les meilleurs enfants. Notons qu’afin d’éviter la convergence prématurée vers un type de croisement particulier, le gène de croisement subit, lui aussi, une mutation, avec une probabilité différente de celle des variables objets.
72
 
Recombinaison et auto-adaptation dans les algorithmes évolutionnaires multicritères
3.2 Résolution de problèmes tests
3.2.1 Problèmes tests
Pour tester les performances des deux algorithmes retenus en fonction des différentes méthodes de variation, nous considérons trois problèmes de la littérature [Zit00][Sch85], décrits au tableau 3.2.
ZDT4
TABLEAU3.2 : PUTILISES POUR LA CARACTERISATION DES PERFORMANCES DUROBLEMES TESTS SPEA2ET DU NSGA-II (MINIMISATION DES OBJECTIFS) Problèmes Caractéristiques 1(x)=x1 0x11 2(x)=g1xg15xi5i=2,...,10 10 g=91+(xi210 cos(4πxi)) i=2 1(x)=1exp(4x1) sin6(6πx1) 2(x)=g(1(f1/g)2) 0xi1 i=1,...,10 o 1 9 / 9ùg=+i1=20xi0.25 -1(x)=410i1=01xi21000xi1000i=1,...,10 ( 110 2=(2)2   x xi )40i=1  
ZDT6
SCH
 ZDT4 est un problème multimodal continu qui contient 219 fronts locaux de Pareto. Le front global, convexe, est obtenu pourg= figure 3.2).1 (voir
 
73
Chapitre 3
Front de P aret o global t héorique
3001.2 Solut ions aléat oires 250 1 200 0.8 f2 150 0.6 100 0.4 50 imalFront opt héorique t0.2 0 0 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 f1f1  figure 3.2 : Problème ZDT4. Représentation des solutions dans l’espace des objectifs pour un tirage aléatoire de 20 000 points et allure du front théorique Le problème ZDT6 présente un espace de recherche « trompeur », ainsi que des solutions non-uniformément distribuées le long du front optimal global (le front est biaisé quand les solutions présentent des valeurs de1(x de 1). Le front global, non-convexe, est obtenu pour) proches g= figure 3.3).1 (voir
Solut ions aléat oires Front de P aret o global t héorique
7 6 5 4 f2 3 2 1 0 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 f1  figure 3.3 : Problème ZDT6. Représentation des solutions dans l’espace Le problème SCH (voir figure 3.4) est une généralisation du problème deSchaffer.Il est caractérisé par un large domaine de définition des variables objets et un front de Pareto convexe.
74
 
Recombinaison et auto-adaptation dans les algorithmes évolutionnaires multicritères
Front de P aret o global t héorique
181 x 10e6 160.9 14 aléat oiresSolut ions0.8 0.7 12 0.6 f210f20.5 8 0.4 6 0.3 40.2 2 0.1 x 10e7 00 0 0.5 1 1.5 2 10 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 f1f1 figure 3.4 : Problème SCH. Représentation des solutions dans l espace des objectifs pour un tirage aléatoire de 20 000 points et allure du front théorique
3.2.2 Critères de performance
Trois critères de performance sont utilisés pour caractériser l’efficacité des algorithmes. 3.2.2.1 Ecart moyen par rapport au front de Pareto théorique ( ) L’écart moyen entre le front constitué de l’ensemble des solutions non-dominées déterminé par l’algorithme et le front théorique, s’exprime par [Zit00]: ε =n1mi aa*a*P*(3.8) PaP P (respectivementP*) représente l’ensemble des solutions non-dominées de la population finale (respectivement le front théorique de Pareto),a eta* à chaque sous- appartenant ensemble. La norme représente la distance euclidienne calculée dans l’espace des objectifs. 3.2.2.2 Ecart moyen par rapport aux solutions extrémales (min) Nous définissons l’écart moyenmin par rapport aux solutions extrémales comme la moyenne des distances minimales entre l’ensemble des solutions non-dominées et les solutions extrémales du front (celles minimisant indépendamment chaque critère) :
 
75
Chapitre 3
N εmin=Nob1jectifiob=je1ctifminaai*imn   aP  (3.9) Nobjectif le nombre d’objectifs et estaiimn* représente la solution théorique du front optimal minimisant le critèrei. 3.2.2.3 Uniformité de la distribution des solutions sur le front () La quantitéà distribuer les solutions uniformément le longtraduit la capacité des algorithmes du front optimal.est une mesure basée sur les distances consécutives entre les solutions non-dominées de l’espace des objectifs [Deb00] : P ∆ =P11=11did (3.10) i d1 la distance euclidienne entre deux solutions non-dominées consécutives, et estd la moyenne de ces distances. Une valeur denulle indique que toutes les solutions non-dominées trouvées par l’algorithme sont espacées de façon équidistante. Par rapport à la définition de dans [Deb00], nous n’incluons pas, dans l’ensemble des solutions non-dominées, les solutions extrémales du front théorique. L’indicateurmin permet déjà de caractériser la qualité de la détection de ces solutions. La figure 3.5 montre la signification des différents critères de performances énoncés. f2 *ε a min1min 1 ε =< εi> Ensemble des individus non dominésPεmin=(ε1 min+ ε2 min)2 P1 ∆ =1did P1i=1
76
εidi
Front de P aret oε2 min ueP * t héoriqa2 minf1 *  figure 3.5 : Signification des différents critères de performances
 
Recombinaison et auto-adaptation dans les algorithmes évolutionnaires multicritères
Comme le montre la figure 3.6, qui illustre différents ensembles solutions par rapport au front théorique, ces trois critères sont complémentaires pour évaluer l’efficacité des algorithmes évolutionnaires de Pareto :   min0 (respectivement0 ) indique une bonne (respectivement une mauvaise) déviation moyenne,   min0 (respectivementmin0) une bonne (respectivement une mauvaise) détection des solutions extrémales théoriques   ∆ ≈0enemt r(seeptcvi∆ ≠0) une bonne (respectivement une mauvaise) répartition des   solutions le long du front optimal.  Les solutions non-dominées sont repérées par des cercles noirs pleins et le front optimal théorique par une ligne continue.
f2f2f2 ε ≈0ε ≈0ε ≈0 εmin0εmin0εm in0 ∆ ≈0∆ ≈0∆ ≠0
f1f1f1 f2f2f2 ε ≈0ε ≠0ε ≠0 εmin0εmin0εmin0 ∆ ≠0∆ ≈0∆ ≠0
f1f1f1  figure 3.6 : Illustration des critères de performance utilisés pour différentes configurations des solutions non-dominées par rapport au front théorique
3.3 Résultats Nous avons successivement comparé les efficacités du NSGA-II et du SPEA2 sur les trois problèmes test, en utilisant les divers opérateurs de croisement et les procédures auto-adaptatives présentés à la section 3.1 . Tous les tests sont réalisés avec le même nombre d’évaluations des fonctions objectifs. Pour chaque optimisation, et quel que soit l’algorithme de résolution, le nombre de générations est fixé à 200 et la taille de la population à 100 individus. La taille de l’archive est aussi égale à 100 et la probabilité de croisement unitaire (pc=1) . Les stratégies de variations étudiées sont :
 
77
Chapitre 3
les 3 méthodes de croisement introduites précédemment à savoir, le BGX (de constante de précisionk=16 ), le SBX (de paramétrage=1 ) et le BLX-0.5. Ces croisements sont utilisés conjointement avec l’opérateur de mutation employé dans le BGA [Schl94] appliqué avec une probabilité de 1/Nparam.  la technique de mutation adaptative anisotrope pour laquelle nous imposons des écarts-types initiaux 10 fois plus faibles que le domaine de définition des variables objets correspondantes (i(0)=(ximaxximin) / 10 ). Cette procédure est appliquée sans opérateur de croisement.  auto-adaptative intégrant les trois croisements précédents et coupléela recombinaison avec l’opérateur de mutation du BGA de probabilité de 1/Nparam. Le gène de croisement est quant à lui muté avec un taux de 5%.
3.3.1 Influence de l’opérateur de variation
Nous présentons, dans les tableaux 3.3 à 3.5, les valeurs des critères de performance pour les différents problèmes tests et pour les diverses stratégies de variation étudiées. Les résultats sont basés sur les valeurs moyennes des critères de performance calculés pour chaque optimisation. Dans ces tableaux, les abréviationsMut. auto-ad etRec. auto-ad respectivement signifient Mutation auto-adaptative et Recombinaison auto-adaptative.  Nous donnons aussi, en annexe F, des exemples d’exécutions typiques qui illustrent la répartition des solution Pareto optimales par rapport aux front théoriques, à l’issue des 200 générations et en fonction des différents opérateurs de variation utilisés.  A partir de ces résultats, nous proposons un classement des opérateurs de croisement et d’auto-adaptation pour chaque algorithme. Ce classement est fondé prioritairement sur la valeur de l’écart moyen .  A l’inverse de ce que l’on peut noter en optimisation monocritère10, nous constatons qu’en l’absence d’un opérateur de croisement, y compris lorsque le NSGA-II et le SPEA2 sont utilisés avec une procédure de mutation auto-adaptative, les résultats obtenus sont médiocres. Cela semble confirmer l’étude récente de [Cos02]  TABLEAU3.3: CRITERES DE PERFORMANCE POUR LE PROBLEMEZDT4. LES MEILLEURS RESULTATS SONT INDIQUES EN GRAS ET LES INTERVALLES DE CONFIANCE A95%SONT DONNES ENTRE CROCHETS  Opérateurmin Classement NSGA-II BGX (k (mauvais) 4 [0.185]=16) 2.231 [0.011] 0.112 [0.148] 1.769                                                  10d’évolution sont habituellement employées avec succès en optimisation monocritère sans opérateurLes stratégies de croisement [Sch95], [Bäc96]. Seule la procédure de mutation gaussienne auto-adaptative est utilisée pour faire évoluer les individus.
78
 
Recombinaison et auto-adaptation dans les algorithmes évolutionnaires multicritères
 SBX ( =1) 1.961 [0.170] 1.656 [0.138] 0.033 [0.009] 3 (bon) BLX-0.5 1.483[0.151]1.275[0.122] 0.019 [0.006]1(excellent) Mut. auto-ad 10.41 [1.000] 9.439 [0.939]0.017[0.001] 5 (très mauvais) Rec. auto-ad 1.688 [0.164] 1.437 [0.136] 0.021 [0.008] 2 (très bon) BGX (k (mauvais) [0.041] 4=16) 5.343 [0.380] 0.301 [0.436] 4.367 SBX ( =1) 2.233 [0.221] 1.894 [0.163] 0.028 [0.008] 3 (bon) SPEA2BLX-0.5 1.527[0.148]1.373 [0.005][0.122] 0.0211(excellent) Mut. auto-ad 10.55 [1.090] 9.525 [1.015]0.012 (très mauvais)[0.002] 5 Rec. auto-ad 1.616 [0.161] 1.427 [0.133] 0.024 [0.006] 2 (très bon)
TABLEAU3.4: CRITERES DE PERFORMANCE POUR LE PROBLEMEZDT6. LES MEILLEURS RESULTATS SONT INDIQUES EN GRAS ET LES INTERVALLES DE CONFIANCE A95%SONT DONNES ENTRE CROCHETS  p teurmin C O éra lassement BGX (k=16) 0.000[0.000]0.000[0.000]0.006[0.000]1(excellent) SBX ( =1) 0.185 [0.018] 0.001 [0.000] 0.202 [0.022] 4 (mauvais) NSGA-II BLX-0.5 0.081 0.097] 0.000 [0.000] 0.096 [0.054] 3 (très bon) Mut. auto-ad 1.866 [0.114] 0.442 [0.077] 0.543 [0.063] 5 (très mauvais) Rec. auto-ad 0.014 [0.006]0.000 (très bon) 2 [0.010][0.000] 0.024 BGX (k=16) 0.068 [0.008]0.000[0.000] 0.071 [0.006] 3 (bon) SBX ( =1) 0.186 [0.016]0.000 [0.015][0.000] 0.141 (mauvais) 4 SPEA2BLX-0.5 0.059[0.005]0.000[0.000] 0.055[0.005] 1(excellent)  Mut. auto-ad 1.662 [0.126] 0.554 [0.090] 0.484 [0.049] 5 (très mauvais) Rec. auto-ad 0.061 [0.006]0.000[0.000] 0.056 [0.007] 2 (très bon)
TABLEAU3.5: CRITERES DE PERFORMANCE POUR LE PROBLEMESCH. LES MEILLEURS RESULTATS SONT INDIQUES EN GRAS ET LES INTERVALLES DE CONFIANCE A95%SONT DONNES ENTRE CROCHETS  p rateurmin Classement O é BGX (k (très mauvais)=16) pas de convergence au bout de 200 générations 5 SBX ( =1)0.007 [0.000]0.086 [0.000][0.006] 0.0061(excellent) NSGA-II BLX-0.5 0.004 [0.008][0.000] 0.2090.004 (bon)[0.000] 3 Mut. auto-ad 0.091 [0.006] 0.195 [0.059] 0.008 [0.001] 4 (mauvais) Rec. auto-ad0.004[0.000] 0.118 [0.009] 0.005 [0.000] 2 (très bon) BGX (k=16) pas 5 de convergence au bout de 200 générations (très mauvais) SBX ( =1) 0.006[0.000]0.100[0.007] 0.005 [0.000]1(excellent) SPEA2 BLX-0.5 0.009 [0.001] 0.289 [0.010]0.002 (bon)[0.000] 3 Mut. auto-ad 0.302 [0.306] 0.445 [0.299] 0.008 [0.002] 4 (mauvais) Rec. auto-ad0.006 0.004 [0.009][0.000] 0.129 (très bon) [0.000] 2 Pour le problème ZDT4, le tableau 3.3 montre que les deux algorithmes sont les plus efficaces lorsqu’ils sont associés au croisement BLX-0.5. Ce croisement réussit bien au SPEA2 pour le problème ZDT6 mais conduit à des performances biens moindres lorsqu’il est utilisé par le
 
79
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.