Algorithmes évolutionnaires
• Algorithmes basés sur les populations
• Origine des algorithmes évolutionnaires
– Obtenus par analogie avec :
•
le processus de l’évolution et de la sélection naturelle
(basé sur le néodarwinisme - Charles Darwin - 19ième siècle)
– Sous l ’influence des conditions extérieures, les caractéristiques des êtres
vivants se modifient progressivement lors de la phase de reproduction
– Générations d’individus mieux adaptés aux conditions complexes de
leur environnement, maximisant donc leur probabilité de survie
– Émergence des espèces qui ont survécu en transmettant leur patrimoine
génétique aux générations futures.
1
Algorithmes évolutionnaires
• Origine des algorithmes évolutionnaires (suite)
– Principe
Faire évoluer les individus d’une population au moyen
d’opérateurs stochastiques afin de favoriser l’émergence
d’individus dont l’évaluation / l’adaptation est meilleure
2
Algorithmes évolutionnaires
• Origine des algorithmes évolutionnaires (suite)
– Principe
• Population initiale d’individus
• Génération successive de nouvelles populations
– Succession d’itérations dénommées générations
– À chaque génération, application de plusieurs opérateurs :
(cid:1) croisement (mélange du matériel génétique)
(cid:1) mutation (perturbation du matériel génétique)
(cid:1) sélection (basé sur l’évaluation des individus - fonction d’évaluation)
(les individus utilisés par un opérateur sont appelées les parents;
ceux obtenus en sortie les descendants /enfants)
3
Algorithmes évolutionnaires
• Glossaire
– Individu
•
une instance du problème à traiter
– Population
•
ensemble d’individus évoluant simultanément
– Génération
•
itération de la boucle de base de l’algorithme évolutionnaire
– Fonction d ’évaluation / adaptation (fitness function)
•
fonction permettant d’évaluer l’adaptation d’un individu
4
Algorithmes évolutionnaires
• Glossaire (suite)
– Génotype (ou chromosome)
•
représentation sous forme de code / suite de gènes
(à l’aide d’un alphabet) d’un individu
– Phénotype
•
représentation réelle d’un individu (instance du problème d’opt.)
Illustration des notions de génotype / phénotype
•
Le phénotype est obtenu par « décodage » du génotype
(
xxx
,
,
21
3
) {
0,
K
,100
} {
,0
K
,
} {
,0
K
} (
;13,
Publicité
200
Phénotype
)
93,171,9
Génotype (binaire classique)
1011101101
010111001
5
(cid:219)
·
·
˛
(cid:219)
Algorithmes évolutionnaires
• Glossaire (suite)
– Gène
un élément d’un génotype, i.e. un des symboles
•
– Allèle
•
variante d’un gène , i.e. la valeur d’un symbole
– Croisement / recombinaison (crossover)
•
combinaison de deux individus pour engendrer un ou deux
nouveaux individus
– Mutation
• modification aléatoire d’un individu
– Sélection
•
choix des individus formant la nouvelle population
6
Algorithmes évolutionnaires
• Analogie problème d’optimisation / algo. évolutionnaire
Problème
d'optimisation
Théorie
de l'évolution
fonction de coût / objectif
fonction de fitness
C(x )
définie à partir de C(X )
variables du problème
"caractéristiques" d'un individu
trouver une "bonne" config.
trouver l'individu le mieux
adapté
algorithme évolutionnaires
7
Algorithmes évolutionnaires
• Schéma
Population
courante
Croisement
Population de
descendants
Sélection
Mutation
Population
évaluée
Évaluation
Population de
descendants mutés
8
Algorithmes évolutionnaires
• Description algorithmique
t = 0
| - Compteur des générations
{
( )
( )
( )
}ta
=
1 K
ta
tP
,
,
Initialisation(P(t))
| -
Publicité
( )
}ta
(
{
)
)
(
( )
1 K
,
,
ta
Évaluation(P(t))
| -
Tant que critère d’arrêt non vérifié faire
m
m
t = t + 1
P’(t) = Croisement(P(t-1)) (ou Recombinaison)
Mutation(P’(t))
Évaluation(P’(t))
( )
'
tP
P(t) = Sélection(
( )tQ
( )
tQ
}1-
)
(
tP
),
{
,
Fin tant que
(cid:1) Population comportant m
(cid:1) F dénote la fonction de fitness
individus (les aj)
9
F
F
¨
˘
˛
Algorithmes évolutionnaires
• Remarques
– Croisement et mutation sont chargés de la reproduction
•
•
calqués sur leur pendant biologique;
– Le croisement assure l’échange d’informations entre individus
– La mutation doit introduire de nouvelles informations
assurent l’exploration de l’espace de recherche
– La sélection guide la recherche
•
•
en favorisant la reproduction des meilleurs individus
de la population courante;
opérateur assurant la convergence (non fi
de l’algorithme évolutionnaire
divergence génétique)
– L’élitisme (garder le meilleur individu trouvé) assure la convergence
10
Algorithmes évolutionnaires
Algorithmes
génétiques
Stratégies
d’évolution
Évolution
différentielle
Représentation
Binaire ; réelle ;
spécifique
Réelle
Réelle
Auto-adaptation
Aucune
Croisement
(recombinaison)
Publicité
• Multipoint ;
• Uniforme ;
• Arithmétique
Ecarts types ;
angles de rotation
• Discrète ;
• Intermédiaire
(Multipartenaire, gén.)
Mutation
Inversion de bits, …
Gaussienne
Aucune
Individus intermédiaires ;
Croisement circulaire à
deux points
Sélection
Déterministe et
probabiliste
Déterministe :
(
(
)l
)
lm
m
+
SE
,
SE ;
Déterministe :
Tournoi binaire
Étude théorique
• Théorie des schémas
• Modèle markovien
• Convergence (élitiste)
Convergence :
• Vitesse ;
• Preuve (certains cas)
Aucune
11
Algorithmes évolutionnaires
• Algorithmes génétiques (Holland / De Jong - 1975)
– Travail au niveau génotypique (en principe)
• Codage binaire
– Binaire classique
=a
01011010
(cid:1) Inconvénient : petite modif. sur le génotype (cid:2) grande différence phénotypique
– Code de gray
(cid:1) Gomme partiellement l’inconvénient du code binaire classique
(utilisables pour résoudre un problème discret (cid:2) discrétisation)
• Codage spécifique au problème considéré
– Voyageur de commerce (5 villes)
(cid:1) On désigne les villes par des lettres de l’alphabet;
(cid:1) ou par des entiers consécutifs;
(cid:1) etc.
1 =a
2 =a
'1 =a
E D C BA
B C
D EA
5 4 3 2 1
12
Algorithmes évolutionnaires
• Algorithmes génétiques (suite)
– Opérateurs de croisement et de mutation - Illustration
• Représentation binaire
• Croisement multipoint (probabilité de croisement pc - proche de 1)
• Mutation (probabilité de mutation pm fixée par l’utilisateur - faible)
13
Algorithmes évolutionnaires
• Algorithmes génétiques(suite)
– Opérateur de sélection
• Sélection proportionnelle non préservative
•
a
j
F•
individu
Publicité
codant
est
l'
{
(
)
(
)
Cmax
a
x
a
'j
'
=
j
j
x
potentiell
solution
,
j
}
)
(
(
)j
C - 1-
tP
x
e
du
problème,
}m,
{
K˛
1,
j
)
(
a
(
∑
a
k
}
)
1-
(
tP
K
,
j
{
1,
)
(
ap
s
)
j
=
k
• Sélection sur le rang
• Sélection par tournois
– Tournoi entre deux individus (cid:2) tournoi binaire
– Tournoi au sein d’une sous-population créée aléatoirement
• Remarques
– Sélection probabiliste (cid:2) un individu peut être choisi plusieurs fois
– Un individu nettement meilleur peut devenir dominant (cid:2) super-individu
14
˛
˛
F
F