Skip to topic | Skip to bottom
Home
Minfo
Minfo.FulconisAngeliquer1.24 - 25 May 2008 - 22:31 - FulconisAngeliquetopic end

Start of topic | Skip to actions

Page de suivi Fulconis Angélique : Le problème des fusiliers

Dans cette page du wiki, vous trouverez l'état d'avancement de mon travail personnel. Notre sujet peut être abordé de quatre façons (approches). Personnellement, mon travail consistera à approfondir l'une d'entre elles : le Backtracking

avril:

Semaine 1 (du 07/04/2008 au 13/04/2008):

Nous avons rencontré notre encadrant "Sébastien Verel" qui nous a précisé le travail de chacun d'entre nous pour la période du lundi 09/04 au jeudi 17/04. Pour ma part, mon objectif consiste à implémenter le bactracking.

Cette semaine : Implémentation de l'algorithme du backtrack en c++ --> utilisation d'une pile (stack) de tableau. Le choix d'une pile n'est pas anodin, en effet : la règle à modifier doit être la dernière à avoir été crée (il y a en quelque sorte des règles plus prioritaires que d'autres). La pile est également un choix quasi obligatoire car les règles obtenues doivent permettre la synchronisation des fusiliers pour un nombre initial de 2 cellules, puis de 3, ... Donc plus la règle a été crée tardivement ( donc positionnée en sommet de pile) et moins il faudra revenir en arrière (à un automate avec un nombre initial de cellule plus petit).

Principe : En cas de conflit retour en arrière en changeant la règle se trouvant en sommet de pile. Les résultats (les règles que j'appelle par la suite les versions)sont copiés dans un fichier et des diagrammes espaces temps sont obtenus à la fin de l'exécution.

J'ai rencontré des difficultés pour résoudre les problèmes de segmentation fault : le programme renvoie des résultats pour n (nombre initial de cellules) de 2 à 6 mais retourne "segmentation fault" pour n de 2 à 7.


Semaine 2 (du 14/04/2008 au 20/04/2008):

Cette semaine, nouveau rendez vous avec monsieur Vérel. Nous lui avons fait part de notre avancement ainsi que des résultats obtenus.

Les problèmes de segmentation fault ont été résolus : j'ai utilisé un debugger gdb avec la commande "bt". Puis j'ai supprimé de nombreux appels récursifs qui sont mal gérés en c++.

Grâce à l'algorithme implémenté (pour le backtracking), j'ai obtenu des premiers résultats (qui semblent prometteurs pour la suite) : synchronisation en temps minimal (2n-2) d'une ligne de fusiliers avec un nombre initial de cellule allant de 2 à 12 (et bien entendu avec les mêmes règles).

Ces résultats vont pouvoir être exploités par Pierre : il va tenter de déceler l'apparition des signaux sur les diagrammes espaces temps que je lui ai fournis. Ils peuvent aussi être utiles à Hamine ou Oualid comme base (règle qu'ils vont donner en entrées à leurs algorithmes) et peut être que cela nous permettra d'obtenir de nouveau résultats.


Semaine 3 (du 21/04/2008 au 27/04/2008):

Un autre problème apparait : le temps d'exécution.

Cette semaine, j'ai effectué des mesures de temps pour avoir une idée de la complexité de l'algorithme en fonction du nombre de cellules initiales et des versions de règles utilisées. Vous pouvez voir (lien temps) quelques mesures de temps et l'on remarque que plus n augmente, plus le temps augmente mais plutôt de façon exponentielle que linéaire. Comme prévu, en voyant la taille de l'espace de recherche, on constate que le temps pose problème.

lien temps obtenu avec le code initial et le problème de l'espace mémoire :temps.

Mon but est donc d'optimiser au maximum mon algorithme pour diminuer le temps d'exécution :

  • sortir les variables de boucles
  • utiliser les versions des règles obtenues qui sont le plus rapides...

Le principal problème est bien évidemment le temps de calcul.

Cette semaine, nous avons également crée un site internet sur lequel nous allons stocker tous les résultats obtenus. Ce site a été réalisé collectivement (à quatre) car nous allons tous l'utiliser par la suite. Chacun d'entre nous a donc réalisé sa partie.

lien provisoire vers ma partie :backtracking. Une version finale du site sera disponible lorsque nous aurons rassemblé nos travaux.

Jeudi, nouveau rendez vous avec Monsieur Vérel. Au cours de cette entrevue, il m'a expliqué d'où provenait le problème : la pile occupe tout l'espace mémoire. Je me suis rendue compte que j'avais crée des tableaux (car il s'agit d'une pile de tableaux) que je ne supprimais pas.

Ce week end, résolution du problème d'espace mémoire. Envoie de mon code à Monsieur Vérel pour qu'il teste le programme sur un ordinateur plus puissant : lancement sur le serveur de calcul. Pour n allant de 2 à 13, plusieurs heures de calculs sont nécessaires et malgré cela, aucune solution n'est trouvée. Lien vers ma page de résultats mis en place.


Semaine 4 (du 28/04/2008 au 04/05/2008):

Cette semaine, plusieurs tests, et taches ont été réalisés :

  • Partir de n = 13, et essayer de backtracker vers n = 2. Cette approche a vite été abandonnée, en accord avec mon encadrant : en effet, dans l'espace de recherche, sans orienter les recherches (en fournissant déjà quelques règles), le temps pour trouver les règles qui synchronisent les cellules (pour n = 13) est trop important.

  • Au lieu d'initialiser une règle nouvellement crée à 0 (puis 1,2,3 et 4 en cas de conflit), j'ai commencé à 1 (puis 0,2,3 et 4 en cas de conflit). J'ai choisi de tester cela car lors de mes premières expérimentations à la main (où j'avais obtenu une synchronisation pour n allant de 2 à 8), l'une des premières règles crée était initialisée à 1. Pourquoi 0 ou 1 : En fait c'est pour tenter de minimiser le nombre de règles (et donc de diminuer les contraintes).
Résultats en lançant l'exécution sur le serveur de calcul: synchronisation des cellules pour n allant de 2 à 5. Pour n = 6, l'exécution ne permet pas pour l'instant d'avoir une solution : le temps de calcul est très important. J'ai essayé d'y parvenir en fournissant plus de règles dès le départ, et mon algortihme a obtenu une synchronisation de 2 à 11.

  • Modification de l'implémentation de la pile. En rajoutant les "deletes" pour résoudre le problème de l'espace mémoire, le temps d'exécution a doublé pour n allant de 2 à 12 (1220 au lieu de 806). Pour éviter la création et suppression des tableaux trop fréquentes qui font perdre du temps, j'ai donc modifié l'implémentation de la pile : au lieu d'avoir un "stack" de tableau, j'ai un tableau à deux dimensions (96 correspond au nombre de règles et 5 correspond aux trois nombres formant la règle, à la valeur attribuée à la règle et au "n" où la règle a été crée). Cette nouvelle implémentation me permet de savoir combien de règles sont utilisées et par rapport à l'ancienne version, j'ai une trace de la pile et je connais donc l'ordre d'apparition des règles. Après avoir réalisé cette modification, le code ne permettait pas d'être utilisé sans un fichier de pile. Or en vu de notre dernière approche, où le backtracking est combiné avec un autre algorithme, il faut que le programme soit exécutable avec seulement un fichier de règles. Pour le rendre compatible, j'ai donc intégré une fonction (create_pile) et permis à l'utilisateur de choisir avec ou sans pile lorsqu'il passe les arguments à l'exécution (cf le readme pour de plus amples explications).

lien temps obtenu avec le code final :temps.

  • Lors d'une entrevue avec mon encadrant, je lui ai exposé mes idées pour améliorer davantage (et je pense de façon importante) mon algorithme, mais celui-ci a préféré que je n'approfondisse pas plus dans cette voie car malgré le fait que cela paraisse être une bonne idée, nous risquions de manquer de temps pour aborder la dernière approche (il faudrait attendre le nouveau code). L'une des limites de notre cahier des charges étant de ne pas trop creuser la même approche. Dans les semaines à venir, cela vous sera toutefois présenté comme une perspective possible pour la suite des travaux de recherche.

  • Modification du site : j'ai inclus les diagrammes espaces temps de ma meilleure solution, les nouveaux résultats de temps trouvés ainsi que le code définitif (backtracking.zip qui comprend un makefile, un readme, le code ...). J'ai également expliqué le principe du backtracking avec plus de détails.

Maintenant l'approche du backtracking est terminée. Il faut à présent l'utiliser en combinaison avec les autres approches.


mai :

Semaine 5 (du 05/05/2008 au 11/05/2008):

Le 05/05 nouveau rendez-vous avec nos encadrants pour faire un point sur l'avancement des recherches. Ils nous ont demandé d'effectuer des statistiques.

Travaux réalisés :

  • Mon code me permet de sauvegarder les différentes versions de règles permettant la synchronisation de 2 à 12. J'ai obtenu 3299 versions différentes pour n = 12(d'au moins une règle) -- en commençant à initialiser une nouvelle règle à 0 -- , et ai donc mis en place un nouveau programme pour compter le nombre de fois qu'une règle prend une certaine valeur et ainsi avoir la valeur la plus souvent utilisée pour une règle. Bien sur cela ne nous donne un indice que pour une certaine partie de l'espace de recherche( en effet, les différentes versions appartiennent toutes à une même zone).

  • Une autre programme me permet d'obtenir le diagramme espace temps moyen pour les 3299 versions de 12 trouvées : il compte le nombre de fois qu'une case du diagramme espace temps pour n=12 va prendre la valeur 0,1, ... ,4 et retourne le diagramme espace temps correspondant à la moyenne.

Ces deux codes pourront être réutiliser par la suite si l'on obtient de nouvelles versions différentes pour n > 12. De plus ces résultats pourront peut-être être exploités par Pierre.

lien pour les versions de 12 : le code statistiques pour 12.

valeur pour chaque règle valeur 12 et valeur la plus fréquente pour chaque règle valeur fréquente 12.

diagramme espace temps moyen diagramme moyen 12.

  • Approche combinée : Cette approche est justifiée car elle permet à mon programme d'avoir une initialisation (règles définies pour n petit, c'est à dire < 5) différentes de celle obtenue qu'avec le backtracking. En effet, l'algorithme modifie les règles crées qui se trouvent dans la pile mais ne remonte pas suffisamment haut dans celle-ci pour changer la valeur des règles obtenues au début de l'exécution. J'avais envisagé (hypothèse lors de mes tests réalisés avec le backtracking uniquement) de modifier manuellement les règles crées avant n=5 pour parcourir une autre zone de l'espace de recherche, mais mon encadrant m'avais indiqué que c'était plutôt le rôle de la recherche tabou de se charger de cela. En fait, le programme peut le faire mais là encore le temps pour obtenir un résultat est inconnu mais très important (vu la taille de l'espace de recherche).En fournissant des règles différentes au départ, je vais donc explorer une autre partie de l'espace de recherche.

Cela explique l'importance de cette approche.

Pour réaliser cette dernière approche, j'ai récupéré les règles obtenues par les différents algorithmes développés par Oualid (Hill Climbing et Recherche Tabou) et par Hamine (Algorithme évolutionnaire).

Le problème était que nous n'avions pas la même façon de représenter les règles, j'ai donc dû créer un petit programme me permettant le passage de leur représentation à la mienne pour pouvoir par la suite utiliser leur regles en argument de mon programme du backtrack.

Code correspondant

Résultats : J'obtiens des versions de 13 différentes de celles fournies initialement, et un nouveau résultat : synchronisation de 2 à 14.


Semaine 6 (du 12/05/2008 au 18/05/2008):

Pour continuer avec la dernière approche, j'ai voulu modifier manuellement certaines règles (car le temps pour que le backtracking les modifie était trop long) et je me suis aperçue que j'avais commis une erreur dans mon programme lorsque j'ai inclu la possibilité de ne pas passer la pile en argument. Une fois mon erreur corrigée, une nouvelle exécution m'a permis d'obtenir de nouveaux résultats : synchronisation de 2 à 16.

Historique de la solution : Tout d'abord le Hill Climbing a donné une règle qui synchronise un automate de 2 à 12. Puis cette solution est utilisée par l’algorithme évolutionnaire. Une nouvelle solution permet la synchronisation de 2 à 13. Enfin, cette dernière solution récupérée pour passer en argument au backtrack, a permis d'avoir la meilleure solution connue à ce jour qui synchronise en temps minimal de 2 à 16.

Le 15/05 rendez-vous avec nos encadrants. Nous leur avons montré nos statistiques et commencé à évoquer ce que contiendra notre rapport (majoritairement ce qui se trouve dans la version finale de notre site et dans le wiki).

Nouvelle mise à jour du wiki et du site avec les nouveaux résultats obtenus grâce à la dernière approche.


Semaine 7 (du 19/05/2008 au 25/05/2008):

Construction du rapport final et préparation de la soutenance finale.



to top

You are here: Minfo > OrganisationDesTER > PagesDeSuivi > SuiviTerFusilier > FulconisAngelique

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback