Algorithme génétique pour les ordonnancements à ressources limitées
Les algorithmes génétiques sont présentés de manière générale et plutôt précise dans une annexe à la fin de ce module.
Ce qui nous intéresse ici est de montrer rapidement comment les algorithmes génétiques peuvent être croisés avec les heuristiques à règle de priorité pour essayer d'explorer l'espace des solutions d'un problème d'ordonnancement de projet à ressources limitées de manière à trouver des solutions que l'on espère de bonne qualité (sans aucune garantie d'optimalité).
Choix de la structure générale, par exemple, le schéma de Goldberg
1) On génère une population initiale de solutions de manière aléatoire ou avec des méthodes heuristiques qui essaient de fabriquer de bonnes solutions.
2) On évalue les solutions de la population en cours et on retient la meilleure de toutes les solutions construites.
3) On passe de la population en cours à une nouvelle population en utilisant des opérateurs génétiques, généralement de "croisement" et/ou de "mutation". Certains individus étant conservés par simple recopie.
4) On retourne en 2) tant qu'un critère d'arrêt n'est pas vérifié, par exemple un nombre maximal de populations générées ou une durée maximale d'exécution.
Choix d'un codage indirect
Dans le cas d'un codage indirect : le chromosome contient des "paramètres" qui permettront de construire une solution en utilisant un générateur.
Ici où nous considérons des règles de priorité et nous allons utiliser un codage indirect.
Le chromosome contient la priorité des tâches et une heuristique à base de priorité permet d'obtenir la solution qui correspond aux priorités.
Si on dispose de plusieurs générateurs, on peut en appliquer plusieurs et retenir la meilleure solution obtenue.
Choix du type de codage
Ou bien on décide d'accorder une priorité différente à toutes les tâches et dans ce cas, on utilise un codage de permutation.
Ou bien on peut utiliser la même valeur de priorité pour plusieurs tâches et on utilise un codage symbolique.
Dans ce dernier cas, le nombre de valeurs de priorité différentes pourrait malencontreusement diminuer au fur et à mesure des itérations de l'algorithme.
Pour éviter cette dégénérescence, lors de certaines mutations, on peut diversifier sur un intervalle les valeurs des priorités existantes tout en respectant leur ordre.
Opérateurs de croisement
L'opérateur de croisement symbolique est utilisable pour le codage symbolique.
De très nombreux opérateurs de croisement ont été proposés pour les codages de permutation, quelqu'uns sont fournis et décrits en détails dans l'annexe sur les algorithmes génétiques, nous en répétons un seul ici à titre d'exemple.
Exemple de croisement symbolique sur des valeurs entières
Un point de croisement est choisi, par exemple de manière aléatoire.
Il est matérialisé sur l'exemple par une barre verticale rose.
Les gènes du parent 1 qui se trouvent avant le point de croisement (coloriés en rose) sont placés au début de l'enfant 1.
Les gènes du parent 2 qui se trouvent avant le point de croisement (coloriés en vert) sont placés au début de l'enfant 2.
Les gènes du parent 1 qui se trouvent après le point de croisement (coloriés en violet) sont placés à la fin de l'enfant 2.
Les gènes du parent 2 qui se trouvent après le point de croisement (coloriés en gris) sont placés à la fin de l'enfant 1.
Exemple de croisement d'ordres : le croisement 1X
Un point de croisement est choisi, par exemple de manière aléatoire.
Il est matérialisé sur l'exemple par une barre verticale rose.
Les gènes du père qui se trouvent avant le point de croisement (coloriés en rose) sont placés au début du fils 1.
Les gènes de la mère qui se trouvent avant le point de croisement (coloriés en vert) sont placés au début du fils 2.
Les gènes du père qui se trouvent après le point de croisement (coloriés en violet) sont placés à la fin du fils 3.
Les gènes de la mère qui se trouvent après le point de croisement (coloriés en gris) sont placés à la fin du fils 4.
Le fils 1 est complété à la fin par les gènes manquant en les triant dans l'ordre de la mère.
Le fils 2 est complété à la fin par les gènes manquant en les triant dans l'ordre du père.
Le fils 3 est complété au début par les gènes manquant en les triant dans l'ordre de la mère.
Le fils 4 est complété au début par les gènes manquant en les triant dans l'ordre du père.
(les parties triées dans l'ordre de l'autre chromosome sont coloriées en jaune)
Remarque : Propriété particulière du croisement 1X
Si le gène i est avant le gène j dans le père et dans la mère, alors, pour tous les enfants obtenus avec le croisement 1X, le gène i sera avant le gène j.
Remarque :
Si l'ordre du père et de la mère vérifie des contraintes de précédence, alors l'ordre des enfants obtenus avec le croisement 1X vérifie également les contraintes de précédence.
Cette propriété est fondamentale si on utilise un codage direct qui décrit la solution qui doit vérifier les contraintes de précédence, comme par exemple pour le problème d'ordonnancement de projet avec une ressource existant en un seul exemplaire.
Elle a n'a pas d'importance lorsque l'on utilise un codage indirect, car c'est le générateur de solution qui s'assure que l'on vérifie bien les contraintes de précédence.
Remarque :
Le croisement LOX, décrit également dans l'annexe, ne vérifie pas la propriété particulière du croisement 1X.
D'autre croisement que le croisement 1X vérifie cette propriété.
Le croisement 1X est vraiment le plus simple qui vérifie cette propriété.
Opérateurs de mutation
L'opérateur de mutation symbolique est utilisable pour le codage symbolique contenant des priorités.
Trois opérateurs de mutation sont proposés pour les ordres en annexe. Nous en rappelons seulement un ici.
Exemple de mutation symbolique sur des valeurs entières
Un gène est choisi de manière aléatoire.
Il prend une autre valeur numérique autorisée, par exemple, de manière aléatoire.
Exemple de mutation d'ordres : l'inversion
Deux positions p et p' sont choisies de manière aléatoire.
Les valeurs des gènes des positions p à p' sont copiées dans les positions p' à p.
La partie de la permutation entre les deux positions est donc inversée.
