[ 11 ] : Problème des Fusiliers : Résolution par Metaheuristiques

Nb etusNombre d'etudiants : 4 max
Responsable(s)
Sébastien Verel
ver.SPAMxel@i3s.unice.fr
http://www.i3s.unice.fr/~verel
Manuel Clergue
cle.SPAMxrgue@unice.fr
http://www.i3s.unice.fr/~clergue
LieuValrose, Université de Nice et/ou laboratoire I3S à Sophia
EnvironnementLinux ou Windows
Pré-requisLa curiosité et l'imagination
Contexte La synchronisation d'une ligne d'automates, problème connu sous le nom de problème des fusiliers, a donné lieu à de nombreux travaux. Le problème a été proposé par J. Myhill en 1957 comme ceci : ''Comment synchroniser une ligne de fusiliers de façon à ce qu'ils se mettent à tirer ensemble, alors que l'ordre donné par un général depuis l'un des deux bords de l'escadron met un certain temps à se propager?''. Chaque fusilier est représenté par une cellule d'un l'automate cellulaire et peut se trouver dans differentes états, les plus importants étant : l'état latent (quiescent ou de repos), l'état de départ (général) qui donne l'ordre et l'état de feu ou de synchronisation. Le but du problème est de trouver les fonctions de transition qui vont permettre d'obtenir une configuration dans laquelle toutes les cellules se trouvent ensemble et pour la première fois dans l'état feu. Mazoyer a trouvé une solution à ce problème lorsque le nombre d'état est 6. De récents travaux encourageants ont tenté de résoudre le problème pour 5 états en transformant le problème en problème d'optimisation et en le résolvant à l'aide d'algorithmes d'optimisation stochatiques tels que le recuit simulé ou les algorithmes évolutionnaires. Dans ce sujet, il s'agira de tenter de trouver une autre solution au problème des fusiliers à 6 états que celle trouvée par Mazoyer en utiliant la méthodologie développée par les récents travaux sur 5 états.
Objectifs Le but de ce travail est de développer un algorithme efficace de résolution du problème des fusiliers à 6 états et mettre en place une page web permettant de comparer les meilleurs résultats sur ce problème.
Existant Les travaux de Mirela Frandes sur le problème des fusiliers proposent une méthodologie et des algorithmes efficaces de résolution pour le problème des fusiliers à 5 états. La solution de Mazoyer peut aussi aider à définir un bon espace de recherche d'une solution pour 6 états.
Description du travail
  • Etudier les travaux précédents sur le problème des fusiliers
  • Définir des algorithmes d'optimisation stochatiques de résolutions
  • Développer ces algorithmes
  • Expérimenter et comparer ces algortihmes
  • Mettre en place une page web de comparaison des meilleurs résultats en s'inspirant de la page tsplib
Références

J.B.Yunés, Synchronisation et automates cellulaires: la ligne de fusillers, Thèse (1993) : la bibliographie de la thèse est un historique sur le problème des fusiliers
http://tel.archives-ouvertes.fr/tel-00139049/en/

Exposé sur les algorithmes de résolution du problèmes des fusiliers à 5 états.
http://www.i3s.unice.fr/~verel/talks/frac2007_fusiliers.pdf

La page wikipedia sur les métaheuristiques
http://fr.wikipedia.org/wiki/M%C3%A9taheuristique

1er choix pour
2e choix pour
3e choix pour
4e choix pour
Note: la chaîne '.SPAMx' est ajoutée automatiquement dans toutes les adresses email pour éviter les spams envoyés par les robots qui parcourent les pages web. Pensez à la retirer avant d'envoyer un mail ...