Algorithme Evolutionnaire à Etats pour la résolution du problème des Fusiliers
15/12/10 18:02 | Stages 2010/11
Laboratoire : I3S, Sophia Antipolis
Equipe : TEA
Contact : Philippe Collard (philippe point collard arobase unice point fr)
Co-encadrant : Sébastien Vérel
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 donne 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 différentes é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 (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.

J. Mazoyer a trouvé une solution à ce problème lorsque le nombre d'états est 6. De très récents travaux encourageants ont tenté de résoudre le problème pour 5 états en l'exprimant comme un 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.

Objectifs :
Dans ce stage, il s'agira de résoudre le problème d'optimisation induit par le problème des fusiliers à 5 états à l'aide de l'algorithme évolutionnaire à états (SEA). Le SEA est un algorithme adaptatif hybride parallèle.

Le but de ce travail est de proposer et d'analyser un algorithme stochastique efficace de résolution du problème des fusiliers à 5 états. Il s'agira d'abord de développer un algorithme évolutionnaire hybride basé sur des algorithmes de recherche locale (recuit simulé, tabu search). Puis ensuite, de les combiner dans au sein de l'algorithme évolutionnaire à état qui permet un contrôle adaptatif parallèle des paramètres des précédentes algorithmes.

Bibliographie
- J.B.Yunès, Synchronisation et automates cellulaires: la ligne de fusiliers, Thèse (1993)
- Exposé sur les algorithmes de résolution du problème des fusiliers à 5 états, FRAC 2007
- S. Verel, M. Clergue, P. Collard, States based Evolutionary Algorithm, PPSN, 2010.