Ce rapport constitue la suite aux algorithmes génétiques.
La première partie présente les indications nécessaires au problème du commis voyageur (PCV) et à celui De l’emploi du temps (EP) par AG.
La deuxième partie est une discussion sur la convergence et l’efficacité des AG.
Enfin, nous concluons par une ébauche sur le choix des valeurs des paramètres des AG.
2 - Exemples (suite) :
2.1 - Problème du PCV :
Le PCV consiste à déterminer l’itinéraire fermé le plus court (ou le moins coûteux) reliant n villes.
En soit, le problème relève de l’analyse combinatoire et sa complexité est de l’ordre de n ! .
Cependant, les méthodes de la programmation dynamique ont amélioré sa complexité pour la porter n22n [1]. La résolution de ce problème par AG permet au bout de trois à quatre générations d’arriver à une solution optimale. Plusieurs méthodes de simulation ont été proposées. Cependant, la fonction d’évaluation est intrinsèque au problème : elle consiste à calculer la longueur ou le coût de l’itinéraire considéré.
2.1.1 - Les opérateurs génétiques :
Oliver [2] propose la construction d’un itinéraire de sorte que chaque ville et sa position proviennent du même parent. Le mécanisme est illustré par l’exemple de 9 villes.
Soient deux parents (itinéraires) :
P1 = (1 2 3 4 5 6 7 8 9)
P2 = (4 1 2 8 7 6 93 5)
On produit le premier itinéraire en prenant la première ville du premier parent :
I1 = (1 x x x x x x x x).
Puisque chaque ville doit être prise dans l’un des parents (à partir de la même position), la prochaine ville qui sera considérée doit être la ville 4 , comme ville de P2 juste en dessous de la ville 1 sélectionnée. Dans P1 , cette ville est à la position ‘’4’’ ; on obtient :
I1= (1 x x 4 x x x x)
Par suite, la ville 8 de P2 juste en dessous de la ville 4 sélectionnée sera prise et on obtient :
I1 = (1 x x 4 x x x 8 x)
Suivant cette règle, les prochaines villes à inclure dans le premier itinéraire sont 3 et 2 qui donnent :
I1 = (1 2 3 4 x x x 8 x).
La sélection de la ville 2 requiert celle de la ville 1 qui est déjà dans la liste. On a, alors, complété un cycle. Les villes restantes 7,6,9 et 5 seront prises de l’autre parent ; on obtient :
I1 = (1 2 3 4 7 6 9 8 5).
De la même façon, en commençant cette fois par le parent P2, on obtient :
I2 = (4 1 2 8 5 6 7 3 9).
Ce qui précède illustre, donc, le procédé de croisement de deux parents. La mutation consisterait à permuter aléatoirement deux villes.
2.1.2 - L’algorithme :
On peut procéder, par exemple, comme suit :
1- On initialise un certain nombre d’itinéraires
2- On procède au croisement deux à deux
3- On procède à la mutation
4- On évalue chaque itinéraire
5- On garde un certain pourcentage de la population parmi les meilleurs
6- On recommence à l’étape 2.
2.2 - Le problème de l’emploi du temps :
2.2.1 - Description du problème :
Le problème de l’emploi du temps revêt une très grande importance pratique. Il a été intensivement étudié en recherche opérationnelle et reconnu NP-hard [3] ; il intègre
plusieurs contraintes non triviales. L’application des AG à ce problème a été testée avec succès avec des données d’une grande école à Milan (Italie) selon la version suivante de l’emploi du temps [4] :
-Une liste des professeurs { T1,….,Tm}
-Une liste d’intervalles de temps (heures) {H1,…..Hn}
-Une liste de classes {C1,…..Ck}.
Le problème consiste à trouver un emploi du temps (prof-temps-classe) avec une fonction d’évaluation satisfaisant aux contraintes spécifiques suivantes :
-étendre quelques classes sur toute la semaine
-Libérer quelques après-midi pour les enseignants à temps partiel
-Avoir un enseignant supplémentaire disponible pour remplacement à chaque heure.
Les contraintes générales sont :
-Le nombre d’heures pour chaque professeur et chaque classe est prédéfini
-Un seul professeur occupe une seule classe à un heure donnée
-Un professeur ne peut pas occuper plus d’une classe en même temps
-Chaque classe programmée pour une période donnée, peut disposer d’un professeur.
2.2.2 - Résolution du problème par AG :
La représentation la plus naturelle du chromosome dans ce problème est une matrice (Rij) (1 =< i =< m et 1 =< j =< n) où chaque ligne correspond à un professeur et chaque colonne à un horaire. Un élément rij appartient à {C1,…..Ck}.
Les opérateurs génétiques suivants ont été utilisés :
-Mutation d’ordre q : l’opérateur sélectionne deux séquences consécutives de q éléments dans une même ligne et les permute.
-Mutation des horaires : l’opérateur sélectionne deux groupes de colonnes (horaires) de R et les permute.
-Croisement : étant données deux matrices R1 et R2 , l’opérateur trie les lignes par ordre décroissant des valeurs de la fonction d’évaluation locale. Les b meilleures lignes seront conservées et les m - b autres proviendront de la deuxième matrice.
- Les auteurs ont introduit dans l’algorithme une fonction de contrôle qui permet d’éliminer les cas où plus d’un professeur sont présents dans la même classe en même temps.
3 - Convergence et paramétrage :
La convergence et le choix des valeurs des paramètres des AG ne sont pas, jusque là, fixés mathématiquement de façon rigoureuse. Cependant, des heuristiques permettent d’y conclure. Aussi, leur efficacité et leur optimalité ont été constatées dans plusieurs thèses dont nous rapportons quelques résultats.
3.1 - Convergence [5] :
La convergence peut être mesurée par la performance statistique : si à une certaine génération, une forte concentration d’individus s’agglutine autour du meilleur (étude de la dispersion), on peut conclure à la convergence. On peut ,aussi, l’observer en mesurant comment les individus changent à chaque position de gène. Un gène est dit avoir convergé lorsque 95% de la population partage la même valeur. La population est qualifiée d’avoir convergé si tous les gènes ont convergé.
3.2 - Choix des valeurs des paramètres [6]:
- Taille de la population :
Trop faible : l’AG n’a pas assez d’échantillons de l’espace de recherche
Elevée : l’AG est plus uniforme et prévenu contre la convergence prématurée dite aussi stagnation locale ou dérive génétique.
Trop élevée : le nombre élevé d’évaluations de la fonction d’adaptation par génération ralentit la convergence.
- Taux de croisement :
Trop élevé : les bonnes structures risquent d’être cassées trop vite par rapport à l’amélioration que peut apporter la sélection.
Trop faible : la recherche risque de stagner à cause du faible taux d’exploration.
Le taux habituel est choisi entre 60% et 100%.
- Taux de mutation :
Trop élevé : la recherche devient trop aléatoire.
Trop faible : la recherche risque de stagner à cause du faible taux d’exploration.
Si la taille de la population est faible, un taux de croisement faible doit être combiné avec un taux de mutation élevé. Ces observation restent valables pour les fonctions continues sans contraintes avec codage binaire.
4-conclusion :
La performance d’un AG dépend plus du codage et de la fonction d’évaluation que de l’influence des paramètres [6]. Cependant, un choix judicieux de ces derniers est essentiel pour l’efficacité de l’algorithme. Il faut souligner que si les valeurs utilisées (60% à 100% pour le croisement et 0.1% à 5% pour la mutation) sont des marges de manœuvre utilisées, dans la pratique elles demeurent trop larges. Nous pensons qu’une étude à ce sujet mérite d’être menée par champs d’application (programmation dynamique, théorie de graphes…) pour de restreindre les intervalles de ces valeurs.
Bibliographie
[1] G.Brassard et P. Bratley : Algorithmes –conception et analyse. Les presses de l’université de Montréal pp157-159. édition Masson Paris 1987.
[2] Oliver, I.M. Smith, D.J., and Holland, J.R.C, a study of permutation crossover operators on the traveling salesman problem pp224-230. 1982.
[3] Forrest, S., implementing semantic netwoks structure using the classifier system. Lawrence Erlbaum Associates, Hillsdale, N .J, pp24-44. 1985.
[4] Colorni, A., Dorigo, M., and Maniezzo, V.,Genetic Algorithms and highly constrained problems : the time table. PP55-59 Procedings of the first International conference on the parallel problem solving from nature (PPSN), Dormund, Germany 1990.
[5]Catherine Kham Phang : Algorithmes heuristiques et évolutionnistes. Thèse de doctorat université de Lille. Octobre 1998.
[6] Grefenstette, j.j optimisation of control parameters for genetic algorithms, IEEE translation on systems Man, and cybernetics vol16, No 1 pp122-128. 1986.
