Travail d’Etude et de Recherche :

Travail dEtude et de Recherche :

Travail dEtude et de Recherche :Le Problme des fusiliers1

Encadrants : Sbastien VEREL, Manuel CLERGUEGroupe :BOUHLEL Oualid,CASANOVA Pierre,FULCONIS Anglique,BENOUALI HamineDescription du sujetDfinition : Automate cellulaireProblmatique et tat de lartLes diffrentes approchesLes mtaheuristiques solution unique : Hill ClimbingRecherche tabouRecuit SimulAlgorithme volutionnaireLe backtrackingLapproche par signauxLes approches combinesMeilleurs rsultats obtenusConclusion

2Plan :

Comment synchroniser une ligne de fusiliers de faon ce quils se mettent tirer en mme temps ?

Rsolution : Modlisation sous forme dun automate cellulaire Recherche des rgles de transition

Etude pour 5 tats3Prsentation du sujet : Le problme des fusiliers J.Myhill 1957

Ligne de fusiliersLigne de fusiliers synchroniss4Automate cellulaire

ReposGnralFeuEtats intermdiairesEtats des cellules

GnralFeuEtats intermdiairesRepos2N-2La grille de N cellules (ici N = 4) 2N-2 : temps optimal pour synchroniser N cellules5Automate cellulaire

rgles de transition : Diagramme espace temps Motif initial Valeur suivanteConfiguration initialeConfiguration finaleMise jour par rgle locale.

Types dordinateurs en plein essor : les machines en rseauxParalllisme simple et universel : les automates cellulaires

Problmatique et tat de lartNombre dtatsTemps optimalTemps non optimal

3 tatsPas de solution :BalzerPas de solution :Yunes,19934 tatsPas de solution :Balzerouvert5 tats OuvertOuvert6 tats Une seule solution:Mazoyer,1986 ouvert7 tats Solution :Mazoyer,1986Solution :Yunes,19938 tats Solution :Balzer,1967Solution Yunes,1993plusieurs milliers dtats Solution :E.Goto6Mtaheuristiques solution unique : Hill Climbing, Recuit Simul, Recherche Tabou

Algorithme volutionnaire

Le backtracking

Approche par signaux

Approches combinesLes diffrentes approches 7Heuristique : algorithme de rsolution bas sur lexprience sans fournir pour autant une solution optimale

Mtaheuristique : ensemble dheuristiques

Mtaheuristique de recherche locale :Algorithme solution unique Hill Climbing, Recuit Simul Algorithme population de solutionsAlgorithme volutionnaire, algorithme de fourmis 8Les mtaheuristiquesEspace de recherche :S ensemble des solutions

Voisinage : sous ensemble de solutions obtenues par transformations donnes

Fonction objectif :valuation pour la meilleure solution9Dfinitions supplmentaires. . .. . .S0Un voisin de S0Choisir solution initiale s SRpter Choisir s V(s) telle que f(s) est maximales sJusqu s optimum local 10Hill Climbing Oprateur local de base de mtaheuristique

Heuristique dexploration maximale

Introduite par Glover en 1986But: chapper aux optima locaux Principe :Introduction dune mmoire dans stratgie dexploration

11Recherche Tabou Choisir une solution s SInitialiser tabou TRpter Choisir s V(s) telle que (f(s) meilleure solution de V(s) et Critre daspiration vrifi)Ou f(s) meilleure solution de V(s) non tabous sUpdate Tabou TJusqu Critre darrt vrifi

Utilis depuis les annes 80Inspir de la physique (thermodynamique )

But: Echapper aux optima locaux Principe: probabilit non nulle de slection dune solution voisine dgrade 12Recuit Simul Choisir solution initiale sS et temprature initiale TRpterChoisir alatoirement sV(s), =f(s)-f(s)Si > 0 alors ssSinon u nombre alatoire de [0,1]

Si u < alors s sFin si Fin siUpdate temprature TJusqu critre darrt vrifi

13Rsultats exprimentaux de Hill Climbing Nombre dexcutions en fonction de taille du problme rsolu Rsultat obtenu pour: 5000 itrations5000 excutions

La moyenne = 5,27

Lcartype = 1,36

Meilleure solution de taille = 1214Rsultats exprimentaux de Hill Climbing

Temps moyen pour chaque taille de ligne de fusiliers synchroniss15Rsultats exprimentaux de Recherche Tabou

Nombre dexcutions en fonction de taille du problme rsolu

Rsultat obtenu pour: 5000 itrations 5000 excutionsLa moyenne = 7,1

Lcartype = 2,19

Meilleure solution de taille = 13

15

16Rsultats exprimentaux de Recherche Tabou Temps moyen pour chaque taille de ligne de fusiliers synchroniss

17Rsultats exprimentaux de recuit simul Nombre dexcutions en fonction de taille du problme rsolu Rsultat obtenu pour: 5000 itrations 75 excutions

La moyenne = 4,24

Lcartype = 0,43

Meilleure solution de taille = 5

Mthode Nb iterations Nb run Temps pour un run Temps totalMoyenne cartype Meuilleur rsultatHill Climbing 5000500028s140000(38h53)5,271,3612Recherche Tabou5000100022s27517s(7h38)7,12,19

13Recuit Simul 500075416S32021(8h53) 4,240,43518Analyse comparative des rsultatsRecherche TabouAlgorithme volutionnaire

19

Principe : bas sur la thorie de lvolution (Darwin)

Population compose dindividus

Evaluation slection, croisement, mutationUtilisation des librairies du package Paradiseo-eoFonction objectif et voisinageRsultats : synchronisation de 2 8 20Implmentation :

Exemple de croisement en un pointGnration initialeGnration suivante21Resultats

Constat : Augmentation du nombre de fusiliers synchroniss en fonction de la taille de la population Meilleurs rsultat : lorsque le taux de croisement et de mutation est proche de 1.0Taux de croisement peu influent sur les rsultats

22Le Backtracking PrincipeTechnique permettant dviter l'numration exhaustive de l'espace de recherche. Etapes : Choisir une valeur pour une rgle Retourner en arrire en cas de conflit Choisir lalternative suivante (attribution dune nouvelle valeur la rgle)Attribution de rgleBbordbordbordbordbordbordOrdre dattribution des valeurs :

BbordbordbordbordbordbordRgle non affecteEtat reposEtat gnralEtat intermdiaire (1)Etat intermdiaire (2)Etat feu uniquement si on a atteint 2N-2itrationsBbord23Conflit et retour en arrire

Cration RgleConflit et retour en arrireAttribution dune nouvelle valeurPoints faisant chouer une solution : L'tat feu symbolisant la synchronisation n'est pas obtenu au bout de 2N-2 itrations. L'tat feu est obtenu avant ce nombre prcis d'itrations. Les rgles ne synchronisent pas les automates ayant une taille plus petite. Rgle prdfinie linitialisation :Cette rgle provoque le conflit

Rgle non affecte

24 Rsultats obtenus

122Ce sont les meilleurs rsultats obtenus avec cette mthode : synchronisation des automates de taille allant de 2 12.2425Mesure de temps

Croissance exponentielle pour une taille de lautomate > 9 Priode de temps importante , pour obtenir synchronisation avec taille = 1326Les signauxPrincipe :

Solution de Mazoyer :Stratgie diviser pour rgner :On dsigne par signal la propagation continue dune information lmentaire au sein dune ligne dautomates.

27Les signaux Dfinitions : Signal vers la droite :la vitesse doit tre maximaleSeulement deux possibilits :Une priode de 1 :

Une priode de 2 :

28Les signauxRsultats:?Comportement avec une priode de 2 :29Approche combine

30Meilleure solution

162Des rsultats indits :De nombreuses solutions en temps optimalUn meilleur rsultat 16 fusiliers

Des perspectives prometteuses :Outils dvelopps performants et disposition sur le siteProbabilit de dcouverte de nouveaux rsultats31Conclusion

32Questions ?Merci de votre attention