OEP'03 – Jeudi 2 octobre 2003 1Johann Dréo (Paris 12, LERISS)

Johann Dréo & Patrick SiarryUniversité Paris 12 (LERISS)

Séminaire Optimisation par Essaim Particulaire

Paris

Diverses techniques d'optimisation inspirées de l'auto-organisation dans les systèmes biologiques

OEP'03 – Jeudi 2 octobre 2003 2Johann Dréo (Paris 12, LERISS)

PlanMétaheuristiques :OEP,Algorithmes évolutionnaires,Systèmes immunitaires,Colonies de fourmis

Théories :Auto-organisation,Programmation à mémoire adaptative,Bases communes.

HCIAC (Colonie de fourmis + communication) :Hétérarchie dense & communication,Bases, Hybridation,Résultats.

Conclusion.

OEP'03 – Jeudi 2 octobre 2003 3Johann Dréo (Paris 12, LERISS)

OEP

� Optimisation

� Classification

� ...

OEP'03 – Jeudi 2 octobre 2003 4Johann Dréo (Paris 12, LERISS)

Algorithmes évolutionnairesMutation

ReproductionSélection

OEP'03 – Jeudi 2 octobre 2003 5Johann Dréo (Paris 12, LERISS)

Systèmes immunitaires

Clonage

Différenciation

Sélection

Artificial Immune Systems and their applicationsDasgupta, Springer Verlag, 1999

OEP'03 – Jeudi 2 octobre 2003 6Johann Dréo (Paris 12, LERISS)

Colonies de fourmisNourriture

Nid

50%50%

?

Optimisation discrète

OEP'03 – Jeudi 2 octobre 2003 7Johann Dréo (Paris 12, LERISS)

Fourmis et organisation du travail

Allocation dynamique de tâches

OEP'03 – Jeudi 2 octobre 2003 8Johann Dréo (Paris 12, LERISS)

Auto-organisation

L'auto-organisation est un processus dans lequel un modèle de niveau global émerge uniquement d'un grand nombre d'interactions entre les composants de bas niveau

du système.

De plus, les règles spécifiant les interactions entre composants du système sont suivies en utilisant

uniquement des informations locales, sans référence au modèle global.

Self-Organization in Biological SystemsCamazine, Deneubourg, Franks, Sneyd, Theraulaz and Bonabeau

Princeton University Press, 2000

OEP'03 – Jeudi 2 octobre 2003 9Johann Dréo (Paris 12, LERISS)

Auto-organisation

Composants simples Système complexeÉmergence

(interactions)

Rétroactions :

PositivesAmplification

NégativesStabilisation

Flux d'informations :

Signaux

Indices

OEP'03 – Jeudi 2 octobre 2003 10Johann Dréo (Paris 12, LERISS)

Programmation à mémoire adaptative

Information(Représentation infos)

Intensification(Exploitation infos)

Diversification(Recherche infos)

===

Mémoire

Recherche locale

Recherche globale

Adaptive Memory Programming: A Unified View of Meta-HeuristicsTaillard, Gambardella, Gendreau, Potvin

European Journal of Operational Research, 1998

OEP'03 – Jeudi 2 octobre 2003 11Johann Dréo (Paris 12, LERISS)

Bases en commun

Programmation à mémoire adaptative:

IntensificationDiversification

BUT

Auto-organisation :

RétroactionsDiversification

MOYEN

Fourmis :� Renforcement / saturation

� PistesOEP :

� Attirance / inertie

� Valeur fOBJ

Émergence

Fourmis :

� Regroupement

� Aléatoire / phéromonesOEP :

� Regroupement

� Coopération

OEP'03 – Jeudi 2 octobre 2003 12Johann Dréo (Paris 12, LERISS)

Dense Heterarchy and mass communication as the basis of organization in ant colonies.

Wilson & Hölldobler, Trends in Ecology and Evolution, 1988

HiérarchieHétérarchie

Hétérarchie dense

OEP'03 – Jeudi 2 octobre 2003 13Johann Dréo (Paris 12, LERISS)

Communication

Canaux

Informations

Propriétés

NourritureDéfense...

PistesTrophallaxies...

IndirecteMémoireModifiée...

OEP'03 – Jeudi 2 octobre 2003 14Johann Dréo (Paris 12, LERISS)

L'algorithme CIAC

�

Pistes de phéromone

�

Recrutement direct

« Continuous Interacting Ant Colony »2

cana

uxL'algorithme CIAC

Continuous Interacting Ant Colony Algorithm Based on Dense Heterarchy

Dréo & SiarryFuture Generation Computer Systems, à paraître

OEP'03 – Jeudi 2 octobre 2003 15Johann Dréo (Paris 12, LERISS)

CIAC : baseSpots de phéromone

Dépôt Renforcement

Zone de perception

Centre de gravité pondéré

OEP'03 – Jeudi 2 octobre 2003 16Johann Dréo (Paris 12, LERISS)

CIAC : baseCommunication directe interindividuelle

MessagesInformations :

Amélioration fonction objectifPosition région d'intérêt

Echange direct d'infosSortie des minimums locaux

OEP

OEP'03 – Jeudi 2 octobre 2003 17Johann Dréo (Paris 12, LERISS)

HCIAC

+ Recherche locale

= Algorithme HCIAC

CIAC

(Simplex de Nelder-Mead)

OEP'03 – Jeudi 2 octobre 2003 18Johann Dréo (Paris 12, LERISS)

Terminale Algorithme...

Algorithme...Périodique

HCIAC : hybridations simples

Fourmi à l'optimum

OEP'03 – Jeudi 2 octobre 2003 19Johann Dréo (Paris 12, LERISS)

HCIAC : hybridation décentralisée

Algorithme...

Déclenchement simplex ?

Seuil

Motivation

OEP'03 – Jeudi 2 octobre 2003 20Johann Dréo (Paris 12, LERISS)

Paramétrage

HCIAC : paramètres

Paramètres fourmis : distribution normale

Paramètres algorithme :

Indice diversification / intensification

Méta-paramétrage par algo bi-objectif :1) vitesse2) précision

OEP'03 – Jeudi 2 octobre 2003 21Johann Dréo (Paris 12, LERISS)

HCIAC : résultats

Auto-adaptation à la fonction : diversification

intensification

OEP'03 – Jeudi 2 octobre 2003 22Johann Dréo (Paris 12, LERISS)

HCIAC : résultatsQualités :

� Précision

� Efficacité

� Parallélisme

Défauts :

� Nb. évaluations

CACO APIFunction % ok evals err % ok evals errR2 100 6842 0.00 [10000] 0.00SM 100 22050 [10000] 0.00Gr5 [10000] 0.18

CIAC HCIACFunction % ok evals err % ok evals errR2 100 11797 3e-3 100 18747 1e-8SM 100 50000 9e-10 100 18616 5e-8Gr5 63 48402 0.01 75 10870 1e-4

OEP'03 – Jeudi 2 octobre 2003 23Johann Dréo (Paris 12, LERISS)

Optimisation continue dynamiqueT

T+1

Formalisation :

� Classes de problèmes de base

� Benchmark

MémoireIntensification / « tracking »Diversification permanente

HCIAC

OEP'03 – Jeudi 2 octobre 2003 24Johann Dréo (Paris 12, LERISS)

Structure d'une métaheuristique

Mémoire

DiversificationIntensification

Intensification

IntensificationHCIAC

Diversification Intensification

Mémoire

OEP

OEP'03 – Jeudi 2 octobre 2003 25Johann Dréo (Paris 12, LERISS)

Points importants

Programmation à mémoire adaptative :

IntensificationDiversification

BUT

Auto-organisation :

RétroactionsFlux d’infos

MOYEN

Émergence

�Population

�Parallélisme�Flexibilité

OEP'03 – Jeudi 2 octobre 2003 26Johann Dréo (Paris 12, LERISS)

http://nojhan.free.fr

Métaheuristiques

Auto-organisation (colonies de fourmis)

Programmation à mémoire adaptative

Dréo, Pétrowski,Siarry, Taillard