Click here to load reader
View
47
Download
0
Embed Size (px)
DESCRIPTION
Travail d’Etude et de Recherche :. Le Problème des fusiliers. Encadrants : Sébastien VEREL, Manuel CLERGUE. Groupe : BOUHLEL Oualid , CASANOVA Pierre, FULCONIS Angélique, BENOUALI Hamine. Plan :. Description du sujet Définition : Automate cellulaire - PowerPoint PPT Presentation
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