Ok. Merci!
Hervé a pigé, c'est celui pour qui je désirais être clair.
Donc, maintenant, on sait calculer à quel point une solution "est pas bonne", puisque la solution idéale aurait une valeur de 0 et que chaque contrainte violée augemente cette valeur.
Après l'espace des solutions et la contrainte, le dernier point essentiel est le Voisinage. C'est le point CLEF d'une bonne MH, car ce sont les paramètres qu'on va lui donner qui feront ou non la bonne solution.
Un voisinage est une liste d'opérations unitaires que l'on peut effectuer sur l'espace des solutions. Une opération unitaire (O.U.) permet de passer d'une solution à une autre.
Pour reprendre l'analogie du cube du vieil erhno rubik, une OU est un mouvement du cube, c'est à dire "faire tourner" l'une des "roues" du cube...
Dans le cas d'ASL, il s'agit d'un tir, d'un mouvement, d'une réparation, etc. Mais l'important est le mot unitaire (vue l'immense possibilité d'actions dans ASL, va falloir soit segmenter le problème en sous problèmes avec une MH dédiée, soit concevoir la MH la plus complexe que je connaisse).
(
J'y repense maintenant, mais on a pondu un site lors de notre projet avec des fiches explicatives moins claire mais plus péchues: http://membres.lycos.fr/projetdi/ )
Maintenant qu'on a ces OU, on leur affecte une probabilité.
On fait telle OU avec telle probabilité, telle OU avec telle autre, etc.
La somme des probas faisant 1 (ou 100% de chances).
C'est l'élément aléatoire du truc, et il doit être créé avec énormément de soin.
Maintenant, que fait on? Ben c'est très simple!
On définit une "température" (le 'recuit simulé' est à l'origine une simulation du mouvement des atomes dans un métal en train de refroidir).
Soit le nombre d'itérations $i.
A chaque itération, on lance un tirage au hasard donnant une OU.
On l'applique sur l'ordonnancement qu'on avait au départ (qui est à définir aussi, mais c'est une autre histoire, aussi complexe que la MH).
On calcule le poid de la solution générée.
Si elle est meilleure que la précédente, on la garde et on incrémente $i.
Si elle est moins bonne, on l'accepte quand même, selon une probabilité qui suit une courbe descendante en fonction du nombre d'itérations. Plus $i est grand, moins on accepte les mauvaises solutions.
Pourquoi? Parce qu'on veut éviter les minimums locaux et qu'une "mauvaise solution" est peut être le premier pas vers un minimum global (quand on cherche à résoudre le rubik's cube, on est bien obligé de parfois détruire ce qu'on avait arrangé pour pouvoir améliorer).
Et quand la solution ne change plus, on s'arrête.
On peut définir l'espace des solutions comme un terrain accidenté, et notre MH est un marcheur. Notre marcheur cherche à aller dans la vallée la plus profonde. Au début, il a la patate, il hésite pas à gravir des montagnes et collines pour sortir des vallées peu profondes... Mais à la fin de la journée il se fatigue et descend au fond de la vallée qu'il a finalement atteinte.
On peut améliorer la MH en lui faisant mémoriser les dix dernières solutions et en lui interdisant de revenir à l'une de ces solutions (recuit avec "queue": la MH refuse de se marcher sur la queue), on peut aussi faire travailler une MH sur 10 solutions de départ et choisir la meilleure ("les fourmis"), etc.
C'est un truc assez simple dans son idée de base, mais assez complexe à mettre en oeuvre. Par contre, les résultats sont incomparables. C'est très puissant.
Je ne sais pas si cela peut être appliqué à ASL, ou si du Branch&Bound ou autre théorie des graphes ne sera pas plus simple et efficace (les IA sont souvent des arbres/graphes).
Je te souhaite un très grand courage pour l'oeuvre titanesque (même sans MH) dans laquelle tu te lances.
Bravo!
greuh.
