Chapitre 11 • Métaheuristiques en optimisation combinatoire
416
les plus pros pères : 10 mil lions de milliards d’indi vi dus, répar tis par tout dans la pla
nète. Leur poids total est du même ordre de gran deur que celui des humains ! Le suc cès
de cette espèce sou lève de nom breuses ques tions.
En par ti cu lier, les ento mo lo gistes ont ana lysé la col la bo ra tion qui s’éta blit entre
les four mis pour aller chercher de la nour ri ture à l’exté rieur de la four mi lière : il est
remar quable que les four mis suivent tou jours le même che min, et que ce che min est
le plus court pos sible. Ce com por te ment est le résul tat d’un mode de com mu ni ca tion
indi recte, via l’envi ron ne ment : la « stigmergie ». Chaque fourmi dépose, le long
de son che min, une subs tance chi mique, la « phéromone » ; tous les membres de la
colo nie per çoivent cette subs tance, et orientent pré fé ren tiel le ment leur marche vers
les régions les plus « odo rantes ».
Une colo nie est ainsi capable de choi sir, sous cer taines condi tions, le plus court
che min à exploi ter, sans que les indi vi dus aient une vision glo bale du tra jet. Ce phé
no mène est illus tré sur la Figure 11.7 par la sélec tion des branches les plus courtes.
En effet, les four mis le plus rapi de ment arri vées au nid, après avoir visité la source
de nour ri ture, sont celles qui empruntent les deux branches les plus courtes. Ainsi, la
quan tité de phéromone pré sente sur le plus court che min est légè re ment plus impor
tante que celle pré sente sur le che min le plus long. Or, une piste pré sen tant une plus
grande concen tra tion en phéromone est plus atti rante pour les four mis, elle a donc une
pro ba bi lité plus grande d’être emprun tée. La piste courte va alors être davan tage ren
for cée que la longue et elle sera à terme choi sie par la grande majo rité des four mis.
Nid
(b)
Nid
Nourriture
Nourriture
(a)
Figure 11.7 Expé rience de sélec tion des branches les plus courtes par une colo nie
de four mis : (a) au début de l’expé rience, (b) à la fin de l’expé rience.
416
les plus pros pères : 10 mil lions de milliards d’indi vi dus, répar tis par tout dans la pla
nète. Leur poids total est du même ordre de gran deur que celui des humains ! Le suc cès
de cette espèce sou lève de nom breuses ques tions.
En par ti cu lier, les ento mo lo gistes ont ana lysé la col la bo ra tion qui s’éta blit entre
les four mis pour aller chercher de la nour ri ture à l’exté rieur de la four mi lière : il est
remar quable que les four mis suivent tou jours le même che min, et que ce che min est
le plus court pos sible. Ce com por te ment est le résul tat d’un mode de com mu ni ca tion
indi recte, via l’envi ron ne ment : la « stigmergie ». Chaque fourmi dépose, le long
de son che min, une subs tance chi mique, la « phéromone » ; tous les membres de la
colo nie per çoivent cette subs tance, et orientent pré fé ren tiel le ment leur marche vers
les régions les plus « odo rantes ».
Une colo nie est ainsi capable de choi sir, sous cer taines condi tions, le plus court
che min à exploi ter, sans que les indi vi dus aient une vision glo bale du tra jet. Ce phé
no mène est illus tré sur la Figure 11.7 par la sélec tion des branches les plus courtes.
En effet, les four mis le plus rapi de ment arri vées au nid, après avoir visité la source
de nour ri ture, sont celles qui empruntent les deux branches les plus courtes. Ainsi, la
quan tité de phéromone pré sente sur le plus court che min est légè re ment plus impor
tante que celle pré sente sur le che min le plus long. Or, une piste pré sen tant une plus
grande concen tra tion en phéromone est plus atti rante pour les four mis, elle a donc une
pro ba bi lité plus grande d’être emprun tée. La piste courte va alors être davan tage ren
for cée que la longue et elle sera à terme choi sie par la grande majo rité des four mis.
Nid
(b)
Nid
Nourriture
Nourriture
(a)
Figure 11.7 Expé rience de sélec tion des branches les plus courtes par une colo nie
de four mis : (a) au début de l’expé rience, (b) à la fin de l’expé rience.