Population Based Metaheuristics:

Algorithmes Génétiques

Régis ATEMENGUE
@regis_ate | [Link]
SBSE, 2024/2024
 Objectifs du cours

Comprendre les principes fondamentaux d'une

métaheuristique basée sur la population
Compréhension des principes de base et des mécanismes
d'un algorithme métaheuristique spécifique, tel que les
algorithmes génétiques, la programmation génétique, etc.

@regis_ate | [Link] 1
 Aperçu du cours

Introduction à la méta-heuristique
Algorithme génétique
basée sur la population

Concepts de base en matière de Mise en œuvre et

population expérimentation pratiques

@regis_ate | [Link]
2
Introduction à la méta-heuristique basée sur la population

@regis_ate | [Link]
3
Classification des techniques de recherche méta-heuristique
Voici quelques classifications des techniques de recherche méta-heuristiques

@regis_ate | [Link]
4
Méta-heuristique basée sur la population
Les algorithmes méta-heuristiques basés sur la population sont une classe
d'approches qui recherchent des solutions quasi optimales à un problème
d'optimisation complexe en conservant un ensemble de solutions candidates et en
utilisant les caractéristiques de la population pour guider l'algorithme de recherche de
manière itérative.

Les algorithmes basés sur la population maintiennent et améliorent plus d'une

solution pour effectuer l'optimisation, où à chaque itération, plusieurs solutions
sont modifiées, et certaines d'entre elles réussissent à être retenues pour l'itération
suivante.

@regis_ate | [Link]
5
Population-Based Meta-heuristics
Les méta-heuristiques basées sur la population utilisent plus d'une solution initiale pour commencer
l'optimisation.

À chaque itération, plusieurs solutions sont modifiées et certaines d'entre elles passent à l'itération
suivante.

La modification des solutions se fait par le biais d'opérateurs qui utilisent souvent des propriétés
statistiques spéciales de la population.

Le paramètre supplémentaire pour la taille de la population est défini par l'utilisateur et reste
généralement constant d'une itération à l'autre.

En exécutant l'algorithme de nombreuses fois, on obtient un vaste ensemble de bonnes

approximations.

@regis_ate | [Link]
6
Méta-heuristique basée sur la population

Les algorithmes métaheuristiques basés sur la population sont appropriés pour les recherches
globales en raison de leur capacité à explorer globalement l'espace des meilleures solutions et à les
exploiter localement. ils sont subdivisés en deux catégories principales :

Evolutionary Algorithm
Swarm Intelligence

@regis_ate | [Link]
7
 Algorithmes évolutionnaires (EA)
Informatique évolutive

@regis_ate | [Link]
8
Algorithmes évolutionnaires (EA)
Les algorithmes évolutionnaires (AE) sont un ensemble de tech- niques d'optimisation et
d'apprentissage automatique qui s'inspirent des processus biologiques de l'évolution.

Ces métaheuristiques exploitent les principes de variation par mutation et recombinaison,

et de sélection des individus les plus performants dans un en- vironnement donné.

En itérant ce processus, le système trouve des solutions de plus en plus bonnes et

résout généralement le problème de manière satisfaisante.

@regis_ate | [Link]
9
De l'évolution naturelle à l'ingénierie
Selon Charles Darwin [DAR 59], l'évolution des êtres vivants
repose sur plusieurs faits :

les variations des caractéristiques individuelles entre les

parents et la progéniture ;

l'héritabilité d'une grande partie de ces caractéristiques ;

une compétition qui sélectionne les individus les plus aptes
d'une population par rapport à leur environnement, afin de
survivre et de se reproduire.

Charles Darwin
Darwin en déduit que la compétition permet la transmission de
source: google
variations héréditaires bénéfiques entre les individus, qui
s'accumulent de génération en génération.

@regis_ate | [Link]
10
Un algorithme évolutionnaire générique
Swarm intelligence

@regis_ate | [Link]
11
Swarm intelligence

Particle Swarm Optimization ou Optimisation par Essaim de

particules est une méta-heuristique permettant de trouver des
solution aux problèmes d’optimisation.

Classé dans la catégorie des population-based algorithms, elle

s’inspire du comportement collectif des oiseaux lors des
déplacements.

Chaque oiseau pour se déplacer se base sur l’individu

connaissant le chemin et aussi sur leurs instincts personnel.

@regis_ate | [Link]
12
Pourquoi les algorithme Génétique ?

@regis_ate | [Link]
13
Pourquoi les algorithme Génétique ?
Les algorithmes génétiques sont un sous-ensemble de l'apprentissage automatique (ML). Dans la pratique,
un algorithme génétique.

Il y a presque toujours une meilleure solution, plus ciblée, pour chaque problème individuel ! Les
algorithmes génétiques sont un excellent outil polyvalent qui peut être appliqué à de nombreux types de
problèmes

L les algorithmes génétiques sont faciles à comprendre, amusants à mettre en œuvre et ils introduisent de
nombreux concepts utilisés par tous les systèmes d'apprentissage automatique.

Si vous êtes intéressé par l'apprentissage automatique mais que vous ne savez pas par où commencer,
commencez par les algorithmes génétiques. Vous apprendrez des concepts importants que vous pourrez
transposer dans d'autres domaines, vous construirez - non, vous gagnerez - un formidable outil polyvalent
que vous pourrez utiliser pour résoudre de nombreux types de problèmes, et vous n'aurez pas besoin
d'étudier des mathématiques avancées pour le comprendre.

@regis_ate | [Link]
14
Algorithme Génétique: Historique

@regis_ate | [Link]
15
Algorithme Génétique: Historique

Alan Turing a proposé des programmes évolutifs en 1950

En 1960, John Holland et des collègues et élèves de l'Université

du Michigan se penchent sur le sujet qui est encore à ses débuts.
Pas à pas, le domaine attire un plus grand nombre d'intéressés. Ils
arrivent à se rapprocher de l'optimum d'une fonction en combinant
les gènes contenus dans les différents
individus de la population.

@regis_ate | [Link]
16
Algorithme Génétique: Historique

En 1975 (après 25 ans), John Holland a publié « Adaptation in

Natural and Artificial Systems » et son travail a jeté les bases
théoriques et empiriques de la programmation génétique.

En 1989, David Goldberg par son

livre intitulé Genetic Algorithms in
Search, Optimization, and Machine
Learning fait connaître au domaine
des algorithmes génétiques une
grande popularisation.

@regis_ate | [Link]
17
Algorithme Génétique: Historique

Aujourd'hui encore, les informaticiens s'intéressent à la

biologie et aux systèmes biologiques pour trouver des idées
sur la manière de créer de meilleurs algorithmes. L'un des
algorithmes d'optimisation les plus récents.

l'un des algorithmes d'optimisation les plus récents inspirés

par la biologie est l'optimisation par colonies de fourmis (Ant
Colony Optimization). qui a été proposé pour la première
fois en 1992 par Marco, D. (1992). L'optimisation par
colonies de fourmis modélise le comportement des
fourmis comme méthode de résolution de divers
problèmes d'optimisation tels que le problème du voyageur
de commerce.

@regis_ate | [Link]
18
Algorithme Génétique: Historique
En 1990, MATLAB a intégré trois algorithmes heuristiques d'optimisation sans dérivation
(recuit simulé, optimisation par essaims de particules, algorithme génétique) et deux
algorithmes de recherche directe (recherche par simplexe, recherche par motif).

En 1991, L’ Europe connaît la première conférence sur le domaine, conférence baptisée:

European Conference on Artificial Life. Elle fut co-organisée par Francisco Varela et Paul
Bourgine.

Depuis les années 2000, L'essor de l'informatique puissante et l'accès aux données
massives permettent d'utiliser les AG pour des problèmes plus complexes, comme
l'analyse d'images, la robotique et la finance.

@regis_ate | [Link]
19
GA: Définition

@regis_ate | [Link]
20
GA: Définition
L'AG est un algorithme de la famille des algorithmes évolutionnaires, un algorithme basé sur la
population popularisé par Holland et ses étudiants pour son application en informatique. Inspiré par le
processus darwinien de sélection naturelle, l'AG initie un ensemble de solutions appelées individus
représentées par des propriétés appelées chromosomes, cet ensemble est appelé une population.

Un algorithme génétique (AG) est une technique de recherche utilisée en informatique pour
trouver des solutions vraies ou approximatives à des problèmes d'optimisation et de recherche.

Les techniques s'inspirent de l'évolution naturelle, comme l'héritage, la mutation, la sélection et

le croisement.

Les GA sont mis en œuvre en utilisant des tableaux de bits ou de caractères pour représenter les
chromosomes.

@regis_ate | [Link]
21
GA: Principe

22
GA: Principe
Les algorithmes génétiques utilisent la théorie de Darwin sur l’évolution des espèces qui
repose sur trois principes : le principe de variation, le principe d'adaptation et le principe
d'hérédité.

Le principe de variation : Chaque individu au sein d’une population est unique. Ces différences,
plus ou moins importantes, vont être décisives dans le processus de sélection.

Le principe d'adaptation : Les individus les plus adaptés à leur environnement atteignent plus
facilement l'âge adulte. Ceux ayant une meilleure capacité de survie pourront donc se
reproduire davantage.

Le principe d’hérédité : Les caractéristiques des individus doivent être héréditaires

pour pouvoir être transmises à leur descendance. Ce mécanisme permettra de faire
évoluer l’espèce pour partager les caractéristiques avantageuses à sa survie.

@regis_ate | [Link]
23
OPÉRATEURS D’ÉVOLUTION

@regis_ate | [Link]
24
OPÉRATEURS D’ÉVOLUTION

Il y a trois opérateurs d'évolution dans les algorithmes génétiques :

La sélection : Choix des individus les mieux adaptés.

Le croisement : Mélange par la reproduction des particularités des individus choisis.

La mutation : Altération aléatoire des particularités d'un individu.

@regis_ate | [Link]
25
 OPÉRATEURS D’ÉVOLUTION : SELECTION
La sélection consiste à choisir les individus les mieux adaptés afin d'avoir une population de solution la
plus proche qui converge vers l'optimum global. Cet opérateur est l'application du principe d'adaptation de
la théorie de Darwin.

Il existe plusieurs techniques de sélection. Voici les principales utilisées :

Sélection par rang : Cette technique de sélection choisit toujours les individus possédant les meilleurs
scores d'adaptation.

Probabilité de sélection proportionnelle à l'adaptation : Technique de la roulette ou roue de la fortune,

pour chaque individu, la probabilité d'être sélectionné est proportionnelle à son adaptation au problème.

@regis_ate | [Link]
26
 OPÉRATEURS D’ÉVOLUTION : SELECTION

Sélection par tournoi : Cette technique utilise la sélection proportionnelle sur des paires d'individus, puis
choisit parmi ces paires l'individu qui a le meilleur score d'adaptation.

Sélection uniforme : La sélection se fait aléatoirement, uniformément et sans intervention de la valeur

d'adaptation.

@regis_ate | [Link]
27
 OPÉRATEURS D’ÉVOLUTION : CROISEMENT
Le croisement, ou enjambement, crossing-over, est le résultat obtenu lorsque deux
chromosomes partagent leurs particularités. Celui-ci permet le brassage génétique
de la population et l'application du principe d’hérédité de la théorie de Darwin.

Il existe deux méthodes de croisement : simple ou double enjambement.

Le simple enjambement consiste à fusionner les particularités de deux individus

à partir d'un pivot, afin d'obtenir un ou deux enfants :

Le double enjambement repose sur le même principe, sauf qu'il y a deux pivots.

@regis_ate | [Link]
28
 OPÉRATEURS D’ÉVOLUTION : MUTATION
La mutation consiste à altérer un gène dans un chromosome selon un facteur de mutation. Ce
facteur est la probabilité qu'une mutation soit effectuée sur un individu. Cet opérateur est
l'application du principe de variation de la théorie de Darwin et permet, par la même occasion,
d'éviter une convergence prématurée de l'algorithme vers un extremum local.

@regis_ate | [Link]
29
FONCTIONNEMENT DES ALGORITHMES GÉNÉTIQUES

@regis_ate | [Link]
30
General

@regis_ate | [Link]
31
 Pseudo Code

@regis_ate | [Link]
32
ALGORITHME

@regis_ate | [Link]
33
ALGORITHME
Les étapes de l’Algorithme Génétique sont:

1. On représente chaque individu par un chromosome de taille fixe, on choisit le nombre N d’individus de la
population initiale, on choisit la probabilité PC de croisement et la probabilité PM de mutation qui va déterminer
respectivement si le croisement et la mutation est fait ou non.

2. On définit la fonction d’évaluation ou encore appelée la fonction fitness f(x) selon le domaine de données de notre
problème (c’est cette fonction qui va nous permettre de calculer le score de chaque individu (c’est à dire à quel
point chaque individu s’en sort bien dans un environnement)

3. On génère N individus (i1, i2, i3, ………,iN) aléatoirement (on peut utiliser l'algorithme glouton pour le faire)

4. On calcule le fitness de chaque individus: f(i1), f(i2),....,f(i3)

5. on fait la sélection c’est à dire on choisit 02 chromosomes ou individus pour croisement selon fitness

6. On fait le croisement et la mutation c'est à dire on crée une paire de descendantes ou enfants de la nouvelle
génération en faisant les croisements et mutations selon la probabilité de croisement PM et de mutation PM

@regis_ate | [Link]
34
ALGORITHME
Les étapes de l’Algorithme Génétique sont:

5. on fait la sélection c’est à dire on choisit 02 chromosomes ou individus pour croisement selon fitness

6. On fait le croisement et la mutation c'est à dire on crée une paire de descendantes ou enfants de la nouvelle
génération en faisant les croisements et mutations selon la probabilité de croisement PM et de mutation PM

7. On met les nouveaux individus dans une nouvelle génération

8. On répète l’étape 5 jusqu’à obtenir le nombre des nouveaux individus de la nouvelle population égale à N

9. On remplace l’ancienne population i avec la nouvelle population i+1

10. On répète l’étape 4 (répète le processus) jusqu’à ce que le test d’arrêt soit satisfait).

@regis_ate | [Link]
35
Terminologie de base

@regis_ate | [Link]
36
terminologies

Population - Il s'agit simplement d'une collection de solutions candidates auxquelles peuvent être
appliqués des opérateurs génétiques tels que la mutation et le croisement. être soumises à des
opérateurs génétiques tels que la mutation et le croisement.

Solution candidate - Une solution possible à un problème donné.

Gène - Les éléments indivisibles qui constituent le chromosome. Classiquement un gène est constitué
de 0 ou de 1

Chromosome - Un chromosome est une chaîne de gènes. Un chromosome définit une solution
candidate spécifique. Un chromosome typique avec un codage binaire pourrait contenir quelque chose
comme « 01101011 ».

@regis_ate | [Link]
37
terminologies

Mutation - Processus par lequel les gènes d'une solution candidate sont modifiés de manière aléatoire
pour créer de nouvelles caractéristiques. aléatoirement pour créer de nouvelles caractéristiques.

Croisement - Processus au cours duquel les chromosomes sont combinés pour créer une nouvelle
solution candidate. Ce processus est parfois appelé recombinaison.

Sélection - Il s'agit de la technique qui consiste à choisir des solutions candidates pour créer la
prochaine génération de solutions.

Fitness - Un score qui mesure la mesure dans laquelle une solution candidate est adaptée à un
problème donné

@regis_ate | [Link]
38
Critère d’arrêt
Le critère d’arrêt est essentiel car il définit à quel moment de notre itération on souhaite
s’arrêter. Ceci peut être :

Lorsque l’on a atteint une solution qui a un niveau satisfaisant de valeur fitness.
Lorsque l’on a atteint un nombre fixe de générations.
Quand on arrive plus à trouver de solution de meilleurs qualités après un ensemble
d’itérations
Lorsque l’on a atteint un plafond de ressource alloué à l’opération comme le temps de
recherche ou la mémoire de calcul
Il y a des cas où ça peut être des combinaisons de cas ci-dessus.

@regis_ate | [Link]
39
Concepts:

@regis_ate | [Link]
40
Critère d’arrêt
Le critère d’arrêt est essentiel car il définit à quel moment de notre itération on souhaite
s’arrêter. Ceci peut être :

Lorsque l’on a atteint une solution qui a un niveau satisfaisant de valeur fitness.
Lorsque l’on a atteint un nombre fixe de générations.
Quand on arrive plus à trouver de solution de meilleurs qualités après un ensemble
d’itérations
Lorsque l’on a atteint un plafond de ressource alloué à l’opération comme le temps de
recherche ou la mémoire de calcul
Il y a des cas où ça peut être des combinaisons de cas ci-dessus.

@regis_ate | [Link]
41
PROS VS CONS

@regis_ate | [Link]
42
PROS VS CONS
Les algorithmes génétiques sont faciles à comprendre car le concept utilise les principes
communs de la biologie évolutive appris au niveau scolaire.

L'algorithme est distinct de l'application, ce qui le rend très agile (Capable de s’adapter et
d’être utilisé efficacement dans divers contextes).

Les algorithmes génétiques peuvent résoudre des problèmes dans divers domaines tels
que l’informatique, l’ingénierie, la médecine, la finance, la logistique, etc.

Il a une forte probabilité de trouver les minima globaux et de ne pas rester coincé aux
minima locaux.

Il peut optimiser diverses fonctions, telles que les fonctions discrètes, les fonctions
continues, les problèmes mixtes continus/discrets, les problèmes objectifs, etc.

@regis_ate | [Link]
43
PROS VS CONS

Les algorithmes génétiques ne nécessitent pas d'informations dérivées ou auxiliaires car

ils obtiennent le score de condition physique à partir de la fonction objectif.

D'autres avantages des algorithmes génétiques incluent leur capacité à résoudre avec
succès des problèmes qui présentent plusieurs optima locaux, des fonctions objectif
non fluides, un grand nombre de paramètres à optimiser, ou des fonctions objectif
bruyantes ou stochastiques.

@regis_ate | [Link]
44
PROS VS CONS

Bien que l'utilisateur ait besoin de moins d'informations sur le problème, cet avantage est
compensé en raison des difficultés liées à la conception de la fonction objective, à la sélection
des opérateurs appropriés et à l'obtention d'une représentation.

Il n'y a pas de garantie quant à l’obtention de la solution optimale au problème posé en un

temps fini.

@regis_ate | [Link]
45
Mise en œuvre et expérimentation pratiques

31