Opérateurs Génétiques Spécialisés

Relation entre arc-mutation, min-conflits e t min-réseau-conflits

Nous pouvons remarquer qu’il y a certaines similitudes entre ce que fait arcmutation et ce que font les deux méthodes stochastiques min-conflits et min-réseauconflits que nous avons décrites dans le chapitre précédent. Les trois choisissent une variable et elles changent sa valeur dans l’instanciation. Néanmoins, elles diffèrent par leur stratégie pour le choix de la variable et pour la sélection de la valeur de la variable. En ce qui concerne le choix de la variable à muter, min- conflits et min-rés eau- conflits prennent la. variable à. partir de l’ensemble des variables en conflits (K(I)), c’est-à-dire, parmi les variables qui appartiennent à une contrainte qui est violée. En revanche, arcmutaüon réalise la sélection de la variable d’une manière purement aléatoire, parmi l’ensemble V de variables du problème. Il parcourt toute l’instanciation, variable par variable, et suivant la probabilité de mutation l’opérateur décide si elle sera mutée. Pour le choix de la valeur, min-conflits choisit la valeur qui minimise le nombre de contraintes violées dans le graphe de contraintes. Par contre, mm-réseau-conflits sélectionne la valeur qui minimise la valeur de la fonction de mm-réseau-conflits (équation 3.5), la valeur donc minimise le nombre de variables impliquées dans la violation des contraintes. Arc-mutation cherche la valeur qui apporte une amélioration globale au problème, une diminution donc de la valeur de la fonction d’évaluation Z(I) mesurée en utilisant mff. il est évident que la valeur de la fonction mff correspond exactement à celle de la fonction ne. Les deux fonctions mesurent le nombre de conflits propagés sur le réseau de contraintes. La différence la plus remarquable entre minrés eau-conflits et arc-mutation, est qu’une variable peut être choisie par arc-mutation  sans qu’elle soit liée à une contrainte non-satisfaite, que ce n’est pas le cas de minrcsc.au-conflits. Il est important de remarquer que min-conflits ainsi que min-réseav-conflÂts gardent la valeur actuelle de la variable quand une amélioration n’est produite par aucun changement. Par contre, arc-mutation empêche l’affectation de la valeur courante à la variable. Avec arc-mutation, il est possible donc que la valeur de la fonction d’évaluation diminue, ce qui n’est pas le cas des heuristiques -min-conflits et mni-réseau-conflits. Le résumé de cette comparaison est montré sur le tableau 4.1.

Arc-crossover

Les meilleurs résultats trouvés jusqu’à présent dans la littérature pour la résoluiion de CSP par des algorithmes évolutionnistes. ont été obtenus avec des algorithmes qui utilisent des opérateurs asexués, [ERR94], [DBB94]. Ces algorithmes sont plutôt orientés vers l’exploration que vers l’exploitation, à cause en partie de la caractéristique d’épistasie des CSP. en d’autres termes à cause de la haute corrélation entre les variables dans le chromosome. De plus, utiliser l’opérateur classique de croisement peut, éventuellement, produire une dégradation de la performance de l’algorithme comme nous l’avons remarqué dans le chapitre 2. Nous ‘proposons un nouvel opérateur sexué arc-crossover qui prend en compte la structure du CSP. Notre objectif premier ici est la réparation des contraintes. Il consiste donc à créer un fils à partir d’une « bonne » recombinaison (voir déf 2.2.4) des valeurs de deux parents. Pour illustrer l’idée qu’il y a derrière sa conception, voyons la figure 4.5. Dans ce cas, nous avons sélectionné deux parents Cri et Cr2 et nous souhaitons générer un fils qui hérite de la meilleure combinaison de leurs valeurs des variables. Supposons que Cxq satisfait le Graphe^ et que Cr2 satisfait le Graphe2. De plus, supposons que la valeur de la variable Â’4 clans Cr2 et la valeur de la variable X^, dans C’/’i satisfont la contrainte Ci, et que la valeur de la variable X3 dans Cv\ et la valeur de la variable A'( , dans Cr2 satisfont la contrainte C2. Si nous faisons un bon croisement entre ces parents, nous pourrons obtenir un fils qui satisfait toutes .

Opérateurs

FlG. 4.5 – Exemple: Bon croisement les contraintes du graphe. 11 est evident que c’est une situation spéciale, mais nous montrerons que le fait d’inclure un opérateur qui prenne en compte l’idée de partition en sous-graphes nous permettra d’obtenir une amélioration de la performance de l’algorithme évolutionniste. Arc-crossover travaille sur la base d’une séquence ordonnée de contraintes. Définition 4.2.3 (Pré-ordre des Contraintes) Soit un CSP binaire P = [V,D,Ç) avec une m.atrice de contraintes R, une instanciatum I et la Contribution de Cnà la fonction d’évaluation c(C0) pour chaque contrainte Ca, (ft = 1,. . ., 77), On définit un Pré-ordre des Contraintes ( noté « < « ), par la règle suivante: Ck, c(Cfc.) Définition 4.2.4 (Priorité de Contraintes) Soit un CSP binaire P = (V. D, () avec une matrice de contraintes R ; une instanciaiion I et la Contribution de Caà la fonction d’évaluation c(Ca) pour chaque contrainte C , (o = 1; • • • , »])• O71 définit la Priorité de Contraintes P comme une séquence sur le. pré-ordre • < des contraintes telle que: (C\ …. , C’,„) avec. Ck, < Ck,+1, Vz = 1,… , r/ – 1