Recombinaison et auto adaptation dans les
80
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
80
pages
Français
Ebook
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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 ?+
Voir
- 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
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)
où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) −
où∆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
=2−ku(3.5) où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)
où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 à 2Nam12arp−1 2et 2Nparam−1 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 0≤x1≤1 − 2(x)=g⎛⎜⎜1xg1⎟−⎞⎠⎟5≤xi≤5i=2,...,10 ⎝ 10 oùg=91+∑(xi2−10 cos(4πxi)) i=2 1(x)=1−exp(−4x1) sin6(6πx1) 2(x)=g(1−(f1/g)2) 0≤xi≤1 i=1,...,10 o 1 9 / 9⎞ ùg=+⎛⎝⎜i1∑=20xi⎠⎟0.25 -1(x)=410i1∑=01xi21000≤xi≤1000i=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 a−a*a*∈P*(3.8) Pa∈∑P où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∑=je1ctifmina−ai*imn a∈P (3.9) où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 ∆ =P1−1=∑−11di−d (3.10) i oùd1 la distance euclidienne entre deux solutions non-dominées consécutives, et estd la moyenne de ces distances. Une valeur de∆nulle 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 P−1 ∆ =1∑di−d P−1i=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
