150
First Last Go Back Go To Find Les algorithmes évolutionnaires : I – les bases Marc Schoenauer Equipe TAO – INRIA Futurs – France http://www.lri.fr/marc/ Avril 2005

Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

  • Upload
    buihanh

  • View
    223

  • Download
    1

Embed Size (px)

Citation preview

Page 1: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Les algorithmes évolutionnaires :I – les bases

Marc SchoenauerEquipe TAO – INRIA Futurs – Francehttp://www.lri.fr/ ∼marc/

Avril 2005

Page 2: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

F très chahutéeL. Taïeb, CMAP & Thomson

Espace de recherche: Interféromètres Positionner des antennes

But : Maximiser la tolérance en conservant la précision.

Cas de 3 antennes,F = Marge d’erreur (position 2ème antenne)

Page 3: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Ω mixte : discrets× réelsSchutz & Bäck, ICD, Dortmund.Martin, Rivory & Schoenauer,

Optique des Solides Paris VI & CMAP.

Espace de recherche: Filtres optiques(matériau,épaisseur)1 . . . (matériau, épaisseur)N

But : Répondre au gabarit fixé.

Page 4: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Ω = Circuits analogiquesKoza et al., Stanford.

Espace de recherche: Circuits analogiquesRéseau de transistors, diodes, résistances

But : Fonctionalités fixées e.g. extraction de racine cubique

Page 5: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

F non calculableHerdy & al., Berlin, PPSN96

Espace de recherche: Mélanges de café

But : Retrouver un arôme F = note de l’expert

Page 6: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 7: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Optimisation

Le problème

Trouverx∗ / F(x∗) = SupF(y), y ∈ Ω

E espace mesuré,Ω ⊂ E,F : Ω 7→ IRF est laFonction objectif.

Maximum global :

x∗ t.q. (∀x ∈ Ω) F(x∗) ≥ F(x)

Maximum local :

x∗ t.q. (∃ε > 0)(∀x ∈ B(x∗, ε) ∩ Ω)F(x∗) ≥ F(x)

Maximastrictssi inégalités strictes pourx 6= x∗

Page 8: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Attention :

Variables continues (E = IRn): B(x, ε) 6= xVariables discrètes : on peut avoirB(x, ε) = x

Exemple: E = 0, 1n, distance de Hamming δH((bi), (b′

i)) =∑

bi=b′i1

Optimisation sous contraintes:Soientgi : Ω 7→ IR, etF = x ∈ Ω; (gi(x) ≤ 0)i=1,...,m et (gi(x) = 0)i=m+1,...,q

gi : contraintesinégalitépouri ∈ [1, m], égalitépouri ∈ [m + 1, q].F : espacefaisable.

TrouverX∗ ∈ F t.q.F(x∗) = SupF(y), y ∈ F

Page 9: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Algorithmes d’optimisation

• Algorithmes de gradient

• Hill-Climbing

• Méthodes énumératives

• Méthodes stochastiques (méta-heuristiques)

Critères de comparaison

• Type d’espace de recherche

• Régularité de la fonction objectif (contraintes)

• Recherche locale – recherche globale

Page 10: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Méthodes de gradient

Xi+1 = Xi + dX ×∇F(Xi)

Contexte :

• Espace continu :Ω ⊆ IRN

• FonctionF dérivable dérivation numérique

Conditions nécessaires :

• Fonction régulière, F convexe .. optimum unique

• ou Connaissance a priori X0 bien choisi

Méthode locale, non applicables sur un espace discret ou mixte

Page 11: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Hill-Climbing

Xi+1 = " Meilleur Voisin " deXi

Contexte :

• Tout espaceΩ "naturel"

• Toute fonctionF

Conditions nécessaires :

• X0 doit être bien choisi

Méthode locale, coûteuse, détermine le plus proche optimum local.

Page 12: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Méthodes de type énumératifParcourir l’espace suivant un ordre déterministe

Contexte :

• Espace fini :Ω ≡ [1..N ] Attention: opt.discret 6= arrondi(opt.continu)

• Toute fonctionF , mais . . .

• Ordre de parcours

– fixé

– dépend du problème Branch-and-Bound, A*, contraintes, . . .

Conditions nécessaires :

• Taille de l’espace limitée

• Discrétisation bien choisie Méthode des intervalles

Méthode globale, coûteuse, non fiable pour des problèmes continus.

Page 13: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Méthodes stochastiques

SélectionnerXi dans l’espaceΩ

D’après une distribution de probabilité

• Monte-Carlo Xi tiré avec une loi uniforme

• Recuit Simulé Kirkpatrick, Gelatt and Vecchi, 1983

• Recherche Taboue F. Glover – 1977 & 1989

• Algorithmes évolutionnaires ... depuis 1965

Méthodes globales, mais TRÈS coûteuses.

Page 14: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 15: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Algorithmes Evolutionnaires : les racines

• Algorithmes Génétiques J. Holland, 75, D.E. Goldberg 89

AI and biology – US, east coast

• Strategies d’Évolution I. Rechenberg 65, 73, H.P. Schwefel 65, 81

Engineers – Germany

• Programmation Evolutionnaire L.J. Fogel, 66, D.B. Fogel, 91, 95

Automata and time series – US, west cost

• Programmation Génétique J. Koza, 92 – a late root!

GAs on parse-trees

Aujourd’hui : pragmatisme oecuménique ?

“Evolutionary Computation”

Page 16: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Paradigme Darwinien

• Sélection naturelle avantage aux espèces adaptées à leur environnement

• Variabilité parents→ enfants par petites déviations apparament non dirigées.

• “Objectif” capacité de survivre et de se reproduire

• Adaptation résultante apparition d’espèces (e.g. bacteries resistantes).

Mais

• Source d’inspiration

• Aide à l’explication

•Pas justification

Page 17: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Algorithmes Evolutionnaires : La Métaphore

Modèle : L’évolution darwinienne des populations biologiques.Les individus les plus adaptés survivent et se reproduisent

Vocabulaire :

Individu ElémentX deΩPerformanceValeur deF(X)

Population Ensemble deP éléments deΩGénération Passage de la populationΠi àΠi+1

Processus:1) Sous la pression du milieu,2) Les individus se croisent, mutent et se reproduisent.3) Au bout d’un nombre certain de générations, les individus les plusperformants apparaissent dans la population.

≡ lesoptima deF ...

Page 18: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Parallèle biologie/algorithmiqueDifférences

Environnement changeant Généralement fixemécanismes spécifiques ?Performance inconnue C’est le point de departfinalité des plumes du paon ?Le sélection élimine les nulsTentation eugénique

Lamarckisme possibleAdaptation/sélectionboîte noire Etudes théoriques ?

Page 19: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Parallèle biologie/algorithmiquePoints communs

Diversité génétique essentielleMaladies fatales Convergence prématuréeMulti-racial utile Solutions multiples utiles

Lenteur du processusNéanderthal: -150 000 à -35 000' 6000 générations Vous verrez!Cro-Magnon: -30 000 à nous' 1200 générations

On est peut-être pas à l’optimum,mais on a des solutions assez bonnes :-)

Page 20: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Algorithmes d’évolution : Le Squelette

Evaluation

Initialisation

Stop ? Sélection

Evaluation

Génération

Croisement,

Remplacement

Meilleur individu

Opérateurs stochastiques: Dépendent de la représentation

"Darwinisme" (stochastique ou déterministe)

Coût calcul

Critère d’arrêt, statistiques, ...

Parents

Mutation, ...Enfants

Géniteurs

Page 21: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 22: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

La feuille de papier qui tombeP. Bentley

Le problème

• Trouver la forme d’un morceau de papier

• qui met le plus de temps possible à tomber

Difficultés

• Pas de simulation

• Pas d’a priori sur la forme de la solutionQuoique . . .

Page 23: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Un algorithme sans ordinateur

Matériel nécessaire

• Une ramette de feuilles A4

• Des ciseaux

• Un bac à sable format A4

• Une dizaine de petites cailloux numérotés

• Un chronomètre

• Une fléchette

• . . . de la patience

Page 24: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Initialisation

• Lancer les petits cailloux en l’air au dessus du bac à sable

• Reporter les positions des cailloux tombés dans le bac sur unefeuille A4

Génotype: Liste ordonnée des points

Page 25: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Morphogénèsepassage du génotype au phénotype

• Tracer le polygone rempli correspondant à la MacPaint

• Découper la forme obtenue

Phénotype: La forme de papier

Page 26: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Évaluation

Pour chaque forme

• Faire 5 fois

• Lâcher la forme de 2m de haut

• Chronométrer le temps d’atteinte du sol

• Faire la moyenne des 5 temps

Page 27: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Croisement

Un croisement possible, pour lequel les ciseaux et le scotch nesuffisent pas.

Page 28: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutations

• Viser avec la fléchette chaque point tour à tourDistance à ajuster selon votre habileté

• Tracer sur une nouvelle feuille les impactsSi la fléchette sort du cadre, enlever le point

Si votre portable sonne, ajouter un point

Page 29: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Darwinisme (remplacement déterministe)

Déchirer la moitié des formes – les plus rapides

Page 30: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

RésultatsAvec 5 formes et 10 générations

Deux des meilleures formes obtenues

Meilleure forme aléatoire : 0.8sToutes les formes après 10 générations de 10 formes :> 2s

Comportement“hélicoptère”

Page 31: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 32: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Points clé

• Espace de recherche quelconqueChoix de la représentation

• Une population, pas un individuAttention à la perte de diversité génétique

• Exploration de l’espace / Optimisation localeLe dilemme EVE

• Indépendance objectif / moteur d’optimisationBoîte noire ou connaissances du contexte ?

No Free Lunch Theorem

Page 33: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Perte de la Diversité Génétique

Si les individus d’une population se ressemblent trop,

1. Les populations suivantes deviennent de plus en plus homogènesfragilité au changement

2. évolution d’une population→ évolution d’un individu

3. Découverte du plus proche optimum local et enlisement de larecherche

Dans la pratique,la population ne se rediversifie pas.

=⇒ Convergence Prématurée

Page 34: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Le Dilemme Exploitation vsExploration

• Exploitation des bons individus.recherche locale: chercher dans le voisinage des meilleurs indi-vidus de la population.

• Exploration des zones inconnues deΩ.recherche globale: il faut pouvoir aller partout.

Excès d’exploitation=⇒ Convergence prématuréeenlisement dans un optimum local

Excès d’exploration=⇒ Pas de convergence≈marche aléatoire

Page 35: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

La représentation

• Le Darwinisme ne dépend que de laperformance

• L’initialisation et les opérateurs de variationne dépendent que dela représentation.

Trois exemples de base:

• Représentation “binaire” Ω = 0, 1N

• Représentation “réelle” Ω = [0, 1]N or IRN . . .

• Représentation par arbres GP

Le choix de la représentation estcrucial sera mis en avant dans tout le cours.

Page 36: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Phénotypes – GénotypesLewontin – 1974

• Espace phénotypique : Evaluation, sélection• Espace génotypique : Croisement, mutation

Préhistoire: Génotypes binaires universelsAujourd’hui : Importance des connaissances

dans la représentationdans les opérateurs

Page 37: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Représentations pour les petits papiers

• Paramétrique bestiale

• Compacte structurée limitée Les épaisseurs pour un bi-profil

• Compacte non structurée Les petits cailloux :-)

• Par “programme” e.g.quadrangle(. . . )+4 triangle(. . . )+3 triangle(. . . )

+ Modularité, réutilisabilité

– Morphogénèse complexe, causalité diffuse

Page 38: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 39: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Évaluation de la population courante

DE TRES LOIN l’étape la plus coûteuse

• Ne pas recalculerF(X) inutilement

• utiliser une estimation deF voire la construire à la volée

• . . . mais pas trop longtemps Optimum approché6= optimum réel

Page 40: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Critères d’arrêt

Pas si simple !

• Quand on a trouvé l’optimum ...:-)

• Quand on n’espère pas trouver mieux Perte de diversité

• Quand le ratio gain espérésurcoût de calcul requis

est trop élevé Rationalité limitée

• Quand on a épuisé ses resssources Nombre fixé d’évaluations

Règle heuristique: après un nombre donné d’évaluations sans amélio-ration.

Page 41: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Evaluation des résultats

Point de vue informatique

Ne jamais tirer de conclusions d’un seulessai !Utiliser des mesures statistiques

Moyennes et ecarts-types, médianes, . . .

Point de vue de l’application

Contexte deconceptionTrouver au moins une fois une très bonne solution

Contexte deproductionTrouver en moyenne une solution assez bonne

Page 42: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 43: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection

Objet : Choisir ceux qui se reproduisent

• Darwinisme: Biais en faveur des plus adaptés

• Biais trop important: Perte de diversité

• Biais trop petit : pas de convergence

Différentes modalités

• Déterministe, comparaisons de fitness ES historique

• Proportionelle roulette, GAs historiques

• Stochastique, basée sur des comparaisons de fitnessGAs historiques, EP historique

Opérateur d’exploitation

Page 44: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Remplacement

Objet : Choisir ceux qui survivent

• L’autre étape Darwinienne

• Peut être déterministe ou stochastique

• Choix parmi les enfants seulement,ou conflit de générations

Opérateur d’exploitation

Page 45: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Moteur d’évolution

Sélection et remplacement

• sont deux étapes de “sélection”

• Sélection : un individu peut être sélectionné plusieurs fois

• Remplacement : sélectionne au plus 1 fois chaque individu

Darwinisme artificiel = sélection+ remplacement≡ Moteur d’évolution

Page 46: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Elitisme

Garantir la survie du meilleur ?

•Théorie: Pas si clair Il faut accepter de perdre pour gagner

cf théorie des(µ, λ)− ES

•Application: psychologiquement trop dur!conserver le meilleur en mémoire

Elitisme fort : quelques meilleurs survivent de toute façon

Elitisme faible:Si Max(F(Πt+1)) < Max(F(Πt))

Remplacer le pire deΠt+1par le meilleur deΠt

Heuristique d’exploitation

Page 47: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection Déterministe

Historiquement : Les moteurs d’évolution(µ +, λ)-ES

• Sélection uniforme (≡ pas de sélection)

• µ parents donnentλ enfants

• Remplacement :(µ, λ)-ES : prochainsµ parents = meilleurs parmi lesλ enfantsPour: meilleurs résultats de convergenceContre: on peut perdre les meilleurs

(µ + λ)-ES : prochainsµ parents =meilleurs parmi lesµ parents+ lesλ enfants

Pour: robustesse pratiqueContre: on peut converger vers un opt. local

Paramètres: µ, λ

Page 48: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection Stochastique(I) La roulette

Objet : Tirer P parents parmiΠt = X1, . . . , XPOn tireP fois un individu avec replacement

Proba[select.Xi] ∝ F(Xi)

Roulette : Largeur de la casei : F(Xi)∑j F(Xj)

Exemple, pourP = 4 etF(Xi) = 50, 25, 15, 10

Tirage d’un parent : Lancer la boule;si elle tombe dans la casei, sélectionnerXi

Page 49: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Algorithme génétique d’Epinal

Historiquement: Le “Simple GA”

• SélectionnnerP individus par tirage de rouletteavec replacement

• GénérerP enfants à l’aide desopérateurs de variation

• Remplacer les parents par les enfants remplacement générationel

Paramètres: pas de paramètres voir plus loin

Page 50: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Tirage à la roulette (2)

Pour : favorise les meilleursmais les mauvais ont des chances

Contre : coût élevévariance élevée

perte de diversité possible

Pression sélectiveps: proba. de sélection du meilleur / proba. moyenne= nb de copies du meilleur sur P tirages

ps = P × F(Xmax)∑j F(Xj)

• Trop forte: le meilleur prend le dessus rapidement

• Trop faible: pas de sélection (∼marche aléatoire)

Page 51: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Tirage à la roulette (3):Mise à l’échelle

OptimiserF ≡ Optimiserα F + β

53(F − 10) 0.2F + 20

Heuristique de Mise à l’échelle fitness scaling

- Ajusterα etβ pour une pression sélective donnée (F fixé)tronquer les valeurs négatives

- Tirage à la roulette surF ′ = αF + β.Exemples et problème du super-individu

Page 52: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Tirage à la roulette (4)Variantes principales

• Reste stochastiqueSélection déterministeE( F(Xi)∑j F(Xj)

)

Puis roulette sur le reste décimal diminue la variance

P sélections simultanées

• Ranking = roulette sur le rang

Largeur de la casei :(

iP×(P−1)/2

meilleur : caseP

en général,α=1 (ranking linéaire)

lisse la sélection

Les valeurs exactes sont sans importance

• Troncation :Sélection à la roulette parmi lesµ meilleurs

augmente la pression sélective

Page 53: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection Stochastique(II) Le tournoi

• Tournoi (déterministe) ps ≈ T

– Tournoi de tailleT ∈ IN

– Choix uniforme deT individus avec ou sans replacement?

Rendre le meilleur

• Tournoi stochastique (binaire) ps ≈ 2t

– Tauxt ∈ [0.5, 1]

– Choix uniforme de2 individusRendre le meilleur avec probabilitét

• Pour : Robustesse par rapport aux erreurs surFFacile à paramétrerT or t

• Contre : forte variance

Page 54: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection : illustration

• 10 parents de fitness toutes différentes

• étagée linéairement, exponentiellement ou logarithmiquement

• Sélection de 100000 géniteurs Variance

• Plusieurs valeurs de pression sélective . . . Mise à l’échelle, rang

• de taille (ou de probabilité) pour les tournois

Page 55: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection : illustration (2)Fitness linéaire – Mise à l’echelle (linéaire)

Page 56: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection : illustration (3)Fitness exp. et log. – Mise à l’echelle (linéaire)

Page 57: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection : illustration (4)Présence d’un super-individu

Page 58: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection : illustration (5)Rang et tournois

Page 59: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection : illustration (5)Variance

Page 60: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Moteur AG standard

Historiquement :

• SélectionnnerP individus par sélection stochastiqueavec remplacement

• GénérerP enfants à l’aide desopérateurs de variation

• Remplacer les parents par les enfantsremplacement générationel

Paramètres: La sélection – et ses paramètres

• Proportionelle (roulette):P pression sélective et mise à l’échelle

• Tournoi :T ou t

Page 61: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Moteur “Steady State GA”

Historiquement (SSGA)

• Sélectionnner1 individu par tournoi

• Générer1 enfants à l’aide desopérateurs de variation

• Remplacer 1 parent par l’enfant par “anti-tournoi”

Paramètres: Tailles des tournois sélection et remplacement

Note: Autres stratégies de remplacement – le pire, le plus vieux, . . .

Page 62: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sélection Stochastique(III) Le tournoi EP

Utilisé comme remplacementChaque individu est sélectionné au plus une fois . . .

• Taille du tournoiT ≥ 2

• Pour chaque individuI

– Choix uniforme deT − 1 individualsavec ou sans remplacement?

– Score(I) = # I “battus”

• Choisir (déterministiquement) les meilleurs scores

Page 63: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Le moteur EP

Historiquement : L’algorithme EP (Evolutionary Programming)

• Sélection uniforme (≡ pas de sélection)

• Chaque parent donne naissance àun enfant par mutation seulement

• Remplacement:Sélection deP individus parmi lesP parents +P enfants partournoi EP

Paramètres: Taille du tournoiT

Note: Ressemble à un moteur(P + P )− ES

Page 64: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 65: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Initialisation de la population

Choix deΠ0 = X1, . . . XP

• Par tirage uniforme dansΩ Ω = 0, 1N , Xji = 0 ou 1 équiprobables

Ω = [0, 1]N , Xji = random()

• . . . mais attention au critère d’uniformité

• En tenant compte des connaissances a prioriAjoût de bonnes solutions manuelles

Mais pas de biais vaut mieux qu’un mauvais biais

• Comme résultat d’une évolution précédente.Utilisation de plusieurs "milieux"F1,F2, ..

La diversité génétique est essentielle !

Opérateur d’exploration

Page 66: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Reproduction

• parents sélectionnés−→ enfants . . .

• par application d’opérateurs de variationGénéralement stochastiques

• Choix parmi les opérateurs

– Séquentiel : Les opérateurs sont appliqués successivementavec une certaineprobabilité

– Proportionel : sélection à la roulette d’un opérateurSelon despriorités

– ou toute combinaison

Page 67: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Opérateurs de variation

Suivant l’arité on définit

• opérateur unaire→ mutation

• opérateur binaire→ crossover Peut modifier l’un des deux, ou les deux

• opérateur N-aire→ orgie

Page 68: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Le croisementopérateur:Ω× Ω → Ω (ouΩ2)

•Analogue: reproduction sexuée.

• Intuition :les enfants héritent des qualités de leurs deux parents...

•Débat: le croisement estL’opérateur majeur des AGsUn opérateur mineur (inutile) pour ES et EP

•Recommandation: essayez !l’intérêt dépend du problèmenotion de fragments de solution

Page 69: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Opérateurs de variation : Le croisement

Exemples classiques

X

Y

Échange degènes Croisement de paramètres réels

Exemple orgiaque: Cinq parents

La foule subjuguée boira ses paroles enflamméesCe plat exquis enchanta leurs papilles expertes

L’aube aux doigts de roses se leva sur un journouveauLe cadavre sanguinolent encombrait la police nationale

Les coureurs assoiffés se jetèrent surle vin pourtant mauvais

pour un enfant surréaliste

Page 70: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Croisement: discussion

Propriétés:

•Opérateur d’exploitation

• Recombinaison des “bonnes” parties

• Effets desctructeurs

Choix du partenaire:Aveugle en général, mais on peut introduire des préférences “sexuelles”Un exemple:

• Des parents sur des pics différenst d’une fonction multi-modaledonneront sans doute des enfants peu performants

• Croisement “restreint” : croiserX avecY ssid( ~X, ~Y ) < seuil

• Prise en compte des contraintes: your brain and my beauty

Page 71: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

La mutationopérateur:Ω → Ω

•Analogue: reproduction asexuée.

• Intuition : les enfants du croisement sont limités parΠt

le seul contrepoids: la mutation

•Grandes lignes:L’enfant doit être en généralprochedu parent

opérateur d’exploitation

L’enfant doit pouvoir êtren’importe oùopérateur d’exploration – ergodicité

•Quelle force?De nombreuses mutations heureuses mutation plus faible

sinon mutations plus forte

• Débat: Un opérateur homéopathique des AGsL’opérateur majeur pour ES et EP

Page 72: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Opérateurs de variation : La mutation

Exemples classiques

• Mutation d’ungène

• Ajout de bruit Gaussien aux paramètres réels

Un exemple sans queue ni tête

La terre est comme un orangebleue

La terre est bleue comme une orange

Page 73: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Le débat croisement – mutation

Le croisement:

• permet de grandes modifications

• les modifications dépendent de la population

• plutôt opérateur d’exploitation

• effets décroissants avec l’évolution

La mutation :

• nécessaire

• nécessité de pouvoir faire de grands pas

• plutôt opérateur d’exploration

• effets destructeurs augmentent avec l’évolution

Page 74: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Le débat croisement – mutation (2)

Efficacité empirique du croisement

• Hypothèse constructive:Assemblage debriques de base, i.e. pseudo-linéarité de la fonctionfitness par rapport à des parties des individus

• Hypothèse opportuniste:Le croisement n’est qu’unemacro-mutation

Headless-chicken crossover

Besoin de mutation

• Ergodicité Résultats théoriques

• Relaxé en cas detrès grandespopulation GP originel

Page 75: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Représentation “binaire”J. Holland

Ω = 0, 1n

• RéglesSi . . . Alorsen logique des prédicats Systèmes de classeurs

• Nombreux problèmes combinatoires SAT, sac-à-dos, . . .

• Nombres entiers . . . et même réels

X ∈ [a, b] → iX = 2nX−ab−a

∈ [0, 2n − 1]

Pros : SimplicitéAnalogie avec leschromosomes(Croisements)quelques arguments théoriques

Cons: No Free Lunch Theoremd’autres arguments théoriques !

Page 76: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Le croisement “binaire”Ω× Ω → Ω× Ω

Ω = 0, 1N : Echange de bits entre les parents.

• Croisement à 1 point J. Holland

(b1, . . . , bN )(c1, . . . , cN )

pc−→

(b1, . . . , bl, cl+1, . . . , cN )(c1, . . . , cl, bl+1, . . . , bN )

• Croisement à 2 points DeJong

(b1, . . . , bN )(c1, . . . , cN )

pc−→

(b1, .., bl, cl+1, .., cm, bm+1, .., bN )(c1, .., cl, bl+1, .., bm, cm+1, .., cN )

• Croisement uniforme SyswerdaEchanger les bits avec probabilité 0.5indépendamment pour chaque position

Croisement destructeur:Attention à l’influence de la représentation

Page 77: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Les mutations binaires0, 1N → 0, 1N

Opérateurs unaires :-)

La mutation “bit-flip” Holland, Goldberg

• Pour chaque individu

• et pour chaque positionl,

(b1, b2, . . . , bN)pm−→ (b1, b2, . . . , bl, bl+1, . . . , bN)

• Pour que la mutation soit effective pm > 1N×P

• Typiquement :1N

Page 78: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutations binaires (2)

La mutation “déterministe”Toujours inverser le même nombre de bits par individu

• Avec probabilitépm par individu

• Choisir aléatoirementkm positions

• Inverser les bits correspondants

Laquelle choisir ?

• Mutation “bit-flip” = mutation standard

• Mutation déterministe parfois plus efficace

Quelle probabilité pm ?

• De nombreuses mutations heureuses augmenterpm

• sinon diminuerpm

Page 79: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Représentation “réelleRechenberg & Schwefel, Michalewicz, Radcliffe, Fogel, . . .

Ω ⊂ IRn

• Tout problème paramétrique i.e. numérique

• . . . et même bien d’autres ! Comparer avec les méthodes déterministes

Pros : “Naturel”quelques arguments théoriques

Cons: No Free Lunch Theorem :-)cache la forêt

Page 80: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Croisement réelΩ = IRN or

∏[ai, bi]

Croisement arithmetique, barycentrique, intermediaire, . . .Eshelman-Schaffer (BLX-α), Michalewicz, Radcliffe . . .

Idée de base: combinaison linéaire des parents

• Globalement( ~X, ~Y ) → α ~X + (1− α)~Y

avecα = U([0, 1])

• Coordonnée par coordonnée

( ~X, ~Y ) → (~αiXi + (1− αi)Yi)

avecαi = U([0, 1]) VA indépendantes.

• Application contractante (perte de diversité)Extension :αi = U([−0.5, 1.5]). Attention aux bornes des variables

Page 81: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Croisement réel (2)

Croisement vectoriel

Le croisement “binaire” peut être rendugénériquepour tout type de“vecteur”, échangeant les variables correspondantes

Exemple: croisement ES “discret”≡ croisement uniforme≡ échange aléatoire de variables

Croisement global ES historiques

• Pour chaque variable, on choisit un “partenaire” différentindépendamment

• Intermédiaire ou discret

Page 82: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Distributions normales (Gaussiennes)

N(0, 1): Distribution normale centrée de variance 1.

Fonction de densitéΦ(x) =

1√2π

e−12x2

avec∫ +∞

−∞Φ(t)dt = 1,

∫ +∞

−∞tΦ(t)dt = 0,∫ +∞

−∞t2Φ(t)dt = 1

La “queue” ne s’annule jamais, mais 68% des tirages sont ds[−1, 1],95% ds[−2, 2] et 99.7% ds[−3, 3].

N(µ,σ2) a pour densité1σΦ(x−µ

σ), pour moyenneµ, et pour varianceσ2.

Page 83: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Réalisation d’une distribution normale

Si X etY sont 2 VA normales indépendantes. La densité de(X, Y ) estΦ(x)Φ(y)

Coordonnées polaires: θ est uniforme sur[0, 2π]Loi der: SoitAr un anneau de largeurdr et de rayonr.

P [(X, Y ) ∈ Ar] = rdre−x2+y2

2 , densité der = re−r2

2 , distribution= 1− e−r2

2

Mais sir a pour distributionF , F (R) est uniforme P [R < a] = F (a)∀aP [F (R) < u] = P [R < F−1(u)] = u

Donc la loi der estF−1(U [0, 1]) =

√−2 log(1− U) =

√−2 log(U)

RéciproquementSi θ = U [0, 2π] etr =√−2 log(U [0, 1]),

alorsX = r cos θ etY = r sin θ sont 2 VA normalesindépendantes.

Page 84: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Distributions normales multi-dimensionelles

Cas isotrope:N(0, ~σ) vecteur de variables normales indépendantesde variancesσi

Cas général:Une variable aléatoire dsIRn de matrice de covarianceC−1 (sym-métrique définie positive) a pour fonction de densité

f(~x) =exp(−1/2~xT C−1~x)√

(2π)ndet(C)

C−1 = (cij), cii = σ2i , variances selon les axes des coordonnées

Pratiquement:La matriceC est définie parn(n − 1)/2 anglesαij, et les matrices derotation correspondantesR(αij).

N(0, C(~σ, ~α)) =n−1∏i=1

n∏j=i+1

R(αij)N(0, ~σ)

Page 85: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutations réellesIRN → IRN

Idée: ajout de bruit Gaussien Xi := Xi + N(0, σ)Tout l’art est dans le choix deσ!

• Basé sur la fitness (type EP)

– Le meilleur mute peu Exploitation

– Le pire mute beaucoup Exploration

• Basé sur l’historique Rechenberg, règle des 1/5

– Une mutation estréussiesi l’enfant est meilleur que le parent

– τ = # mutations réussies dans les dernièresT générations

–Si τ > 0.2 σ = 1.22σsinon σ = 0.83σ

• Mutations adaptatives (ES modernes) σ ajustée par l’évolution !

Page 86: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutations adaptatives

Les paramètres de mutation sont portés par l’individu, e.g.

~X = (X1, . . . , XN , σ)

Une mutation en deux temps:- Muterσ et tous les paramètres de mutation

- MuterXi en utilisant la nouvelle valeur deσLesσ sont ajustées gratuitement !

Pourquoi ?

• Des mutations successives avec unσ aberrant ne peuvent pas êtreconstament réussies

• Les individus qui survivent longtemps résultent de nombreuses mu-tations successives réussies

• Les individus qui survivent longtemps doivent donc avoir des“bons” σ

Page 87: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutations adaptatives (2)

•Déviation standard scalaireUn σ par individu ( ~X, σ)

Xi ∈ [ai, bi], σ ∈ IR+

Mutation: pouri = 1 . . . Nσ := σ exp(τN(0, 1))Xi := Xi + N(0, σ)

•Déviation standard vectorielleUn σ par variable ( ~X,~σ)

Xi ∈ [ai, bi], σi ∈ IR+

Mutation:κ = τN(0, 1)pouri = 1 . . . Nσi := σi exp(κ + τ ′N(0, 1))Xi := Xi + N(0, σi)

Page 88: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutations adaptatives (3)

•Mutations corréléesUne matrice de corrélation par individu ( ~X, [C])

Peu utilisée – mais puissante

x = (~x, ~σ, ~α), xi ∈ [ai, bi], σi ∈ IR+, αij ∈ [0, 2π]

σi −→ σiexp(τ ′N(0, 1) +τNi(0, 1))αij −→ αij + βNj(0, 1)xi −→ xi + N(0, σi)

D’après Schwefel

τ ∝ 1√2√

Nτ ′ ∝ 1√

2Nβ = 0.0873 (=5o)

Page 89: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Evidence of self-adaptivity – SA-ESDeb & Beyer 01

Experiments on dynamic landscapeSlightly elliptic function with random moves of minimum everyK generations

Fitness andσ15 for non-isotropic mutation

Page 90: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Implicitly self-adaptive “operators”Reproduction operator depend on thewhole population

• Simulated Binary Crossover (SBX) Deb & Agrawal, 95

• Differential Evolution Storn & Price, 96

• Estimation of Distribution Algorithms

– EMNAglobal Larrañaga & Lozano, 01

– IDEA Bosman & Thierens, 00

– MBOAs Ocenasek & Schwarz, 02

Seecomparative resultsin Kern & al., ICALP 03

• Learnable Evolution Model (LEM):Machine Learningguides thebirth of new individuals Michalski, 99

Page 91: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Simulated Binary Crossover

Probability for offspring appearance (1D)

Distant parents Closely spaced parents

Page 92: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Evidence of self-adaptivity – SBXDeb & Beyer 01

Monitor the variance of variablesSame dynamic elliptic function (random moves of minimum everyK generations)

Fitness andvar(x15) for SBX operator

Page 93: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Differential Evolution Storn & Price 96

(c) DE Web site

Page 94: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Evidence of self-adaptivity – DE

Fitness andvar(xi), i ∈ [1, 20] for DEusing Matlab code from DE Web site

Page 95: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Self-adaptivity – discussion

• Stability: Correlated mutation and DE require crossover

• Sensitivity to thecharacteristic basisof the fitness:Correlated mutation (and DE) perform poorly on rotated (elliptic)functions

• Speed: Adaptation can be very slow

But what covariance matrixis – should be – learned?

Page 96: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Optimal covariance matrix

• On thesphere functionfS(X) = ||X||2,Best choice isId Bäck & Schwefel, 93

Isotropy argument?

• Onelliptic functionfH(X) = 12X

THXBest choice is(1

2H)−1 change of variable→ sphere function

• From Taylor expansion, all (regular) functions arelocally elliptic :-)

f (X) = f (X0) + (X −X0)T∇f (X0)

+12(X −X0)

TH(X0)(X −X0) + o(||X −X0||2)

Page 97: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

But what does SA-ES learn?

fH = 12

∑ni=1(106)

i−1n−1x2

i

( 12H)−1 =

1 0 · · · 0...

.... . .

...

0... 0 10−6

Fitness and square-root of eigenvalues for SA-ES onfH (n = 10)

Page 98: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Back to adaptivity Hansen & Ostermeier 96-01

• The actual path contains local information on the landscape

• It is lost through the self-adaptive mutation process

−→ DerandomizedEvolution Strategies

• Consecutive steps in colinear directions→ increase step-size and vice-versa

• Add direction information to the covariance matrix

• Also, use a(µ/µ, λ)− ES better with small populationsScheel, 85

i.e. generate offspring from<X >n+1=∑µ

i=1 wiXni:λ

Xni:λ, i = 1, . . . , µ: bestµ offspring from theλ mutations of<X >n

Page 99: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Cumulative Step-size Adaptation Hansen & Ostermeier 96

A (µ/µ, λ)− ES with covariance matrixIn or diag(σ1, . . . , σn)

• Compute thecumulative pathpn using

pn+1σ = (1− cσ)p

nσ +

√cσ(2− cσ)

√µ<X >n+1 − <X >n

σn

• Update thestep-sizeby e.g.isotropic

σn+1 = σn exp

(1

(||pn+1

σ ||E(||N (0, Id)||)

− 1

)).

• Note: E[||N (0, Id)||] =√

2Γ(n+12 )/Γ(n

2) is approximated practi-

cally by√

d(1− 14d

+ 121d2)

Page 100: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Cumulative Step-size Adaptation – Rationale

• About (1− cσ) and√

cσ(2− cσ)if pn

σ ∼ N (0, Id)

and√

µ<X>n+1−<X>n

σn ∼ N (0, Id)and they are independent,then pn+1

σ ∼ N (0, Id)

• Aboutσ update rule:if there is no selection (i.e.λ = µ)

then√

µ<X>n+1−<X>n

σn =√

λ1λ

∑λi=1 Xn

i:λ−<X>n

σn ∼ N (0, Id)and σn+1 ∼ σn . . . and nothing happens

Page 101: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Covariance Matrix Adaptation Hansen & Ostermeier, 01

A (µ/µ, λ)− ES with full covariance matrixCn

• Update the(global) step-size

– pn+1σ = (1−cσ)p

nσ+√

µ√

cσ(2− cσ)(Cn)−

12<X >n+1

µ − <X >nµ

σn

– σn+1 = σn exp

(1

(||pn+1

σ ||E(||N (0, Id)||)

− 1

)).

•Rationale: idem CSA with a full covariance matrixCn

Page 102: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

CMA (2) Hansen & Ostermeier, 01

• Update theCovariance Matrix: Rank 1 update

– compute the cumulated pathpn+1c = (1 − cc)p

nc +

√µ√

cc(2− cc)<X >n+1

µ − <X >nµ

σn.

– Cn+1 = (1− ccov)Cn + ccovp

n+1c pn+1T

c

•Rationale:

– pn+1c is (roughly) the descent direction

– Cn is updated with the rank 1 matrixpn+1c pn+1T

c whose eigen-vector ispn+1

c

Page 103: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

CMA (Refinement) Müller, Hansen & Koumoutsakos, 02

• Use allµ best offspring to updateCn:

– Un+1 =

µ∑i=1

(Xi:λ− <X >nµ)(Xi:λ− <X >n

µ)T

(σn)2Rankµ

– Cn+1 = (1−ccov)Cn+ccov(αcovp

n+1c pn+1T

c +(1−αcov)Un+1)

• Increase the speed of adaptation in high dimensions

CMA parameters From extensive experiments

cc =4

d + 4, cσ =

10

d + 20, dσ = max(1,

d + 10) +

1

ccov =1

µ

2

(d +√

2)2+ (1− 1

µ) min(1,

2µ− 1

(d + 2)2 + µ)

with initial valuesp0σ = 0, p0

c = 0 andC0 = Id.

Page 104: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

CMA-ES at work

Sphere function,n = 2, initial point (0, 109).Fitness, (global) step-size, sign(x2) and sqrt(eigenvalues)

Page 105: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

What does CMA-ES learn?

fH = 12

∑ni=1(106)

i−1n−1x2

i

( 12H)−1 =

1 0 · · · 0...

.... . .

...

0... 0 10−6

Fitness and square-root of eigenvalues for CMA-ES onfH (n = 10)

Page 106: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Evidence of self-adaptivity – CMA-ES

Monitor the step-sizeSame dynamic elliptic function (random moves of minimum everyK generations)

Page 107: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Some comparative results

Based on tests on a few benchmark analytical functionsDon’t generalize

too quickly

• SBX≡ SA-ES on non-correlated functions Beyer & Deb, 01

Correlated SA-ES better than SBX on correlated fnssee alsoPCX, Deb et al., 03

• CMA > SA-ES Hansen et al., 01-03

• CMA > SBX > DE Auger, forthcoming

• CMA > EDAs (IDEA best of EDAs) Kern, Hansen et al., ICALP 03

• BFGS> CMA for quasi-elliptic functionsCMA > BFGS on multi-modal functions Hansen et al., 04

Page 108: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Further steps toward determinism Auger, 04

• Learn theHessian matrix from available sample points

Use Taylor formula and Least Square approximation:ming,H

1N

∑Nk=1( f (Xk)− f (X0)− (Xk −X0)

Tg

−12(Xk −X0)

TH(Xk −X0) )2

• The unknown variables:g = (gi)1≤i≤d andH = (Hij)1≤i≤j≤d d(d + 3)/2

• Amounts to minY ||AY − F ||22for someN × d(d + 3)/2 matrix A N = # sample points

• Linear (pseudo-inverse), but complexity isn6

Page 109: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

LS-CMA-ES (2)

• LearnH everyk generations onlySliding window ofd(d + 3)/2 most recent evaluated points

• Switchesback to CMAif approximation ofH is poorAccording to criterionQ =

1

N

N∑k=1

(f(Xk)− f(X0)− (Xk −X0)

T g − 12(Xk −X0)

T H(Xk −X0)

f(Xk)− f(X0)− (Xk −X0)T g

)2

Cannot perform worse than CMA!

• Step-size can beself-adaptive log-normal mutation

or CMA-like best choice

Page 110: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Pseudo-code for LS-CMA-ES Self-Adaptive step-size

Initialisation : x(0) ← x0; σ(0) ← σ0; C(0) ← In; p(0)c ← 0; archive← ∅; Mode← LS

while (not critère d’arrêt )dog ← g + 1

Création deλ enfants:x(n+1)j ← x(n) + σ(n)exp(τNj(0, 1))Nj(0, C(n)), j ∈ [1, λ]

Évaluation de enfants: Calculf(x(n+1)j ) pour tout1 ≤ j ≤ λ

Sélectionde meilleur enfantx(b): x(n+1) ← x(n+1)b ; σ(n+1) ← σ(n) exp(τNb(0, 1))

Stoker les enfants dans l’archive

p(n+1)c ← (1− cc)p

(n)c +

√cc(2−cc)

σ(n) (x(n+1) − x(n))

if mode LS C(n+1) ← C(n)

sinon ( mode CMA) C(n+1) ← (1− ccov)C(n) + ccovp(n+1)c (p

(n+1)c )T

if (n mod nupd =0)Calculer gx(n) , Hx(n) à partir desd2 plus récents individus archivésif Q(gx(n) , Hx(n)) < Qth Mode← LS; C(n+1) ← ( 1

2Hx(n))−1

sinon Mode← CMAend if

end while

Page 111: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

LS-CMA-ES at work

(1, λ)-LS-CMA-ES (µ/µ, λ)-LS-CMA-ES

with self-adaptivestep-size withCMA-like step-size adaptation

Fitness, (global) step-size and sqrt(eigenvalues) onfH with d = 10

Page 112: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Evidence of self-adaptivity – LS-CMA-ES

Monitor the step-sizeSame dynamic elliptic function (random moves of minimum everyK generations)

Page 113: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

LS-CMA-ES vs CMA-ES

Elliptic function - dim 50 and 70.

From left to right: min, median and max, for(1, λ)-LS-CMA-ES,(1, λ)-CMA-ES and

(µ/µ, λ)-CMA-ES.

Page 114: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

LS-CMA-ES vs CMA-ES (2)

Results on the banana function Self-adaptive step-size for LS-CMA-ES

fRos =∑d−1

i=1 100(x2i − xi+1)

2 + (xi − 1)2

(1, λ)-LS-CMA-ES (µ/µ, λ)-CMA-ES (1, λ)-CMAdim min med max min med max min med max20 0.98 6.03 – 1.4 2.3 – 1.4 3.1 –50 1.1 30 – 9.5 22 – 9.5 12 –

# fitness evaluation (unit=104) to reach10−10

( –→ not reached in105 evaluations)

Page 115: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Results on multi-modal functions

(µ/µ, λ)-LS-CMA-ES with cumulative step-size adaptationon Rastrigin function:fRast = 10d +

∑di=1(x

2i − 10 cos(2πxi))

PopSize=30 for both Popsize(CMA-ES)=150

CMA-ES

requires larger population and more evaluations

Page 116: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

LS-CMA-ES on noisy functions

Tests on noisy functions:

f b,0elli =

∑di=1(104)

i−1d−1(xi)

2 Non-noisy function

f b,1elli =

∑di=1(104)

i−1d−1(xi + 10−6Ni(0,1)

(102)i−1d−1

)2 Noise on the variables

f b,2elli =

∑di=1(104)

i−1d−1(xi + 10−4Ni(0,1)

(102)i−1d−1

)2

f b,3elli =

∑di=1(104)

i−1d−1(xi + 10−2Ni(0,1)

(102)i−1d−1

)2

f b,aelli =

∑di=1(104)

i−1d−1(xi)

2 + 10−4N(0, 1) Noise on the fitness

Page 117: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Noise – results (dim=20)

(µ/µ, λ)-LS-CMA-ES (µ/µ, λ)-CMA-ESFonction fstop mean std. dev. mean std. dev.fb,1elli 10−10 5226 124 – –

fb,2elli 10−6 4160 119 – –

fb,3elli 10−2 3157 146 ? 0.40

fb,1elli 10−6 4124 119 11743 365

fb,2elli 10−4 3585 108 11003 414

fb,3elli 10−1 2856 145 ? 0.23

fb,0elli 10−10 5173 128 12892 310

10−6 4105 117 11677 35310−4 3568 109 10968 41810−2 3026 97 9775 60110−1 2762 98 8860 641

fb,aelli 10−2 3130 115 12120 450

# fitness evaluations to reachfstop –→ all 100 trials failed;? pe→ only a fractionpe succeeded

Page 118: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

LS-CMA-ES vs CMA-ES: discussion

Comparative results Dimension up to 70

• Much better on elliptic and quasi-elliptic functions

• Similar on Rosenbrock and flat functionsApproximated Hessian never accurate w.r.t.Q

• More robust on multi-modal problems Work in progress

• Unexpected increased robustness w.r.t. noiseCoefficients of LS problem satisfy some Law of Large Number (N > 30 i.e.

d > 8)?

Drawbacks

• Computational cost Not an issue for expensive fitness functions

• Better approximation? e.g. Rosenbrock

Page 119: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Autres mutations réelles

Lorsque la mutation adaptative n’est pas utilisable, e.g. pour des es-paces de recherche mixtes

• Mutation Gaussienne, avecσ décroissant Difficile à régler

• Mutation uniforme (Michlewicz) xi = U( [xi − ε, xi + ε])

• Mutation “triangulaire” (Michalewicz)

Page 120: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Espaces d’arbres - Programmation génétiqueJ. Koza

Le rêve : Le programme qui écrit le programme

Ω = Arbres(N , T )N ensemble de noeuds (ou opérateurs)T ensemble de feuilles (ou opérandes)

Exemples :

N = if-then-else, while-do, repeat-until,..T = expressions, instructionsΩ = Programmes

N = +,×T = X,RΩ = Polynomes deX.

Page 121: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Espaces d’arbres (2)

• “Toutes” fonctions analytiques ensemble de primitives non limité

• Expressions booléennes Multiplexeur, classifieur, . . .

• Contrôleurs robots, usines, . . .

• Règles de développement Embryogénèse artificielle

Pros : Richesse en fonction des primitivesFermeture du croisement

Cons: aucun argument théorique !

Page 122: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Initialisation des arbres

• Choisir une profondeur max des arbres.

• Probabilités de sélection dansN etT .

• Besoin d’opérateurs sécurisés (ex :log(0) ?).

• La population initiale doit être suffisamment diverse.

Procédure Grow : Lancer CreeArbreGrow(ProfMax)Procédure (récursive) CreeArbreGrow(profondeur)

Si profondeur == 1 Retourner un élémentx dansTChoisir un élémentx dansN ∪ TSi x est un noeud (//x ∈ N ), soitk l’arité dex

Pouri = 1 àk,

yi = CreeArbreGrow(profondeur-1)

retournerx(y1, . . . yk).

sinon retournerx.

Page 123: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Initialisation des arbres (2)

Procédure Full: Lancer CreeArbreFull(ProfMax)Procédure (récursive) CreeArbreFull(profondeur)

Si profondeur == 1 Retourner un élémentx dansTChoisir un élémentx dansN , soitk l’arité dex

Pouri = 1 àk,

yi = CreeArbreGrow(profondeur-1)

retournerx(y1, . . . yk).

Procédure “Ramped half and half”, pour favoriser la diversité.

• SoitN = PProfMax−1

• Pour i=2 àProfMax

• CréerN/2 arbres via Grow(i) etN/2 via Full(i)

Page 124: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Croisement des arbres

Principe :Deux points sont choisis dans les deux parentsLes sous-arbres sous ces points sont échangés.

Page 125: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Croisement des arbres (2)

Idée-Force: fermeture syntaxique

Points délicats:

• Vérifier que la longueur max des arbres est respectée.

• Tout croisement est-il possible ?

Remarque:1. Opérateur historiquement privilégié de GP.2. “Le croisement suffit à produire des mutations”...3. Le croisement tend à produire un enfant long et un enfant court.

Page 126: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutation des arbres

Remarque:1. Opérateur historiquement absent de GP (#popu> 2000).

2. Plusieurs types de mutation.

Mutation traditionnelle

• Remplacement de sous-arbre Choisir un point dans le parent

Remplacer le sous arbre par un arbre aléatoire

• Remplacement de noeud Choisir un noeud/feuille dans le parent

Remplacer ce noeud/feuille par un noeud/feuille de même arité

Page 127: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutation des arbres (2)

Mutation “promotionnelle”

• Insertion de noeud Choisir un point dans le parent

Faire du fils le petit fils

• Promotion de noeud Choisir un noeud/feuille dans le parent

Remplacer le noeud pere par le noeud fils

Point délicat de la mutation GP:

• Viole le “strong causality principle” : Pas de contrôle fin

Page 128: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Mutation des arbres (3)Mutation: Terminaux numériques

Mutation “numérique”

• Muter toutes les constantes dans l’arbre. très destructeur

• Mise à niveau : tirern jeux de constantes, garder le meilleur.coupler optim. non paramétrique/paramétrique

• Optimisation de type montée, ou . . . évolutinnaire

Points délicats:

• Mutation structurelles:Possibilité de remettre en cause la structure de l’arbre

⇒ Ajustement des constantes nécessaire

• Très peu de “petites” modifications possibles

Page 129: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Espaces d’arbres – Un premier exemplecoll. B. Lamy

• Régression symbolique

• 50 points (X0,X1,P(X0,X1)), P polynôme connu•

Fitness =

i=50∑i=0

[Tree(X0, X1)− P (X0, X1)]2

Remarque: Il faut avoir de bonnes raisons pour utiliser GP pour larégression !

Page 130: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Le polynôme

P (X0, X1) = 2.5 ∗X02 + 1.2 ∗X12 − 1.8 ∗X0 + 0.6 ∗X1

Meilleur résultat: version postfixée((-1.42455)+((-2.57915)+((2.32683)+(X1+(X0+((X1+((X0*(X0+X0))+(X1*X1)))+((-0.968281)+((0.0169015)*((X1*(-15.3847))+((X1+(((X0*X1)+(X1-(X0+((-18.7284)+(X0+((X0*X1)+X1))))))+(X1+((-7.21495)*(X1+((-19.0404)+((4.32199)*(((-0.381033)*(X1*X1))+(X1+X1)))))))))-(X0*((14.7915)*((11.0556)-(X0+X0))))))))))))))

Après simplification par Maple

2.499997075∗X02+1.200819057∗X12−1.797686828∗X0+0.597758036∗X1−0.006760359

Page 131: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 132: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Algorithme Génétique CanoniqueJ. Holland – 75

• E = 0, 1N , maximisation

• Initialisation uniforme desX0i , i = 1, . . . , P

• Boucle des générations : PopulationX ti , i = 1, . . . , P

–Évaluation desF(X ti ), i = 1, . . . , P

–Sélectionpar roulette,rang,tournoi −→ X′

i, i = 1, . . . , P

–Croisement1,2,N-points, avec probabilitépc, de paires aléa-toirement choisies(X

i, X′

j) −→ X′′

i , i = 1, . . . , P

–Mutation : pour chaque bitbi de chaqueX′′

j ,bi → bi, probabilitépm −→X t+1

i , i = 1, . . . , PRemplacement générationnel

Originellement, roulette et 1-point

Page 133: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Evolutionary ProgrammingL. Fogel – 63

• Tout espace de rechercheΩ. . . oú l’on peut définir un opérateur de mutation

• Initialisation uniforme (?)

• Boucle des générations : PopulationX ti , i = 1, . . . , P

– Appliquer lamutation une fois à chaque parent−→ Yi, i = 1, . . . , P

–Évaluation desF(Y ti ), i = 1, . . . , P

–Tournoi EP (stochastique) parmi les parents + enfantsX t

i , i = 1, . . . , P ∧ Y ti , i = 1, . . . , P

Note: Originellement, automates à états finis, et remplacement déterministe

Page 134: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Stratégies d’évolutionRechenberg and Schwefel – 1965

• E = IRN or∏

[ai, bi], minimization

• Initialisation uniformeX0i , i = 1, . . . , µ

• Boucle des générations : PopulationX ti , i = 1, . . . , µ

–Évaluation desF(X ti ), i = 1, . . . , µ

– Faireλ fois• Générer un enfantX

j parcroisementDiscret ou intermediaire, Global ou “local”

Sur les variables et les “σ”

• Mutation adaptative deX′

j −→ Yj, j = 1, . . . , λ

–Sélectiondéterministe deX t+1i , i = 1, . . . , µ

Parmi lesλ Yj (µ , λ)− ESParmi lesµ X t

i et lesλ Yj (µ + λ)− ES

Note: Originellement, 1+1, pas de croisement(!), règle des 1/5

Page 135: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Genetic ProgrammingJ. Koza – 92

• Espaces d’arbres représentant des programmes Pseudo-LISP

• Initialisation non triviale “ramp half-and-half”

• Tout moteur d’évolution type GA SSGA

Note:

• Une communauté en pleine expansion

• Approche morphogénétique systématique

• Résultats fascinants

Page 136: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Les racines - résumé

GA ES EP GPReprésentation 0, 1N IRN FSA ArbresSélection Oui Non Non OuiNatalité 1 1-10 1 SSGA-likeCroisement Oui Pourquoi pas? Jamais ! OUIMutation Mineure Adaptative Oui NONRemplacementGenerationnel Déterministe Tournoi SSGA

Tendence Moderne : une boîte à outils générale

Page 137: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Recuit Simulé

Minimisation

• Individu xk ∈ E (Pas de sélection!)

• Choix dexk+1 dans un voisinage dex.

• Loi de Boltzmann:∆ = F (xk+1)− F (x)Probabilité d’accepterxk+1 : exp(−∆

T),

T “température”→ 0 qdk →∞– Toujours accepté si∆ < 0

– De moins en moins d’augmentations acceptées qdk →∞.

Choix du voisinage ?Comment faire varierT?

Page 138: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Schémas de recuit

• Metropolis:

Tk =T0

ln(k)

Convergence (Geman & Geman 1984)

• Schéma exponentiel(trés utilisé)

Tk+1 = cTk

• RS adaptatif (ASA, Ingber 1989)E = IRD. Une température par coordonnée.

Ti(k) = T0iexp(−cik1/D)

+ techniques adaptatives.

Page 139: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Recherche TaboueGlover 89-95

Espaces discrets

• Petites populations (1 historiquement).

• Sélection du(es) meilleur(s).

• Création des enfants dans un voisinage.

• Utilisation de l’histoire de la recherchepour éliminer des candidats-

enfants

• Remplacement des parents par les meilleurs enfants.

• On garde trace du (des) meilleurs individus rencontrés.

Choix du voisinage ?Gestion de l’histoire ?

Page 140: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Histoire

• Histoire récente:Liste taboue des derniers essais.Décourage les mouvements vers des attributs (variables) présents dans les derniers

points examinés.

• Histoire fréquente:Décourage les mouvements vers des attributs (variables) souvent rencontrés.

Stratégies d’intensificationAprès un nombre d’essais sans amélioration, on repart de “vieux” op-tima rencontrés.Stratégies de diversificationOn encourage les mouvements vers des attributs (variables) rarementvus.

Page 141: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Plan

• Contexte Optimisation

• L’algorithme le paradigme biologique

• Un exemple sans ordinateur

• Points-clé Diversité, exploitation vs exploration, représentation

• Les étapes

– Evaluation, arrêt

– Moteur d’évolution Darwinisme artificiel

– Initialisation, opérateurs de variationChaînes de bits, nombres réels et arbres

• Les instances historiques

• Conclusions et références

Page 142: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Autres Aspectsliste non exhaustive

• Découverte de plusieurs optima Heuristiques de partage (sharing)

• Couplage avec des méthodes locales Hybridisation

• Optimisation sous contrainte Pénalisation et méthodes spécifiques

• Optimisation multi-critères Plusieurs objectifs contradictoires

• . . .

Page 143: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Conclusions provisoires

Echecs:

• J’ai essayé en boite noire, ça ne marche pas...

• J’ai essayé sur un pb résolu, c’était ridiculement lent, comparé à ...

Contextes recommandés:

• Problèmes non résolus fonctions chahutées, contraintes chahutées

• Plusieurs optima critères implicites, multi-critères

• Problèmes (très) mal posés validation de l’utilisateur

• A coupler avec des méthodes locales avec mesure

Page 144: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Faire attention à

• La représentation du problème on ne saurait y passer trop de temps

• Les opérateurs d’évolution le croisement a-t-il un sens ?

Principe de causalité forte

préférez le sur-mesure

• Choix des paramètres Force de sélection

Taille population

probabilité des opérateurs

• Le calcul de la fonctionF S’il y a un bug, l’évolution le trouvera...

Travaillez, prenez de la peine !

Page 145: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Bibliography

LIVRES: Si vous n’en lisez qu’un :-)

• A.E. Eiben and J.E. SmithIntroduction to Evolutionary Computing, Springer Verlag,2003

• Z. Michalewicz,Genetic Algorithms+Data Structures = Evolution Programs, SpringerVerlag, 1992–1996. Toujours jeune !

LIVRES: Les ancêtres

• L.J. Fogel and A.J. Owens and M.J. Walsh,Artificial Intelligence Through SimulatedEvolution, John Wiley & Sons, 1966

• J. Holland,Adaptation in natural and artificial systems, University of Michigan Press,Ann Arbor, 1975

• H.-P. Schwefel,Numerical Optimization of Computer Models, John Wiley & Sons, 1981(Nelle édition 1995).

• D. E. Goldberg,Genetic algorithms in search, optimization and machine learning,Addison Wesley, 1989 Classique, mais dépassé

• J. Koza,Genetic Programming, I, II (& III), MIT Press, 1992, 1994 (& 1999) . . . + videos!

Page 146: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Les référence

• D. B. Fogel,Evolutionary Computation, Toward a New Philosophy of Machine Intelli-gence, IEEE Press, 1995.

• Melanie Mitchell,An Introduction to Genetic Algorithms, MIT Press, 1996.

• T. Bäck,Evolutionary Algorithms in theory and practice, New-York:Oxford UniversityPress, 1995.

• W. Banzhaf, P. Nordin, R.E. Keller, F.D. Francone,Genetic Programming — An Intro-duction On the Automatic Evolution of Computer Programs and Its Applications, MorganKaufmann, 1997.

• Th. Bäck and D.B. Fogel and Z. Michalewicz,Handbook of Evolutionary Computation,Oxford University Press, 1997.

• Michael D. Vose,The Simple Genetic Algorithm: foundations and theory, MIT Press,1999.

• D. E. Goldberg,The Design of Innovation: Lessons from and for Competent GeneticAlgorithms, Kluwer Academic Publishers, 2001.

Page 147: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Journaux

• Evolutionary Computation MIT Press

• Transactions on Evolutionary Computation IEEE

• Genetic Programming and Evolvable Hardware Journal Kluwer

• Theoretical Computer Science – TCS-C – Theory of Natural Computing Elsevier

• Natural Computing Kluwer

• Applied Soft Computing Elsevier

• BioSystems Elsevier

• Journal of Heuristics Kluwer

• Journal of Global Optimization (electronic)

Page 148: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Sur la toile

• Evonet: European Network of Excellence on Evolutionary Com-putationhttp://evonet.lri.fr/

• EC-Digest: mailing liste pour les nouvelles (sous forme de “di-gest”) du monde évolutionnaire.http://ec-digest.research.ucf.edu/

Page 149: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Conférences

Historiquement

• ICGA Int. Conf. on Genetic AlgorithmsDepuis 1987, USA

• PPSN Parallel Problems Solving from NatureDepuis 1990, Europe

Paris 2000!!!

• EP Annual Conf. on Evolutionary ProgrammingDepuis 1992, USA

• ICEC IEEE Int. Conf. on Evolutionary ComputationDepuis 1994, World-wide

• GP Genetic Programming Int. Conf.Depuis 1996, USA

Page 150: Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes Evolutionnaires : les racines • Algorithmes Génétiques J. Holland, 75, D.E

•First •Last •Go Back •Go To •Find

Aujourd’hui

• GP + ICGA =GECCO (annuelle depuis 1999)Genetic and Evolutionary Computation COnference

ConférenceACM depuis . . . 2005

• ICEC + EP + Galesia =CEC (annuelle depuis 1999)Congress on Evolutionary Computation

• EuroGP, EvoCOPetEvoNet Workshops(annuels depuis 1998)European Conf. onGenetic Programming

Evolutionary Combinatorial OptimizationApplication of Evolutionary Computation Workshops

• EA (bi-annuelle depsuis 94) Evolution Artificielle

Toulouse 94, Brest 95, Nîmes 97, Calais 99, Dijon 01, Marseille 03, Lille 05

• . . . et toujoursPPSN!