Réf.

: S7218 V2

Algorithmes génétiques,
Date de publication :
10 décembre 2020 algorithmes évolutionnaires

Cet article est issu de : Automatique - Robotique | Automatique et ingénierie système

par Évelyne LUTTON

Mots-clés Résumé Les principes de base des algorithmes évolutionnaires (AE), dont les plus
Algorithmes évolutionnaires | connus sont les algorithmes génétiques (AG), sont directement inspirés de la théorie de
Algorithmes génétiques |
Optimisation stochastique | l’évolution selon Darwin. Ces méthodes de résolution de problèmes, d’optimisation
Darwinisme artificiel stochastique, copient de façon très simplifiée la capacité de populations d’organismes
vivants à s’adapter à leur environnement à l’aide de mécanismes de sélection et
d’héritage génétique. Cet article donne un panorama rapide du « darwinisme artificiel » et
de la variété de ses applications.

Keywords Abstract Evolutionary Algorithms (EA), including the most famous ones, Genetic
Evolutionary algorithms | Algorithms (GA), are based on Darwin’s theory. These problem-solving or stochastic
Genetic algorithms | Stochastic
optimisation | Artificial optimization methods mimic in a very simplified manner the capabilities of populations of
darwinism living organisms to adapt to their environments thanks to selection and genetic
inheritance mechanisms. This paper provides a brief panorama of artificial Darwinism and
its varied and numerous applications.

Pour toute question :

Service Relation clientèle
Techniques de l’Ingénieur
Immeuble Pleyad 1 Document téléchargé le : 15/09/2021
39, boulevard Ornano
93288 Saint-Denis Cedex Pour le compte : 7200049459 - universite savoie mont blanc // [Link]

Par mail :
[Link]@[Link]
Par téléphone :
00 33 (0)1 53 35 20 20 © Techniques de l'Ingénieur | tous droits réservés
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

Algorithmes génétiques,
algorithmes évolutionnaires
par Évelyne LUTTON
Directrice de recherche INRAE
UMR MIA 518, AgroParisTech/INRAE
Institut des systèmes complexes, 113 rue Nationale, 75013, Paris, France.
Cet article est la version actualisée de l’article S7218 intitulé Algorithmes génétiques
et algorithmes évolutionnaires rédigé par Évelyne LUTTON et paru en 2006

1. Algorithmes génétiques, évolutionnaires, darwinisme artificiel...... S 7 218v2 - 3

1.1 Bref historique du domaine ....................................................................... — 3
1.1.1 Darwinisme, évolutionnisme ............................................................ — 3
1.1.2 Versions artificielles du darwinisme ................................................ — 3
1.2 Notions et vocabulaire de base ................................................................. — 4
2. Programmer et utiliser un algorithme évolutionnaire......................... — 4
2.1 Structure et ingrédients.............................................................................. — 4
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

2.2 Représentations et opérateurs génétiques ............................................... — 5

2.2.1 Représentation discrète..................................................................... — 5
2.2.2 Représentation continue ................................................................... — 7
2.2.3 Représentation fonctionnelle : programmation génétique ............ — 7
2.3 Sélection et pression sélective................................................................... — 8
2.4 Exploitation/exploration : un dosage délicat ............................................ — 9
3. Aperçu théorique : pourquoi et comment ça marche ? ...................... — 9
3.1 Approche intuitive : schémas, théorème des schémas ........................... — 9
3.2 Analyse markovienne ................................................................................. — 10
3.3 Analyse fractale, irrégularité du fitness .................................................... — 11
4. Extensions du modèle...................................................................................... — 11
4.1 Nichage et paysages multimodaux ........................................................... — 11
4.2 Coopération/coévolution ............................................................................ — 12
4.2.1 Systèmes de classeurs ...................................................................... — 12
4.2.2 Vie artificielle ...................................................................................... — 13
4.2.3 Approche parisienne.......................................................................... — 13
4.3 Multiobjectif................................................................................................. — 14
4.4 Approches interactives ............................................................................... — 14
5. Exemples d’application ................................................................................... — 15
5.1 Vision stéréo pour la robotique : l’algorithme des mouches .................. — 15
5.2 Exploration artistique, exemple du logiciel ArtiE-Fract ........................... — 16
6. Conclusion ........................................................................................................... — 17
7. Remerciements................................................................................................... — 17
8. Glossaire ............................................................................................................... — 17
9. Sigles, notations et symboles....................................................................... — 18
Pour en savoir plus .......................................................................................... Doc. S 7 218v2

D epuis les années 1970, de nombreuses méthodes d’optimisation stochas-

tique ont été développées sur la base de principes simplifiés d’évolution
darwinienne. L’anglicisme « algorithmes évolutionnaires (AE) » choisi pour
désigner ces méthodes est intentionnel : la communauté française employant

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 1

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

ces méthodes a jugé important de distinguer les travaux évolutionnistes,

portant sur des modèles biologiques très complexes, des approches évolution-
naires, utilisant des modèles informatiques ultra-simplifiés.
Actuellement, les algorithmes dits « génétiques » (AG) sont les plus médiatisés
parmi ces techniques, mais il en existe d’autres (programmation génétique, stra-
tégies d’évolution, évolution grammaticale, par exemple) qui diffèrent par leur
interprétation des principes darwiniens. La composante commune de ces tech-
niques est qu’elles font évoluer des populations organisées en générations – qui
représentent par exemple des points d’un espace de recherche quand on sou-
haite optimiser une fonction – sous l’action conjuguée de deux catégories
d’opérateurs stochastiques produisant :
•  une pression de sélection permettant de sélectionner des individus auto-
risés à se reproduire : « les meilleurs » au regard d’une fonction définie
sur l’espace de recherche considéré, dite « fonction d’évaluation », « fonc-
tion de performance », ou « fitness », et qui traduit le problème que l’on
cherche à résoudre ;
•  des variations aléatoires qui produisent de nouveaux individus, afin de
constituer la génération suivante : croisement par échange d’informations
entre plusieurs points, mutation par perturbation locale sur un point, pour
faire un parallèle avec la génétique.
L’efficacité de ce schéma est fondée sur l’hypothèse que l’action des opéra-
teurs génétiques sur des individus sélectionnés produit statistiquement des
individus de plus en plus proches de la solution recherchée. En d’autres
termes, le processus stochastique figuré par les populations successives doit
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

être correctement calibré et paramétré pour converger vers ce que l’on

souhaite, c’est-à-dire le plus souvent l’optimum global de la fonction de perfor-
mance. Une grande part des recherches théoriques sur les algorithmes
évolutionnaires est consacrée à cet épineux problème de convergence et à
celui de savoir ce qui rend la tâche aisée ou difficile pour un algorithme évolu-
tionnaire (notion d’AE-difficulté). Comme nous le verrons dans ce panorama,
des réponses théoriques rassurantes existent (oui, cela converge, si l’on res-
pecte certaines hypothèses), mais d’autres questions cruciales d’un point de
vue pratique restent ouvertes (vitesses de convergence, notamment). On peut
cependant dire que les résultats théoriques justifient l’efficacité des algo-
rithmes évolutionnaires en tant qu’heuristiques de recherche aléatoire,
confortant ainsi leur large usage empirique.
Du point de vue de l’optimisation, le grand intérêt des algorithmes évolution-
naires est que ce sont des méthodes stochastiques d’ordre 0, c’est-à-dire que
seule la connaissance des valeurs de la fonction à optimiser aux points
d’échantillonnage est nécessaire (il n’y a pas nécessité de connaître des déri-
vées), ce qui en fait des méthodes d’optimisation utilisables pour des fonctions
très irrégulières, mal conditionnées ou complexes à calculer. En revanche, un
algorithme évolutionnaire a un coût calculatoire qui peut devenir important.
Ces deux caractéristiques en font des méthodes adaptées aux cas où les
méthodes standard plus rapides du point de vue du calcul (par exemple, des
méthodes de gradient requérant l’existence et le calcul de dérivées) ne sont
plus applicables, du fait qu’elles se trouvent trop rapidement piégées dans des
optima locaux : espace de recherche trop vaste, fonctions trop irrégulières, jeu
de variables mixtes, par exemple. Nous verrons plus loin que d’autres pro-
blèmes – comme les problèmes dynamiques ou les problèmes interactifs –
peuvent être traités à l’aide d’une approche évolutionnaire. Enfin, il est souvent
avantageux d’hybrider les approches évolutionnaires avec d’autres approches
d’optimisation (descente de gradient, recherche Tabou, recuit simulé, etc.).
Malgré l’apparente simplicité d’un processus évolutionnaire (ce qui a conduit
de nombreux programmeurs à écrire très vite « leur » algorithme génétique,
parfois bien décevant), fabriquer un algorithme évolutionnaire efficace est une
tâche difficile, car les processus évolutionnaires sont très sensibles aux choix
algorithmiques et paramétriques, aux représentations du problème notam-
ment. Le design des ingrédients de base d’un algorithme évolutionnaire

S 7 218v2 – 2 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

efficace n’est pas si simple et l’expérience prouve que les grandes réussites
sont fondées sur une très bonne connaissance du problème à traiter, sur une
bonne compréhension des mécanismes évolutionnaires et sur une bonne dose
de créativité. Il est tout bonnement hasardeux de considérer ces techniques en
« boîte noire », comme un « optimiseur universel », que l’on utilise sans faire
aucun réglage.
Cela dit, les « success-stories » sont nombreuses, et les techniques évolu-
tionnaires font partie de notre quotidien ; il suffit par exemple de suivre ce qui
se fait dans les conférences internationales du domaine (EvoStar, CEC, GECCO,
PPSN, EA) pour s’en convaincre. En effet, le champ d’application des algo-
rithmes évolutionnaires est très large : il va des applications réelles complexes
comme le contrôle du flux de pipelines de gaz, le design de profils d’ailes, le
routage aérien ou la planification de trajectoires de robots, à des problèmes
plus théoriques et combinatoires, en théorie des jeux, en modélisation écono-
mique, en finance, en commande de processus et en apprentissage.

1. Algorithmes génétiques, années 1960. Ces deux approches reposent sur l’imitation du phé-
nomène d’apprentissage collectif – on dit aussi d’adaptation –
évolutionnaires, d’une population naturelle, fondée sur les observations de Darwin
et sur la théorie moderne de l’évolution. Ces deux courants ont
darwinisme artificiel évolué assez parallèlement jusqu’aux années 2000, chacun ayant
son champ d’application particulier, tous deux devenant actuelle-
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ment de plus en plus attirants aussi bien pour les chercheurs que
pour les industriels, grâce notamment à la vulgarisation des calcu-
1.1 Bref historique du domaine lateurs parallèles, à l’accroissement des puissances de calculs, et
enfin à la diffusion d’utilitaires de programmation (comme GA-Lib,
1.1.1 Darwinisme, évolutionnisme EO, EASEA, ou plus récemment des bibliothèques en langage
python comme Inspyred).
Charles Darwin a construit sa théorie de l’évolution des espèces Le courant américain, initialisé par John Holland dans les
par l’observation systématique de lignées d’espèces, en particulier années 1960, est à l’origine de ce que l’on appelle les algorithmes
au cours d’un voyage effectué de 1831 à 1836 sur le Beagle à des- génétiques (AG) [49]. Bien qu’ils aient été prévus initialement
tination des côtes sud-américaines, des mers du Sud, du Pacifique, dans le cadre d’optimisation ou d’apprentissage dans le domaine
de l’Australie et de la Nouvelle-Zélande. Les espèces endémiques discret, les AG ont été facilement étendus à l’optimisation sur des
des îles Galapagos attirèrent son attention, lui rendant évidentes domaines continus [30].
l’extrême variabilité des espèces, accentuée par l’isolement géo-
graphique et l’impitoyable concurrence vitale due au confinement. En Allemagne, sont apparues à peu près en même temps des
Selon lui, l’évolution se fonde sur trois principes (extrait de méthodes appelées « stratégies d’évolution » (SE) [95] [97] [47].
La Grande Encyclopédie Larousse, 1973) : Ces méthodes étaient au contraire prévues initialement pour
fonctionner sur des domaines continus et ont été étendues à des
• « partout, toujours, et de mille manières, les faunes et les flores applications en optimisation discrète [97].
ont varié ;
Ces deux approches ont de nombreux points communs ; leurs
• les lignées observées individuellement, par voie d’élevage ou différences résident principalement dans leurs origines (approche
de culture, présentent d’innombrables variations de détails ; continue versus approche discrète). Le principal reproche que l’on
• la lutte pour la vie est si féroce et la sélection naturelle si a pu faire à ces méthodes, par rapport à d’autres méthodes d’opti-
rigoureuse que la moindre variation utile fait triompher la misation plus classiques, est le manque de résultats théoriques
lignée qui la possède. » généraux de convergence. En effet, la modélisation de ces proces-
De nombreux biologistes et philosophes ont suivi ce courant, sus stochastiques à base de populations est beaucoup plus ardue,
opposant la théorie de Darwin à celles de ses prédécesseurs, et il a fallu attendre assez longtemps pour voir établir des théo-
comme Linné et Lamarck, puis proposant des variations autour rèmes de convergence convaincants (section 3). Un historique
des notions de base du darwinisme. plus complet sur les AG peut se trouver dans [38] ou [25].
L’évolutionnisme s’est aussi développé en sociologie et en ethno- Parallèlement à des recherches théoriques dont les bases les plus
logie dans le but, parfois controversé, de trouver des modèles de solides (les modèles markoviens) n’ont été posées que relativement
développement des sociétés (du plus simple au plus complexe, récemment, on s’est intéressé assez vite à d’autres adaptations des
notamment). On n’entrera pas ici dans les querelles de l’évolution- paradigmes naturels. Cela a donné naissance à de nouveaux
nisme, de l’inné et de l’acquis, il suffit de savoir que les trois prin- modèles d’algorithmes évolutionnaires : implantation de phéno-
cipes darwiniens constituent un modèle d’évolution qu’il est mènes biologiques plus évolués comme le partage des ressources
intéressant d’étudier d’un point de vue informatique. et les niches écologiques (section 4.1), la coévolution de différentes
espèces (notions de prédateurs et de proies) [2] [14] [46] [52] [55]
[56] [57] [101] ou la dominance et la diploïdie [103] [43].
1.1.2 Versions artificielles du darwinisme
Nota : pour les AG diploïdes, les représentations chromosomiques (les codes)
L’idée d’utiliser les principes des processus d’évolution orga- contiennent l’information en double (représentation diploïde). Cette particularité permet
semble-t-il de rendre les algorithmes plus robustes, particulièrement en environnement
nique en tant que technique d’optimisation globale a émergé indé- dynamique, grâce à cette redondance d’information qui joue un rôle de « mémoire » à
pendamment des deux côtés de l’océan Atlantique à partir des long terme.

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 3

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

D’autres approches, comme les algorithmes à estimation de distri- algorithmique du terme par une maximisation de la fonction
bution, correspondent à une interprétation plus statistique et plus d’évaluation sur les individus de la population.
globale des opérateurs génétiques [90] [65] ainsi que le célèbre algo-
rithme « covariance matrix adaptation evolution strategy » (CMA-ES),
qui représente localement la fonction à optimiser sous la forme À retenir
d’une matrice de covariance.
• Un algorithme évolutionnaire (AE) est un algorithme d’optimi-
Enfin, en s’éloignant quelque peu des préoccupations d’optimisa- sation stochastique inspiré des trois principes de l’évolution
tion numérique pure, de nouveaux thèmes de recherche se sont darwinienne : variations aléatoires, transmissions des caractères
ouverts progressivement : programmation génétique, vie artificielle, et sélection.
optimisation multiobjectif, contrôle et suivi de données dyna- • Les AE regroupent un ensemble de techniques telles que
miques, classification, apprentissage, applications interactives. les algorithmes génétiques (AG), les stratégies d’évolution
(SE), la programmation génétique (PG).
• Il n’est pas nécessaire que la fonction optimisée (fitness)
1.2 Notions et vocabulaire de base soit dérivable ni même continue.

L’origine biologique des algorithmes évolutionnaires colore leur

vocabulaire ; il mérite ici d’être précisé afin d’éviter toute confusion.
En effet, comme souvent en pareil cas, ces emprunts de vocabulaire 2. Programmer et utiliser
ont favorisé la dérive – et la simplification parfois abusive – de bon
nombre de termes. Les principaux éléments de vocabulaire sont un algorithme
résumés dans le tableau 1.
évolutionnaire
Les individus représentent des solutions ou des points de
l’espace de recherche. Cet espace de recherche est appelé envi-
ronnement ; c’est sur cet environnement que l’on cherche à maxi- 2.1 Structure et ingrédients
miser une fonction (souvent à valeurs positives, pour simplifier)
appelée fonction d’évaluation ou fitness. Les ingrédients de base d’un algorithme évolutionnaire « cano-
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

Les représentations ou codages (discrets ou continus) des solu- nique » peuvent être décrits simplement ; cependant, ce qui est pré-
tions sont appelés chromosomes, et dans le cas de l’AG cano- senté ci-après doit être compris comme une « recette de cuisine ». Les
nique, ils sont discrets, binaires et de longueur fixe. On emploie applications efficaces à base d’algorithmes évolutionnaires sont sou-
aussi le terme de génotype en ce qui concerne les chromosomes, vent plus complexes, le problème essentiel étant d’adapter, de créer
tandis que les solutions (les vecteurs de l’espace de recherche) même, ses propres opérateurs pour les faire correspondre aux spécifi-
constituent le phénotype. L’algorithme travaille ainsi au niveau du cités du problème.
génotype : à l’aide des opérateurs génétiques, il induit une topolo- La base d’un algorithme évolutionnaire classique est une boucle
gie de recherche dans l’espace phénotypique, ce qui conditionne générationnelle de populations d’individus correspondant chacun
l’efficacité de la recherche. à une solution au problème considéré [26] [38] [84]. Les individus
sont représentés, sous forme discrète ou continue par exemple, à
L’algorithme évolutionnaire fait évoluer sa population de façon l’aide de chromosomes ou de gènes. Le schéma de la figure 1
à adapter les individus à l’environnement ; cela se traduit au sens donne une vision synthétique simplifiée de la boucle évolution-
naire dont les principales étapes sont les suivantes.

■ La sélection détermine quels individus de la population courante

Tableau 1 – Vocabulaire des EA : une (im)prudente sont autorisés à se reproduire (les parents). Cette opération est
analogie avec la biologie fondée sur la qualité des individus, estimée à l’aide d’une fonction,
nommée fitness, fonction d’évaluation, ou encore performance.
Dans le schéma canonique de l’AG « à la Goldberg », deux parents
Algorithme évolutionnaire Méthode d’optimisation donnent deux enfants ; ainsi, on sélectionne un nombre de parents
égal au nombre d’enfants désirés, mais évidemment bien d’autres
Individu Solution (vecteur) schémas moins conventionnels peuvent être programmés (deux
parents pour un enfant, n parents pour p enfants, etc.). Le para-
Population Ensemble de solutions mètre principal de cette étape de sélection est ce que l’on appelle
la pression sélective, qui correspond globalement au quotient de
Chromosome Représentation ou codage la probabilité de sélection du meilleur individu sur la probabilité de
de la solution (exemple : code sélection de l’individu moyen de la population courante. Ce para-
binaire) mètre contrôle la rapidité de concentration de la population autour
de son meilleur individu.
Croisement ou recombinaison Opération sur deux codes
■ La reproduction génère des descendants à partir des parents
sélectionnés. Les deux opérations principales sont le croisement,
Mutation Opération sur un code qui combine les gènes de deux parents, et la mutation, qui
consiste en une légère perturbation du génome. Ces opérations
Environnement Espace de recherche sont appliquées aléatoirement, et dépendent de deux paramètres :
la probabilité de croisement pc et la probabilité de mutation pm.
Fitness Valeur de la fonction Ces probabilités ont une influence considérable sur la qualité des
Degré d’adaptation à optimiser résultats globaux (vitesse de convergence et précision).
à l’environnement
■ L’évaluation consiste à calculer (ou estimer) la performance des
Évolution Maximisation de la fonction individus nouvellement créés. C’est là, et uniquement là qu’inter-
vient la fonction à optimiser. Aucune hypothèse n’est faite sur la

S 7 218v2 – 4 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

■ L’initialisation du processus est usuellement faite de façon aléa-

toire (différentes stratégies sont d’ailleurs envisageables pour
échantillonner correctement un espace de recherche complexe ou
Génération de grande dimension). C’est là que l’on peut injecter la ou les solu-
de la population intiale tions initiales que l’on a pu obtenir par ailleurs, par exemple à
l’aide d’autres techniques de résolution. Si l’initialisation a théori-
Population quement peu d’importance – on converge en limite toujours vers
des « parents » l’optimum global – on constate expérimentalement que cette étape
joue énormément sur la variance des résultats, ainsi que sur la
rapidité d’obtention de ceux-ci. Il est ainsi souvent très avantageux
Sélection d’injecter un maximum de connaissances a priori sur le problème
par le biais de l’initialisation.
Création d’une nouvelle ■ L’arrêt du processus, de même, est essentiel du point de vue pra-
population de « parents » Croisements tique. Si l’on connaît la valeur-cible de l’optimum recherché, on peut
à partir de celle et mutations s’arrêter dès que cette valeur est atteinte par le meilleur individu de
des « enfants » la population courante. Dans le cas contraire, il est délicat de savoir
Population quand arrêter l’évolution. Une stratégie couramment employée
des « enfants » consiste à stopper l’algorithme dès qu’un nombre maximal d’itéra-
tions est atteint, ou qu’un stade de « stagnation » est identifié. Il est
aussi possible de tester la dispersion de la population. Il est évident
NON Arrêt de l’évolution ? qu’une bonne gestion de l’arrêt de l’évolution contribue de façon
importante à l’efficacité de la méthode, au même titre que le réglage
OUI des principaux paramètres de l’algorithme (taille de population, pro-
Extraction
babilités de croisement et de mutation).
de la solution Les modes de représentation, opérateurs, stratégies de sélection
et de remplacement les plus classiques sont détaillés ci-après, mais
on pourra trouver dans la littérature bien d’autres déclinaisons de
ces composantes dans des espaces de recherche non standard, en
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

Figure 1 – Organigramme de l'algorithme évolutionnaire simple

fonction des applications (espaces de listes, de graphes...).

fonction elle-même, excepté le fait qu’elle puisse servir de base au

processus de sélection (elle doit pouvoir permettre de définir une
2.2 Représentations
probabilité ou au minimum un ordonnancement des solutions). et opérateurs génétiques
Le choix d’une représentation est l’un des points fondamentaux.
■ Le remplacement, enfin, gère la manière dont on constitue la
En algorithmique d’optimisation, la correspondance entre les carac-
génération n + 1. La stratégie simpliste qui consiste à remplacer
tères exprimés des individus (phénotypes) et les chromosomes
l’ensemble des parents par tous leurs descendants a été expéri-
(génotypes) est usuellement directe ; c’est une représentation bijec-
mentalement et théoriquement déboutée dans le cadre des appli-
tive. Ce n’est pas le cas dans la nature. Il existe par exemple des
cations d’optimisation : il est nécessaire de maintenir un taux
gènes qui ne sont pas exprimés dans le phénotype (introns) ou des
d’élitisme, même faible, tout simplement pour ne pas perdre la
gènes qui s’expriment conditionnellement à l’environnement ou à
mémoire des bons individus visités. Les stratégies usuelles de
des gènes voisins (épistasie).
remplacement consistent à maintenir un pourcentage donné des
meilleurs individus de la population courante dans la population Le code binaire est la représentation discrète la plus simple
suivante (De Jong, par exemple, emploie un paramètre qui gère le que l’on puisse utiliser ; d’autres types de codes permettent des
taux de renouvellement de la population : le « generation gap »). extensions très intéressantes, comme les systèmes de classeurs,
Ce paramètre est lui aussi essentiel pour le bon comportement de qui manipulent des chaînes représentant des règles (SI < condi-
convergence de l’algorithme évolutionnaire. tion > ALORS < action >).
Enfin, pour ce que l’on appelle des problèmes d’ordre (pro-
■ Dans les approches de type « stratégie d’évolution » (evolution blème du voyageur de commerce, ordonnancement de tâches, par
strategy - ES), on parle de stratégies (μ, λ) ou (μ + λ) [4] [47], ce qui exemple), le choix du codage est essentiel. En effet, l’algorithme
signifie que λ descendants sont générés à partir d’une population manipule des codes, et tente de trouver pour chaque gène de ce
de μ individus. La stratégie «, » consiste à gérer l’élitisme par le code la meilleure valeur possible, c’est-à-dire qu’il sait traiter un
biais de la différence μ – λ (on garde les μ – λ meilleurs individus problème de valeurs. En revanche les problèmes d’ordre, eux,
de la population courante et on complète par les λ descendants), demandent une recherche de la meilleure permutation possible
tandis que la stratégie « + » est une version plus adaptative dans des gènes du code. La solution couramment employée est soit de
sa gestion de l’élitisme : à partir d’un ensemble intermédiaire de transformer le problème d’ordre en un problème de valeur, soit
taille μ + λ constitué des μ individus de la population courante et de modifier les opérateurs génétiques (voir [59] par exemple).
des λ descendants, on sélectionne les μ meilleurs individus de la
génération suivante. Bien évidemment, les opérateurs génétiques dépendent du choix
de la représentation. Trois représentations classiques ainsi que leurs
opérateurs associés sont détaillés ci-après.
■ Il est aussi possible (dans le cas des implantations parallèles,
notamment) de s’affranchir de la notion de génération avec un
schéma stationnaire, consistant à produire à chaque itération de 2.2.1 Représentation discrète
l’algorithme un ou deux nouveaux individus et à les injecter dans la
population courante via une opération de remplacement, ou plus Cette représentation, dont fait partie la représentation binaire,
exactement de « sélection inverse » (déterministe ou aléatoire), de est la caractéristique historique du courant « algorithme géné-
façon à remplacer les plus mauvais individus de la population par tique » du domaine, même si par la suite on a vu apparaître des
des nouveaux venus. AG à codage réel.

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 5

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

Chaque individu de la population est représenté par une chaîne [Link] Croisement discret
de longueur fixe, dont les éléments (gènes) sont choisis dans un
alphabet fini. Cela concerne des problèmes combinatoires dis- L’opérateur de croisement est une composante importante du
crets, mais aussi des problèmes continus que l’on s’autorise à mécanisme de convergence de l’AG ; intuitivement, il permet une
discrétiser. Dans ce dernier cas, la longueur du chromosome est concentration de la population autour des « bons » individus. Le
un paramètre important qui contrôle la précision de l’échantillon- choix de la probabilité de croisement pc (qui décide si les informa-
nage de l’espace, et par voie de conséquence, la précision limite tions génétiques de deux individus sont mélangées ou transmises
du résultat [112] [67]. sans modification aux descendants) correspond à un compromis
subtil entre composantes d’exploration et d’exploitation de l’algo-
Les implantations sur code binaire, c’est-à-dire où l’alphabet est rithme. La plupart du temps, le choix de cette probabilité est fait
(0,1), sont les plus courantes encore actuellement. John Holland a par tâtonnement expérimental.
argumenté l’optimalité, selon la théorie des schémas, de l’alphabet Il existe un grand nombre d’opérateurs de croisement ; les plus clas-
binaire (c’est l’alphabet le plus petit possible), ce qui a poussé de siques dans le cadre de l’optimisation stochastique sont (figure 2) :
nombreux programmeurs à adopter ce codage quasi systémati-
quement [50]. Cette stratégie a depuis été de nombreuses fois • le croisement à un point, où un site de croisement est choisi
remise en question. David Goldberg, par exemple, introduit la aléatoirement sur le chromosome, puis les chaînes de code
notion de complexité d’un code, et explique que, d’un point de sont échangées autour de ce site ;
vue pratique, le choix d’un code est un compromis entre taille • le croisement à deux points : deux sites de croisement sont
de l’alphabet et complexité du codage [39]. Cette notion de choisis, et les portions de code sont échangées par alternance ;
complexité pour un code correspond au fait que de petites varia- • le croisement uniforme, où chaque gène d’un descendant est
tions du code peuvent ou non induire de grandes modifications choisi aléatoirement parmi les gènes des parents ayant la
sur les solutions associées. En d’autres termes, cela traduit la même position dans le chromosome. Assez souvent, le second
corrélation des tailles des voisinages au niveau du génotype et au descendant est construit en prenant les choix complémentaires
niveau du phénotype. du premier, comme sur la figure 2.
Une autre contrainte importante pour le codage, qui intervient D’autres types de croisements existent, comme le croisement
aussi dans ce compromis et que l’on oublie parfois, est la complexité multipoint ou des croisements spécialisés, comme dans le cas du
algorithmique du processus de codage/décodage. En effet, ces opé- problème du voyageur de commerce ou des problèmes d’ordon-
rations sont effectuées un grand nombre de fois au cours de l’évolu- nancement, qui tiennent compte de la structure particulière du
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

tion de l’algorithme ; elles ont donc un poids non négligeable dans le codage employé.
coût algorithmique de l’ensemble.
[Link] Mutation discrète
Pour la plupart des applications des AG binaires en optimisation
numérique, le chromosome est simplement une concaténation des De façon schématique, la mutation effectue une perturbation
codes binaires de toutes les composantes du vecteur de l’espace mineure du chromosome de l’individu ; par exemple, dans le cas
de recherche. L’espace de recherche doit donc être borné. On a d’un codage binaire, un site de mutation est choisi aléatoirement
parlé aussi beaucoup dans ce contexte des codes de Gray, qui et le bit correspondant est inversé (figure 3). La probabilité de
pourraient sembler mieux répondre à la contrainte de complexité mutation pm est souvent définie comme la probabilité de muter
que le code binaire classique. Des recherches théoriques, corrélées un bit d’un individu et non celle de muter un individu (comme
expérimentalement, ont prouvé que cela est faux [67] : il n’y a pas pour la probabilité de croisement), ce qui fait qu’un individu peut
de réponse universelle, tout dépend de la fonction optimisée voir plusieurs de ses bits inversés par l’opérateur de mutation si
(fitness) et de la forme de l’espace de recherche ! pm est suffisamment élevée.

Parents Descendants
1
Croisement à 1 point
2

Parents Descendants
1
Croisement à 2 points
2

Parents Descendants
1
Croisement uniforme
2

Figure 2 – Croisements binaires

S 7 218v2 – 6 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

produit un descendant à partir d’un couple de vecteurs (x, y)

de  grâce au tirage aléatoire d’une constante α, souvent choisie
Parents Descendants de façon uniforme dans [0, 1] – ou dans [– ε, 1 + ε] pour le croise-
ment (BLX-ε) – tel que :
010011010011101001111011110 010010010011101001111011110

La constante α peut être tirée une fois pour toutes pour

l’ensemble des coordonnées de , ou tirée indépendamment
pour chacune de ses coordonnées (variante dite « uniforme » de
Figure 3 – Mutation binaire simple
ce croisement).
La généralisation de ce croisement à un croisement à plus de deux
L’effet de cet opérateur est de « troubler » la tendance à la parents, voire à l’ensemble de la population (croisement « global »),
concentration induite par la sélection et le croisement, de façon à est assez directe [98].
laisser à la population la possibilité de « visiter » d’autres régions
de l’espace de recherche. Il a été prouvé que cet opérateur limite [Link] Mutations continues
la « dérive génétique » due au processus de sélection élitiste [44]. Beaucoup d’opérateurs de mutation ont été proposés et expéri-
La probabilité de mutation reste usuellement très faible et, très mentés pour la représentation réelle ; les plus classiques sont
souvent, elle est maintenue à une valeur fixée tout au long de détaillés ci-après.
l’évolution de l’AG. Des schémas génétiques fondés sur une pro-
■ La mutation gaussienne consiste à ajouter un bruit gaussien
babilité de mutation variable, qui décroît au fur et à mesure de
N(0,σ) aux composantes du vecteur-individu concerné, ce qui
l’évolution de l’AG, sont aussi utilisés. D’un point de vue théo-
implique l’ajustement d’un paramètre supplémentaire, σ, la dévia-
rique, il a été prouvé qu’un tel AG converge vers l’optimum global
tion standard du bruit :
de son espace de recherche pour une taille de population finie, si
sa probabilité de mutation pm(k) décroît à chaque génération en
respectant une borne minimale [27] :
L’ajustement de σ est relativement complexe (trop petit, il ralentit
l’évolution, trop grand, il perturbe la convergence de l’AE) ; de nom-
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

breuses stratégies ont été proposées, consistant à rendre ce para-

Soit M la taille de la population, mètre variable au cours de l’évolution, soit en fonction du temps, de
la valeur de fitness, des axes de l’espace de recherche (mutations
L la longueur des chromosomes. non isotropes), ou encore autoadaptatif, comme ci-après. Des études
Bien sûr, une telle décroissance est extrêmement lente et néces- ont aussi été menées sur l’emploi de bruits non gaussiens [19].
site un nombre infini de générations pour arriver à zéro (un calcul
de la formule pour une population de 100 individus ayant des ■ La mutation log-normale autoadaptative est une des grandes
chromosomes de longueur 32 donne une valeur de probabilité de innovations des stratégies évolutionnaires ; elle consiste à faire
mutation qui décroît de 0,5 à 0,499 en 1 000 générations !). Il est gérer les paramètres σ directement par l’AE, en l’intégrant au code
extrêmement rare que l’on ait besoin d’employer dans la pratique génétique. Les individus sont donc des vecteurs (x, σ), et la muta-
la formule de décroissance théorique pour pouvoir faire converger tion se traduit simplement comme suit :
l’algorithme. L’emploi d’un taux de décroissance plus rapide per-
met d’améliorer l’efficacité de l’AG en permettant dans les pre-
mières générations une exploration large de l’espace de recherche,
puis une concentration plus marquée (exploitation des zones les
plus intéressantes) lors des dernières générations. De nombreux travaux théoriques et expérimentaux ont montré
l’intérêt et la puissance de ces méthodes autoadaptatives.
2.2.2 Représentation continue ■ La mutation uniforme, inspirée des approches AG, consiste à
tirer uniformément la nouvelle valeur de la composante xi de
La représentation continue, aussi dite « représentation réelle », l’individu x dans un intervalle [Mini, Maxi], c’est un opérateur plus
définit un algorithme évolutionnaire qui effectue sa recherche dans « brutal », mais qui peut être efficace malgré tout lorsqu’il convient
ou une partie de celui-ci. Cette représentation est historiquement de maintenir une bonne diversité (en complément d’autres opéra-
liée aux approches de type stratégies d’évolution (SE) ; elle s’est teurs de mutation, par exemple).
ensuite étendue aux algorithmes génétiques. Elle implique le plus
souvent que l’on identifie espace des génotypes et espace de Il existe de nombreuses autres mutations spécialisées, par
phénotypes. Les opérateurs génétiques que l’on peut employer dans exemple pour le traitement des contraintes, particulièrement utiles
cette représentation sont soit des extensions continues des opéra- lorsque les solutions recherchées se trouvent près des limites de
teurs discrets, soit directement des opérateurs continus exploitant la l’espace contraint. Une excellente revue des divers opérateurs
géométrie de l’espace . génétiques se trouve dans [6].

[Link] Croisements continus 2.2.3 Représentation fonctionnelle :

Une première stratégie consiste à transposer les croisements programmation génétique
discrets en mélangeant les composantes réelles d’un chromosome Le domaine de la programmation génétique (PG, ou GP pour
sans toucher à leur contenu. C’est une adaptation directe des opé- genetic programming) correspond à une représentation par des
rateurs de croisements binaires précédents, par exemple les croi- structures de longueurs variables sous forme d’arbres. La PG avait
sements à un point, plusieurs points ou les croisements uniformes. été prévue à l’origine pour manipuler des programmes codés en
L’avantage de la représentation continue est certainement mieux LISP, afin de créer des programmes pouvant résoudre des pro-
exploitée avec des croisements continus qui mélangent plus inti- blèmes pour lesquels ils n’ont pas été explicitement programmés
mement les composantes des vecteurs parents pour fabriquer de (« créer des programmes sans programmer » selon John Koza [58]).
nouveaux individus ; par exemple, le croisement barycentrique, Un grand nombre de problèmes de natures très différentes peuvent
encore appelé croisement intermédiaire, arithmétique ou BLX, être formulés comme un problème d’induction de programme, et

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 7

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

donc abordés grâce à la PG. La richesse de la représentation L’évolution d’un programme au sein de la PG se fait simultané-
arborescente de taille variable (figure 4) fonde le succès de cette ment sur sa taille, sa structure et son contenu. L’ensemble des
technique dans le milieu évolutionnaire. structures possibles d’un programme est l’ensemble de toutes les
Un algorithme de PG explore un espace de programmes compositions récursivement possibles de fonctions à partir d’un
composés à partir d’éléments d’un ensemble de fonctions et ensemble de fonctions et d’un ensemble de
d’éléments d’un ensemble de terminaisons, qui sont typiquement
terminaisons .
des ensembles de symboles sélectionnés comme étant appropriés
à la solution des problèmes dans le domaine d’intérêt (variables, Les fonctions de F peuvent inclure des opérations arithmétiques
données d’entrée, constantes, etc.). Plus précisément, les indivi- (+, –, *, …), des fonctions mathématiques (sin, cos, exp, log), des
dus de la population sont des programmes (ou des formules opérations booléennes (ET, OU, NOT), des opérateurs condition-
mathématiques) qui, lorsqu’ils sont exécutés, sont eux-mêmes nels (if, then, else), des commandes d’itérations (do – until, for),
des solutions possibles au problème posé. des commandes de récursion ou des fonctions spécifiques à
Les croisements se font par échange de sous-arbres (figure 5). l’application envisagée.
Les mutations sont plus complexes ; on en distingue plusieurs, Les terminaisons sont par exemple des constantes ou des
suivant leur action sur la structure du génome : variables qui représentent une mesure, une variable d’état.
• suppression/ajout de nœud ;
Les applications de la PG sont très nombreuses et très variées
• modification de la fonction d’un nœud en conservant son (contrôle optimal, planification de trajectoires et d’actions en
arité, ou non (auquel cas, on peut générer des parties de robotique, régression symbolique) ; pour plus de précisions, le
codes non utilisées, les introns) ; lecteur peut se référer à [58] [93] [37], par exemple.
• mutation des constantes (valeurs continues), par exemple par
ajout d’un bruit gaussien ;
• mutation des variables discrètes, par permutation ou tirage 2.3 Sélection et pression sélective
aléatoire uniforme dans un ensemble de valeurs.
La sélection des individus d’une population est faite en rapport
avec leur adaptation à l’environnement (leur fitness). La fonction à
optimiser, qui est employée pour évaluer l’adaptation à l’environ-
nement, doit pouvoir être rendue positive (par une transformation
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

mathématique) : c’est la seule contrainte qui lui est imposée. Il

*
n’est pas nécessaire qu’elle soit continue ou dérivable.
L’idée est de sélectionner aléatoirement des individus pour
+ + la phase de reproduction, en favorisant les meilleurs individus. La
figure 6 montre une sélection simple, dite « sélection proportion-
nelle », qui se fait par tirage aléatoire biaisé.
cos * 1 x L’influence de la pression sélective vis-à-vis de la diversité géné-
tique est énorme et le bon déroulement de l’algorithme en dépend
étroitement. La sélection proportionnelle peut par exemple favoriser
x 2 y la domination d’un « super individu » ayant une valeur de fitness
largement supérieure aux autres individus de la population. Cela
peut mener à une convergence prématurée, par sursélection de cet
Figure 4 – Arbre de représentation pour la fonction (cos x + 2y) (1 + x) individu qui impliquera le blocage des populations au voisinage de
ce point. De même, un ralentissement de l’évolution peut provenir
de l’aplatissement des valeurs de fitness au sein de la population,
amenant à des probabilités de sélection quasi-uniforme au sein de
la population.

1 2

Proportionnel
Parents à f (X1)

Nœuds 1 et 2 sélectionnés X1

Enfants X3

X2

Figure 6 – Sélection proportionnelle, ou roue de la fortune : tirage

aléatoire uniforme sur un disque où chaque solution occupe
un secteur de taille proportionnelle à la valeur de sa fonction
Figure 5 – Croisement en programmation génétique d’évaluation

S 7 218v2 – 8 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

Il est ainsi nécessaire de construire des méthodes de sélection temps de calcul (on l’a dit, l’approche en « boîte noire » n’est pas
où l’on peut avoir un contrôle sur la pression sélective. Quelques raisonnable). La réponse à cette question n’est pas simple. Cepen-
méthodes, parmi les plus fréquemment utilisées, sont données dant, de nombreuses analyses théoriques et expérimentales four-
ci-après : nissent quelques éléments de réponse pour comprendre quand
• le scaling se fait par transformation linéaire sur le fitness l’emploi d’un AE se justifie ou peut apporter quelque chose en
pour que le maximum de sa valeur réétalonnée soit C fois la comparaison ou en collaboration avec des techniques classiques.
moyenne sur la population courante. C représente une Historiquement, la théorie des schémas représente la première
mesure de pression sélective [38]. Les coefficients de réétalo- « théorie » de convergence globale des algorithmes génétiques ;
nage sont recalculés à chaque génération, de façon à mainte- c’est en fait une modélisation extrêmement simplifiée du compor-
nir C à une valeur fixée (usuellement entre 1,2 et 2, voir tement d’un AE [49] [38], reposant sur des hypothèses valides uni-
section 3.2) ; quement dans les premiers pas de l’algorithme et dans le cas de
• la sélection par le rang affecte une probabilité de sélection populations de taille infinie. Du fait de ces approximations, cette
proportionnelle au rang de chaque individu dans la population approche a été relativement décriée ; elle reste cependant une
classée par ordre de fitness décroissant ; excellente base intuitive pour comprendre les mécanismes
• la sélection par tournoi consiste, à chaque fois qu’il faut de convergence, notamment concernant le rôle de l’opérateur de
sélectionner un individu, à tirer aléatoirement T individus croisement.
dans la population (indépendamment de leurs valeurs de Parallèlement, ont été développés des résultats de convergence
fitness), et à choisir le meilleur d’entre eux. La pression locale pour les stratégies d’évolution [4] [35] [36], puis ensuite des
sélective est directement reliée à la taille du tournoi : plus T modèles globaux plus rigoureux, comme les modélisations mar-
est grand, plus elle est importante. koviennes, à base de systèmes dynamiques [1] [27] [51] [87] [116],
ou selon des modèles de physique statistique [94] [99] [100]. Ces
approches beaucoup plus complexes donnent des résultats précis
2.4 Exploitation/exploration : sur la dynamique de populations de taille finie, mais encore sur
un dosage délicat des modèles simplifiés.

Intuitivement, la sélection agit comme un opérateur de « pilotage », La modélisation des AE est un sujet théorique très complexe
de concentration, tandis que croisement et mutation ont plutôt une et très actif. Les enjeux théoriques et pratiques sont importants et
action d’éparpillement, d’exploration non dirigée. Ensemble, sélec- les thèmes majeurs sont :
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

tion et opérateurs génétiques (croisement/mutation) doivent donc • la convergence des AG et l’estimation d’une vitesse de conver-
garantir que la population se concentre dans des régions intéres- gence ;
santes de l’espace de recherche, où la fonction d’évaluation a des
valeurs élevées. Il existe néanmoins un risque de convergence pré- • la facilité ou difficulté des paysages de fitness pour un AE
maturée pour cause de perte de diversité génétique ou par dérive (étude des fonctions déceptives, des paysages de fitness,
génétique. NK-landscapes, analyse d’épistasie) ;
La mutation, plus encore que le croisement, joue un rôle de • le réglage des divers paramètres d’un AG ;
« dispersion » : il est démontré théoriquement que la mutation
permet de maintenir la diversité génétique de la population, et • le choix d’une bonne représentation.
ainsi de limiter l’effet de dérive génétique [87]. L’efficacité d’un AE
est donc liée au dosage subtil de ces composantes d’exploitation/ Trois grands courants de ce thème de recherche sont rapide-
concentration et d’exploration/dispersion, afin de converger le ment présentés ci-après.
plus rapidement possible vers l’optimum global de la fonction à
optimiser.
3.1 Approche intuitive : schémas,
À retenir théorème des schémas
• La base d’un AE classique d’optimisation est une boucle Bien qu’un AG manipule directement une population de codes
générationnelle faisant évoluer des populations d’individus au cours de son évolution, on peut comprendre globalement son
correspondant chacun à une solution. fonctionnement en considérant qu’il recherche et manipule impli-
• Cette boucle est composée de plusieurs étapes : sélection, citement des similarités entre codes (tout comme lorsque l’on
reproduction (croisement et mutation), évaluation et rempla- joue au jeu du « Master mind »). La formalisation de cette
cement. recherche de similarités entre codes est fondée sur la notion de
• Les individus peuvent être, par exemple, représentés sous schéma [50].
forme discrète (AE), continue (SE) ou fonctionnelle (PG).
En effet, l’évaluation individuelle d’un code donné contribue
• Chaque opérateur de la boucle contribue au délicat dosage
assez peu à comprendre dans quelle direction rechercher un meil-
entre exploitation et exploration.
leur code, même si celui-ci est bon : cette évaluation n’indique en
rien si une partie ou une caractéristique de ce code a contribué à
lui faire obtenir une bonne évaluation. La seule chose que l’on
peut en déduire est que des composantes bénéfiques sont pré-
3. Aperçu théorique : sentes dans ce code. On voit donc l’intérêt de traiter simultané-
ment une population de codes pour acquérir une information
pourquoi et comment ça générique par analyse de similarités.

marche ? La théorie des schémas a été développée à l’origine pour les AG

à chaînes binaires, puis a été étendue à d’autres représentations,
notamment à la représentation fonctionnelle [92].
La grande question est de savoir quand et comment utiliser effi-
cacement des AE, puisque ce sont des algorithmes d’optimisation Dans le modèle de représentation binaire, un schéma corres-
assez complexes à mettre en œuvre et relativement coûteux en pond à un sous-espace de l’espace de recherche ; par exemple, le

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 9

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

schéma 01##11#0 représente l’ensemble des codes binaires de

longueur 8 suivant (le caractère # représente soit un 0 soit un 1) :
# # # 0 01 # 1 # 0 # # #

Longueur
de définition = 7

Figure 7 – Longueur de définition d'un schéma

d’un schéma est longue, plus il a de chance d’être cassé par un

croisement.
Les schémas permettent de condenser de différentes manières ■ De même, l’effet de la mutation est lié à ce que l’on définit
des informations sur la fonction d’évaluation, et ce, sur l’espace comme l’ordre du schéma, c’est-à-dire le nombre de bits fixés du
de recherche en entier : un schéma, associé à son fitness moyen, schéma : (l’ordre du schéma de la figure 7 est 5, par
c’est-à-dire la moyenne des valeurs de fitness des codes qu’il
exemple). Si pm est la probabilité de mutation d’un bit (pm << 1),
représente, constitue une description simplifiée, mais globale, de
l’environnement. L’interprétation de fonctionnement associée à la probabilité pour un schéma d’être détruit est alors :
cette représentation simplifiée donne quelques intuitions sur les   .
raisons de la robustesse d’un AG [25].
Une interprétation du théorème des schémas consiste à dire que
Plus formellement, pour un code de longueur l défini par la les « bons » schémas, de longueur de définition courte et d’ordre
chaîne discrète prenant ses valeurs dans un alphabet V (pour un faible, ont tendance à croître exponentiellement dans la popula-
code binaire V = {0, 1}), un schéma est simplement une chaîne tion. L’idée qu’il faut minimiser la destruction de morceaux intéres-
dont l’alphabet est . Le caractère # représente indif- sants de solution implique par exemple que l’on doit rechercher
féremment un élément de l’alphabet du code. Pour un alphabet de des codages pour lesquels les bons schémas (de fitness moyen
taille k, il existe (k +1)l schémas possibles (3l dans le cas d’un élevé) sont aussi des schémas courts (longueur de définition et
alphabet binaire de longueur l). ordres faibles). Ce sont les fameux « building blocks » [38].
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

L’analyse de la variation du nombre de représentants de cer- Cette interprétation fournit des outils d’évaluation des représen-
tains schémas au sein d’une population au cours de l’évolution tations grâce à l’analyse de la nature des building blocks (notam-
donne des clés de compréhension sur les mécanismes de conver- ment en utilisant les fonctions de Walsh [40] [41] et permet
gence et sur les rôles des opérateurs génétiques [25] [38]. Il faut d’approcher la notion d’épistasie [25]. Cela permet en outre de
cependant comprendre que les schémas servent uniquement en construire des fonctions « difficiles » pour un AG : les fonctions
tant qu’outils pour expliquer la structure des codes et pour décrire « AG-déceptives ». Par exemple, les fonctions dont les optima
de façon compacte les similarités entre codes. sont isolés sont difficiles : les meilleurs points sont entourés par
les pires dans la topologie induite par le code.
Si l’on suppose qu’un schéma H apparaît avec une certaine fré-
quence m (H, t) dans la population à la génération t, le théorème
des schémas donne une borne sur l’espérance du nombre de
représentants d’un schéma H à la génération n + 1 pour le modèle 3.2 Analyse markovienne
de l’AG canonique (sélection proportionnelle, sans réétalonage,
croisement à un point et mutation binaire) et pour une population L’une des limitations des analyses fondées sur la théorie des
de taille infinie : schémas est l’hypothèse de population de taille infinie ; il est assez
vite devenu nécessaire d’avoir des modèles plus rigoureux et plus
précis. Si l’on considère la séquence des populations produites par
(1) un AE comme la réalisation d’un processus stochastique dans un
espace d’états fini, la façon dont est construit l’algorithme permet de
Les termes de cette inégalité traduisent les actions des diffé- dire que ce processus est markovien (une réalisation de ce proces-
rents opérateurs. sus ne dépend que de son état précédent) [27].
Les premiers travaux selon cette approche concernaient des
■ La sélection dépend de l’évaluation d’un schéma, mesurée par la modèles extrêmement simples, mais ils ont très vite permis de
valeur moyenne des évaluations de ses représentants dans la modéliser des comportements inaccessibles aux modèles à popu-
population courante, respectivement à la valeur moyenne de lation de taille infinie. Par exemple, Goldberg et Segrest [44] ont
proposé une modélisation d’un AG de population de taille finie,
fitness sur l’ensemble de cette population. Il faut préciser que
avec des chromosomes de longueur 1 ; ils ont abouti à une ana-
l’évaluation moyenne d’un schéma est une valeur artificielle qui
lyse de la dérive génétique. Le phénomène de dérive génétique,
indique grossièrement dans quelle direction continuer la recherche
connu et étudié depuis longtemps par les biologistes, a été mis en
au sein de l’espace de recherche (autrement dit, le sous-espace le
parallèle avec le comportement d’un AG sur une population de
plus intéressant à explorer). Le terme dit que plus un taille finie sans pression sélective. Cette compréhension du phé-
nomène de dérive n’est pas possible par la théorie des schémas,
schéma a une valeur moyenne élevée, plus il sera reproduit dans puisque ce phénomène est une conséquence directe de la mani-
la génération n + 1. pulation de populations de taille finie. Goldberg et Segrest ont
examiné en détail l’évolution de la dérive génétique en fonction
■ Dans cette approche, on ne sait modéliser les opérateurs géné- de la pression sélective, ce qui a permis de comprendre certains
tiques que par leur action destructrice (d’où le signe ≥ de l’équa- phénomènes de convergence prématurée, ainsi que le rôle fonda-
tion (1)). Un schéma de longueur l est détruit par le croisement à mental de l’opérateur de mutation pour limiter la dérive géné-
un point avec une probabilité , où δ(H) est la distance entre tique. En outre, leur étude de l’influence de la pression sélective
sur la probabilité de converger vers le bon optimum a permis de
le premier et le dernier bit fixé du schéma ; c’est la longueur de proposer des bornes pour la valeur de pression sélective – c’est
définition du schéma (figure 7). Plus la longueur de définition de là que vient la recommandation de fixer la pression sélective

S 7 218v2 – 10 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

entre 1,2 et 2 lorsque l’on fait un réétalonnage de la fonction • le débruitage multifractal de signaux et d’images [69] [75] ;
d’évaluation (section 2.3). • l’optimisation d’antennes fractales [22].
Les travaux de Davis et Principe [27] sur des chromosomes de
Ce succès est naturellement lié au fait que lorsque que l’on fait
longueur supérieure à 1 sont fondés sur un modèle simple à trois
une analyse d’un signal irrégulier, on est souvent confronté à des
opérateurs (sélection, croisement, mutation) avec une taille de
problèmes d’optimisation complexes, où les fonctions à optimiser
population finie, constante tout au long de l’évolution de l’AG. Ils
sont elles-mêmes très irrégulières, possèdent de très nombreux
considèrent cependant que les probabilités de mutation et de
maxima locaux et ne sont parfois ni dérivables, ni même conti-
croisement peuvent varier, ce qui leur a permis de dériver la
nues. Les méthodes stochastiques, et tout particulièrement les
contrainte sur la probabilité de mutation décrite en section 2.1.2
algorithmes évolutionnaires, sont bien adaptés à ces problèmes
et d’assurer la convergence en un temps infini si cette contrainte
d’optimisation.
est respectée.
Une approche similaire, mais moins directement utilisable, pro- D’un point de vue théorique, le fait de se placer dans un cadre
posée par Nix et Vose [87] a permis d’obtenir des résultats de fractal, c’est-à-dire de supposer que les signaux considérés pos-
convergence, mais en examinant le cas où la taille de la population sèdent certaines propriétés de régularité locale, permet d’analy-
varie au fur et à mesure de l’évolution de l’AG, les probabilités de ser plus précisément le comportement d’un modèle d’AE. Par
mutation et de croisement restant constantes. exemple, dans [67] [81] [77], l’étude concerne l’influence de
quelques paramètres d’AG canonique sur une mesure de décep-
Enfin, les travaux de Cerf [16] [17] proposent un cadre mathé- tivité, et fournit des indications sur la façon d’ajuster ces para-
matique plus général qui recoupe à la fois les résultats de mètres. Cela débouche sur un outil d’analyse de l’influence du
Davis et Principe et ceux de Nix et Vose. Cette approche permet codage des chromosomes dans un AG. Enfin, les travaux de
en plus de dériver une décroissance de la probabilité de muta- Landrin-Schweitzer et Lutton [63], fondés sur un modèle marko-
tion en fonction de la taille de la population, et ouvre la voie vien et une analyse multifractale, ouvrent la voie à une analyse
vers l’analyse de la vitesse de convergence d’un AG simple en des temps de convergence.
fonction de la complexité de la fonction à optimiser et de la
taille de population choisie.
À retenir
3.3 Analyse fractale, irrégularité • Les AE ont un fonctionnement complexe ; ils sont délicats
du fitness
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

à mettre en œuvre et relativement coûteux en temps de

calcul. C’est pourquoi il est important de comprendre quand
Dans le cadre de la modélisation d’AG comme systèmes et comment les utiliser efficacement.
dynamiques, des comportements « fractals » ont été mis en évi- • Il existe différentes approches théoriques qui fournissent
dence [53]. Cette approche a principalement permis de générer des éléments de compréhension des mécanismes de conver-
des images fractales (figures de stabilité) et l’aspect fractal des gence. Parmi celles-ci, la théorie des schémas, l’analyse
AG pourrait de ce fait éventuellement être considéré comme markovienne ou l’analyse fractale.
anecdotique. Mais le rapport entre algorithmes génétiques et
fractales va plus loin. En effet, s’il est vrai que les AE sont adap-
tés à l’optimisation de fonctions irrégulières en général, il est
difficile d’être plus précis sans spécifier le type d’irrégularité
auquel on s’intéresse. Or, la géométrie fractale se donne juste-
ment pour tâche de quantifier cette notion, et à l’intérieur d’une
4. Extensions du modèle
classe de fonctions définie par son irrégularité, il est possible
d’obtenir des résultats théoriques plus fins sur le comportement
d’un AE. 4.1 Nichage et paysages multimodaux
D’un point de vue général, la géométrie fractale doit sa célébrité Lorsque les fonctions à optimiser présentent plusieurs optima
principalement à ses aspects « graphiques », ces formes et images équivalents, l’AE classique converge aléatoirement vers un seul
fractales (ensembles de Julia ou de Mandelbrot, montagnes ou des optima. Or, dans de nombreuses applications, il est parfois
paysages fractals) qui possèdent une infinité de détails et des important de pouvoir détecter tous les optima, c’est-à-dire faire
propriétés dites d’autosimilarité. Il existe cependant d’autres aspects plus qu’une simple recherche de la solution optimale. Des exten-
de la géométrie fractale concernant l’analyse de signaux complexes sions de l’AE classique, copiées sur le phénomène naturel de
(qui ne sont pas nécessairement fractals) où les théories fractale et création de niches écologiques, sont fondées sur la gestion impli-
multifractale se sont montrées très utiles, avec des applications très cite ou explicite de sous-populations (ou de niches). Les schémas
variés comme en finance, en analyse de signaux, d’images ou de de partage de ressources (sharing) sont particulièrement intéres-
trafic dans les réseaux [113] [31]. sants : si les individus d’une même sous-population ont à partager
leurs ressources, la croissance de cette sous-population est limi-
tée, et lorsqu’il y a surpopulation, les individus tendent à recher-
Approche multifractale cher de nouvelles régions à coloniser.
Très brièvement, l’approche multifractale fournit à la fois des On peut séparer grossièrement les méthodes de nichage en deux
outils de quantification des irrégularités locales des signaux classes. La première classe [30] [83] comprend des techniques qui
considérés et des outils d’estimation de la fréquence d’apparition ont pour but de maintenir la diversité au sein de la population tout
de ces irrégularités locales. au long de l’évolution de l’algorithme, et qui, dans une certaine
mesure, favorisent la séparation en sous-populations. La seconde
classe de méthodes modifie la fonction d’évaluation pour simuler
Dans ce domaine, les algorithmes évolutionnaires se sont révé- un partage des ressources locales dans la population [38] [42].
lés des outils efficaces pour plusieurs applications « fractales » :
Ces méthodes ont été étudiées avec beaucoup d’attention dans
• la résolution du problème inverse pour les IFS [73] [82] [86] les années 1990-2000 et la capacité de la technique de partage à
[112] [117] [118], avec une application en modélisation de permettre la localisation de plusieurs bonnes solutions dans un
signaux de parole [111] ; espace de recherche a été démontrée en modélisant la suite des
• la compression d’images [3] [60] ; populations de l’AG comme une chaîne de Markov [51].

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 11

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

On note aussi l’existence de techniques qui créent explicitement figure 9a. En faisant agir un AG classique sur cette population de seg-
des sous-populations, comme [23], sur des processeurs séparés et ments (l’évaluation de l’adaptation à l’environnement d’un segment
échangent des individus entre ces sous-populations lorsque l’on est faite par comptage de points de contours de l’image en coïnci-
estime que ces sous-populations sont stabilisées (punctuated dence avec ce segment), on obtient une concentration de la popula-
equilibria), en créant ainsi une sorte de « catastrophe ». tion de segments comme celle de la figure 9b. Si l’on emploie une
technique de sharing, on obtient une convergence comme celle de la
Ces méthodes reposent toutes sur la définition d’une distance figure 9c. L’intérêt du sharing dans ce cas est évident puisqu’il
sur l’espace de recherche, calculée soit entre les chromosomes permet, par simple clusterisation de la population finale, de dégager
(distance génotypique), soit sur l’espace de recherche lui-même plusieurs segments en une fois sur l’image.
(distance phénotypique), et qui sert à définir le voisinage d’un
point de l’espace de recherche (où intervient le paramètre de taille
de voisinage σshare) (figure 8). Le partage peut être implanté en 4.2 Coopération/coévolution
divisant la fonction d’évaluation F par une mesure du nombre
d’individus dans la niche (ou le voisinage) mi de rayon L’idée de faire « plus que de l’optimisation » avec les AE est née
très tôt. Il a été vu précédemment qu’il est possible d’aborder des
σshare :  . problèmes d’optimisation multimodale. On peut aller plus loin et
formuler les problèmes comme des tâches d’apprentissage collec-
tif de façon à ce que la solution recherchée soit construite à partir
L’effet du partage est de séparer la population en sous-populations
de l’ensemble d’une population évoluée et non plus à partir du
de tailles proportionnelles à la hauteur des pics. Goldberg et
seul meilleur individu de la population finale.
Richardson ont montré qu’un AG avec partage se stabilise lorsque
Les thèmes les plus marquants de cette tendance sont les
 ( , k avec h et k des optima locaux différents) (figure 8). systèmes de classeurs (qui sont aussi une des bases historiques des
AG), l’approche parisienne, les techniques de coévolution proie/pré-
L’efficacité d’un partage dépend essentiellement du réglage du dateurs, et les techniques à base de colonies d’insectes sociaux,
paramètre de diamètre du voisinage σshare, qui règle la séparation dont les plus connus sont les ACO, algorithmes à colonies de four-
minimale entre deux pics détectés. Des méthodes d’estimation du mis [32] [33].
paramètre σshare ont d’ailleurs été proposées [29].
4.2.1 Systèmes de classeurs
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

Cette méthode de partage peut être complétée par une restric-

tion des croisements. En effet, si l’on examine l’évolution d’un AE
Un système de classeurs (SC ou classifier system) peut être défini
avec partage sur une fonction multimodale simple, on peut remar-
comme un système d’apprentissage qui apprend des règles syntac-
quer que certains individus dérivent entre deux optima. Cela est dû
tiques simples (appelées « classeurs ») pour guider ses performances
au fait que le croisement de deux individus appartenant à deux
niches différentes résulte rarement en un individu proche de l’un
des deux optima correspondants. Booker [7] a proposé de limiter
le croisement entre espèces différenciées en modifiant l’opérateur
de sélection. Goldberg et Richardson [42] ont prouvé sur des
fonctions multimodales simples que la restriction de croisement
(bien que plus coûteuse en temps de calcul) améliore l’efficacité du
partage des ressources.

Exemple
Pour illustrer cela, la figure 9 montre l’effet d’un sharing sur la
convergence d’une population (exemple tiré de [78]). L’application
consiste à détecter des segments sur des images de contours (les
contours sont dessinés en gris). On commence par initialiser aléatoi-
rement une population d’individus, des segments représentés sur la

a population initiale aléatoire

de segments
F(x)
xx
x x x xxx
x x x xx
x xx x
xx x
fmin
x xxx
x

x
2σshare Individu

Espace de recherche b convergence avec un algoritme c Convergence avec sharing

génétique classique
(80 générations)
Optima sélectionnés

Figure 8 – Répartition de la population dans un schéma de nichage Figure 9 – Effet du sharing sur la convergence d’une population

S 7 218v2 – 12 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

dans un environnement arbitraire [8] [38]. Un tel système manipule 4.2.2 Vie artificielle
des règles (ou classeurs) de la forme : SI < condition > ALORS
< action >. Différentes applications des SC comme les animats ouvrent la
voie à la simulation de comportements « intelligents » collectifs
Il est composé : ou individuels et à ce que l’on nomme la « vie artificielle ». Ce
• d’un système de règle et de messages ; domaine peut être actuellement considéré comme un domaine de
recherche à part entière, où les méthodes évolutionnaires jouent
• d’un système d’attribution de crédits ;
un rôle important.
• et d’un algorithme génétique (figure 10).
Les informations venant de l’environnement sont codées via
Animats
des détecteurs sous forme d’un ou de plusieurs messages de
taille finie. Ces messages provenant de l’environnement sont Les animats (pour « animaux artificiels ») sont des sys-
stockés dans la liste de messages et peuvent alors activer les tèmes qui doivent résoudre des problèmes simples, comme
règles ou classeurs. Lorsqu’il est activé, un classeur renvoie un trouver de la nourriture et éviter les obstacles, en construi-
message à la liste de messages. Ces messages peuvent alors à sant des modèles comportementaux fondés sur un ensemble
leur tour activer d’autres classeurs, ou bien déclencher une action de règles.
transmise à l’environnement par l’intermédiaire de déclencheurs.
De cette façon, le système combine des interactions avec l’exté-
rieur et des actions de « réflexion » internes, pour déterminer Nous n’entrerons pas dans la polémique de la définition de ce
quelle sera la prochaine action. En un sens, il coordonne les flux qu’est la vie artificielle, on se rapportera à une formulation [64] [13]
d’informations venant de l’extérieur (détecteurs) et les traitements due à Langton : « La vie artificielle est le champ d’études dédié à la
internes (liste de messages et population de classeurs) pour compréhension de la vie, qui essaie de trouver une abstraction des
effectuer des actions (déclencheurs). principes dynamiques fondamentaux mis en jeu dans les phéno-
mènes biologiques, en recréant cette dynamique dans d’autres
Un message dans un SC est simplement une chaîne de bits. Un milieux physiques (comme un ordinateur) les rendant ainsi acces-
classeur est une règle de production : < condition > : < action >, il sibles à un nouveau genre de manipulations expérimentales. » Plus
joue un rôle fondamental dans les échanges de messages. précisément, on peut dire que la vie artificielle regroupe les pro-
La condition est un système de reconnaissance des formes où grammes de recherche qui concernent les systèmes autonomes,
le caractère # a été ajouté à l’alphabet binaire (comme pour les leurs caractérisations et leurs modes spécifiques de survie.
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

schémas décrits en section 3.1, # correspond soit à un 0, soit à Dans ce cadre, les AE sont l’une des techniques employées pour
un 1). Une fois que la condition du classeur est remplie, ce clas- modéliser l’évolution des systèmes artificiels. Ainsi, les AE trouvent
seur devient candidat à poster son message dans la liste des leur utilité aussi bien en tant qu’outils pour résoudre des problèmes
messages à la prochaine étape. Le fait que le classeur délivre pratiques (d’optimisation, par exemple) qu’en tant que modèles de
effectivement son message est conditionné par le résultat d’une processus d’évolution [85].
sorte de tirage aléatoire fondé sur l’évaluation de la valeur (ou
poids) du classeur.
4.2.3 Approche parisienne
L’évaluation de la valeur d’un classeur est faite par le système
d’attribution des crédits tout au long de l’évolution du SC. Ce système Cette idée de coévolution peut aussi s’exploiter dans le cadre de
est un algorithme relativement complexe, appelé « bucket-brigade ». l’optimisation pure. Ce que l’on appelle actuellement l’approche
Schématiquement, pour toute action, il distribue la récompense ren- parisienne est une utilisation de ce concept [24] ; elle repose sur la
voyée par l’environnement aux classeurs qui ont été activés pour capacité des EA à attirer l’ensemble d’une population dans des
générer cette action [8]. zones quasi-optimales de l’espace de recherche. L’idée est donc
de fabriquer un paysage de fitness et un processus d’évolution où
l’ensemble de la population (ou du moins une grande partie)
représente la solution recherchée. Les individus ne représentent
plus une solution potentielle complète au problème posé, mais
une partie seulement de cette solution. La solution au problème
ENVIRONNEMENT est construite à partir de plusieurs individus de la population qui
« collaborent » pour produire la solution.
C’est donc bien une approche à relier aux autres techniques de
Système
coévolution : une population est une société qui construit en
de classeurs
commun la solution recherchée. Cependant, contrairement aux
approches de coévolution classiques, les espèces ne sont pas clai-
Algorithme rement identifiées ; on ne fonctionne pas sur un modèle proie/pré-
génétique dateur, par exemple.
Population Bien entendu, la spécification et le calibrage de tels algorithmes
de classeurs deviennent notablement plus complexes que dans le cas des
Information 10# : 111 approches évolutionnaires classiques, et la diversité des popula-
Détecteurs 00# : 000 Déclencheurs tions devient un facteur crucial pour le succès des méthodes
Action
101 #1# : 010 111 d’évolution parisienne. En outre, le fractionnement d’un problème
Récompense
Attribution en sous-problèmes interconnectés qui se prête à une approche
des crédits parisienne n’est pas toujours possible.
Liste de messages De façon schématique, les AE parisiens ont toutes les compo-
101 santes des AE classiques plus (figure 11) :
000 • deux fonctions de fitness : une fonction globale qui est calculée
111 sur l’ensemble de la population, ou sur une grande proportion
de celle-ci (par exemple à la suite d’un processus de clusterisa-
tion, ou d’élimination des individus trop mauvais), et une
Figure 10 – Schéma d'un système de classeurs fonction locale calculée sur chaque individu, qui mesure la

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 13

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

Pour aborder cela, on se fonde sur la notion de domination de

Génération
Pareto : pour deux solutions x1 et x2 au problème précédent, x1
de la population intiale
domine x2 (on écrit : ) si et seulement si :

Population
des « parents »
La solution au problème d’optimisation multicritère précédent
est donc un ensemble de solutions, formant ce que l’on nomme le
Sélection front de Pareto, qui est l’ensemble des solutions non dominées
dans l’espace de recherche. L’idée d’utiliser des AE pour trouver
le front de Pareto d’un problème multicritère a paru assez natu-
Croisements relle, mais cela nécessite de modifier légèrement le schéma évolu-
Création d’une nouvelle et mutations tionnaire classique. La procédure de sélection doit notamment
population de « parents » être adaptée de façon à pousser la population vers le front de
à partir de celle Pareto, tout en maintenant une bonne diversité afin d’assurer un
des « enfants » Population bon échantillonnage de celui-ci (éviter les solutions dégénérées
des « enfants » où toutes les solutions sont concentrées en un seul point du front
de Pareto).
En 2020, les méthodes NSGA (non-dominated sorting genetic
Calcul du fitness global et répartition algorithm) en versions II et III développées par Deb et ses collabo-
sur les individus de la population rateurs [28] sont reconnues comme les plus efficaces pour de
nombreux problèmes courants, le défi actuel étant ce que l’on
appelle le « many-objective », c’est-à-dire le cas où le nombre de
NON
Génération fonctions est grand [34] [18] [21].
de la population intiale
OUI
Génération 4.4 Approches interactives
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

de la population intiale
La tâche d’optimisation se complique sévèrement lorsque l’on
cherche à aborder des problèmes pratiques, et l’on est parfois
Figure 11 – Schéma d'un algorithme parisien : la sélection obligé de développer des stratégies spécifiques dans le cas où l’on
(dans l’ovale bleu clair) se fait sur un fitness
qui est la combinaison d'une contribution locale (fitness local) ne sait pas précisément définir « ce que l’on recherche. » C’est le
et d'une contribution globale (fitness global). La contribution cas, par exemple, pour les techniques d’optimisation multicritères,
globale est calculée à chaque génération (cadre orange) où une réelle optimisation multicritère s’impose lorsque l’on ne sait
sur l’ensemble de la population pas donner de poids relatifs aux différents critères en jeu (ce qui
permettrait par exemple de construire un unique fitness comme
combinaison pondérée des critères). Le problème se complique
proportion dans laquelle cet individu contribue à la solution encore lorsque l’on se trouve dans des cas où ce que l’on souhaite
globale ; optimiser n’est pas mesurable à l’aide d’une fonction mathéma-
tique (un jugement esthétique ou la simple notion de « satisfaction
• un processus de redistribution qui répartit à chaque généra- de l’utilisateur ») ; il devient nécessaire de faire intervenir un utilisa-
tion le fitness global sur les individus ayant contribué à la teur humain dans la boucle évolutionnaire. Cela a donné naissance
solution ; à un courant dit d’« algorithmes évolutionnaires interactifs » très
• un mécanisme de maintien de la diversité, afin d’éviter les attrayant, car touchant des domaines d’application très variés.
modes dégénérés où tous les individus sont concentrés sur la Les premiers travaux sur le sujet [102] [108] [2] [66] étaient
même zone de l’espace de recherche. orientés vers la création artistique et la synthèse d’images numé-
Cette approche a permis de nombreuses applications, et notam- riques. De nombreuses études touchent maintenant des domaines
ment des applications en fouille de texte [61] [62], en imagerie d’application très divers, où les quantités à optimiser sont liées à
médicale [114] [115], dans le domaine artistique [20] et en vision des jugements subjectifs (visuels ou auditifs) et sont clairement
robotique temps-réel (vision stéréo par algorithme des mouches dans la tendance actuelle qui vise à recentrer les systèmes infor-
[70] [71]), ce qui est tout à fait notable pour des algorithmes ayant matiques sur leurs utilisateurs (autrement dit à mettre réellement
une réputation d’extrême gourmandise en temps de calcul. le système artificiel au service de l’humain). Des travaux tout à fait
caractéristiques sur le sujet sont par exemple [107] pour l’adapta-
tion de prothèses auditives, [54] pour le développement de lois de
contrôle de bras de robot qui correspondent à des mouvements
4.3 Multiobjectif souples, proches de l’humain et psychologiquement bien perçus
par l’utilisateur, ou pour le design de pages Web [88]. On pourra
Se poser des questions liées à l’optimisation conduit souvent à trouver une revue de ce vaste sujet dans [104] [106].
se poser le problème de l’identification précise de ce que l’on sou-
haite optimiser. Cela est particulièrement important dans des cas La définition initiale des algorithmes évolutionnaires interactifs
complexes où il existe par exemple plusieurs critères de juge- (AEi ou iEC) en tant qu’AE dont le fitness est donné par une interac-
ment, parfois non compatibles entre eux (maximiser la résistance tion humaine a été maintenant étendue à une notion plus complète
d’une pièce mécanique, tout en minimisant son poids et son coût de l’interaction humain-machine au sein de l’AE [10]. Le fitness
de fabrication, par exemple). Ces optimisations sont d’autant plus peut n’être établi que partiellement par interaction ; des interven-
complexes à traiter que l’on ne sait pas forcément estimer les tions de l’utilisateur directement au niveau des génomes, des opé-
poids relatifs des divers critères et contraintes en jeu. On parle rateurs génétiques, des paramètres et diverses stratégies peuvent
alors non plus d’optimisation simple, mais d’optimisation multi- être envisagées.
critère : minimiser (f1(x), f2(x), …, fn(x)), sans donner de priorité Une définition des AEi pourrait être raisonnablement : « un AE
relative entre les divers critères. où le processus évolutionnaire est contraint par une interaction

S 7 218v2 – 14 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

avec un utilisateur humain ». Les AE ont accès uniquement à un techniques d’apprentissage (réseaux de neurones, évolution de
espace de paramètres n’ayant pas de signification précise, excep- langages, grammaires et plus récemment, deep learning).
tée celle qui peut être traduite en termes de fitness automatique
(que l’on passe ou non par un espace « phénotypique » intermé- ■ En informatique : où les gens s’intéressent plus particulièrement
diaire). L’évaluation subjective produite par un utilisateur humain à la parallélisation des AE, au design de langages de spécification,
peut soit remplacer ou compléter ce fitness automatique, soit à leur implantation efficace ; sont aussi traités des problèmes
intervenir dans chacune des composantes du système évolution- d’allocation de ressources ou de test de logiciel.
naire (initialisation, moteur évolutionnaire, variations de structure ■ En robotique : où l’on s’intéresse aux MOBOTS (mobile robots)
du génome, paramétrisation). et autres animats, individuellement ou en population, qui doivent
En outre, l’interaction avec l’humain pose plusieurs problèmes, pouvoir se mouvoir et agir dans des environnements inconnus,
que l’on peut lier à ce que l’on appelle le « goulot d’étranglement variables et accomplir des tâches complexes.
de l’utilisateur » [91], autrement dit, la lassitude de celui-ci. Dans de
tels systèmes d’optimisation, il faut trouver des moyens d’éviter ■ En physique et en ingénierie : source de nombreux problèmes
des interactions répétitives, ennuyeuses ou mal perçues de l’utilisa- réels complexes, par exemple pour la modélisation ou l’optimisation
teur [9]. Le travail de l’artiste Steven Rooke [119] montre bien par de structures mécaniques [45] [68] [110] de profils d’ailes d’avion, de
exemple la quantité impressionnante d’interactions nécessaires à tuyères de réacteurs, ou de processus chimiques industriels.
l’apparition d’images esthétiques lorsque l’on part d’une « soupe ■ En économie et en finance : pour la simulation d’économies arti-
primordiale » de composantes primitives. Les techniques propo- ficielles (systèmes à base d’agents), l’optimisation de portefeuilles
sées pour rendre les interactions plus efficaces sont par exemple bancaires.
[5] [91] [105] :
• de réduire la taille des populations et du nombre de généra- ■ En traitement d’images, du signal, pour détecter des formes
tions ; caractéristiques, problème que l’on peut comprendre soit comme
une optimisation, soit comme une application de règles de déci-
• de choisir des modèles spécifiques pour contraindre la sion (SC), en vision stéréo [72], en débruitage d’images [76].
recherche dans des zones a priori intéressantes de l’espace
de recherche ; ■ En biologie et en médecine, pour certaines tâches de séquence-
ment du génome, dans l’analyse du repliement de protéines, en
• de faire de l’apprentissage automatique (fondé sur un analyse de données et imagerie médicale [114].
nombre limité de quantités caractéristiques) sur la base
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

des votes antérieurs de l’utilisateur afin de proposer une ■ En agronomie et en agroalimentaire [79].
prénotation automatique des individus et de ne présenter à
À titre d’exemple, deux applications en vision robotique et
l’interaction que les individus les plus intéressants de la
design graphique sont détaillées ci-après.
population [80] [15].

À retenir 5.1 Vision stéréo pour la robotique :

l’algorithme des mouches
• Le nichage traite le cas de l’optimisation multimodale (trou-
ver simultanément des solutions équivalentes). Dans l’approche parisienne, la représentation de la solution
• La coopération-coévolution (l’approche parisienne, en parti- d’un problème est répartie sur l’ensemble de la population. Cette
culier) fractionne un problème en un ensemble de sous- approche sert de base à l’algorithme des « mouches » conçu pour
problèmes interconnectés pour rendre l’évolution plus efficace. les applications de reconnaissance des formes. L’application de
• L’optimisation évolutionnaire multiobjectif utilise la notion cette méthode au problème de stéréovision permet d’obtenir une
de dominance de Pareto pour proposer un ensemble de analyse 3-D de la scène de manière élégante et rapide, exhibant
compromis. une capacité inattendue des AE à traiter des problèmes en
• L’optimisation interactive permet de prendre en compte « temps réel », notamment dans les systèmes mobiles robotisés
des quantités subjectives, non calculables. où la puissance de calcul disponible est réduite [11].
Une « mouche » est un point 3D de la scène, représenté par ses
trois coordonnées (x,y,z). La population des mouches est initiali-
sée aléatoirement dans le champ de vision des caméras, puis sou-
5. Exemples d’application mise à un algorithme d’évolution dont le but est de faire
converger le plus grand nombre possible de mouches sur les sur-
faces des objets de la scène (figure 12). Pour cela, le fitness de
Les EA touchent des domaines d’application extrêmement chaque mouche évalue sa conformité aux données : si la mouche
variés, et intéressent des chercheurs et des ingénieurs de disci- est posée sur un objet, ses projections sur les caméras droite et
plines très diverses. gauche sont corrélées (car elles correspondent à un même point
physique) (figure 13). Le calcul du fitness se réduit donc à deux
■ En optimisation numérique : lorsque les fonctions à optimiser calculs géométriques (le calcul des projections de la mouche) et
sont complexes, de grandes dimensionnalités, irrégulières, mal une corrélation de voisinage sur les images gauche et droite.
connues. L’algorithme est complété par des opérateurs génétiques de
facture assez classique dans les stratégies d’évolution : mutation
■ En optimisation combinatoire : pour des problèmes de théorie adaptative, croisement à deux parents, croisement à trois parents,
des graphes (voyageur de commerce, coloration de graphes), de ainsi qu’un opérateur de sharing jouant un rôle de régularisation
séquencement de tâches, de répartition de ressources, d’emploi du en empêchant les trop fortes concentrations locales de mouches.
temps, du sac à dos, dont la résolution efficace est fondée le plus
souvent sur des AE hybridés avec des techniques « classiques ». Après les premiers essais sur des couples d’images stéréosta-
C’est dans ce cadre que de nombreuses études ont été menées sur tiques (synthétiques et naturelles), et en vue d’une application en
la représentation des problèmes et le traitement des contraintes. robotique, la méthode a été testée avec succès sur des séquences
stéréodynamiques, où les mouches jouent le rôle de support de la
■ En intelligence artificielle et sciences cognitives : où l’on exploite représentation de l’environnement dans le robot et tirent parti
plutôt les capacités adaptatives des AE en hybridation avec des efficacement de la continuité temporelle de la scène. Ainsi, il n’est

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 15

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

Couple Stéréo

Initialisation
Reconstruction

Évaluation

Paramètres
des caméras Sélection

Paramètres
Évolution
génétiques

Figure 12 – Algorithme des mouches pour la vision stéréo : chaque individu de la population est un point 3D (x, y, z), une « mouche ».
L’évolution de cette population a pour but de positionner les mouches sur les surfaces visibles de la scène

5.2 Exploration artistique, exemple

du logiciel ArtiE-Fract
b1 A
a1 Les formes fractales sont des objets artistiques attrayants, car elles
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

combinent complexité et structure « hiérarchique » non triviale, mais

B la théorie mathématique sous-jacente est assez complexe et ne per-
b2 met pas une manipulation directe de ces formes. ArtiE-Fract est un
a2
logiciel interactif élaboré à partir d’un algorithme évolutionnaire, de
façon à faciliter pour le non mathématicien et le non informaticien la
création de telles images.
Figure 13 – Évaluation des mouches par projection : la mouche B, L’utilisateur (l’artiste) contrôle une recherche aléatoire dans
positionnée sur un objet physique de la scène, est projetée en b1 l’espace des formes fractales et l’algorithme évolutionnaire s’efforce
et b2 sur les caméras gauche et droite, respectivement. Les pixels
situés autour de b1 et b2 sont corrélés. Au contraire, la mouche A de s’approcher de ce que l’utilisateur recherche précisément ou intui-
qui n’est pas « posée » sur un objet a des images a1 et a2 non tivement, par le biais de l’analyse des évaluations successives
corrélées, qui ne correspondent pas au même point d’ensembles d’images qui lui sont présentées. Cette idée d’approche
aléatoire évolutionnaire n’est pas neuve (voir par exemple les tra-
vaux de [102] ou de William Latham [109] dans le domaine de la syn-
pas nécessaire (ni souhaitable) de réinitialiser la population à thèse graphique).
chaque nouvelle image : une fois obtenue la convergence initiale, La valeur ajoutée du système ArtiE-Fract est une interaction directe
la population de mouches est capable de suivre de manière conti- très poussée, grâce aux modèles d’images fractales employés (les
nue le déplacement relatif des objets dans la scène [12]. De plus, le systèmes de fonctions itérées – ou IFS – non linéaires) de façon à
fitness étant calculé pour chaque mouche à l’aide des données- faciliter la démarche créatrice. Ainsi, deux modes d’interaction sont
image disponibles les plus récentes, l’algorithme n’est pas disponibles à tout moment dans ArtiE-Fract :
contraint par le cadencement de la délivrance des images par les
caméras (algorithme asynchrone), ce qui lui permet d’exploiter • une interaction « passive », où l’utilisateur donne des notes
pleinement l’asynchronisme naturel des imageurs CMOS, contrai- aux images qui lui sont présentées à l’écran (recherche aléa-
rement aux algorithmes classiques de stéréovision [96]. toire orientée) ;
Si cette méthode ne prétend pas être aussi performante (du • une interaction « directe », où les images peuvent être mani-
moins en termes de précision et d’exhaustivité d’analyse) que les pulées de façon non triviale : modifiées colorimétriquement
méthodes classiques de stéréovision basées sur une segmentation ou structurellement, ou même distordues géométriquement
préalable et une mise en correspondance de primitives, elle permet via des points de contrôle. Divers types de morphings et de
d’obtenir des résultats immédiats et de qualité progressive, même transformations sont en outre accessibles pour créer des
avec une puissance de calcul réduite, ce qui la rend particulière- animations. Cette interaction « directe » est intégrée au sein
ment bien adaptée aux applications en robotique mobile. Elle a été de la boucle évolutionnaire comme mutation « interactive ».
expérimentée pour l’évitement d’obstacles en robotique mobile L’interaction directe au niveau des phénotypes donne un contrôle
[89], ce qui a été l’occasion d’y ajouter plusieurs fonctionnalités : plus complet à l’utilisateur (l’artiste), de façon à rendre le concept
• la fusion de capteurs extéroceptifs par l’ajout d’un terme sup- classique d’AE interactif plus souple dans le cadre de la création
plémentaire par capteur dans le fitness ; artistique. L’idée est d’exploiter les capacités de recherche aléatoire
d’un EA pour assister l’artiste.
• la fusion de capteurs proprioceptifs (mouvement propre du
Une autre caractéristique d’ArtiE-Fract est la disponibilité d’un
robot) par mise à jour continue des positions des mouches ;
mode d’évolution parisienne : à tout instant de l’évolution, un méca-
• la génération de commandes d’évitement d’obstacles par nisme permet de passer du mode parisien au mode global ou inver-
adaptation de méthodes classiques de planification (méthodes sement, ce qui donne une grande souplesse dans le contrôle du
par potentiels) à la représentation particulaire des obstacles. comportement plus ou moins aléatoire (« mélangeant ») du système.

S 7 218v2 – 16 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

Figure 14 – Quelques images générées avec ArtiE-Fract

ArtiE-Fract a été élaboré avec soin pour permettre au designer

d’utiliser une large variété de stratégies et de paramètres de
contrôle prédéfinis, tout en lui laissant la possibilité, s’il le sou-
haite, de les régler directement lui-même pour ses besoins spéci-
fiques. ArtiE-Fract donne ainsi un accès souple et convivial à des
modèles classiques de fractales (formes autoaffines), mais aussi
et surtout à des images fractales peu courantes (des systèmes de
fonctions itérées non linéaires) [74].

À retenir
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

• Les algorithmes évolutionnaires sont utilisés dans de nom-

breux domaines pour l’optimisation de fonctions complexes,
mais aussi pour d’autres tâches (apprentissage, modélisation,
exploration, recherche de compromis).
• L’algorithme des mouches est un algorithme évolution-
naire de coopération-coévolution qui permet de traiter très Figure 15 – Œuvre de l’artiste Emmanuel Cayla avec ArtiE-Fract
rapidement le problème de la vision stéréo (reconstruction
d’une information de profondeur à partir de deux images).
• ArtiE-Fract est un AE interactif permettant d’explorer un Cela amène à revenir et à insister sur l’importance de la repré-
espace de formes fractales sur des critères esthétiques. sentation des solutions et du design des opérateurs associés. Ces
algorithmes, pour être vraiment efficaces, ne doivent pas être
considérés comme une boîte noire (ou une roue de secours !) : s’il
est facile de fabriquer un algorithme évolutionnaire de base, il est
aussi facile d’en faire un gaspilleur de ressources (temps de calcul,
6. Conclusion espace mémoire et autres). À cet égard, il est toujours très forma-
teur de comparer son algorithme évolutionnaire à un algorithme
de recherche aléatoire pure, pour en évaluer l’efficacité... En
Après avoir vécu un fort effet de mode dans les années 1990-2000, résumé, faire un algorithme évolutionnaire efficace est souvent
le domaine des algorithmes évolutionnaires reste remarquablement complexe, car cela nécessite de comprendre précisément aussi
actif. bien le domaine d’application concerné que les subtilités des
mécanismes évolutionnaires.
• Au niveau théorique : des travaux importants, essentielle-
ment en ce qui concerne l’étude de la convergence de ces
algorithmes (modélisation par chaînes de Markov), ont per-
mis de poser des bases solides pour ces techniques, initia-
lement critiquées à cause de leur aspect « empirique ». Ces 7. Remerciements
approches fournissent un cadre théorique riche, qui permet
de raffiner bon nombre d’analyses de convergence et L’auteure tient à remercier pour leur aide Messieurs Jean Louchet
d’efficacité. et Amine Boumaza, auteurs de la méthode décrite dans la sec-
• Au niveau applicatif : les domaines d’application sont très tion 5.1, qui l’ont aimablement autorisée à reproduire les figures 12
variés, et ces algorithmes sont largement utilisés en recherche et 13, ainsi que Monsieur Emmanuel Cayla qui lui a permis de
et dans le milieu industriel. reproduire l’une de ses œuvres en figure 15.

D’un point de vue expérimental, on constate que ces algorithmes

sont efficaces pour effectuer une recherche au sein d’espaces multi-
dimensionnels difficiles et irréguliers, en limitant le risque de conver-
gence prématurée. D’un autre côté, vu leur coût calculatoire, il est
8. Glossaire
inefficace de vouloir appliquer un AE dans des cas où des techniques
comme les méthodes de gradients marchent bien, ce qui fonde une Adaptation à l’environnement ; fitness
recommandation classique consistant à dire : « Employez les AG Fonction optimisée par un algorithme évolutionnaire, utilisée au
lorsque rien d’autre ne marche » ! sein de l’opérateur de sélection. Aussi appelée « fonction d’évaluation »,

Copyright © – Techniques de l’Ingénieur – Tous droits réservés S 7 218v2 – 17

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

ou de « performance ». Il n’est pas nécessaire qu’elle soit continue Optimisation multiobjectif ; multi-objective optimisation (MOO)
ou dérivable.
Optimisation permettant de prendre en compte plusieurs cri-
Algorithme évolutionnaire (AE) ; evolutionary algorithm (EA) tères sans les prioriser, fondée sur la notion de dominance de
Nom générique pour les heuristiques ou les algorithmes d’opti- Pareto. Ces algorithmes font évoluer un ensemble de solutions
misation stochastique s’inspirant de la théorie de l’évolution vers le front de Pareto, c’est-à-dire l’ensemble des solutions non
darwinienne. dominées, représentant tous les compromis optimaux entre les
différents critères.
Algorithme à estimation de distribution ; estimation of distribu-
tion algorithm (EDA) Pression sélective ; selective pressure
Heuristique d’optimisation opérant sur un espace continu (réels) Paramètre essentiel de l’opérateur de sélection dans un algo-
et faisant évoluer une distribution représentant la probabilité de rithme évolutionnaire. Il a une influence sur l’équilibre explora-
trouver l’optimum dans une région donnée. Des populations succes- tion/exploitation de l’algorithme, et par ricochet sur le compromis
sives sont produites par échantillonnage de la distribution. L’algo- vitesse de convergence/précision du résultat.
rithme CMA-ES (covariance matrix adaptation evolution strategy)
fait partie de cette catégorie. Programmation génétique (PG) ; genetic programming (GP)
Algorithmes à colonies de fourmis ; ant colony optimisation Algorithme évolutionnaire fondé sur une représentation fonc-
(ACO) tionnelle (usuellement codés sous forme d’arbres de tailles
Algorithmes d’optimisation à base de populations, inspirés du variables). L’espace de recherche est alors l’espace des expres-
comportement de fourmis recherchant un chemin entre leur colonie sions que l’on peut construire à partir d’un jeu fixé d’opérateurs,
et une source de nourriture. de variables et de constantes.
Algorithme génétique (AG) ; genetic algorithm (GA) Stratégies évolutionnaires (SE) ; evolution strategies (ES)
Algorithme d’optimisation utilisant les principes darwiniens de Algorithme d’optimisation numérique opérant sur un espace de
sélection, variations par croisement/mutation, et transmission, recherche continu, utilisant lui aussi les principes darwiniens.
développé à l’origine pour des espaces de recherche discrets
(chaînes binaires, par exemple). Vie artificielle ; artificial life
Évolution interactive ; interactive evolution, interactive evolutio- « La vie artificielle est le champ d’études dédié à la compréhen-
nary computation (iEC) sion de la vie, qui essaie de trouver une abstraction des principes
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

dynamiques fondamentaux mis en jeu dans les phénomènes bio-

Algorithme évolutionnaire dans lequel le processus est contraint
logiques, en recréant cette dynamique dans d’autres milieux phy-
par une interaction avec un utilisateur humain, visant à optimiser
siques (comme un ordinateur) les rendant ainsi accessibles à un
une fonction qui dépend de jugements subjectifs (évaluations esthé-
nouveau genre de manipulations expérimentales. » [64].
tiques, par exemple).
Coopération-coévolution ; cooperative co-evolution
Algorithmes de résolution de problèmes à base d’AEs où la
solution au problème est construite à partir de plusieurs individus
qui « coopèrent » pour produire une solution. Il existe deux
9. Sigles, notations
grandes tendances : les approches multipopulations où l’évalua- et symboles
tion d’un individu d’une population dépend de l’état d’un ou de
plusieurs individus d’autres populations, et les approches mono-
populations où les individus coopèrent au sein d’une même popu-
lation. L’ensemble de la population – ou une grande partie de
celle-ci – représente alors la solution recherchée. L’approche pari- AE Algorithme évolutionnaire
sienne appartient à cette dernière catégorie.
AEi Algorithmes évolutionnaires interactifs
Évolutionisme ; evolutionism
Théorie de l’évolution des populations naturelles. La théorie AG Algorithmes génétiques
fondatrice fut exposée par Charles Darwin dans son ouvrage On
the Origin of Species by Means of Natural Selection, or the Preser- BLX Blend crossover, croisement par mélange
vation of Favoured Races in the Struggle for Life (De l'origine des
CMA-ES Covariance matrix adaptation evolution strategy
espèces au moyen de la sélection naturelle, ou la préservation des
races favorisées dans la lutte pour la vie), dont la première édition EA Evolutionary algorithm, algorithme évolutionnaire
parut en 1859. Une théorie synthétique de l’évolution, ou synthèse
néodarwinienne, fut ensuite élaborée aux XIXe et XXe siècles, inté- ES Evolution strategy, stratégies évolutionnaires
grant des connaissances sur la génétique des populations, l’héré-
dité, l’épigénétique et la biologie moléculaire. GP Genetic programming
Le terme anglais « evolutionism » est souvent opposé au créa-
tionisme (creationism) qui fait référence au débat théologique sur iEC Interactive evolutionary computation
l’origine des espèces (encore actuellement très présent outre-
Atlantique, par exemple). NSGA Non-dominated sorting genetic algorithm
Opérateurs génétiques ; genetic operators PG Programmation génétique
Opérateurs de variation agissant sur les individus d’une popula-
tion d’un algorithme évolutionnaire : le croisement mélange les SC Système de classeurs
informations provenant de deux individus et la mutation introduit
SE Stratégie d'évolution
une petite perturbation sur un individu.

S 7 218v2 – 18 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

P
O
U
Algorithmes génétiques, R
algorithmes évolutionnaires
E
N
par Évelyne LUTTON

S
Directrice de recherche INRAE
UMR MIA 518, AgroParisTech/INRAE
Institut des systèmes complexes, 113 rue Nationale, 75013, Paris, France.
A
Sources bibliographiques
V
[1] ALTENBERG (L.). – Evolutionary Computation [13] BOURGINE (P.) et VARELA (F.J.). – Towards A Problem Solving, Genetic Programming and
O
I
Models from Population Genetics, Part 2: An Practice of Autonomous Systems, in Towards Evolvable Machines Journal, 1(4), pp. 339-
Historical Toolbox, in Congress on Evolutionary A Practice of Autonomous Systems: Procee- 361 (2000).
Computation (2000). dings of the First European Conference on [25] DAVIDOR (Y.). – Genetic Algorithms and

R
[2] ANGELINE (P.J.) et POLLACK (J.B.). – Artificial Life, Paris, France, pp. xi-xvii (1991). Robotics. A heuristic Strategy for Optimiza-
Competitive Environments Evolve Better So- [14] BULL (L.) et FOGARTY (T.C.). – Co-evolving tion. Teaneck, NJ: World Scientific (World
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

lutions for Complex Tasks, in Proceedings of Communicating Classifier Systems for Scientific Series in Robotics and Automated
the Fifth International Conference on Genetic Tracking, in, pp. 522-527 (1993). Systems - vol. 1) (1991).
Algorithms, San Mateo, California: Morgan [15] CANCINO (W.), BOUKHELIFA (N.) et LUTTON [26] DAVIS (L.). – Genetic Algorithms and Simu-
Kaufmann (1993). (E.). – EvoGraphDice: Interactive Evolution for lated Annealing, Pittman, London (1987).
[3] GOERTZEL (B.). – Fractal image compression
with the genetic algorithm, Complexity Inter-
national, 1 (1994).
Visual Analytics, in IEEE Congress on Evolu-
tionary Computation, June 10-15 (2012).
[27] DAVIS (T.E.) et PRINCIPE (J.C.). – A Simu-
lated Annealing Like Convergence Theory for P
L
[16] CERF (R.). – Une théorie asymptotique des the Simple Genetic Algorithm, in Procee-
[4] BAECK (T.), HOFFMEISTER (F.) et SCHWEFEL Algorithmes Génétiques, PhD Thesis, Uni- dings of the Fourth International Conference
(H.P.). – A Survey of Evolution Strategies, in versité Montpellier II (1994). on Genetic Algorithm, pp. 174-182 (1991).

U
International Conference on Genetic Algo- [17] CERF (R.). – Artificial Evolution, European [28] DEB (K.) et al. – A Fast Elitist Non-Dominated
rithms, pp. 2-10 (1991). Conference, AE 95, Brest, France, September Sorting Genetic Algorithm for Multi-Objective
[5] BANZHAF (W.). – Handbook of Evolutionary 1995, Selected papers, in Springer Verlag, Optimization: NSGA-II, in Schoenauer, M. et

S
Computation, in Oxford University Press pp. 37-54 (1995). al. (eds) Parallel Problem Solving from Nature
(1997). [18] CHAND (S.) et WAGNER (M.). – Evolutionary - PPSN VI 6th International Conference, Paris,
[6] BEN HAMIDA (S.). – Algorithmes évolution- many-objective optimization: A quick-start France: Springer Verlag (2000).
naires : prise en compte des contraintes et guide, Surveys in Operations Research and [29] DEB (K.) et GOLDBERG (D.E.). – An investigation
applications réelles, PhD Thesis, Université Management Science, 20(2), pp. 35-42, doi: of niche and species formation in genetic func-
Pris-Sud XI, spécialité informatique (2001). 10.1016/[Link].2015.08.001 (2015). tion optimization, in Proceedings of the third
[7] BOOKER (L.B.). – Recombination Distribu- [19] CHANG-YONG (L.) et XIN (Y.). – Evolutionary Conference on Genetic Algorithms, ICGA89,
tions for Genetic Algorithms, in FOGA-92, programming using mutations based on the pp. 42-50 (1989).
Foundations of Genetic Algorithms, Vail, Levy probability distribution, IEEE Transactions [30] DEJONG (K.A.). – The Analysis of the Beha-
Colorado (1992). on Evolutionary Computation, 8(1), pp. 1-13 vior of a Class of Genetic Adaptive Systems.
[8] BOOKER (L.B.), GOLDBERG (D.E.) et HOLLAND (2004). PhD Thesis. University of Michigan (1975).
(J.H.). – Classifier Systems and Genetic Algo- [20] CHAPUIS (J.) et LUTTON (E.). – ArtiE-Fract : [31] DEKKING (M.) et al. – Fractals : Theory and
rithms, Artificial Intelligence, 40(1-3), pp. 235- Interactive Evolution of Fractals, in 4th Interna- Applications in Engineering, Springer Verlag
282 (1989). tional Conference on Generative Art. Milano, (1999).
[9] BOUKHELIFA (N.) et al.. – Evolutionary Visual Italy (2001). [32] DORIGO (M.) et DI CARO (G.). – The Ant
Exploration: Evaluation With Expert Users, in [21] COELLO COELLO (C.A.) et al. – Evolutionary Colony Optimization Meta-Heuristic, New
EuroVis 2013, 15th annual Visualization multiobjective optimization: open research Ideas in Optimization, pp. 11-32 (1999).
Symposium (2013). areas and some challenges lying ahead, [33] DORIGO (M.), DI CARO (G.) et GAMBAR-
[10] BOUKHELIFA (N.) et al.. – Evolutionary Visual Complex & Intelligent Systems, 6(2), pp. 221- DELLA (L.M.). – Ant Algorithms for Discrete
Exploration: Evaluation of an IEC Framework 236, doi: 10.1007/s40747-019-0113-4 (2020). Optimization, Artificial Life, 5(2), pp. 137-172
for Guided Visual Search, Evolutionary [22] COHEN (N.). – Antennas in Chaos : Fractal- (1999).
computation (2015). Element Antennas, in Fractals in Engineering [34] FLEMING (P.J.), PURSHOUSE (R.C.) et
[11] BOUMAZA (A.) et LOUCHET (J.). – Dynamic 97, INRIA (1997). LYGOE (R.J.). – Many-Objective Optimiza-
Flies: Using Real-Time Parisian Evolution in [23] COHOON (J.P.), MARTIN (W.N.) et RICHARDS tion: An Engineering Design Perspective, in
Robotics, in Springer Verlag, L. 2038 (ed.) (D.S.). – Genetic algorithms and punctuated COELLO COELLO (C.A.), HERNÁNDEZ
EVOIASP2001 (2001). equilibria in VLSI, in Schwefel, H.-P. and AGUIRRE (A.), and ZITZLER (E.) (eds) Evolu-
[12] BOUMAZA (A.M.) et LOUCHET (J.). – Mobile Männer, R. (eds) Parallel Problem Solving tionary Multi-Criterion Optimization. Berlin,
Robot Sensor Fusion Using Flies, in Raidl, from Nature - Proceedings of 1st Workshop, Heidelberg: Springer Berlin Heidelberg,
G. R. et al. (eds) Applications of Evolutionary PPSN 1, Dortmund, Germany: Springer- pp. 14-32 (2005).
Computing, EvoWorkshops2003: EvoBIO, Verlag, Berlin, Germany (Lecture Notes in [35] FOGEL (D.B.). – An Analysis of Evolutionary
EvoCOP, EvoIASP, EvoMUSART, EvoROB, Computer Science), pp. 134-144 (1991). Programming, in FOGEL (D. B.) and
EvoSTIM, University of Essex, England, UK: [24] COLLET (P.) et al. – Polar IFS + Parisian ATMAR (W.) (eds) Proceedings of the First
Springer-Verlag (LNCS), pp. 357-367 (2003). Genetic Programming = Efficient IFS Inverse Annual Conference on Evolutionary Pro-

Copyright © – Techniques de l’Ingénieur – Tous droits réservés Doc. S 7 218v2 – 1

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

P ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

O
U gramming,La Jolla, California, pp. 43-51 Report 93002, Department of General Enginee- [69] LÉVY VÉHEL (J.) et LUTTON (E.). – Evolutio-

R [36]
(1992).
FOGEL (D.B.). – Asymptotic Convergence
ring, 117 Transportation Building, 104 South
Mathews Avenue, Urbana, IL 61801-2996: Uni-
versity of Illinois at Urbana Champaign (1993).
nary signal enhancement based on Hölder
regularity analysis, in EVOIASP2001
Workshop, Como Lake, Italy, Springer Ver-
Properties of genetic Algorithms and Evolu-
tionary Programming: Analysis and Experi- [52] HUSBANDS (P.) et MILL (F.). – Simulated Co- lag, LNCS 2038 (2001).
ments, in Journal of Mathematical Biology Evolution as The Mechanism for Emergent [70] LOUCHET (J.). – Using an Individual Evolu-

E
(1992). Planning and Scheduling, in, pp. 264-270 tion Strategy for Stereovision, Genetic Pro-
[37] GANDOMI (A.H.), ALAVI (A.H.) et RYAN (C.). (1991). gramming and Evolvable Machines Journal,
– Handbook of Genetic Programming Appli- [53] JULIANY (J.) et VOSE (M.D.). – The Genetic Kluwer, 2(2), pp. 101-109 (2001).

N [38]
cations, Cham: Springer International Publi-
shing. doi: 10.1007/978-3-319-20883-1 (2015).
GOLDBERG (D.A.). – Genetic Algorithms in
Algorithm Fractal, Evolutionary Computa-
tion, 2(2), pp. 165-180 (1994).
[54] KAMOHARA (S.), TAKAGI (H.) et TAKEDA
[71] LOUCHET (J.) et al. – Dynamic Flies: a new
pattern recognition tool applied to stereo
sequence processing, Pattern Recognition
Search, Optimization, and Machine Learning. (T.). – Control Rule Acquisition for an Arm Letters (2002).
Reading, MA: Addison-Wesley Publishing Wrestling Robot, in IEEE Int. Conf. on Sys- [72] LOUCHET (J.). – Genetic and Evolutionary
tem, Man and Cybernetics (SMC97), Orlando,

S
Company, inc (1989). Computation in Image Processing and
[39] GOLDBERG (D.E.). – Simple genetic algorithms FL, USA (1997). Computer Vision, Stefano Cagnoni, Evelyne
and the minimal, deceptive problem, in DAVIS [55] KAUFFMAN (S.A.) et JOHNSEN (S.). – Co- Lutton and Gustavo Olague (Eds), in. Sprin-

A
(L.) (ed.) GASA, Morgan Kaufmann Publishers, Evolution to the Edge of Chaos: Coupled ger Verlag (2006).
pp. 74-88 (1987). Fitness Landscapes, Poised States, and Co- [73] LUTTON (E.) et al. – Mixed IFS: resolution of
[40] GOLDBERG (D.E.). – Genetic Algorithms and Evolutionary Avalanches, in ALifeII confe- the inverse problem using Genetic Program-

V Walsh functions : Part I, a gentle intro- rence (1992). ming, Complex Systems, 9, pp. 375-398
duction. \em TCGA Report No 88006,Tusca- [56] KOZA (J.R.). – Evolution and coevolution of (1995).
loosa, US: University of Alabama (1988). computer programs to control independently [74] LUTTON (E.), CAYLA (E.) et CHAPUIS (J.). –

O [41] GOLDBERG (D.E.). – Genetic Algorithms and

Walsh functions : Part II, deception and its
analysis, \em TCGA Report No 89001, Tusca-
acting agents, in Proceedings SAB90,
pp. 366-375 (1990).
[57] KOZA (J.R.). – Genetic evolution and co-
ArtiE-Fract: The Artists Viewpoint, in EvoMU-
SART2003, 1st European Workshop on Evolu-
tionary Music and Art. Essex: LNCS, Springer

I [42]
loosa, US: University of Alabama (1989).
GOLDBERG (D.E.) et (J.) RICHARDSON. –
evolution of computer programs, in ALifeII
conference, pp. 603-629 (1991).
[75]
Verlag (2003).
LUTTON (E.), GRENIER (P.) et LÉVY VÉHEL

R
Genetic Algorithms with sharing for multi- [58] KOZA (J.R.). – Genetic Programming, MIT (J.). – An interactive EA for mulifractal baye-
modal function optimization, in GREFENS- Press (1992). sian denoising, in EvoIASP 2005, Lausanne
TETTE (J.J.) (ed.), Second International
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

[59] KRUEGER (M.). – Méthode danalyse dalgo- (2005).

Conference on Genetic Algorithms and their rithmes doptimisation stochastique à l’aide [76] LUTTON (E.), GRENIER (P.) et LÉVY VÉHEL
Applications, Hillsdale, New Jersey: Law- dalgorithmes génétiques, PhD Thesis, Télé- (J.). – An Interactive EA for Multifractal Baye-
rence Erlbaum Associates, pp. 41-49 (1987). com Paris (1993). sian Denoising, in EVOIASP (2005).

P [43] GOLDBERG (D.E.) et SMITH (R.E.). – Nonsta-

tionary function optimization using genetic
algorithms with dominance and diploidy, in
[60] VENCES (L.) et RUDOMIN (I.). – Fractal com-
pression of single images and image se-
quences using genetic algorithms (1994).
[77] LUTTON (E.) et LÉVY VÉHEL (J.). – Pointwise
Regularity of Fitness Landscapes and the

L
Performance of a Simple ES, in CEC06,
GREFENSTETTE (J.J.) (ed.) Proceedings of [61] LANDRIN-SCHWEITZER (Y.) et al. – Introducing Vancouver (2006).
the second international conference on gene- Lateral Thinking in Search Engines with Inte-
tic algorithms and their applications, Hills- [78] LUTTON (E.) et MARTINEZ (P.). – A Genetic

U
ractiveEvolutionary Algorithms, in Annual Algorithm with Sharing for the Detection of
dale, New Jersey: Lawrence Erlbaum Asso- ACM Symposium on Applied Computing (SAC
ciates, pp. 59-68 (1987). 2D Geometric Primitives in Images, in AE 95:
2003), Special Track on"Computer Applications Selected Papers from the European confe-

S
[44] GOLDBERG (D.E.) et SEGREST (P.). – Finite in Health Care" (COMPAHEC 2003) (2003).
Markov Chain Analysis of Genetic Algo- rence on Artificial Evolution. London, UK:
[62] LANDRIN-SCHWEITZER (Y.), COLLET (P.) et Springer-Verlag, pp. 287-303 (1996).
rithms, in Genetic Algorithms and their LUTTON (E.). – Interactive GP for Data Retrie-
Applications : Proceedings of the Second [79] LUTTON (E.), PERROT (N.) et TONDA (A.). –
val in Medical Databases, in EUROGP03,
International Conference on Genetic Algo- Evolutionary algorithms for food science and
LNCS, Springer Verlag (2003).
rithms, pp. 1-8 (1987). technology, John Wiley (Genetic Program-
[63] LANDRIN-SCHWEITZER (Y.) et LUTTON (E.). ming and Evolvable Machines). Available at:
[45] HAMDA (H.) et al. – Compact Unstructured – Perturbation theory for Evolutionary Algo-
Representations in Evolutionary Topological [Link]
rithms: towards an estimation of conver- (2016).
Optimum Design, Applied Intelligence, 16 gence speed, in SCHOENAUER (M.) et al.
(2002). (eds), Parallel Problem Solving from Nature [80] LUTTON (E.), PILZ (M.) et LÉVY VÉHEL (J.). –
[46] HILLIS (W.D.). – Co-evolving parasites im- - PPSN VI 6th International Conference. Paris, The Fitness Map Scheme. Application to
prove simulated evolution as an optimization France: Springer Verlag (2000). interactive multifractal image denoising, in
procedure, in, pp. 228-234 (1990). CEC2005, Edinburgh, UK: IEEE Congress on
[64] LANGTON (C.G.) et al. (eds). – Artificial Life Evolutionary Computation (2005).
[47] HOFFMEISTER (F.) et BÄCK (T.). – Genetic al- II : Proceedingds of the Workshop on Aritfi-
gorithms and evolution strategies: similari- cial Life Held February, 1990 in Santa Fe, [81] LUTTON (E.) et VÉHEL (J.L.). – Hölder func-
ties and differences, in SCHWEFEL (H.-P.) New Mexico, Addison Wesley, Reading, MA tions and Deception of Genetic Algorithms,
and MÄNNER (R.) (eds), Parallel Problem (1991). IEEE transactions on Evolutionary computa-
Solving from Nature - Proceedings of 1st tion, 2(2), pp. 56-72 (1998).
[65] LARRANAGA (P.), LOZANO et (J.A.). –  Esti-
Workshop, PPSN 1, Dortmund, Germany: mation of Distribution Algorithms: A New [82] MANTICA (G.) et SLOAN (A.). – Chaotic optimi-
Springer-Verlag, Berlin, Germany (Lecture Tool for Evolutionary Computation, Kluwer, zation and the construction of fractals : solu-
Notes in Computer Science), pp. 455-469 Boston, MA (2002). tion of an inverse problem, Complex Systems,
(1991). 3, pp. 37-62 (1989).
[66] LATHAM (W.) et al. – The Application of
[48] HOLLAND (J.H.). – Outline for a logical theory Evolutionary and Biological Processes to [83] MAULDIN (M.L.). – Maintening diversity in
of adaptative systems, Journal of the associa- Computer Art and Animation, in Computer genetic search, in Proceedings of the Natio-
tion for the Computing Machinery, (3), pp. Graphics Proceedings, pp. 389-390 (1993). nal Conference on Artificial Intelligence
297-314 (1962). (1984).
[67] LEBLANC (B.) et LUTTON (E.). – Bitwise
[49] HOLLAND (J.H.). – Adaptation in Natural et regularity and GA-hardness, in ICEC 98, [84] MICHALEWICZ (Z.). – Genetic Algorithms +
Artificial System, Ann Arbor, University of May 5-9, Anchorage, Alaska (1998). Data Structures = Evolution Programs, New
Michigan Press (1975). York: Springer Verlag (Artificial Intelligence)
[68] LERICHE (R.) et HAFTKA (R.T.). – Optimiza-
[50] HOLLAND (J.H.). – Genetic Algorithms, tion of Laminate Stacking Sequence for (1992).
Scientific American, 267(1), pp. 66-72 (1992). Buckling Load Maximization by Genetic [85] MITCHELL (M.) et FORREST (S.). – Genetic
[51] HORN (J.). – Finite Markov Chain Analysis of Algorithm, AIAA Journal, 31(5), pp. 951-969 Algorithms and Artificial Life, Artificial Life
Genetic Algorithms with Niching, IlliGAL (1993). (1993).

Doc. S 7 218v2 – 2 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

_____________________________________________________________________________ ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES

P
O
[86] NETTLETON (D.J.) et GARIGLIANO (R.). – [96] SAPIN (E.), LOUCHET (J.) et LUTTON (E.). – [107] TAKAGI (H.) et OHSAKI (M.). – IEC-based
U
Evolutionary algorithms and a fractal inverse
problem, Biosystems, 33, pp. 221-231 (1994).
The Fly Algorithm revisited: Adaptation to
Cmos image sensor, in ICEC 2009, Interna-
tional Conference on Evolutionary Compu-
Hearing Aids Fitting, in IEEE Int. Conf. on
System, Man and Cybernetics (SMC99),
Tokyo, Japan (1999).
R
[87] NIX (A.E.) et VOSE (M.D.). – Modeling genetic
algorithms with Markov Chains, Annals of tation. Madeira, Portugal (2009).
[108] TODD (S.J.P.) et LATHAM (W.). – Evolu-
Mathematics and Artificial Intelligence, 5(1), [97] SCHWEFEL (H.P.). – Evolutionsstrategie und tionary Art and Computers, Academic Press

E
pp. 79-88 (1992). numerische Optimierung, PhD Thesis. Tech- (1992).
[88] OLIVER (A.), MONMARCHÉ (N.) et VENTU- nische Universitat, Berlin (1975).
[109] TODD (S.) et LATHAM (W.). – Artificial Life or
RINI (G.). – Interactive Design of Web Sites [98] SCHWEFEL (H.-P.). – Numerical Optimization

N
Surreal Art ?, in First European Conference
with a Genetic Algorithm., in, pp. 355-362 of Computer Models, John Wiley & sons, on Artificial Life, pp. 504-513 (1991).
(2002). New-York (1981).
[99] SHAPIRO (J.L.) et PRÜGEL-BENNETT (A.). – [110] TROMPETTE (P.), MARCELIN (J.L.) et SCH-
[89] PAUPLIN (O.) et al. – Obstacle detection by
Maximum Entropy Analysis of Genetic Algo- MELDING (C.). – Optimal damping of viscoe-
Evolutionary Algorithm: the Fly Algorithm, in
rithm Operators, Lecture Notes in Computer lastic constrained beams or plates by use of
The second International Conference on Au-
a genetic algotithm, in IUTAM (1993).

S
tonomous Robots and Agents, ICARA2004. Science, 993, pp. 14-24 (1995).
Palmerston North, New Zealand (2004). [100] SHAPIRO (J.L.), RATTRAY (M.) et PRÜGEL- [111] VÉHEL (J.L.), DAOUDI (K.) et LUTTON (E.). –
[90] PELIKAN (M.), GOLDBERG (D.G.) et LOBO (F.). BENNETT (A.). – The Statistical Mechanics Fractal Modeling of Speech Signals, Fractals,

A
– A survey of optimization by building and Theory of Genetic Algorithm Dynamics, in 2(3), pp. 379-382 (1994).
using probabilistic models, Computational First International Conference on Evolu- [112] VÉHEL (J.L.) et LUTTON (E.). – Optimization
Optimization and Applications, (21), pp. 5-20 tionary Computation and Its Applications, of Fractal Functions Using Genetic Algo-

[91]
(2002).
POLI (R.) et CAGNONI (S.). – Genetic Pro-
Moscow (1996).
[101] SIEGEL (E.). – Competively evolving decision
trees against fixed training cases for natural
rithms, in Fractal 93 (1993).
[113] VÉHEL (J.L.), LUTTON (E). et TRICOT (Eds)
V
O
gramming with User-Driven Selection : (C.). – Fractals in Engineering : From Theory
Experiments on the Evolution of Algorithms language processing, in Advances in Genetic
to Industrial Applications. Springer Verlag
for Image Enhancement, in 2nd Annual Conf. Programming (1994).
(1997).

I
on Genetic Programming (1997). [102] SIMS (K.). – Artificial Evolution for Computer
Graphics, Computer Graphics, 25(4), pp. 319- [114] VIDAL (F.P.) et al. – Artificial Evolution for 3D
[92] POLI (R.) et LANGDON (W.B.). – Schema
328 (1991). PET Reconstruction, in Artificial Evolution
Theory for Genetic Programming with One-
2009. Springer (LNCS) (2009).

R
point Crossover and Point Mutation, Evolu- [103] SMITH (R.E.) et GOLDBERG (D.E.). – Diploidy
tionary Computation Journal, 6(3), pp. 231-252 and Dominance in Artificial Genetic Search, [115] VIDAL (F.P) et al. – PET Reconstruction Using
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

(1998). Complex Systems, 6, pp. 251-285 (1992). a Cooperative Coevolution Strategy, in

[93] POLI (R.), LANGDON (W.B.) et MCPHEE Proceedings of the IEEE Medical Imaging
[104] TAKAGI (H.). – Interactive Evolutionary
(N.F.). – A field guide to genetic program- Conference 2009, Orlando, Florida: IEEE
Computation : System Optimisation Based
(2009).

P
ming, published via \texttt[Link] and on Human Subjective Evaluation, in IEEE Int.
freely available at \texttt[Link] Conf. on Intelligent Engineering Systems [116] VOSE (M.). – Modeling simple genetic algo-
[Link], available at: [Link] (INES98), Vienna, Austria (1998). rithms, in FOGA-92, Foundations of Genetic

L
[Link] (2008). [105] TAKAGI (H.). – New Topics from Recent Algorithms, Vail, Colorado (1992).
[94] PRÜGEL-BENNETT (A.) et ROGERS (A.). – Interactive Evolutionary Computation Re- [117] VRSCAY (E.R.). – Fractal Geometry and Ana-
Modelling Genetic Algorithm Dynamics, in searches, in Knowledge-Based Intelligent In- lysis, pp. 405-468 (1991).

U
KALLEL (L.), NAUDTS (B.), and ROGERS (A.) formation and Engineering Systems, p. 14
(eds), Theoretical Aspects of Evolutionary (2008). [118] VRSCAY (R.). – Moment and collage methods
Computing, Berlin, Heidelberg: Springer for the inverse problem of fractal construc-
[106] TAKAGI (H.). – New IEC Research and

S
Berlin Heidelberg, pp. 59-85. doi: 10.1007/ tion with iterated function systems, in Fractal
Frameworks, in FODOR (J.) and KACPRZYK
978-3-662-04448-3_4 (2001). 90 Conference (1990).
(J.) (eds), Aspects of Soft Computing, Intelli-
[95] RECHENBERG (I.). – Evolutionsstrategie : gent Robotics and Control, Springer Berlin [119] WORLD (L.). – Aesthetic Selection: The Evo-
Optimierung Technicher System nach Prinzi- Heidelberg (Studies in Computational Intelli- lutionary Art of Steven Rooke [About the
pien der Biologischen Evolution, Fromman gence), pp. 65-76. doi: 10.1007/978-3-642- Cover], IEEE Computer Graphics and Appli-
Holzboog, Stuttgart (1973). 03633-0_4 (2009). cations, 16(1), pp. 4 (1996).

Outils logiciels
Inspyred, bibliothèque dalgorithmes bioinspirés en langage python DEAP, Genetic Programming in Python
[Link] [Link]
GAlib - C++ Genetic Algorithms Library Evolving Objects (EO), a template-based, ANSI-C++ evolutionary compu-
[Link] tation
[Link]
Matlab Global Optimization Toolbox (inclut des algorithmes génétiques)
Langage de spécification EASEA, multi plates-formes
[Link]
[Link]
GPLAB, A Genetic Programming Toolbox for MATLAB
[Link]

Sites Internet
Association Évolution artificielle IEEE Evolutionary Computation Technical Committee
Elle regroupe les chercheurs français de ce domaine et organise confé- [Link]
rences internationales (EA), journées et écoles committee
[Link] SPECIES, Society for the Promotion of Evolutionary Computation in
SIGEVO, Special Interest Group on Genetic and Evolutionary Computation Europe and its Surroundings
[Link] [Link]

Copyright © – Techniques de l’Ingénieur – Tous droits réservés Doc. S 7 218v2 – 3

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

P ALGORITHMES GÉNÉTIQUES, ALGORITHMES ÉVOLUTIONNAIRES ____________________________________________________________________________

O
U
Événements
R ACM Genetic and Evolutionary Computation Conference (GECCO) Parallel Problem Solving from Nature (PPSN)
[Link] [Link]
IEEE Congress on Evolutionary Computation (CEC) Conférences EA

E [Link]
EvoStar
[Link]

N
Colocation de quatre conférences internationales ayant lieu en Europe
(EuroGP, EvoApplications, EvoCOP et EvoMUSART)
[Link]

S
A
V
O
I
R
Parution : décembre 2020 - Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]

P
L
U
S

Doc. S 7 218v2 – 4 Copyright © – Techniques de l’Ingénieur – Tous droits réservés

tiwekacontentpdf_s7218 v2 Ce document a ete delivre pour le compte de 7200049459 - universite savoie mont blanc // [Link]
GAGNEZ DU TEMPS ET SÉCURISEZ VOS PROJETS
EN UTILISANT UNE SOURCE ACTUALISÉE ET FIABLE

Techniques de l’Ingénieur propose la plus importante

collection documentaire technique et scientifique
en français !
Grâce à vos droits d’accès, retrouvez l’ensemble
des articles et fiches pratiques de votre offre,
leurs compléments et mises à jour,
et bénéficiez des services inclus.

   
RÉDIGÉE ET VALIDÉE MISE À JOUR 100 % COMPATIBLE SERVICES INCLUS
PAR DES EXPERTS PERMANENTE SUR TOUS SUPPORTS DANS CHAQUE OFFRE
NUMÉRIQUES

 + de 350 000 utilisateurs

 + de 10 000 articles de référence
 + de 80 offres
 15 domaines d’expertise
Automatique - Robotique Innovation
Biomédical - Pharma Matériaux
Construction et travaux publics Mécanique
Électronique - Photonique Mesures - Analyses
Énergies Procédés chimie - Bio - Agro
Environnement - Sécurité Sciences fondamentales
Génie industriel Technologies de l’information
Ingénierie des transports

Pour des offres toujours plus adaptées à votre métier,

découvrez les offres dédiées à votre secteur d’activité

Depuis plus de 70 ans, Techniques de l’Ingénieur est la source

d’informations de référence des bureaux d’études,
de la R&D et de l’innovation.

[Link]
CONTACT : Tél. : + 33 (0)1 53 35 20 20 - Fax : +33 (0)1 53 26 79 18 - E-mail : [Link]@[Link]
 LES AVANTAGES ET SERVICES
compris dans les offres Techniques de l’Ingénieur

  
ACCÈS

Accès illimité Téléchargement des articles Consultation sur tous

aux articles en HTML au format PDF les supports numériques
Enrichis et mis à jour pendant Pour un usage en toute liberté Des contenus optimisés
toute la durée de la souscription pour ordinateurs, tablettes et mobiles

 
SERVICES ET OUTILS PRATIQUES

Questions aux experts* Articles Découverte Dictionnaire technique multilingue

Les meilleurs experts techniques La possibilité de consulter des articles 45 000 termes en français, anglais,
et scientifiques vous répondent en dehors de votre offre espagnol et allemand

 
Archives Impression à la demande Alertes actualisations
Technologies anciennes et versions Commandez les éditions papier Recevez par email toutes les nouveautés
antérieures des articles de vos ressources documentaires de vos ressources documentaires

*Questions aux experts est un service réservé aux entreprises, non proposé dans les offres écoles, universités ou pour tout autre organisme de formation.

ILS NOUS FONT CONFIANCE

[Link]
CONTACT : Tél. : + 33 (0)1 53 35 20 20 - Fax : +33 (0)1 53 26 79 18 - E-mail : [Link]@[Link]