Optimisation combinatoire par découverte des dépendances dans les

algorithmes évolutifs

Robin Gras

Institut Suisse de Bioinformatique

• Pourquoi un problème est-il difficile?

• Pas uniquement sa taille:

Si toute les variables sont indépendantes => solution en temps linéaire sur le nombre de variables.

Ex: oneMax nombre de 1 dans un vecteur binaire.

• Lié à l’épistasie / corrélation entre variables

La valeur que doit prendre une variable dans une bonne solution dépend de la valeur d’autres variables.

Ex: déceptive function

0

0.2

0.4

0.6

0.8

1

1.2

0 1 2 3 4

score

• Comment mesurer la complexité d’un problème?

• Sa taille n: nombre de variables impliquées

• Degré de liberté i des variables: nombre d’instanciations possible des variables

Ex: (i-1)Max complexité en O(n*i)

• Degré de dépendance k des variables: de combien de variables au maximum dépend chacune des variables

Ex: Complexité en O((n/2)*i2)

De façon générale complexité en O((n/k)*ik)

• Chevauchement des dépendances entre variables

Ex: de façon générale NP-complet mais existence de solutions heuristiques exactes polynomiales.

})1,0,1{,max(1

20

122

in

i

ii xxx

})1,0,1{,max( 11

iinii xxx

• Un problème général paramétrable: le NK-landscape

• Problème de taille N avec des dépendances de tailles K avec chevauchement aléatoire.

Ex: avec N = 4, K = 2, i = 2

.18 .04 .73 .91

.42 .77 .35 .11

.68 .31 .04 .89

.91 .17 .25 .70

.93 .12 .73 .53

.59 .64 .82 .77

.19 .94 .38 .21

.43 .49 .62 .55

x1 x2 x3 x4

Contexte de locus

x1 x2 x3 x4

Locus

000001010011100101110111

voisinage

Calcul du fitness pour la chaîne 0110

1 001 .42

2 011 .17

3 110 .38

4 100 .53

Fitness = (.42 + .17 + .38 + .53)/4 = .375

• Autre vision de la complexité (1):

• Nombre de maximum globaux par rapport à la taille de l’espace de recherche.

• Nombre de maximum locaux par rapport aux maximum globaux.

• Bassin d’attraction des maximum globaux/locaux.

• Étude faite par reverse hillclimbing.

Ne peut se faire que pour des problèmes de petites tailles.

Extrapolation à des problèmes plus grands.

• Dépendent des opérateurs utilisé pour parcourir l’espace.

• Autre vision de la complexité (2):

• Problème d’optimisation sur les graphe (ex: coloriage) = problème avec dépendances.

• Graphes “small world” représente les problèmes les plus difficiles.

• Un réseau de dépendances presque régulier semble donc rendre un problème difficile.

• La distribution de la probabilité d’explorer plus de nœuds (branch and bound) qu’un nombre de nœuds donné suit une loi de type “heavy tailed”.

• Approche de type SHC la plus efficace dans ce cas (pb SAT).

• Que se passe-t-il dans le cas small world + peu de maximum?

• La complexité effective de la résolution dépend des connaissances sur la structure du problème

• OneMax: in -> n*i

• k dépendances non chevauchantes: in -> (n/k)*ik

• k dépendances chevauchantes: in -> ?

• Grand bassins d’attraction des max globaux -> forte probabilité pour un SHC de trouver la solution.

• Dans l’absolu, la connaissance de la structure permet de choisir un opérateur donnant la solution par un hillclimbing

• La difficulté est que dans le cas général on ne connaît pas la structure.

• Comment réagissent les méthodes d’explorations à ces différentes difficultés?

• Comment améliorer les méthodes existantes?

• Etude sur l’efficacité des méthodes évolutionnistes

• Tests comparatifs avec d’autres méthodes d’explorations.

Résultats très variables en fonction des problèmes et des implémentation mais SHC souvent bien placé.

• Modélisation du comportement de convergence par processus markovien.

Pour une solution: matrice de taille

Pour la population complète: matrice de taille

• Description de la population par ses cumulants (moyenne, écart type, “skewness”…)

Limité aux GA simples appliqués à des problèmes simples

2)( ni

2)(pni

• Approches évolutionistes basées sur la découverte de la structure du problème.

• Principe: les populations de solutions rencontrées pendant le processus évolutif représentent une statistique des bonnes solutions.

• Premier travaux par Muehlenbein (1997) sur l’UMDA (univariate marginla distribution algorithm).

• Représentation de la population par un vecteur de fréquence de la fréquence de chaque instance de chaque variable.

• Utilisation de ce vecteur pour générer la nouvelle population.1 1 … 0

0 1 … 1

0 1 … 0

.25 .85 … .33

0 1 … 1

0 1 … 0

0 0 … 0

.75 .15 … .67

• Convergence en O(n ln(n)) évaluations sur OneMax.

• Problème: ne peut pas découvrir les dépendances donc risque important d’être piégé sur des maximum locaux.

• Nouvelle version (Wook 2003) utilisant une population de vecteurs de fréquences. Moins de risque d’être piégé (grande population) mais pas de découverte des dépendances.

• Nouvelle approche: PMBGA (probabilistic model-building genetic algorithms), par Pelikan et Goldberg (1999), basé sur la découverte des dépendances pour explorer.

• Découverte de la structure.

• Il faut un échantillon de l’espace de recherche suffisant pour qu’une analyse statistique soit significative et non biaisée.

• Deux alternatives:

• Avoir une population de taille suffisante pour que toutes l’information nécessaire à l’extraction de la structure soit présente.

• Avoir une population de taille quelconque et créer à posteriori de la diversité.

• Méthode BOA (bayesian optimization algorithm) choisit la première approche.

• BOA se place dans l’hypothèse de dépendance de taille maximum k non chevauchante.

• Taille de la population minimale pour que toutes les instances de tous les blocs de taille k soit présent dans la population initiale.

• Probabilité pk qu’une instance particulière d’un bloc de taille k soit présente dans une population de taille p.

• Probabilité ps que toutes les instances d’un bloc soient présente.

pkk i

p ))1

(1(1

ki

p

k ep

1

ki

p

kk eiiks epp

)(

• Si est la probabilité que toutes les instances ne soient pas présente, on a:

• d’ou:

• Problème: pourquoi ne pas calculer la probabilité que pour les m blocks toutes les instances soient présente?

ki

p

keie

1

))ln()ln(( ikip k

))ln()ln(( mikip k

mipks

k

p )))2

11(1((

)ln()ln(2 ikmiP ks

Estimée, problème taille 160 Estimée, problème taille 16000

Complète, problème taille 160 Complète, problème taille 16000

• Amplification de la meilleure instance de bloc.

• Sélection par tournoi

• Comportement initial

• Comportement final

• Mais ne considère qu’un seul bloc!

stt PP )1(11

sP

sP

P

P

t

t

t

t

)1(11

))1(1())1(1)()1(1( ''1 tctc

stt PPPPPP

• Taille de la population pour séparer deux instances d’un même bloc:

et

• Probabilité de choisir H2 plutôt que H1, normale avec:

• D’ou:

• Dans le cas de m blocs indépendants et avec la variances des opérateurs génétiques:

21 HH ffd 2/)( 22

21

2HHM

Pi

dZ

Mk 2

22

2)(

2

222d

iZP Mk

koi

i id

mZP 2

2 )1(2

• Variante plus récente (gambler’s ruin problem):

• Limitations:

• Compétition uniquement entre 2 instances de chaque bloc.

• Les blocs sont indépendants.

• Ne dit rien de l’efficacité des opérateurs à sélectionner les blocs.

• Les blocs ont des variances de même grandeur.

d

miP ik 1)ln(

• Bayesian optimization algorithm: découvrir les dépendances.

• Utilisation d’un réseau bayésien pour représenter et découvrir les dépendances.

• Principes:

Initialiser une pop aléatoire

Sélectionner les meilleurs

Modéliser les dépendances dans cette sous-population

Utiliser le modèle pour générer la nouvelle population

• Plus d’opérateur génétique explicite (sauf sélection).

• Rappel sur les réseaux bayésiens

• Le calcul des probabilité associées aux axes nécessite le calcul d’une table de taille par variable i

)|()(1

0jj

n

j

XpXp

rain

accident

Wet road

radar speed

ji

• Apprentissage d’un réseau bayésien a partir d’un ensemble de données sur n variables.

• Apprendre la structure: quels sont les j parents de tous les nœuds j.

2n structures de réseau possible pour n variables.

• Apprendre les probabilités associées à tous les arcs.

• Dans le cas de variables complètes nécessite uniquement le calcul des n tables de taille

• Définir une métrique permettant de mesurer la qualité du réseau en fonction des données.

• Définir une stratégie d’exploration 2n structures possibles.

ji

• La métrique BIC (bayesian information criterion):

Avec

• Procédure d’exploration (gloutonne):

Initialiser un réseau vide

Parmi toutes opérations autorisées (insertion, délétion ou retournement d’arc) choisir celle qui augmente le plus le score

)2

)log(2)|(()(

1

PPXHBBIC j

n

jjj

)|log(),()|(,

jjjjx

jj xxpXHjj

• Taille de la population pour ne placer un arc de la variables X2 à la variable X1.ssi il est significatif (cas ou X1 n’a pas de parent)

• Il faut résoudre

avec

• Pour estimer D il faut estimer les p(x1) et p(x2) après sélection (par tournoi)

• On en déduit: et si alors

Avec N l’écart type de la distribution des fitness des solutions avec X1=x1 ou X2=x2

)log()|()( 2112 PPXXHXXBIC

2

)log()()( 11

PPXHXBIC

02

)log())|()(( 211

PPXXHXH

02

)log(

D

PP )|()( 211 XXHXHD

)( 1.2NOP nN 2 )( 05.1nOP

• Dans le cas ou X1 a k-2 parents:

• Limitations:

• Dépendances sans chevauchement.

• Dépendances de tailles fixes.

• Contribution des blocs à la fitness de même ordre.

• Connaissance préalable de complexité de la structure pour choisir la taille.

• Un certain nombre d’approximations sans doute un peu brutales.

• Effet des heuristiques de création du modèle non prisent en compte.

• Danger de découvrir des dépendances non significatives.

)2( 05.1nOP k

• HBOA (hierarchical bayesian optimization algoritm)

• La différence majeur est l’utilisation de graphe de décision pour modéliser les dépendances de chaque variable.

• Compactage de l’information

• Plus haut niveau de représentation (?)

• Utilisation de niche écologique pour préserver de la diversité et donc trouver des solutions pour des problèmes à trappes de plusieurs niveaux.

• Résultat très bon sur les problèmes spécifiques.

• Résultats correct de HBOA sur spin glasses.

• Très bon résultats de HBOA + HC sur spin glasses.

• Bon résultat de HBOA + HC sur certains problèmes SAT

• Résultat faible de HBOA + HC sur les problèmes SAT difficiles.

• Nos résultats:

0

20000

40000

60000

80000

100000

120000

140000

160000

25 35 45 55 65 75 85 95

size [bits]

nu

mb

er

of

ev

alu

ati

on

s

Classical GA Highway BOA

0

500

1000

1500

2000

2500

3000

3500

25 35 45 55 65 75 85 95

size [bits]

co

mp

uti

ng

tim

e [

s/1

00

]

Classical GA Highway BOA

• Comment faire autrement, sachant que le but est de choisir les meilleures opérations affectuer dans un temps donner pour obtenir le meilleur résultat possible (à niveau d’heuristique équivalent):

• Utiliser la statistique de toute la population passée.

• Utiliser des opérateurs avec une fréquence dépendant de l’état de l’exploration.

• Apprendre les dépendances de façon approchée par étapes.

• Tenir compte dans la force des liens de la qualité des solutions associées.

• Utiliser d’autre modèle des dépendances: corrélation, entropie corrélé, implication statistique, keyGraph…

• Construire les opérateurs à partir des dépendances.

• Utilisé la connaissance de l’espace exploré pour diriger la recherche.