![]() |
guill.net
-
La page des réseaux
|
![]() ![]() |
1
- Introduction
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) :
21-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é.
211-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.
212-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.
22-Le problème de l’emploi du temps :
221-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.
222-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.
31-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é.
32-Choix des
valeurs des paramètres [6]:
-Taille de la population :
-Taux de mutation :
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.