Fonction d’évaluation

Dans le chapitre précédent, nous avons présenté les composantes d’un algorithme evolutionniste. Mais la question suivante demeure; Qu’est-ce que peut apporter de plus un algorithme évolutionniste, par rapport aux méthodes stochastiques traditionnelles pour la résolution des CSP? En premier lieu, un algorithme évolutionniste permet une recherche multiple (population de pré-solutions), on peut donc chercher en parallèle dans différents espaces de recherche. Au contraire, les méthodes stochastiques traditionnelles ne cherchent qu’avec une seule pré-solution. Une différence fondamentale, à notre avis, des algorithmes évolutionnistes par rapport aux méthodes stochastiques classiques (telles que G S AT ou min-conflits et leurs variantes) réside dans la coopé- ration possible entre les pré-solutions de la population pour trouver une solution au problème. Une pré-solution n’évolue plus individuellement mais peut se combiner avec d’autres. Dans un algorithme évolutionniste qui fait évoluer de manière aléatoire les différents individus de la population (exploration), on ajoute de l’exploitation qui cherche à profiter de la connaissance contenue dans les différentes pré-solutions, en les combinant. Puisque notre but est de concevoir un algorithme évolutionniste pour ré- soudre des problèmes de satisfaction de contraintes, nous allons donc dans ce chapitre aborder la définition d’une fonction d’évaluation, en essayant de prendre en compte quelques caractéristiques des CSP. Pour profiter du mécanisme que fournissent les algorithmes évolutionnistes, il nous faut aussi de bons opérateurs qui soient capables de mettre en valeur la connaissance des pré-solutions par une bonne combinaison.

Ce l’onction d’évaluation standard (voir définition 2.5.1), afin de motiver l’introduction de notre nouvelle fonction, après avoir défini quelques concepts. Ensuite, nous incorporerons cette fonction, comme heuristique dans la méthode de min-conflits et puis la comparerons à l’aide de quelques résultats. Enfin, nous évaluerons le comportement de cette fonction dans un algorithme génétique qui résout le problème de coloriage de graphe avec 3 couleurs. Finalement, nous proposerons une extension de cette fonction pour les problèmes n-aires. heuristiques pour guider le « parcours stochastique’1 dans l’espace de recherche. La fonction d’évaluation est utilisée pour mesurer l’amélioration de lïnstanciation modifiée et pour conduire la. recherche vers des instantiations plus prometteuses en termes de satisfaction des contraintes. Souvent, cette fonction est la fonction d’évaluation standard Zstd(l) de la définition 2.5.1, qui correspond au nombre de contraintes violées. }Fre95|. Par exemple, considérons le CSP suivant dont le graphe et la matrice de contraintes sont illustrés par la figure 3.1:

Fonction d’évaluation pour CSP binaire

Zf,t,i(ï) sera pour les deux égal à 1, car chacune ne viole qu’une seule contrainte. Regardons maintenant le graphe de contraintes: la contrainte Ci est liée aux trois antres contraintes, ce qui veut dire que si nous changeons quelques valeurs des variables pertinentes pour C2, cela pourrait éventuellement, se traduire par une violation d’autres contraintes satisfaites à présent. En revanche, C\ est liée à C2 et C4. On peut donc penser qu’une réparation de cette contrainte aurait moins de conséquences vis à vis des autres contraintes qui sont déjà satisfaites dans le réseau. C’est cette idée que nous allons incorporer dans la définition de la nouvelle fonction d’évaluation. A part Z,,,i(ï). d’autres fonctions d’évaluation, plus spécifiques au type de problème a traiter, ont été proposées dans la littérature pour les CSP binaires. Par exemple, pour le problème de N-reines, Eiben et al. [ERR94J ont utilisé comme fonction d’évaluation le nombre de contraintes non satisfaites sur la diagonale. Pour un problème de dessin mécanique. Thorton a proposé de minimiser Y = Y.’^ ou d¿ est l’erreur normalisée pour la contrainte i. [Tho94j. Notre objectif ici est de définir une Fonction indépendante du problème à résoudre. D’autre part, le fait de prendre en compte le seul nombre de contraintes violées signifie: On se place dans le premier cas, c’est-à-dire, nous voulons obtenir une solution du CSP (et non une solution à un problème relâché). Nous souhaitons définir une fonction d’évaluation qui représente une sorte de « distance » entre une insfanciation et une solution, en termes du nombre de changements effectués par un algorithme de recherche locale. Une fonction qui considère donc la difficulté d’obtenir une solution. Cela nous a conduite à la définition de la nouvelle fonction qui prend en compte la structure du réseau de contraintes, plus précisément le degré de liaison entre les diöerei ! tes variables.