Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes...

•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

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)

Ω 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é.

Ω = 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

F non calculableHerdy & al., Berlin, PPSN96

Espace de recherche: Mélanges de café

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

• 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

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∗

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

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

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

Hill-Climbing

Xi+1 = " Meilleur Voisin " deXi

Contexte :

• Tout espaceΩ "naturel"

• Toute fonctionF

• X0 doit être bien choisi

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

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, . . .

• 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.

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.

• Les étapes

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”

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).

• Source d’inspiration

• Aide à l’explication

•Pas justification

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 ...

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 ?

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 :-)

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

• Les étapes

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 . . .

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

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

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

É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

Croisement

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

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

Darwinisme (remplacement déterministe)

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

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”

• Les étapes

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

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

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

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.

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

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

• Les étapes

É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

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.

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

• Les étapes

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

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

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

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

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: µ, λ

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

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

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)

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

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

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

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

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

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

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

Sélection : illustration (5)Rang et tournois

Sélection : illustration (5)Variance

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

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, . . .

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

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

• Les étapes

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

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

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

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

Opérateurs de variation : Le croisement

Exemples classiques

É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

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

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

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

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

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

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 !

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

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

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

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

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

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

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.

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

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.

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, ~σ)

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 !

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” σ

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)

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)

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

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

Simulated Binary Crossover

Probability for offspring appearance (1D)

Distant parents Closely spaced parents

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

Differential Evolution Storn & Price 96

(c) DE Web site

Evidence of self-adaptivity – DE

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

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?

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)

But what does SA-ES learn?

fH = 12

∑ni=1(106)

i−1n−1x2

( 12H)−1 =

1 0 · · · 0...

.... . .

0... 0 10−6

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

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

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

√cσ(2− cσ)

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

• Update thestep-sizeby e.g.isotropic

σn+1 = σn exp

(||pn+1

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

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

2Γ(n+12 )/Γ(n

2) is approximated practi-

cally by√

d(1− 14d

+ 121d2)

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 =√

∑λi=1 Xn

i:λ−<X>n

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

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+1 = σn exp

(||pn+1

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

•Rationale: idem CSA with a full covariance matrixCn

CMA (2) Hansen & Ostermeier, 01

• Update theCovariance Matrix: Rank 1 update

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

√µ√

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

µ − <X >nµ

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

n+1c pn+1T

•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

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

• Use allµ best offspring to updateCn:

– Un+1 =

µ∑i=1

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

(σ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

d + 4, cσ =

d + 20, dσ = max(1,

d + 10) +

ccov =1

(d +√

2)2+ (1− 1

µ) min(1,

2µ− 1

(d + 2)2 + µ)

with initial valuesp0σ = 0, p0

c = 0 andC0 = Id.

CMA-ES at work

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

What does CMA-ES learn?

fH = 12

∑ni=1(106)

i−1n−1x2

( 12H)−1 =

1 0 · · · 0...

.... . .

0... 0 10−6

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

Evidence of self-adaptivity – CMA-ES

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

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

Further steps toward determinism Auger, 04

• Learn theHessian matrix from available sample points

Use Taylor formula and Least Square approximation:ming,H

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

−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

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 =

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

Cannot perform worse than CMA!

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

or CMA-like best choice

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

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

Evidence of self-adaptivity – LS-CMA-ES

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

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.

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)

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

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

f b,3elli =

∑di=1(104)

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

(102)i−1d−1

f b,aelli =

∑di=1(104)

i−1d−1(xi)

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

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

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

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)

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.

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 !

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.

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)

Croisement des arbres

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

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.

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é

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

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

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 !

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

• Les étapes

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

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

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

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

• Une communauté en pleine expansion

• Approche morphogénétique systématique

• Résultats fascinants

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

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 “température”→ 0 qdk →∞– Toujours accepté si∆ < 0

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

Choix du voisinage ?Comment faire varierT?

Schémas de recuit

• Metropolis:

Tk =T0

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.

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 ?

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.

• Les étapes

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

• . . .

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

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 !

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!

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.

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)

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/

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

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!

Les algorithmes évolutionnaires : I – les bases - lri.frmarc/Ponts/Intro2005.pdf · Algorithmes...

Documents

algorithmes genetiques

Application des méthodes évolutionnaires Inspiration biologique et algorithmes EquipeBOUQUET Gaëtan CHAZELLE Johann ESCOUTE Guillaume BOUILLOT Lucas

Algorithmes au quotidien

Algorithmes, nature, humains : la rencontre Claire Mathieu · 2018. 11. 14. · Quels algorithmes pour comprendre la nature ? Algorithmes, nature, humains : la rencontre Claire Mathieu

Projet FRACTALES Approches Fractales pour l’Analyse et la ... · 6.13. Simulations de Monte Carlo parallèles compétitives 17 6.14. Surcompression d’images par algorithmes évolutionnaires

INF1101 Algorithmes et structures de données1 Cours 6 Algorithmes de tri

Les algorithmes d'arithmetique

Complexité des algorithmes

Algorithmes de filtrage

Plateformes algorithmes travail

LES ALGORITHMES D’APPROXIMATION

Résolution de problèmes de classification par algorithmes évolutionnaires grâce au logiciel DEAP

Algorithmes Evolutionnaires - LAAS · 2014-11-24 · Fred Glover 1986. ... 12 . Début . Initialisation ... et pour >100 sommets, l’écart type GRASP 4.69% et MA 2.15%. La différence

Algorithmes Amiel-Tison

Quoi de neuf dans les algorithmes génétiquesleriche/presentation_UTC04.pdf · 2004. 12. 7. · Algorithmes évolutionnaires (AE) pour l’optimisation ou ou Pas de condition particulière

Approche syndromique & algorithmes

TD1 Algorithmes

Les algorithmes de manipulation du contraste Les algorithmes de rehaussement par pseudo-couleurs Les algorithmes de création de composées-couleurs Les

Les matériaux dans le sport, (r)évolutionnaires

Méthodes et Algorithmes Graphiques