SYNTHESE

Métaheuristiques pour l’optimisation

et auto-organisation dans les systèmes
biologiques

Johann Dréo — Patrick Siarry

Université de Paris XII Val-de-Marne

Laboratoire d’Etude et de Recherche en Instrumentation,
Signaux et Systèmes (LERISS, EA 412)
61, avenue du Général de Gaulle, F-94010 Créteil
{dreo,siarry}@univ-paris12.fr

RÉSUMÉ. Cet article propose de mettre en relation les concepts d’auto-organisation et

de programmation à mémoire adaptative (PMA) dans le domaine des métaheuristiques
d’optimisation. L’auto-organisation est décrite dans le cadre de la biologie et la PMA est dé-
finie. Les principales catégories de métaheuristiques utilisant ces deux notions sont décrites et
leurs utilisation de l’auto-organisation et de la PMA mise en valeur.
ABSTRACT. This article proposes to link the concepts of self-organization and adaptive memory
programming (AMP) in the field of optimization metaheuristics. The self-organization is de-
scribed within the framework of biology and the AMP is defined. The main categories of the
metaheuristics using these two concepts are described and their use of the self-organization and
the AMP is highlighted.
MOTS-CLÉS :optimisation, métaheuristique, intelligence en essaim, auto-organisation, program-
mation à mémoire adaptative.
KEYWORDS: optimization, metaheuristic, swarm intelligence, self-organization, adaptive memory
programming.

RSTI - TSI. Volume 25 – n◦ 2/2006, pages 221 à 239

222 RSTI - TSI. Volume 25 – n◦ 2/2006

1. Introduction

La biologie est la source d’inspiration de nombreuses métaheuristiques. Ainsi, les

théories de l’évolution ont inspiré les algorithmes évolutionnaires (Goldberg, 1994),
les phénomènes de suivi de piste chez les fourmis ont conduit à l’élaboration des
algorithmes de colonies de fourmis (Bonabeau et al., 1999), l’étude de l’organisation
de groupes d’animaux a donné naissance aux méthodes d’optimisation par essaims
particulaires (Eberhart et al., 2001). Il existe, en outre, d’autres algorithmes, moins
connus que ceux que nous venons de citer, qui découlent de la biologie : en particulier,
des algorithmes inspirés du fonctionnement du système immunitaire (De Castro et al.,
1999), des algorithmes pour l’allocation dynamique de tâches (Cicirello et al., 2001),
s’appuyant sur des modèles d’organisation du travail chez les fourmis, des algorithmes
de classification suggérés par les essaims d’insectes (Aupetit et al., 2003).
Une contribution importante de la biologie dans ce domaine vient de la théorie
de l’auto-organisation (Camazine et al., 2000, p.8), qui permet d’analyser les pro-
priétés de plusieurs métaheuristiques issues des métaphores biologiques. Cette théorie
(notamment étudiée en dehors de la biologie (Nicolis et al., 1977)) décrit les condi-
tions d’apparition de phénomènes complexes à partir de systèmes distribués, dont les
agents font l’objet d’interactions simples, mais nombreuses. La théorie met en avant
des concepts tels que la communication, les rétroactions, l’amplification des fluctua-
tions et l’émergence. L’intelligence en essaim est ainsi née sur deux fronts : via une
approche « systèmes auto-organisés » (ayant donné lieu aux algorithmes de colonies
de fourmis) et via une approche « systèmes socio-cognitifs » (ayant conduit à l’opti-
misation par essaim particulaire).
Nous proposons de mettre la théorie de l’auto-organisation en relation avec le
concept de programmation à mémoire adaptative (Taillard, 1998), qui tente de dé-
crire les points-clefs des métaheuristiques modernes, en insistant notamment sur le
rôle de la mémoire et des mécanismes d’intensification et de diversification.
Plus généralement, nous pensons que la théorie de l’auto-organisation combinée
à la programmation à mémoire adaptative donne des clefs pour concevoir les compo-
sants de base de métaheuristiques relevant de l’intelligence en essaim.
Cet article est structuré comme suit. Nous décrivons d’abord dans la section 2
les principaux concepts mis en avant dans les théories de l’auto-organisation et de la
programmation à mémoire adaptative, et nous dégageons les relations entre ces deux
théories, du point de vue des métaheuristiques. Nous présentons ensuite dans la sec-
tion 3 quelques métaheuristiques qui gagnent à être placées dans le cadre de la théorie
de l’auto-organisation. Nous exposons en particulier dans la section 3.6 un exemple
d’algorithme inspiré par cette démarche : l’algorithme CIAC. En conclusion, nous ten-
tons de dégager quelques concepts généraux susceptibles de constituer des « briques
de base », pour l’élaboration de nouvelles métaheuristiques relevant des théories de
l’auto-organisation et de la programmation à mémoire adaptative.
 Métaheuristiques et auto-organisation 223

2. Théories de l’auto-organisation et de la programmation à mémoire

adaptative

2.1. Auto-organisation

L’auto-organisation est un phénomène décrit dans plusieurs disciplines, notam-

ment en physique (Prigogine et al., 1971; Nicolis et al., 1977) et en biologie . Etant
donné que les métaheuristiques présentées dans cet article sont inspirées de phéno-
mènes biologiques, nous avons choisi de considérer une définition dans ce cadre. Une
définition claire a été proposée (Camazine et al., 2000, p.8) :

« L’auto-organisation caractérise un processus au cours duquel un

modèle émerge au niveau global uniquement d’un grand nombre d’in-
teractions entre les composants de niveau local du système. De plus, les
règles spécifiant les interactions entre composants du système sont sui-
vies en utilisant uniquement des informations locales, sans référence au
modèle global. »

Deux termes sont à préciser pour une bonne compréhension, « modèle » et « émer-
ger ». Le mot modèle est une traduction approximative du mot anglais « pattern », qui
déborde la notion de modèle, et peut signifier aussi structure, configuration générale,
forme, schéma, type (Meinhardt, 1982). D’une manière générale, il s’applique à un
« arrangement organisé d’objets dans l’espace ou le temps ». Une propriété émergente
d’un système est quant à elle une caractéristique qui apparaît « à l’improviste » (sans
avoir été explicitement déterminée), de par les interactions entre les composants de ce
système. Nous parlerons donc d’émergence pour souligner le caractère non-déterminé
d’une propriété, sans faire référence au fait que cette propriété soit organisée en mo-
dèle ni qu’elle soit située à un niveau différent des interactions.
La question cruciale est donc de comprendre comment les composants d’un syst-
ème interagissent entre eux pour produire un modèle complexe (au sens relatif du
terme, i.e. plus complexe que les composants eux-mêmes). Un certain nombre de phé-
nomènes nécessaires ont été identifiés : ce sont les processus de rétroaction et la ges-
tion des flux d’informations.
Les rétroactions positives sont des processus dont le résultat renforce l’action,
par exemple par amplification, facilitation, auto-catalyse, etc. Les rétroactions posi-
tives sont capables d’amplifier les fluctuations du système, permettant la mise à jour
d’informations peu apparentes. De tels processus peuvent facilement entraîner une di-
vergence du système, s’ils ne sont pas maintenus sous contrôle par des rétroactions
négatives, qui jouent ainsi le rôle de stabilisateurs du système. Lorsqu’ils sont couplés,
de tels processus de rétroaction sont de puissants générateurs de modèles (Camazine
et al., 2000).
Dans le cadre de la biologie du comportement, il est intuitif que les interactions
entre les composants d’un système vont très souvent mettre en jeu des processus de
communication, de transfert d’informations entre individus. D’une manière générale,
224 RSTI - TSI. Volume 25 – n◦ 2/2006

les individus peuvent communiquer, soit par le biais de « signaux », c’est-à-dire en uti-
lisant un moyen spécifique pour porter une information, soit par le biais d’« indices »,
où l’information est portée accidentellement (Seeley, 1989). De même, l’information
peut provenir directement d’autres individus, ou bien passer par le biais de l’état d’un
travail en cours. Cette deuxième possibilité d’échange d’informations, par le biais de
modifications de l’environnement, se nomme la stigmergie (Grassé, 1959; Theraulaz
et al., 1995).
D’une manière générale, tous ces processus sont plus ou moins interconnectés,
permettant à un système constitué d’un grand nombre d’individus agissant de concert
de résoudre des problèmes trop complexes pour un individu unique.

2.2. Programmation à mémoire adaptative

Le concept de programmation à mémoire adaptative (PMA) (Taillard, 1998;

Taillard et al., 1998) est né de l’observation que les métaheuristiques récentes ten-
daient à devenir proches. Ainsi, du point de vue de la programmation à mémoire
adaptative, certaines métaheuristiques partagent maintenant une démarche commune,
présentée dans l’algorithme 1.

1) Mémorisation d’un jeu de solutions ou une structure de données rassemblant

les particularités des solutions produites par la recherche,
2) construction d’une solution provisoire sur la base des données mémorisées,
3) amélioration de la solution par un algorithme de recherche locale,
4) mémorisation de la nouvelle solution ou de la structure de données associée.

Algorithme 1. Démarche employée par un programme à mémoire adaptative

La notion de programmation à mémoire adaptative insiste sur trois concepts fon-

damentaux : la mémoire, l’intensification et la diversification. Dans la littérature des
algorithmes évolutionnaires, ces deux dernières notions sont souvent désignés par les
termes exploitation et exploration, ayant un sens similaire. Nous avons choisi ici d’uti-
liser les termes de la définition originale de la programmation à mémoire adaptative,
employés plus généralement dans la littérature de la recherche avec tabous ou du recuit
simulé.
La mémoire représente ici l’information récoltée par l’algorithme, sur laquelle il va
s’appuyer pour effectuer sa recherche. La mémoire est présente sous de nombreuses
formes possibles, de la plus simple (une population de points) à des structures plus
complexes (les pistes de phéromones des algorithmes de colonies de fourmis). De
notre point de vue, la mémoire est une modélisation des solutions, elle est un moyen
de décrire la fonction objectif. Cette modélisation s’opère par une distribution sur
l’espace de recherche, biaisée vers les meilleures solutions, qui évolue vers les optima
 Métaheuristiques et auto-organisation 225

du problème. Cette mémoire peut être définie comme globale (par rapport au problème
dans son ensemble) ou inter-individuelle (d’une solution relativement à une autre).
L’intensification consiste en l’utilisation des informations disponibles pour amé-
liorer la pertinence de celles-ci. Du point de vue des métaheuristiques, il s’agit géné-
ralement tout simplement de recherche locale. Les algorithmes de recherche locale
sont maintenant souvent employés en association avec d’autres métaheuristiques plus
complexes, donnant lieu à des algorithmes hybrides (Talbi, 2002). On rencontre ainsi
souvent l’algorithme du « simplexe » de Nelder-Mead (Nelder et al., 1965), mais des
métaheuristiques plus complexes, comme la recherche avec tabous, sont parfois em-
ployées.
La diversification est la recherche de nouvelles informations, afin d’augmenter la
connaissance du problème. Ce sont souvent des méthodes stochastiques, et il est pour
le moment difficile de dégager des idées générales, tant la diversité d’approches de
cette composante des métaheuristiques est grande.
En pratique, les trois composantes de la PMA sont liées, et il est parfois diffi-
cile de distinguer où elles se situent dans les métaheuristiques proposées. De fait, les
métaheuristiques tentent d’équilibrer la balance entre diversification et intensification,
et bien souvent les améliorations d’une métaheuristique existante consistent à faire
pencher la balance dans un sens ou dans l’autre.
Le concept de programmation à mémoire adaptative se veut une forme de généra-
lisation du mode de fonctionnement des métaheuristiques. Certaines métaheuristiques
ont un mode de fonctionnement qui semble d’emblée très proche de la PMA, c’est
le cas par exemple de la méthode GRASP (« Greedy Randomized Adaptive Search
Procedure ») (Resende, 2000) ou encore des algorithmes à estimation de distribution
(EDA) (Larranaga et al., 2002). Cependant, la PMA propose une approche généraliste,
sans entrer dans les détails de l’implémentation, qui induisent souvent des a priori sur
la façon d’aborder tel ou tel problème. C’est le cas par exemple des EDA où la phase
de diversification utilise un tirage aléatoire dans une loi donnée, il y a donc un a
priori fort sur le type de loi utilisée, qui dépend en pratique du problème abordé. La
programmation à mémoire adaptative tente d’unifier différentes métaheuristiques, et
déborde le cadre des algorithmes utilisant l’auto-organisation décrits dans cet article.

2.3. Bases communes

L’auto-organisation nous renseigne sur la structure à employer pour concevoir des

métaheuristiques flexibles et capables de s’adapter à un problème donné. En effet,
la grande qualité de tels systèmes est de construire des comportements complexes à
partir de règles simples, en se fondant sur une architecture fortement décentralisée
(on rencontre également le terme de parallèle ou distribuée), maintenant reconnue et
utilisée pour sa flexibilité et son efficacité (Rudolph, 1992; Pardalos et al., 1996).
226 RSTI - TSI. Volume 25 – n◦ 2/2006

La programmation à mémoire adaptative nous renseigne quant à elle sur les méth-
odes employées par des métaheuristiques efficaces. Les auteurs insistent d’ailleurs sur
les qualités de la PMA : parallélisme et flexibilité (Taillard et al., 1998).
Les points communs entre ces deux théories sont donc nombreux et, du point de
vue de la conception des métaheuristiques, il existe une relation simple entre elles : la
PMA décrit le « but » à atteindre, et la théorie de l’auto-organisation un « moyen » pour
atteindre ce but. Ainsi, une métaheuristique efficace devrait, selon la programmation
à mémoire adaptative, mettre en place des mécanismes de mémoire, d’intensification
et de diversification, reste la question des moyens à utiliser pour mettre en place ces
mécanismes. L’auto-organisation propose un modèle de réalisation : un algorithme
à base de population définissant des interactions simples au niveau local permettant
l’émergence d’un comportement complexe au niveau global.

3. Métaheuristiques inspirées de la biologie

Cette section présente quelques métaheuristiques inspirées de la biologie et uti-

lisant des phénomènes d’auto-organisation. Nous avons délibérément choisi de res-
treindre la liste des métaheuristiques présentées à des classes d’algorithmes parmi les
plus connues, afin d’éviter une énumération peu pertinente et forcément incomplète.
De plus, certaines classes de métaheuristiques se recoupent entre elles, la classification
proposée ici est celle la plus communément admise.
Une partie de cette présentation est tirée de notre ouvrage (Dreo et al., 2003a).

3.1. Optimisation par essaim particulaire

L’optimisation par essaim particulaire (« Particle Swarm Optimization », PSO)

(Kennedy et al., 1995; Eberhart et al., 2001) est issue d’une analogie avec les compor-
tements collectifs de déplacements d’animaux. La métaphore a de plus été largement
enrichie de notions de socio-psychologie. En effet, chez certains groupes d’animaux,
comme les bancs de poissons, on peut observer des dynamiques de déplacements re-
lativement complexes, alors que les individus eux-mêmes n’ont accès qu’à des infor-
mations limitées, comme la position et la vitesse de leurs plus proches voisins. On
peut par exemple observer qu’un banc de poissons est capable d’éviter un prédateur :
d’abord en se divisant en deux groupes, puis en reformant le banc originel, tout en
maintenant la cohésion du banc.
Ces comportements collectifs s’inscrivent tout à fait dans la théorie de l’auto-
organisation décrite précédemment. Pour résumer, chaque individu utilise l’informa-
tion locale à laquelle il peut accéder sur le déplacement de ses plus proches voi-
sins pour décider de son propre déplacement. Des règles très simples comme « rester
proche des autres individus », « aller dans la même direction », « aller à la même vi-
tesse » suffisent pour maintenir la cohésion du groupe tout entier, et pour susciter des
comportements collectifs complexes et adaptés.
 Métaheuristiques et auto-organisation 227

Les auteurs de la méthode d’optimisation par essaim particulaire se sont inspirés de

ces comportements en s’appuyant sur la théorie de la socio-psychologie du traitement
de l’information et des prises de décisions dans les groupes sociaux (Eberhart et al.,
2001). Fait exceptionnel et remarquable, cette métaheuristique a été conçue d’emblée
dans le cas continu, et c’est toujours dans ce domaine que se situent la majorité des
applications à ce jour. La méthode en elle-même met en jeu des groupes de particules
sous forme de vecteurs se déplaçant dans l’espace de recherche. Chaque particule est
caractérisée par sa position et un vecteur de changement de position (appelé vélocité
ou vecteur vitesse). À chaque itération, la particule se déplace. La socio-psychologie
suggère que des individus se déplaçant sont influencés par leur comportement passé
et par celui de leurs voisins (voisins dans le réseau social et non nécessairement dans
l’espace). On tient donc compte, dans la mise à jour de la position de chaque particule,
de la direction de son mouvement, sa vitesse, sa meilleure position et la meilleure
position de ses voisins.
Ici, les rétroactions positives sont mises en place au niveau de l’attirance des par-
ticules les unes pour les autres. Les limitations de déplacement de chaque particule
entre deux itérations forment les rétroactions négatives. La mémoire est structurée au
niveau local, entre particules voisines, à chaque itération chaque particule n’évolue
qu’en fonction de ses proches voisins, et non pas selon l’état global de la population à
l’itération précédente.
On trouvera un état de l’art complet sur l’optimisation par essaim particulaire et
les concepts qui lui sont associés dans (Eberhart et al., 2001), ainsi qu’une synthèse
en français dans (Clerc, 2002).

3.2. Algorithmes évolutionnaires

Les algorithmes évolutionnaires (AEs) sont des techniques de recherche inspirées

par l’évolution biologique des espèces, apparues à la fin des années 1950 (Fraser,
1957). Parmi plusieurs approches (Holland, 1962; Fogel et al., 1966; Rechenberg,
1965), les algorithmes génétiques (AGs) en constituent certainement l’exemple le plus
connu, à la suite de la parution en 1989 du célèbre livre de D. E. Goldberg (Goldberg,
1989) : Genetic Algorithms in Search, Optimization and Machine Learning (voir en
(Goldberg, 1994) la traduction française).
Le principe d’un algorithme évolutionnaire se décrit simplement. Un ensemble de
N points dans un espace de recherche, choisis a priori au hasard, constituent la popu-
lation initiale ; chaque individu x de la population possède une certaine performance,
qui mesure son degré d’adaptation à l’objectif visé : dans le cas de la minimisation
d’une fonction objectif f , x est d’autant plus performant que f (x) est plus petit. Un
AE consiste à faire évoluer progressivement, par générations successives, la composi-
tion de la population, en maintenant sa taille constante. Au cours des générations, l’ob-
jectif est d’améliorer globalement la performance des individus ; on s’efforce d’obtenir
228 RSTI - TSI. Volume 25 – n◦ 2/2006

un tel résultat en mimant les deux principaux mécanismes qui régissent l’évolution des
êtres vivants, selon la théorie de C. Darwin :
– la sélection, qui favorise la reproduction et la survie des individus les plus per-
formants,
– et la reproduction, qui permet le brassage, la recombinaison et les variations
des caractères héréditaires des parents, pour former des descendants aux potentialités
nouvelles.
En pratique, une représentation doit être choisie pour les individus d’une population.
Classiquement, un individu pourra être une liste d’entiers pour des problèmes com-
binatoires, un vecteur de nombres réels pour des problèmes numériques dans des
espaces continus, une chaîne de nombres binaires pour des problèmes booléens, ou
pourra même, au besoin, combiner ces représentations dans des structures complexes.
Le passage d’une génération à la suivante se déroule en quatre phases : une phase de
sélection, une phase de reproduction (ou de variation), une phase d’évaluation des per-
formances et une phase de remplacement. La phase de sélection désigne les individus
qui participent à la reproduction. Ils sont choisis, éventuellement à plusieurs reprises,
a priori d’autant plus souvent qu’ils sont performants. Les individus sélectionnés sont
ensuite disponibles pour la phase de reproduction. Celle-ci consiste à appliquer des
opérateurs de variation sur des copies des individus sélectionnés pour en engendrer de
nouveaux ; les opérateurs les plus utilisés sont le croisement (ou recombinaison), qui
produit un ou deux descendants à partir de deux parents, et la mutation, qui produit
un nouvel individu à partir d’un seul individu. La structure des opérateurs de variation
dépend étroitement de la représentation choisie pour les individus. Les performances
des nouveaux individus sont ensuite mesurées, durant la phase d’évaluation, à partir
des objectifs fixés. Enfin, la phase de remplacement consiste à choisir les membres
de la nouvelle génération : on peut, par exemple, remplacer les individus les moins
performants de la population par les meilleurs individus produits, en nombre égal.
L’algorithme est interrompu après un certain nombre de générations, selon un critère
d’arrêt à préciser.
Dans cette famille de métaheuristiques (Baeck et al., 2000a; Baeck et al., 2000b),
les rétroactions sont parfois difficiles à cerner, tant les variantes sont nombreuses.
D’une façon générale, les rétroactions positives sont implémentées sous la forme
d’opérateurs de type sélection, alors que les rétroactions négatives sont typiquement
mises en place par des opérateurs de mutation. La mémoire est située au niveau lo-
cal, l’évolution de chaque individu d’une itération à l’autre étant liée à l’évolution des
individus voisins.

3.3. Systèmes immunitaires

Le terme « système immunitaire artificiel » (« Artificial Immune System », AIS)

s’applique à une vaste gamme de systèmes différents, notamment aux métaheuris-
tiques d’optimisation inspirées du fonctionnement du système immunitaire des verté-
 Métaheuristiques et auto-organisation 229

brés. Un grand nombre de systèmes ont été conçus dans plusieurs domaines différents
tels que la robotique, la détection d’anomalies ou l’optimisation (voir (De Castro et
al., 2000) pour un aperçu de différentes applications).
Le système immunitaire est responsable de la protection de l’organisme contre les
« agressions » d’organismes extérieurs. La métaphore dont sont issus les algorithmes
AIS met l’accent sur les aspects d’apprentissage et de mémoire du système immu-
nitaire dit adaptatif (par opposition au système dit inné), notamment via la discri-
mination entre le soi et le non-soi. En effet, les cellules vivantes disposent sur leurs
membranes de molécules spécifiques dites « antigènes ». Chaque organisme possède
ainsi une identité unique, déterminée par l’ensemble des antigènes présents sur ses
cellules. Les lymphocytes (un type de globule blanc) sont des cellules du système
immunitaire qui possèdent des récepteurs capables de se lier spécifiquement à un an-
tigène unique, permettant ainsi de reconnaître une cellule étrangère à l’organisme. Un
lymphocyte ayant ainsi reconnu une cellule du non-soi va être incité à proliférer (en
produisant des clones de lui-même) et à se différencier en cellule permettant de gar-
der en mémoire l’antigène, ou en cellule permettant de combattre les agressions. Dans
le premier cas, il sera capable de réagir plus rapidement à une nouvelle exposition à
l’antigène : c’est le principe même de l’efficacité des vaccins. Dans le second cas, le
combat contre les agressions est possible grâce à la production d’anticorps. La figure 1
résume ces principales étapes. Il faut également noter que la diversité des récepteurs
dans l’ensemble de la population des lymphocytes est quant à elle produite par un
mécanisme d’hyper-mutation des cellules clonées.

Antigènes
Cellule de défense

Récepteurs Anticorps

Clonage Différenciation

Sélection Cellule mémoire

Figure 1. La sélection par clonage : des lymphocytes, présentant des récepteurs spé-
cifiques d’un antigène, se différencient en cellule mémoire ou en cellule participant à
la défense active de l’organisme par le biais d’anticorps
230 RSTI - TSI. Volume 25 – n◦ 2/2006

Les principales idées utilisées pour la conception de la métaheuristique sont les

sélections opérées sur les lymphocytes, accompagnées par les rétroactions positives
permettant la multiplication et la mémoire du système. En effet, ces caractéristiques
sont capitales pour maintenir les propriétés auto-organisées du système.
L’approche utilisée dans les algorithmes AIS est très voisine de celle des algo-
rithmes évolutionnaires (Gaspar et al., 1999), mais a également été comparée à celle
des réseaux de neurones (Dasgupta, 1997). On peut, dans le cadre de l’optimisation
difficile, considérer les AIS comme une forme d’algorithme évolutionnaire présen-
tant des opérateurs particuliers. Pour opérer la sélection, on se fonde par exemple sur
une mesure d’affinité entre le récepteur d’un lymphocyte et un antigène ; la mutation
s’opère quant à elle via un opérateur d’hyper-mutation directement issu de la méta-
phore.
Une description des fondements théoriques et de nombreuses applications des sys-
tèmes immunitaires artificiels peut être trouvée dans (De Castro et al., 1999), (De Cas-
tro et al., 2000; Dasgupta et al., 1997), et dans (Dasgupta, 1999).

3.4. Algorithmes de colonies de fourmis

Les fourmis ont la particularité d’employer pour communiquer des substances vo-
latiles appelées phéromones. Elles sont très sensibles à ces substances, qu’elles per-
çoivent grâce à des récepteurs situés dans leurs antennes. Ces substances sont nom-
breuses et varient selon les espèces. Les fourmis peuvent déposer des phéromones au
sol, grâce à une glande située dans leur abdomen, et former ainsi des pistes odorantes,
qui pourront être suivies par leurs congénères.
Les fourmis utilisent les pistes de phéromones pour marquer leur trajet, par
exemple entre le nid et une source de nourriture. Une colonie est ainsi capable de choi-
sir (sous certains conditions) le plus court chemin vers une source à exploiter (Goss
et al., 1989; Beckers et al., 1992), sans que les individus aient une vision globale du
trajet.
En effet, les fourmis le plus rapidement arrivées au nid, après avoir visité la source
de nourriture, sont celles qui empruntent le chemin le plus court. Ainsi, la quantité
de phéromone présente sur le plus court trajet est légèrement plus importante que
celle présente sur les chemins plus longs. Or, une piste présentant une plus grande
concentration en phéromone est plus attirante pour les fourmis, elle a une probabilité
plus grande d’être empruntée. La piste courte va alors être davantage renforcée que
les longues, et, à terme, sera choisie par la grande majorité des fourmis.
Le premier algorithme de colonies de fourmis (Colorni et al., 1992) a été conçu
pour optimiser le problème du voyageur de commerce. Ce problème consiste à cher-
cher le trajet le plus court reliant n villes données, chaque ville ne devant être visitée
qu’une seule fois. Le problème est plus généralement défini dans un graphe complè-
 Métaheuristiques et auto-organisation 231

tement connecté (N, A), où les villes sont les noeuds N et les trajets entre ces villes,
les arêtes A.
Dans l’algorithme du « Ant System » (AS) (Colorni et al., 1992), à chaque itération
t (1 ≤ t ≤ tmax ), chaque fourmi k (k = 1, . . . , m) parcourt le graphe et construit
un trajet complet de n = |N | étapes (on note |N | le cardinal de l’ensemble N ). Pour
chaque fourmi, le trajet entre une ville i et une ville j dépend de :
1) la liste des villes déjà visitées, qui définit les mouvements possibles à chaque
pas, quand la fourmi k est sur la ville i : Jik ,
2) l’inverse de la distance entre les villes : ηij = d1ij , appelée visibilité. Cette in-
formation statique est utilisée pour diriger le choix des fourmis vers des villes proches,
3) la quantité de phéromone déposée sur l’arête reliant les deux villes, appelée
l’intensité de la piste. Ce paramètre définit l’attractivité d’une partie du trajet global et
change à chaque passage d’une fourmi. C’est, en quelque sorte, une mémoire globale
du système, qui évolue par apprentissage.
La règle de déplacement (appelée « règle aléatoire de transition proportionnelle » par
les auteurs (Bonabeau et al., 1999)) est la suivante :


(τij (t))α ·(ηij )β

(τil (t))α ·(ηij )β
si j ∈ Jik
pkij (t) =
P
l∈J k
i [1]
 0 / Jik
si j ∈
où α et β sont deux paramètres contrôlant l’importance relative de l’intensité de la
piste, τij (t), et de la visibilité, ηij . Avec α = 0, seule la visibilité de la ville est prise
en compte ; la ville la plus proche est donc choisie à chaque pas. Au contraire, avec
β = 0, seules les pistes de phéromone jouent. Pour éviter une sélection trop rapide
d’un trajet, un compromis entre ces deux paramètres, jouant sur l’importance relative
de la diversification et de l’intensification, est nécessaire.
Après un tour complet, chaque fourmi laisse une certaine quantité de phéromone
k
∆τij (t) sur l’ensemble de son parcours, quantité qui dépend de la qualité de la solu-
tion trouvée :

(
Q
k Lk (t)
si (i, j) ∈ T k (t)
∆τij (t) = [2]
0 / T k (t)
si (i, j) ∈

où T k (t) est le trajet effectué par la fourmi k à l’itération t, Lk (t) la longueur du tour
et Q un paramètre fixé.
L’algorithme ne serait pas complet sans le processus d’évaporation des pistes de
phéromone. En effet, pour éviter d’être piégé dans des solutions sous-optimales, il est
nécessaire de permettre au système « d’oublier » les mauvaises solutions. On contre-
balance donc l’additivité des pistes par une décroissance constante des valeurs des
arêtes à chaque itération. La règle de mise à jour des pistes est donc :
232 RSTI - TSI. Volume 25 – n◦ 2/2006

τij (t + 1) = (1 − ρ) · τij (t) + ∆τij (t) [3]

k
k=1 ∆τij (t) et m est le nombre de fourmis. La quantité initiale de
où ∆τij (t) = Pm
phéromone sur chaque arête suit une distribution uniforme d’une petite quantité τ0 ≥
0.
La figure 2 présente un exemple simplifié de problème du voyageur de commerce
optimisé par un algorithme AS.

(a) (b) (c) (d)

Figure 2. Le problème du voyageur de commerce optimisé par l’algorithme AS, les

points représentent les villes et l’épaisseur des arêtes la quantité de phéromone dé-
posée. (a) exemple de trajet construit par une fourmi, (b) au début du calcul, tous
les chemins sont explorés, (c) le chemin le plus court est davantage renforcé que les
autres, (d) l’évaporation permet d’éliminer les moins bonnes solutions

Dans ces algorithmes, les rétroactions positives sont formées par l’attrait des four-
mis pour les pistes les plus concentrées. Le principe de l’évaporation concrétise les
rétroactions négatives. La mémoire est mise en place au niveau global, par les pistes
de phéromones.
Les algorithmes de colonies de fourmis sont pour l’essentiel appliqués à
des problèmes combinatoires, notamment du type du voyageur de commerce
(Gambardella et al., 1995; Dorigo et al., 1996; Dorigo et al., 1997b; Dorigo et
al., 1997a). Cependant, devant le succès rencontré par ces algorithmes, d’autres pistes
commencent à être explorées : par exemple, l’utilisation de ces algorithmes dans des
problèmes continus (Dreo et al., 2004b) et/ou dynamiques (Di Caro et al., 1998),
ou encore l’exploitation de ce type d’algorithmes dans un cadre d’intelligence en
essaim (Bonabeau et al., 1999) et avec d’autres métaheuristiques (Monmarché et
al., 1999; Monmarché et al., 2000a; Dreo et al., 2003b; Dreo et al., 2004a). Le livre
de référence sur les algorithmes de colonies de fourmis (Bonabeau et al., 1999) insiste
sur les aspects biologiques du domaine et présente un grand nombre d’algorithmes.
 Métaheuristiques et auto-organisation 233

3.5. Autre algorithme inspiré des insectes sociaux

Il existe des métaheuristiques inspirées du comportement des insectes sociaux qui

ne sont pas explicitement liées aux – plus connus – algorithmes de colonies de four-
mis. En effet, les comportements de ces espèces sont complexes et riches ; et les ca-
ractéristiques auto-organisées que présentent ces groupes d’insectes sont une source
d’inspiration intéressante.
Un bon exemple est celui d’un algorithme inspiré des modèles d’organisation du
travail chez les fourmis (Campos et al., 2000; Cicirello et al., 2001; Nouyan, 2002).
Le partage des tâches chez certaines espèces fait apparaître des individus qui accom-
plissent des tâches spécifiques, ce qui permet d’éviter les coûts (en temps et en éner-
gie par exemple) liés aux ré-attributions de tâches. Cependant, la spécialisation des
individus n’est pas rigide, ce qui pourrait être préjudiciable à la colonie, mais elle
s’adapte en fonction des nombreux stimulus internes et externes perçus par les indivi-
dus (Wilson, 1984).
Des modèles de comportement ont été proposés pour expliquer ce phénomène
(Bonabeau et al., 1996; Bonabeau et al., 1998; Theraulaz et al., 1998). Ces modèles
mettent en jeu, pour chaque type de tâche, des seuils de réponse représentant le niveau
de spécialisation de l’individu. Ces seuils sont soit fixés (Bonabeau et al., 1998), soit
mis à jour en fonction de l’accomplissement des tâches par les individus (Theraulaz
et al., 1998).
Ces modèles ont inspiré des algorithmes pour l’allocation dynamique de tâches, où
chaque machine se voit associée à un individu disposant d’un jeu de seuils de réponse
Θa , où Θa,j représente le seuil de l’agent a pour la tâche j. La tâche j envoie aux
agents un stimulus Sj représentant le temps d’attente de la tâche. L’agent a aura une
probabilité d’effectuer la tâche j de :
Sj2
P (Θa,j , Sj ) =
Sj2 + Θ2a,j
L’algorithme dispose ensuite de règles de mise à jour des seuils et de règles de dé-
cision, au cas où deux agents tenteraient d’effectuer la même tâche (voir (Cicirello
et al., 2001) pour plus de détails). Des améliorations à cet algorithme de base
(Nouyan, 2002) ont permis d’augmenter sa rapidité et son efficacité sur des problèmes
d’allocation dynamique de tâches.
Ici, les rétroactions positives sont liées à la spécialisation des individus, alors
que les rétroactions négatives sont mises en place sous la forme des changements
de tâches. La mémoire est locale, au niveau des seuils des différents individus.

3.6. Algorithme de colonie de fourmis auto-organisé

Nous avons élaboré un algorithme de colonie de fourmis, se focalisant sur les

principes de communication, mis en avant plus haut (Dreo et al., 2002). Cet algorithme
234 RSTI - TSI. Volume 25 – n◦ 2/2006

est apparenté aux algorithmes de colonies de fourmis pour les problèmes continus
(Bilchev et al., 1995; Wodrich et al., 1997; Mathur et al., 2000; Monmarché et al.,
2000b), qui manipulent une population à la manière des algorithmes évolutionnaires
(Ling et al., 2002).
Une formalisation des échanges d’informations est proposée autour de la notion
de canaux de communication. En effet, il existe plusieurs moyens de faire passer de
l’information entre deux groupes d’individus, par exemple par dépôts de pistes de phé-
romone ou par échanges directs (Holldobler et al., 1990; Dreo, 2001). On peut définir
différents canaux de communication représentant l’ensemble des caractéristiques du
transport de l’information. Du point de vue des métaheuristiques, il y a trois caractéris-
tiques principales : la portée (le nombre d’individus mis en cause dans l’échange d’in-
formation), la mémoire (la persistance de l’information dans le système) et l’intégrité
(les modifications engendrées par l’utilisation du canal de communication). De plus,
l’information passant par un canal de communication peut être n’importe quelle infor-
mation d’intérêt, comme par exemple la valeur et/ou la position d’un point de l’espace
de recherche.
L’algorithme CIAC (acronyme pour « Continuous Interacting Ant Colony ») utilise
deux canaux de communication :
1) Le canal stigmergique (du nom donné aux processus de communication indi-
rects tels que les pistes employés par les fourmis) fait appel à des spots de phéromone,
déposés sur l’espace de recherche, qui vont être plus ou moins attractifs pour les four-
mis artificielles, selon leurs concentrations et leurs distances.
2) Le canal direct est implémenté sous la forme d’échange de messages entre deux
individus. Une fourmi artificielle possède une pile de messages reçus et peut en en-
voyer à une autre fourmi.
Le manque d’efficacité de CIAC dans le domaine de l’intensification a donné lieu à
une hybridation (Dreo et al., 2003c) avec l’algorithme de recherche locale de Nelder-
Mead (Nelder et al., 1965). Cette variante de l’algorithme, appelée HCIAC (« Hybrid
Continuous Interacting Ant Colony »), utilise donc deux canaux de communication,
et exploite en outre une recherche locale et des processus décisionnels stochastiques.
Implémentés à l’aide de fonctions de type stimulus/réponse, qui permettent de définir
un seuil de choix pour une action. L’implémentation de la recherche locale est, comme
le suggèrent les théories de la PMA et de l’auto-organisation, fortement décentralisée.
Les rétroactions positives sont ici mises en place par l’attrait des fourmis pour les
spots de phéromones existants et les échange de messages, les rétroactions négatives
par l’évaporation et les choix stochastiques. La mémoire est à la fois globale (spots de
phéromones) et locale (messages entre deux fourmis, seuils de choix).
 Métaheuristiques et auto-organisation 235

4. Conclusion

Les deux théories présentées permettent de mieux comprendre le fonctionnement

des métaheuristiques existantes et d’orienter la conception de nouvelles métaheuris-
tiques. Les concepts importants à retenir sont l’utilisation par les métaheuristiques
modernes de la mémoire, de l’intensification et de la diversification, ainsi que l’aspect
distribué et flexible de ces algorithmes. Cependant il faut souligner la difficulté de
conception d’un système auto-organisé, ce qui explique que l’inspiration vienne de la
biologie, où de tels systèmes sont relativement courants.
Les difficultés principales sont les suivantes :
– concevoir une mémoire échantillonnant correctement le problème et dont il est
aisé d’extraire l’information pertinente pour orienter la recherche,
– équilibrer la balance entre des techniques d’intensification et de diversification,
– maintenir la flexibilité de l’algorithme, de façon à ce qu’il s’adapte au problème.
Les perspectives ouvertes par les points de vue des théories de la programmation à
mémoire adaptative et de l’auto-organisation permettront peut-être la conception de
nouvelles métaheuristiques. Il apparaît de plus en plus que les multiples variantes pro-
posées dans la littérature, jouant sur des points cruciaux, comme la balance diversifi-
cation/intensification, gagneraient à s’appuyer sur une analyse plus rigoureuse qu’une
simple démarche empirique par essais et erreurs.

5. Bibliographie

Aupetit S., Monmarché N., Slimane M., Guinot C., Venturini G., « Clustering and Dynamic
Data Visualization with Artificial Flying Insect », Genetic and Evolutionary Computation
Conference (GECCO), 2003.
Baeck T., Fogel D. B., Michalewicz Z., Evolutionary Computation 1 : Basic Algorithms and
Operators, Institute of Physics Publishing, 2000a.
Baeck T., Fogel D. B., Michalewicz Z., Evolutionary Computation 2 : Advanced Algorithms
and Operators, Institute of Physics Publishing, 2000b.
Beckers R., Deneubourg J. L., Goss S., « Trails and U-Turns in the Selection of a Path by the
Ant Lasius Niger », J. Theor. Biol., vol. 159, p. 397-415, 1992.
Bilchev G., Parmee I., « The Ant Colony Metaphor for Searching Continuous Design Spaces »,
Lecture Notes in Computer Science, vol. 993, p. 25-39, 1995.
Bonabeau E., Dorigo M., Theraulaz G., Swarm Intelligence, From Natural to Artificial Systems,
Oxford University Press, 1999.
Bonabeau E., Theraulaz G., Deneubourg J.-L., « Quantitative Study of the Fixed Threshold
Model for the Regulation of Division of Labour in Insect Societies », Proceedings Roy. Soc.
London B, vol. 263, 1996.
Bonabeau E., Theraulaz G., Deneubourg J.-L., « Fixed Response Thresholds and the Regulation
of Division of Labor in Insect Societies », Bulletin of Mathematical Biology, n◦ 60, p. 753-
807, 1998.
Camazine S., Deneubourg J., Franks N., Sneyd J., Theraulaz G., Bonabeau E., Self-Organization
in Biological Systems, Princeton University Press, 2000.
236 RSTI - TSI. Volume 25 – n◦ 2/2006

Campos M., Bonabeau E., Theraulaz G., Deneubourg J.-L., « Dynamic Scheduling and Divi-
sion of Labor in Social Insects », Adaptive Behavior, p. 83-96, 2000.
Cicirello V., Smith S., Wasp-like Agents for distributed Factory Coordination, Technical Report
n◦ CMU-RI-TR-01-39, Robotics Institute, Carnegie Mellon University, Pittsburgh, Decem-
ber, 2001.
Clerc M., « L’optimisation par essaim particulaire : principes, modèles et usages », Technique
et Science Informatiques, vol. 21, p. 941-964, 2002.
Colorni A., Dorigo M., Maniezzo V., « Distributed Optimization by Ant Colonies », in F. Varela,
P. Bourgine (eds), Proceedings of ECAL’91 - First European Conference on Artificial Life,
Elsevier Publishing, Paris, France, p. 134-142, 1992.
Dasgupta D., « Artificial Neural Networks Vs. Artificial Immune Systems », Sixth International
Conference on Intelligent Systems, Boston, June, 1997.
Dasgupta D., Artificial Immune Systems and their applications, Springer Verlag, 1999.
Dasgupta D., Attoh-Okine N., « Immune-based systems : A survey », Proceedings of the IEEE
International Conference on Systems, Man and Cybernetics, vol. 1, IEEE Press, Orlando,
p. 369-374, October, 1997.
De Castro L., Von Zuben F., Artificial Immune Systems : Part I : Basic Theory and Applications,
Technical Report n◦ TR-DCA 01/99, Department of Computer Engineering and Industrial
Automation, School of Electrical and Computer Engineering, State University of Campinas,
Brazil, December, 1999.
De Castro L., Von Zuben F., Artificial Immune Systems : Part II - A Survey of Applications,
Technical Report n◦ DCA-RT 02/00, Department of Computer Engineering and Industrial
Automation, School of Electrical and Computer Engineering, State University of Campinas,
Brazil, February, 2000.
Di Caro G., Dorigo M., « AntNet : Distributed stigmergic control for communications net-
works », Journal of Artificial Intelligence Research, vol. 9, p. 317-365, 1998.
Dorigo M., Gambardella L. M., « Ant Colonies for the Traveling Salesman Problem », BioSys-
tems, vol. 43, p. 73-81, 1997a.
Dorigo M., Gambardella L. M., « Ant Colony System : A Cooperative Learning Approach to
the Traveling Salesman Problem », IEEE Trans. Evol. Comp., vol. 1, p. 53-66, 1997b.
Dorigo M., Maniezzo V., Colorni A., « The Ant System : Optimization by a Colony of Coope-
rating Agents », IEEE Trans. Syst. Man Cybern, vol. B, n◦ 26, p. 29-41, 1996.
Dreo J., « Modélisation de la mobilisation chez les fourmis », Mémoire de DEA, Université
Paris7 & Université Libre de Bruxelles, 2001.
Dreo J., Pétrowski A., Siarry P., Taillard E. D., Métaheuristiques pour l’optimisation difficile,
Eyrolles, September, 2003a.
Dreo J., Siarry P., « A New Ant Colony Algorithm Using the Heterarchical Concept Ai-
med at Optimization of Multiminima Continuous Functions », in M. Dorigo, G. Di Caro,
M. Sampels (eds), Proceedings of the Third International Workshop on Ant Algorithms
(ANTS’2002), vol. 2463 of Lecture Notes in Computer Science, Springer Verlag, Brussels,
Belgium, p. 216-221, September, 2002.
Dreo J., Siarry P., « Diverses techniques d’optimisation inspirées de la théorie de l’auto-
organisation dans les systèmes biologiques », Journée optimisation par essaim particulaire
(OEP’2003), 2 October, 2003b.
 Métaheuristiques et auto-organisation 237

Dreo J., Siarry P., « Un algorithme de colonie de fourmis en variables continues hybridé avec
un algorithme de recherche locale », 5ème Congrès de la Société Française de Recherche
Opérationnelle et d’Aide à la Décision (ROADEF 2003), Avignon, France, February, 2003c.
Dreo J., Siarry P., « Algorithmes à estimation de distribution et colonies de fourmis », 11ème
journée évolutionnaire (JET11), 12 March, 2004a.
Dreo J., Siarry P., « Continuous Interacting Ant Colony Algorithm Based on Dense Heterar-
chy », Future Generation Computer Systems, 2004b. to appear.
Eberhart R., Kennedy J., Shi Y., Swarm Intelligence, Evolutionary Computation, Morgan Kauf-
mann, April, 2001.
Fogel L. J., Owens A. J., Walsh M. J., Artifical Intelligence through Simulated Evolution, Wiley,
1966.
Fraser A. S., « Simulation of genetic systems by automatic digital computers », Australian
Journal of Biological Sciences, vol. 10, p. 484-491, 1957.
Gambardella L. M., Dorigo M., « Ant-Q : A Reinforcement Learning Approach to the Tra-
velling Salesman Problem », Proceedings Twelfth International Conference on Machine
Learning, vol. ML-95, Morgan Kaufmann, Palo Alto, p. 252-260, 1995.
Gaspar A., Collard P., « From GAs to artificial immune systems : improving adaptation in time
dependent optimization », in P. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, A. Zal-
zala (eds), Proceedings of the Congress on Evolutionary Computation, vol. 3, Washington
D.C., p. 1859-1866, 1999.
Goldberg D. E., Genetic Algorithms in Search, Optimization and Machine learning, Addison-
Wesley, 1989.
Goldberg D. E., Algorithmes génétiques. Exploration, optimisation et apprentissage automa-
tique, Addison-Wesley France, 1994.
Goss S., Aron S., Deneubourg J. L., Pasteels J. M., « Self-Organized Shortcuts in the Argentine
Ant », Naturwissenchaften, vol. 76, p. 579-581, 1989.
Grassé P.-P., « La reconstruction du nid et les coordinations interindividuelles chez Bellicosi-
termes natalensis et Cubitermes sp. La théorie de la stigmergie : essai d’interprétation du
comportement des termites constructeurs », Insectes sociaux, vol. 6, p. 41-83, 1959.
Holland J. H., « Outline for logical theory of adaptive systems », J. Assoc. Comput. Mach., vol.
3, p. 297-314, 1962.
Holldobler B., Wilson E., The Ants, Springer Verlag, 1990.
Kennedy J., Eberhart R. C., « Particle swarm optimization », Proc. IEEE Int. Conf. on Neural
Networks, vol. IV, Piscataway, NJ : IEEE Service Center, p. 1942-1948, 1995.
Larranaga P., Lozano J., Estimation of Distribution Algorithms, A New Tool for Evolutionary
Computation, Genetic Algorithms and Evolutionary Computation, Kluwer Academic Pu-
blishers, 2002.
Ling C., Jie S., Ling Q., Hongjian C., « A Method for Solving Optimization Problems in Conti-
nuous Space Using Ant Colony Algorithm », in M. Dorigo, G. Di Caro, M. Sampels (eds),
Proceedings of the Third International Workshop on Ant Algorithms (ANTS’2002), vol.
2463 of Lecture Notes in Computer Science, Springer Verlag, Brussels, Belgium, p. 288-
289, September, 2002.
Mathur M., Karale S. B., Priye S., Jyaraman V. K., Kulkarni B. D., « Ant Colony Approach to
Continuous Function Optimization », Ind. Eng. Chem. Res., vol. 39, p. 3814-3822, 2000.
238 RSTI - TSI. Volume 25 – n◦ 2/2006

Meinhardt H., Models of Biological Pattern Formation, Academic Press, London, 1982.
Monmarché N., Ramat E., Dromel G., Slimane M., Venturini G., On the similarities between
AS, BSC and PBIL : toward the birth of a new meta-heuristics, E3i n◦ 215, Université de
Tours, 1999.
Monmarché N., Ramat N., Desbarat L., Venturini G., « Probabilistic search with genetic algo-
rithms and ant colonies », in A. Wu (ed.), Proceedings of the 2000 Genetic and Evolutionary
Computation Conference Workshop, p. 209-211, 2000a.
Monmarché N., Venturini G., Slimane M., « On how Pachycondyla apicalis ants suggest a new
search algorithm », Future Generation Computer Systems, vol. 16, p. 937-946, 2000b.
Nelder J. A., Mead R., « A simplex method for function minimization », Computer Journal,
vol. 7, p. 308-313, 1965.
Nicolis G., Prigogine I., Self-organization in Non-equilibrium Systems, New York, 1977.
Nouyan S., « Agent-Based Approach to Dynamic task Allocation », in M. Dorigo, G. Di Caro,
M. Sampels (eds), Proceedings of the Third International Workshop on Ant Algorithms
(ANTS’2002), vol. 2463 of Lecture Notes in Computer Science, Springer Verlag, Brussels,
Belgium, p. 28-39, September, 2002.
Pardalos P., Xue G., Panagiotopoulos P. D., « Parallel Algorithms for Global Optimization
Problems », Solving Combinatorial Optimization Problems in Parallel, p. 232-247, 1996.
Prigogine I., Glandsdorf P., Thermodynamic Theory and Structure, Stability and Fluctuations,
Wiley and Sons, New York, 1971.
Rechenberg I., Cybernetic Solution Path of an Experimental Problem, Royal Aircraft Establish-
ment Library Translation, 1965.
Resende M., Greedy randomized adaptive search procedures (GRASP), Technical Report n◦
TR 98.41.1, AT&T Labs-Research, 2000.
Rudolph G., Parallel approaches to stochastic global optimization, IOS Press, Amsterdam,
p. 256-267, 1992.
Seeley T. D., « The honey bee colony as a superorganism », American Scientist, vol. 77, p. 546-
553, 1989.
Taillard E. D., Programmation à mémoire adaptative et algorithmes pseudo-gloutons : nouvelles
perspectives pour les méta-heuristiques, Thèse d’habilitation à diriger les recherches, Uni-
versité de Versailles Saint Quentin en Yvelines, France, 1998.
Taillard E. D., Gambardella L. M., Gendreau M., Potvin J.-Y., « Adaptive Memory Program-
ming : A Unified View of Meta-Heuristics », European Journal of Operational Research,
vol. 135, n◦ 1, p. 1-16, 1998.
Talbi E.-G., « A Taxonomy of Hybrid Metaheuristics », Journal of Heuristics, vol. 8, n◦ 5,
p. 541-564, August, 2002.
Theraulaz G., Bonabeau E., « Coordination in distributed building », Science, vol. 269, p. 686-
688, 1995.
Theraulaz G., Bonabeau E., Deneubourg J.-L., « Response Threshold Reinforcement and Di-
vision of Labour in Insect Societies », Proceedings of the Royal Society of London B, vol.
265, p. 327-335, 1998.
Wilson E., « The relation between Caste Ratios and Division of Labour in the Ant Genus
Pheidole (Hymenoptera : Formicidae) », Behav. Ecol. Sociobiol., vol. 16, p. 89-98, 1984.
 Métaheuristiques et auto-organisation 239

Wodrich M., Bilchev G., « Cooperative distributed search : the ant’s way », Control and Cyber-
netics, 1997.

– Livre sur les métaheuristiques :

http://www.eyrolles.com/php.informatique/Ouvrages/9782212113686.php3
– Livre sur la théorie de l’auto-organisation :
http://www.scottcamazine.com/personal/selforganization/SOMain.html
– Thèse sur la programmation à mémoire adaptative :
http://ina.eivd.ch/collaborateurs/etd/articles.dir/IDSIA-52-98.ps
– Méthode des essaims particulaires :
http://www.particleswarm.net/
– Groupe de travail sur les algorithmes évolutionnaires :
http://www.afia.polytechnique.fr/node.php?lang=fr&node=285
– Méthode des colonies de fourmis :
http://iridia.ulb.ac.be/~mdorigo/ACO/
– Système immunitaires artificiels :
http://www.cs.kent.ac.uk/people/staff/jt6/aisbook/ais-researchers.htm

Article reçu le 6 novembre 2003

Version révisée le 28 janvier 2005

Johann Dréo est docteur en informatique et biologiste de formation, ses recherches portent sur
les métaheuristiques inspirées du comportement des insectes sociaux.

Patrick Siarry est ingénieur de l’Ecole Supérieure d’Electricité et professeur à l’université

Paris XII Val-de-Marne, où il dirige des travaux de recherche sur les métaheuristiques pour
l’optimisation difficile.