Discuter:Algorithme de colonies de fourmis

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Informatique
 Algorithme de colonies de fourmis fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
AdQ AdQ Cet article a été classé comme d'Avancement AdQ selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?)

Je ne saisis pas le lien avec l'article du lien mentionné sous "article connexe". -- Olivier

A première vue, il n'y en a pas. Demande à l'auteur (Utilisateur:Vberger) du lien, il saura peut être t'éclairer. 22 jun 2005 à 13:54 (CEST) Vlad2i поговорить / أن يتحدّث

[modifier] Article : Algorithme de colonies de fourmis

Je n'ai pas saisi l'intérêt du lien que vous avez ajouté à la fin de l'article Algorithme de colonies de fourmis, sous Articles connexes. Pouvez-vous me le préciser, ou bien est-ce une erreur? (C'est moi qui ai fait la première traduction de la page en anglais). -- Olivier

Prigogine (voir plutôt version anglaise, plus développée) est en fait l'un des pioniers des systèmes auto-organisés et des systèmes complexes, tant du coté de sciences telles que la physique ou la chimie, mais aussi en des systèmes biologiques ou sociaux. Voir par exemple en:Self-organizing system pour un lien entre les deux. Le lien est pertinent, mais il y a peut-être des liens plus pertinents. Je n'ai pas de grande expertise en le domaine.

Vberger 23 jun 2005 à 12:13 (CEST)

Je remplace ce lien par Auto-organisation, dont le lien avec l'article me semble plus clair. -- Olivier, 28 juin 2005

[modifier] Une remarque à l'occasion de la proposition AdQ

J'ai essayé de regarder l'article en détail... et bien je n'arrive pas à deviner ce que veut dire le "ll" dans les formules du 2. Est-ce une notation "évidente" pour les habitués de l'algorithmique (et dans ce cas un lien bleu permettant de la saisir pour un profane serait agréable) ou est-ce un typo ? Touriste ✉ 9 février 2007 à 22:14 (CET)

Bon je viens de trouver le pdf Eyrolles, donc ai la réponse. Simplement il me semble qu'il y a un typo dans la formule quand même : au dénominateur ça devrait être du \eta_{il}^{\beta} et non du \eta_{ij}^{\beta} si je ne m'abuse (simple normalisation en somme des probas = 1 ; en l'état ce n'est pas cohérent !) Touriste ✉ 9 février 2007 à 22:21 (CET)
Très juste, c'est corrigé. Quel oeil de lynx :-) nojhan→☸ 22 mars 2007 à 15:19 (CET)

[modifier] Remarque de Marco Dorigo

Je recopie ici un mail de Marco_Dorigo, tel qu'il me l'a envoyé suite à une demande de ma part. Ses remarques sont en anglais, car c'était plus facile pour lui.

remove the comma:

années 90 [1][2], pour -> années 90 [1][2] pour


Un modèle expliquant ce comportement est le suivant :

1 ...

8 à terme, l'ensemble des fourmis a donc « choisi » la piste la plus courte.


This description is OK in general, but is wrong when referred to the double bridge experimen, as it seems to be given the previous paragraph:

qu'une colonie de fourmis ayant le choix entre deux chemins d'inégale longueur menant à une source de nourriture avait tendance à exploiter le chemin le plus court. .

Ce système est à la limite d'un système chaotique, l'état où aucune branche n'est plus marquée qu'une autre est un point instable, les états où une branche est choisie sont des points stables.

This sentence is non-sense and should be removed. Chaos is a precise notion in system theory and cannot be used here.

Fait

De tels systèmes trouvent leur intérêt dans l'étude des systèmes complexes (à travers les systèmes massivement parallèles), et dans leur lien avec l'intelligence artificielle [5].

This sentence should also be removed as it has no meaning.

L'information échangée à -> L'information échangée a

Fait

The first two formulas in the section "Description formelle" have a strange symbol just on the right side of the big parenthesis

Fait

Remove the sentence:

Il est nécessaire de régler ? et ? en faisant un compromis entre une intensification trop grande (?=0) ou une diversification trop poussée (?=0).

It is wrong


Fait

Une fois la tournée des villes effectuée, une fourmi dépose une certaine quantité de phéromone sur chaque arête de son parcours

Becomes:

Une fois la tournée des villes effectuée, chaque fourmi $k$ dépose une quantité $\Delta\tau^k_{ij}$ de phéromone sur chaque arête de son parcours

Fait

The last equation (after the sentence "À la fin de chaque itération de l'algorithme, les pistes déposées par les fourmis s'évaporent :") is wrong.

The sum on the right side of the + sign should be removed. In fact, we are talking here of evaporation only, not of overall pheromone update.

Fait

This part is wrong:

En effet, dans les problèmes combinatoires, il est possible que la meilleure solution finisse par être trouvée, alors même qu'aucune fourmi ne l'aura évaluée directement. Ainsi, dans l'exemple du problème du voyageur de commerce, il n'est pas nécessaire qu'une fourmi parcoure effectivement le chemin le plus court : celui-ci peut être construit à partir des segments les plus renforcés des meilleures solutions.

It is impossible that an ACO algorithms finds the best solution without any ant finding it!


1988, Moyson et Manderick publient un article

This is wrong. The article was never published. It was presented in a workshop without publication. This is, by the way, the reason why the article is so difficult to find.

Fait

1991, M. Dorigo propose le Ant System dans sa thèse de doctorat (qui ne sera publiée qu'en 1992[17]).

should be:

1991, M. Dorigo propose le Ant System dans sa thèse de doctorat (qui ne sera publiée qu'en 1992[17]). Le premier article sur ant system est ecrit (cite here the technical report below). Il sera publié 5 ans plus tard dans le IEEE Transactions on System, Man, and Cybernetics [6].

Dorigo M., V. Maniezzo & A. Colorni (1991). Positive feedback as a search strategy. Tech. Rep. No. 91-016, Dip. Elettronica, Politecnico di Milano, Italy.

Fait


1995, Bilchev et Parmee proposent la première adaptation aux problèmes continus [18].

This wrong and should be removed. The algorithm of Bilchev et Parmee has nothing to do with ACO. It is based on some ant inspiration, but has no connection with ACO. It also contains terminology errors that have already confused many people.

This should be added:

1996, Dorigo, Maniezzo et Colorni publient le Ant System[6]. L'article avait eté soumis en novembre 1991.

Fait

1996, Dorigo et Gambardella publient le Ant Colony System[19].

becomes:

1997, Dorigo et Gambardella publient le Ant Colony System[19].

Fait

2001, AntOptima, the first company devoted to the application of ACO to logistic problems, is founded (www.antoptima.ch)

Fait (vers www.antoptima.com)

In the Sources section a reference to my book on ACO is missing:

Dorigo M. & T. Stützle (2004). Ant Colony Optimization. Cambridge, MA: MIT Press/Bradford Books

Fait (section "voir aussi, le livre n'ayant pas été utilisé comme source)

There are really many errors in the references.

First, many of them are double: 2 and 17, 3 and 15, 8 and 19, 7 and 20.

In ref. 6 the title of the article should be: Ant system : optimization by a colony of cooperating agents

In ref. 16 DiLoreto -> Di Loreto

Fait

Recopié par Dom 1 mars 2007 à 22:50 (CET)

Je n'ai pas trop compris le passage « This description is OK in general, but is wrong when referred to the double bridge experimen, as it seems to be given the previous paragraph: ». Aurais-tu une idée de ce qu'il veut dire par là ?
Je suis comme toi je ne comprends pas plus que toi pourquoi ça ne serait pas juste dans ce cas.Dom
Concernant le passage sur le chaos, je pensais ouvrir par la suite sur les idées en auto-organisation (genre Pirgogine, tout ça), mais ça faisait effectivement tâche en l'état. Par contre, les idées sur la stabilité du système sont correctes, mais ont sans doute plus leur place dans un article dédié.
Sur le passage « This sentence should also be removed as it has no meaning. », j'avoue ne pas comprendre non plus ce qui est reproché. En ce qui me concerne, ça me parait assez correct, à défaut d'être très clair. Mais bon, la phrase n'est pas du tout du tout essentielle et peut très bien être enlevée sans grande perte.
Pour moi la phrase a un sens, mais étant complètement incompétent dans le domaine, je me demande quel est l'intérêt pour l'étude des systèmes complexes, et le lien avec l'intelligence artificielle. Des exemples permettraient d'être moins vague et donc d'apporter une preuve.Dom
Sur le passage qui « It is wrong » : oui et non. Oui, parce qu'il serait en effet plus juste de dire que alpha et beta permettent de régler le compromis entre l'influence de la gestion des pistes et celle de la recherche locale (appelée « l'heuristique » dans les travaux de Dorigo). Non, parce que ça reviens en pratique au même... Ceci dit, autant être tout à fait rigoureux.
« It is impossible that an ACO algorithms finds the best solution without any ant finding it! » : la phrase est probablement mal comprise, car c'est vrai. Il faudrait sans doute reformuler plus clairement...
La remarque en anglais me semble clair. Par contre si j'ai bien compris algorithme est itératif et les fourmis ne sont pas identifiées, on ne peut donc pas parler d'une fourmi qui trouverait ou ne trouverait pas la solution.Dom
« This wrong and should be removed. The algorithm of Bilchev et Parmee has nothing to do with ACO. », question difficile : l'article en français ne traite pas de la seule idée qu'à M. Dorigo de ce que récouvre ACO, mais des algorithmes inspirés du comportement des colonies de fourmis. Personnellement, je pense que c'est la meilleure approche : essayer de couvrir l'ensemble de la littérature sur le sujet, qu'elle soit ou non pertinente pour tel ou tel auteur. Par ailleurs, j'ai rapidement essayé de trouver un article de M. Dorigo où il donne son avis sur la question, mais je n'en ai pas trouvé. Il semblerait qu'il omette purement et simplement de parler de ce genre de travaux, ou, quand c'est le cas, qu'il ne dise pas grand chose sur l'intérêt qu'il leur trouve... Cela pose un problème dans wikipédia où les points de vues doivent être sourcés. L'idéal serait vraiment de trouver une source écrite...
Je suis d'accord avec toi sur ce point, peut-être faudrait-il faire apparaitre les deux points de vue.Dom
Pour le reste, c'est fait, quelle chance d'avoir eu ces corrections :-) nojhan→☸ 22 mars 2007 à 15:15 (CET)
Tu as raison c'est vraiment une chance qu'il puisse comprendre le français et qu'il ait répondu. :-) Dom 22 mars 2007 à 21:45 (CET)
  1. Bon, mettons que ce soit à mettre sur le compte d'un problème de compréhension...
  2. Supprimé, ce serait trop long à détailler, on fera ça dans des articles plus généraux.
  3. Le passage vise surtout à montrer l'aspect contstruction des solutions par composants. Je tâcherais de le clarifier plus tard.
  4. OK, je le ferais quand je trouverais des sources. nojhan→☸ 24 mars 2007 à 16:51 (CET)