Upload
buihanh
View
223
Download
1
Embed Size (px)
Citation preview
•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
•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)
•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é.
•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
•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
•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
•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∗
•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
•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
•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
•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.
•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.
•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.
•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
•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”
•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
•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 ...
•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 ?
•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 :-)
•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
•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
•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 . . .
•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
•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
•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
•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
•First •Last •Go Back •Go To •Find
Croisement
Un croisement possible, pour lequel les ciseaux et le scotch nesuffisent pas.
•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
•First •Last •Go Back •Go To •Find
Darwinisme (remplacement déterministe)
Déchirer la moitié des formes – les plus rapides
•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”
•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
•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
•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
•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
•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.
•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
•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
•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
•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
•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.
•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
•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
•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
•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
•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
•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
•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: µ, λ
•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
•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
•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)
•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
•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
•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
•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
•First •Last •Go Back •Go To •Find
Sélection : illustration (2)Fitness linéaire – Mise à l’echelle (linéaire)
•First •Last •Go Back •Go To •Find
Sélection : illustration (3)Fitness exp. et log. – Mise à l’echelle (linéaire)
•First •Last •Go Back •Go To •Find
Sélection : illustration (4)Présence d’un super-individu
•First •Last •Go Back •Go To •Find
Sélection : illustration (5)Rang et tournois
•First •Last •Go Back •Go To •Find
Sélection : illustration (5)Variance
•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
•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, . . .
•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
•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
•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
•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
•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
•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
•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
•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
•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
•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
•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
•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
•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
•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 !
•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
•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
•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
•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
•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
•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
•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.
•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.
•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, ~σ)
•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 !
•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” σ
•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)
•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)
•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
•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
•First •Last •Go Back •Go To •Find
Simulated Binary Crossover
Probability for offspring appearance (1D)
Distant parents Closely spaced parents
•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
•First •Last •Go Back •Go To •Find
Differential Evolution Storn & Price 96
(c) DE Web site
•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
•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?
•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)
•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)
•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
•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
dσ
(||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)
•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
•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
dσ
(||pn+1
σ ||E(||N (0, Id)||)
− 1
)).
•Rationale: idem CSA with a full covariance matrixCn
•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
•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,
3µ
d + 10) +
1
cσ
ccov =1
µ
2
(d +√
2)2+ (1− 1
µ) min(1,
2µ− 1
(d + 2)2 + µ)
with initial valuesp0σ = 0, p0
c = 0 andC0 = Id.
•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)
•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)
•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)
•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
•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
•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
•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
•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
•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)
•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.
•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)
•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
•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
•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
•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
•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)
•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.
•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 !
•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.
•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)
•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.
•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.
•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é
•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
•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
•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 !
•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
•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
•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
•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
•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
•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
•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
•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?
•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.
•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 ?
•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.
•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
•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
• . . .
•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
•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 !
•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!
•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.
•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)
•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/
•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
•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!