Opérateur Dynamique Adaptatif

Motivation 

Nous nous sommes tournée vers d’autres concepts en évolution artificielle pour arriver à améliorer les résultats déjà prometteurs de nos opérateurs. Nous avons défini  dans le chapitre précédent l’opérateur arc-crossover qui prend en compte le réseau de contraintes pour combiner les valeurs des parents d’une manière plus appropriée pour créer un fils. Il est basé sur une priorité statique des contraintes, qui est définie au début de l’algorithme suivant la connectivité. A re- crossover nous semble être un bon opérateur car il nous a permis de modifier la vision d’une recherche évolutionniste aveugle par rapport au problème, tout en gardant un degré de généralité pour pouvoir être appliqué à différents types de CSP et ainsi de profiter de certaines caractéristiques du réseau de contraintes. Nous souhaitons améliorer sa performance en incorporant les idées de l’adaptation. Ce concept a été récemment repris et défini d’une manière plus formelle en [HME97]. Il donne à l’algorithme génétique plus de souplesse en lui permettant l’adaptation et le changement de sa configuration, suivant l’état courant de la recherche. Dans le contexte des CSP, ceci signifie qu’on pourrait éventuellement permettre à l’algorithme la non-satisfaction temporaire de certaines contraintes. L’algorithme pourrait commencer son évolution avec un sous ensemble de contraintes, composé par celles qui sont les plus difficiles à satisfaire.

OPÉRATEUR DYNAMIQUE ADAPTATIF 

Adaptation 

de contraintes et continue sa recherche pour trouver une solution pour le problème global. Une autre idée serait de pouvoir changer la priorité des contraintes dans l’analyse. Par exemple, eu rendant comme prioritaire la contrainte qui a été historiquement (‘pendant la recherche de l’algorithme), la plus difficile à satisfaire [Eib96j. Nous commençons ce chapitre par un résumé des concepts qu’on utilise en adaptation. Ensuite, nous définissons un nouvel opérateur qui est né à partir à’ arc-crossover mais qui a inclus certaines idées d’adaptation. A la fin du chapitre, nous comparons les résultats d’un algorithme évolutionniste pour le problème de 3-coloriage. avec ceux d’mitres algorithmes qui utilisent d’autres opérateurs. Nous montrons aussi les résultats obtenus pour le 3-coloriage avec: des graphes peu denses. Nous concluons alors ce chapitre par un ensemble de tests réalisés avec des CSP aléatoires. 

Adaptation 

L’adaptation de paramètres et, d’opérateurs est un des sujets les plus prometteurs eu évolution artificielle. L’idée est de faire une sorte de « syntonisation » de l’algorithme avec le problème pendant sa résolution. Hinterding et al. [HME97] proposent le classement suivant pour les types d’adaptation: 

 (Adaptation Statique) 

On dit que l’algorithme réalise une adaptation statique si ses paramètres stratégiques ont une valeur constante pendant son exécution. En conséquence, on a besoin d’un agent ou d’un mécanisme externe pour syntoniser les paramètres et sélectionner les valeurs les plus appropriées. Un cas typique est lorsqu’on fait tourner l’algorithme plusieurs fois, en essayant de trouver les valeurs des paramètres qui le rendent plus performant. Ce cas correspond justement à notre algorithme de sélection (voir 3.12), pour lequel nous avons trouvé les valeurs de « svntonisatkm » pour a et li. 

CD A: Crossover Dynamique Adaptatif

L’operateur Crossover Dynamique Adaptatif (CDA) est basé sur l’idée à’arccrossover, c’est-à-dire, avec deux parents produire un fils qui hérite la meilleure combinaison des valeurs de leurs variables. Mais, dans CDA, nous incorporons les idées d’adaptation, en lui permettant de changer la priorité d’analyse des contraintes dans le croisement, suivant les caractéristiques des parents. Cela veut dire que les positions de recombinaison ne sont pas fixées et l’ordre de l’analyse des contraintes non plus. La figure 5.3 montre la conséquence d’une analyse suivant une priorité des contraintes différente de celle qu’utilise arc-crossover. Dans l’exemple, les deux parents ne violent que la contrainte d . Arc-crossover définit une priorité P suivant la contribution de chaque contrainte à la fonction d’évaluation. Prenons une autre priorité P c a qui considère comme la contrainte la plus prioritaire celle qui est violée (C4). Ensuite, nous réalisons la procédure de arc-crossover séparément avec les deux priorités, nous voyons qu’avec P c a nous trouvons une solution, alors qu’avec P le fils peut être une copie du parenti. Nous avons construit P c a en sachant que la contrainte C4 est violée par les deux parents, en prenant, donc en compte l’information des parents. C’est cette idée que 131 5. OPERATEUR DYNAMIQUE ADAPTATIF • 5.3, GDA: Crossover Dynamique Adaptatif [ \L, X, X 4 X , Parent 1: 3 i : | ? j ¡ ¡ Parent 2 : ¡ | 3 | ! » «  » | 2 « ~ 2 P= C2.C4,Cfi> P ==S c( Cs ) = 7 cl C(s i = 5 Évaluation 5 5 C5.C?,C|,C2,Có> 1 i l L’LX FlG. 5.3 – Exemple: Différentes Priorités pour Crossover nous allons incorporer dans le nouvel opérateur. Pour ce faire, nous avons besoin des ( léfinitions suivantes : Définition 5.3.1 (Nombre de violations) Etant donné un CSP P = (V,D,Ç), deux instanciations Ii et I2, et les fonctions e(Cn.I) pourl- I 1 ; I 2 pour toute contrainte Ca On définit le nombre de violations communes pour la contrainte CQ, nv(Ca, Ij, I 2 j comme: nv(G,.Ii,l 2 ) = < 0 e(Ca , I 1 )=e(Cû , I 2 ) = 0 1 soit e(Ca, Ii) # 0 ou e(CQ, I2) # 0 [ 2 e(Ca,li)¿0, e¿e(C Q ;I 2 ) # 0 Ii et I2 correspondent respectivement aux instanciations du parenti et dupareraÍ2- Pour chaque contrainte Cn, le nombre de violations sera zéro si les deux parents satisfont la contrainte. Il vaut un dans le cas où un parmi eux satisfait la contrainte J. OPÉRATEUR DYNAMIQUE ADAPTATIF • j.3. CDA: Crossover Dynamique Adaptatif er deux quand la contrainte est violée par les deux parents. En utilisant cette fonction, nous allons définir une nouvelle priorité qui prend en compte l’état actuel des parents.