Discussion :

[tomjr]

Bonjour, je viens d'implémenter la méthode de recherche tabou pour améliorer mes solutions dans un problème de graphe.

J'ai cependant deux problèmes :

-la condition d'arrêt
-la taille de la liste tabou

Pour la condition d'arrêt, j'ai mis en place un compteur, et lorsque le nombre d'itérations souhaité par l'utilisateur est atteint, la méthode s'arrête et renvoi le meilleur résultat. C'est un peu brutal non?

Pour la taille de la liste tabou, je laisse le choix à l'utilisateur, mais je me demande si il n'y a pas une taille "idéale" pour la liste tabou, en fonction du nombre de sommets dans le graphe?

[pseudocode]

On peut savoir quel est le problème de départ qui t'a conduit à utiliser une recherche taboo ?

[tomjr]

Je vais essayer de faire simple!

Les sommets correspondent à des centres de télécommunication, les arcs sont le coût des liaisons entre les centre.

Je dois créer plusieurs (nombre fixé par les données) "groupes" de centres. Un groupe, est un arbre regroupant un nombre de sommets comprit entre un cardinal min et un cardinal max (min et max sont aussi fixés par les données).

En plus des centres, il y a aussi un sommet "satellite". Ce sommet satellite doit être relié à un centre par groupe.

Au final, la solution est un arbre. Je dois créer les groupes de la meilleure façon possible afin de minimiser le coût de l'arbre.

[pseudocode]

Ok.

Et ton algorithme de recherche, il parcourt quel espace de solutions ? Le choix des centres ? Le choix des sommets dans les groupes, pour une configuration de centres connus ?

[tomjr]

Par exemple, dans un graphe de 10 sommets, les contraintes peuvent m'imposer de faire 3 groupes contenant entre 2 et 4 sommets chacun.

Pour ma recherche tabou, je pars d'une solution du type:

Ilot1 : 1-2-3-4
Ilot2 : 5-6-7-8
Ilot3 : 9-10

Une solution voisine sera par exemple :

Ilot1 : 1-2-3
Ilot2 : 5-6-7-8
Ilot3 : 9-10-4

Pour les graphes de 10 sommets, par trop de problème vu le peu de solutions voisines à explorer.

Mais j'ai aussi des graphes 100 sommets, et là, je pense que le choix de la taille de la liste tabou et le choix de la condition d'arrêt influent beaucoup sur la solution finale.

[pseudocode]

Donc tu explores l'espace des "mutations possibles" de ta configuration de départ ?

[tomjr]

C'est ça! Je calcule le résultat pour chacune des "mutations possibles" et je choisi la meilleure des mutations pour l'itération suivante.

L'inverse de la meilleure mutation est ajoutée à la liste tabou (pour éviter de rester bloqué dans un minimum local).

[pseudocode]

C'est ça! Je calcule le résultat pour chacune des "mutations possibles" et je choisi la meilleure des mutations pour l'itération suivante.

L'inverse de la meilleure mutation est ajoutée à la liste tabou (pour éviter de rester bloqué dans un minimum local).

Je voudrais pas dire, mais ca ressemble plus à un algorithme génétique qu'a une recherche taboo.

[tomjr]

Ho! Et c'est une bonne nouvelle ça?

Faudrait quand même que mon algorithme ressemble un peu à la méthode tabou!

[pseudocode]

Ho! Et c'est une bonne nouvelle ça?

Faudrait quand même que mon algorithme ressemble un peu à la méthode tabou!

Voilà l'algorithme:

Je confirme. Ton algo ressemble beaucoup a un algo génétique. On prend des individus (solutions initiales), on crée de nouveaux individus par mutations, on garde les N meilleurs individus, et on recommence.

Tu peux garder ton concept de "liste taboo" si tu veux explicitement exclure certains individus.

[tomjr]

J'ai trouvé une condition d'arrêt plus satisfaisante et ma méthode me donne de bons résultats.

Merci pour l'aide!

[kaisser]

Bonjour Tomjr,
j'espère que ca ce passe bien pour toi ta méthode de recherche de Tabou ,
En fait j'ai un exposé sur ça le lundi prochain , et j'aimerais bien avoir un code , question de pousser la présentation de l'algorithme.
Donc si ce possible , est ce que tu pourrais me passé ton code ?

Merci beaucoup