Application des algorithmes génétiques aux problèmes de graphes et d'ordonnancement
Nous allons tout d'abord dresser une liste de problèmes liés à la théorie des graphes et/ou à l'ordonnancement que l'on peut résoudre de manière approchée en utilisant des méta-heuristiques.
Nous verrons ensuite quels sont les codages et les opérateurs génétiques qui peuvent être utilisés pour ces problèmes en les regroupant par grandes familles de codage.
Listes de problèmes de graphes et d'ordonnancement
Problème 1 :
---------------
Colorier un graphe (non orienté) en utilisant un minimum de couleurs.
Problème 2 :
---------------
Trouver un circuit hamiltonien de longueur minimale.
Ce problème est bien connu sous le nom du problème du voyageur de commerce.
Problème 3 :
---------------
Minimiser la durée totale d'un ordonnancement de projet avec une seule ressource disponible en un seul exemplaire.
Problème 4 :
---------------
Minimiser la durée totale d'un ordonnancement de projet avec une ou plusieurs ressources dont au moins une existe en plusieurs exemplaires.
Problème 5 :
---------------
Minimiser la somme totale (ou pondérée) des retards pour un problème d'ordonnancement d'atelier avec une seule machine en un seul exemplaire.
Problème 6 :
---------------
Minimiser la somme totale (ou pondérée) des retards pour un problème d'ordonnancement d'atelier avec une seule machine en un seul plusieurs exemplaires.
Problème 7 :
---------------
Minimiser la durée totale d'un flow shop de permutation lorsqu'il y a strictement plus de 2 machines en un seul exemplaire.
Utilisation d'un codage binaire
Le codage binaire convient mal ou est d'une utilisation très compliquée pour la liste des problèmes considérés.
On pourrait utiliser une matrice binaire pour le problème n° 1 (problème de coloration)
où MB(i,j) = 1 si les points i et j ont la même couleur et 0 sinon.
On pourrait également utilisé une matrice binaire pour les problèmes n° 2, 3, 5 et 7 (problèmes où le choix d'un ordre permet d'obtenir une solution)
où MB(i,j) = 1 si la tâche i est avant la tâche j et 0 sinon.
Mais les opérateurs génétiques associés sont trop compliqués pour être proposés dans ce cours.
Ils ont leur place dans des articles de recherche, moins dans un cours, même de niveau master.
Utilisation d'un codage symbolique
Problème 1 :
---------------
C(i) = numéro de la couleur du point i.
Il est à noter que lorsque l'on a une solution, par exemple, avec p couleurs,
le choix de la couleur de chaque stable colorié est arbitraire
et il y a en fait factoriel(p)=1x2x3x...xp codages différents que l'on peut obtenir en permutant les couleurs utilisées.
Pour éviter cela, il faut utiliser, par exemple, un opérateur de normalisation des chromosomes à utiliser,
soit a priori avant d'appliquer les opérateurs génétiques
soit a posteriori après avoir appliqué les opérateurs génétiques.
Les opérateurs génétiques sont ceux déjà présentés pour le codage symbolique
La normalisation peut être, par exemple. en suivant l'ordre des gènes du chromosome :
- Le point 1 est toujours de couleur 1 (et peut même ne pas figurer dans le chromosome).
- Le premier point qui n'est pas de couleur 1 est de couleur 2.
- Le premier point qui n'a ni la couleur 1, ni la couleur 2 est de couleur 3.
et ainsi de suite.
Les autres problèmes :
-------------------------
Le problème du voyageur de commerce et les problèmes d'ordonnancement peuvent être résolus en utilisant un codage symbolique à condition d'utiliser un codage indirect et de disposer d'un ou de plusieurs générateurs qui permettent de transformer le génotype contenant des priorités de placement pour les tâches en un phénotype correspondant à un ordonnancement réalisable dont on pourra calculer la valeur du critère de manière à évaluer le chromosome.
C'est surtout intéressant pour les problèmes d'ordonnancement cumulatif où certaines ressources existent en plusieurs exemplaires.
Pour les problèmes disjonctifs, on peut préférer le codage de permutation.
Utilisation du codage de permutation
Son utilisation est immédiate et tous les opérateurs génétiques de croisement et de mutation conviennent pour les problèmes n°2, 5 et 7 pù toutes les permutations correspondent à des solutions réalisables.
On peut les utiliser, mais les opérateurs génétiques doivent assurer la faisabilité des solutions obtenues pour le problème n° 3 où il ne faut pas créer de circuits de longueur strictement positive dans le graphe potentiel-tâche enrichi par les disjonctions arbitrées par la permutation.
La fermeture transitive de l'union de la permutation et du graphe potentiel-tâche de l'ordonnancement de projet permet de vérifier l'existence de tels circuits et peut aider les opérateurs génétiques à ne pas les créer.
En général, il est préférable d'avoir un dispositif qui assure que les opérateurs génétiques créent des solutions réalisables, plutôt que de jeter les solutions non réalisables obtenues.
Par exemple, si les deux parents sont faisables, alors le croisement 1X donnent des enfants également faisables.
