Diverses techniques d'optimisation inspirées de la théorie de l'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,
E.A. 412)
61 avenue du Général
de Gaulle, 94010 Créteil
courriels :
dreo@univ-paris12.fr,
siarry@univ-paris12.fr
La biologie des organismes est la source d'inspiration de nombreuses métaheuristiques. Ainsi, les théories de l'évolution ont inspiré les algorithmes évolutionnaires, les phénomènes de suivi de piste chez les fourmis ont conduit à l'élaboration des algorithmes de colonies de fourmis, l'étude de l'organisation de groupes d'animaux a donné naissance aux méthodes d'optimisation par essaims particulaires. Il existe, en outre, d'autres algorithmes, moins connus que ceux que nous venons de citer, qui s'inspirent de la biologie : en particulier, des algorithmes inspirés du fonctionnement du système immunitaire, des algorithmes pour l'allocation dynamique de tâches, inspirés de modèles d'organisation du travail chez les fourmis, des algorithmes de classification inspirés des bancs de poissons.
Une contribution importante de la biologie dans ce domaine vient de la théorie de l'auto-organisation, qui permet d'expliquer les propriétés de plusieurs métaheuristiques issues des métaphores biologiques. Cette théorie, encore peu connue en dehors de la communauté de l'éthologie, décrit les conditions d'émergence 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, l'hétérarchie dense, les rétroactions, l'amplification des fluctuations 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 donné lieu à l'optimisation par essaims particulaires).
En nous plaçant dans le cadre de la théorie de l'auto-organisation, nous avons conçu un algorithme inspiré des colonies de fourmis : l'algorithme CIAC (« Continuous Interacting Ant Colony »), qui insiste sur l'importance des canaux de communication. Dans cet algorithme, les fourmis artificielles possèdent deux moyens d'échange des informations : via des pistes de phéromone (principe de base des algorithmes de colonies de fourmis), ou via un échange direct (très similaire à l'échange d'information dans l'optimisation par essaims particulaires). Plus généralement, nous pensons que la théorie de l'auto-organisation nous donne des clefs pour concevoir les composants de base de métaheuristiques relevant de l'intelligence en essaim.
Au cours de cet exposé, nous présenterons d'abord quelques métaheuristiques qui, comme l'optimisation par essaim particulaire, gagnent à être placées dans le cadre de la théorie de l'auto-organisation. Nous dégagerons ensuite les principaux concepts qui sont mis en avant dans cette théorie, en insistant particulièrement sur l'importance des formes de communication. Nous exposerons ensuite notre travail sur l'optimisation en variables continues à l'aide de colonies de fourmis exploitant à la fois une forme indirecte et une forme directe de communication. En conclusion, nous tenterons de dégager quelques concepts généraux susceptibles de constituer des «briques de base» pour l'élaboration de nouvelles métaheuristiques relevant de la théorie de l'auto-organisation.
Mots clefs : métaheuristique, intelligence en essaim, auto-organisation, biologie.