B.

FAYECH

Soft Computing, B.FAYECH ENSIT, 2024-2025 1

  Historique
 Définition
 Terminologie
 Architecture globale des algorithmes évolutifs
 Codage
 Sélection
 Croisement
 Mutation
 Propriétés

Soft Computing, B.FAYECH 2

ENSIT, 2024-2025
  1860
◦ Charles Darwin : L'origine des espèces au moyen de la sélection naturelle
ou la lutte pour l'existence dans la nature.
◦ Théorie de l'évolution des espèces : sous l'influence des contraintes
extérieurs, les êtres vivants se sont graduellement adaptés à leur milieu
naturel au travers de processus de reproductions.

 20ème siècle
◦ Existence des mutations génétiques.
◦ Les chercheurs en informatique étudient des méthodes pour permettre aux systèmes
d'évoluer spontanément en fonction des nouvelles conditions.

 1966
◦ Programmation évolutionnaire L. J. Fogel.

Soft Computing, B.FAYECH 3

ENSIT, 2024-2025
 1973
◦ Stratégie d'évolution I. Rechenberg.

 1975
◦ Dans les années 1960, John Holland étudient les systémes évolutifs et, en 1975, il introduit
le premier modèle formel des algorithmes génétiques (the canonical genetic algorithm
AGC) dans son livre Adaptation in Natural and Artificial Systems.

 1989
◦ David Goldberg publie un ouvrage de vulgarisation des algorithmes génétiques.

 1990
◦ Programmation d'une panoplie d'algorithmes génétiques transcris en C++, appelée GAlib.
(librairie d’outils pour des problèmes d'optimisation en utilisant les AG et pour servir de
support de programmation)

Soft Computing, B.FAYECH 4

ENSIT, 2024-2025
  Les algorithmes évolutifs sont des algorithmes d'optimisation s'appuyant sur des
techniques dérivées de la génétique et des mécanismes d'évolution de la nature :
croisements, mutations, sélections, etc…
 Algorithme de recherche globale : avec plusieurs solutions évoluant en parallèle !

 Principe inspiré d'une analogie biologique :

◦ on considère un ensemble de solutions comme une population d'individus susceptible
d'évoluer et de se croiser, en suivant certaines règles proches de la sélection naturelle.
 L'intérêt principal est de couvrir l'espace de recherche plus largement : exploration

 Trois opérations sont réalisées successivement sur la population :

◦ la sélection des meilleures solutions/individus en proportion de leur adaptation ou avec
une probabilité proportionnelle
◦ le croisement d'individus entre eux
◦ la mutation éventuelle d'un ou de plusieurs individus : changements aléatoires

Soft Computing, B.FAYECH 5

ENSIT, 2024-2025
  Individu ou solution : possède une empreinte génétique, appelée chromosome
 Chromosome : (génotype) éléments à partir desquels sont élaborés les
solutions (mutation et croisement génétiques).

 Gènes : un ensemble de caractéristiques constituant les chromosomes

 Allèles : les valeurs que peuvent prendre les gènes

 Population : (génération) ensemble de chromosomes

 Reproduction : étape de combinaison des chromosomes

 Fitness ou adaptation d’un individu : L'adaptation ou fitness d'un individu :
donnée par une fonction d'utilité (on cherche à maximiser l'adaptation des
individus).

Soft Computing, B.FAYECH 6

ENSIT, 2024-2025
  Après la phase de formulation mathématique, une structure de données est associée à
chaque point de l’espace de recherche.
 Représentation génétique des solutions du problème
 Le codage approprié des solutions sous forme de chromosomes ou génotypes.
 Gène : un paramètre de la solution
 Chromosome : suite de gènes
 La qualité du codage conditionne le succès de l’AG
 Au début : codage binaire

ENSIT, 2024-2025 Soft Computing, B.FAYECH 7

  Le codage peut être :
 direct quand il y a une correspondance biunivoque entre l’ensemble des
chromosomes et celui des solutions qui leur correspond
 indirect quand un générateur doit être utilisé pour définir la solution associée à
un chromosome
 mixte lorsqu’il combine les deux codages
 Exemple : problème d’affectation d’une tournée à un véhicule avec 10 villes et des
variables d’affectation binaires
1 2 3 4 5 6 7 8 9 10
1 1 0 0 1 0 0 0 1 1

 Exemple : PVC avec codage d’une permutation

ENSIT, 2024-2025 Soft Computing, B.FAYECH 8

 Genèse

Evaluation

[Arrêt] Sélection

Mutation Croisement

Reproduction

ENSIT, 2024-2025 Soft Computing, B.FAYECH 9

  Genèse : première phase de l’algorithme dans laquelle la population initiale est
construite d’une manière aléatoire ou à travers des résultats issus d’autres
techniques d’optimisation.

 Evaluation : consiste à calculer la valeur de la fonction coût ou d’évaluation pour

chaque individu. Selon Holland, fitness = coût/moyenne de la population. En
général, confusion entre fitness et fonction d’évaluation.

 Sélection : le choix des éléments les plus adaptés pour la formation de la nouvelle
génération.

 Croisement et mutation : phase de reproduction dans laquelle une nouvelle

population est construite à partir des individus sélectionnés via des opérateurs de
croisement et de mutation.

 Arrêt : il s’agit d’un test de l’efficacité de l’algorithme à travers une valeur de la

fonction objectif à atteindre, le nombre d’itérations ou le temps d’exécution. La
solution courante est prise quand ce test est vérifié ; sinon, les étapes sont
recommencées à partir de l’évaluation.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 10

 Population de 10
Hypothèse: les individus
00100110 chromosomes sont classés selon leur
performance par ordre
Genèse I1 I2
décroissant (meilleur I1)
Une nouvelle I3 I4
génération f7 I5 I6
Evaluation I7 I8
I1 I2 Population
f9 I9 I10
I3 I4 Intermédiaire de 10
I5 I6
[Arrêt?] individus sélectionnés
I7 I8
I9 I10 Sélectionner les 4
I1 I2
meilleurs individus
(déterministe) I3 I4
I1 I2
Sélection
I3 I4
I1 I2

Mutation
Croisement
00100110
00100110 00100011
00100010
I’1 I’2
01110011 01110110

Modifier aléatoirement les I’3 I’4

individus avec prob pm I’5 I’6
Croiser les couples
I’7 I’8
d’individus avec prob pc
I’9 I’10

ENSIT, 2024-2025 Soft Computing, B.FAYECH 11

  La sélection consiste à choisir les individus de la population courante qui vont survivre
et se reproduire : création d’une population intermédiaire.
 Sélection en fonction de la valeur de la fonction coût (fitness) qui évalue les solutions.
 L’opérateur de sélection joue un rôle primordial dans la détermination de la performance
des nouvelles générations et donc dans l’amélioration de la qualité des solutions.

 Plusieurs techniques de sélection

 La sélection déterministe (« steady state ») consiste par exemple à garder les k
meilleurs individus (d’une population de n individus) au sens de leurs fitness et de
rejeter le reste, ce qui implique leur classement ou « ranking ». Un individu peut
donc être sélectionné plusieurs fois.

I1 I2
I1 I2
I3 I4 Sélection des 4 meilleurs
I3 I4
Population I5 I6 Population
I1 I2
I7 I8 intermédiaire
I3 I4
I9 I10 I1 I2

f1>f2>…>f10

ENSIT, 2024-2025 Soft Computing, B.FAYECH 12

  Sélection par tournoi (stochastique)
 Sur une population de chromosomes, former m paires de chromosomes
(successifs, premier/denier, aléatoirement, …).
 Ajout d’un paramètre à l'AG : probabilité de victoire du plus fort, çad la
chance qu’a le meilleur chromosome de chaque paire d'être sélectionné (en
général de 70% à 100%).
 A partir des paires, faire combattre les individus et déterminer ceux qui vont
survivre pour la reproduction.
Plus fort ou plus
Paires d’individus faible?
it1 (I1, I10) Aléa=0,25<p →Plus fort : I1
I1 I2 Sélection par tournoi it2 (I2, I9) Aléa=0,53<p →Plus fort : I2
I1 I2
I3 I4 prob de choix du plus fort it3 (I3, I8) Aléa=0,05<p →Plus fort : I3
I3 I7
I5 I6 p=0,75 it4 (I4, I7) Aléa=0,88>p →Plus faible : I7
I5 I1
I7 I8 it5 (I5, I6) Aléa=0,67<p →Plus fort : I5 I9 I3
I9 I10 it6 (I1, I10) Aléa=0,14<p →Plus fort : I1 I4 I5
it7 (I2, I9) Aléa=0,93>p →Plus faible : I9
it8 (I3, I8) Aléa=0,33<p →Plus fort : I3
f1>f2>…>f10 (I4, I7) Aléa=0,66<p →Plus fort : I4
it9
it10 (I5, I6) Aléa=0,21<p →Plus fort : I5

Soft Computing, B.FAYECH 13

ENSIT, 2024-2025
  Sélection par de la Roulette (« Roulette / Wheel »)[Goldberg]
 Chaque individu occupe une surface de la roue proportionnelle à sa fonction
coût.
 En supposant que fi est la valeur de la fonction coût associée au i-ème
individu, la probabilité pi de sélection de ce dernier est en fait égale à fi/fs où
fs=fj.
 On génère un nombre R entre 0 et fs .
 On calcule ensuite une somme S des évaluations en s'arrêtant dès que R est
dépassé.
 Le dernier chromosome dont la fonction d'évaluation vient d'être ajoutée est
sélectionné.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 14

  Exemple : Population de départ

fs=59; S=0 (position du curseur)

Roulette 33,25 It1 : R=9 → S=9 → I4
It2 : R=5 → S=14 → I3
3 It3 : R=25 → S=39 → I1
19 11 It4 : R=10 → S=49 → I4
I2 I1
14,25
44,25
I3 I4
2 5 Population des survivants
9,25
24 Nouv. Ind. séquence
1 4 1 11000

0 59 2 00101
3 01011
4 11000

ENSIT, 2024-2025 Soft Computing, B.FAYECH 15

  La sélection par rang (stochastique)
 consiste à trier les individus dans l’ordre croissant selon leur fitness et de leur
attribuer des rangs : 1 pour le pire, 2 pour le second, etc.
 Sélection par roulette mais selon les rangs des individus

 Exemple :
Chromosomes 1 2 3 4 5 6 Total

Probabilités
89 % 4,1 % 0,2 % 3,3 % 2,1 % 1,3 % 100 %
initiales

Rang 6 5 1 4 3 2 21
Probabilités
29 % 24 % 5% 19 % 14 % 9% 100%
finales

→ Réaliser une sélection par Roulette avec ces nouvelles prob.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 16

  Exercice
Donner la population résultante d’une sélection par les rangs,
en considérant les nombres suivants tirés successivement au
hasard : (2, 9, 3.5, 1.5)
Rang
2
3
1 5
4
10

3 2
fs=10; S=0 I2 I1
2,5 7,5
It1 : R=2 → S=2 → I3 I3
1
It2 : R=9 → S=11 → =1→ I4 I4
It3 : R=3,5 → S=4,5 → I2 1,5
4
It4 : R=1,5 → S=6 → I1
0 10

Soft Computing, B.FAYECH 17

ENSIT, 2024-2025
  Sélection uniforme
 La sélection se fait aléatoirement, uniformément et sans intervention de la
valeur d’adaptation.
 Chaque individu a donc une probabilité 1/N d'être sélectionné, où N est le
nombre total d’individus dans la population.

 Exercice
En considérant les nombres suivants tirés successivement au hasard, donner la
population résultante d’une sélection uniforme :
(0.33, 0.22, 0.94, 0.47, 0.09, 0.43, 0.56, 0.13, 0.03)

I1 I2 I3 I4
0 0,25 0,5 0,75 1

It1 : R=0,33 → I2
It2 : R=0,22 → I1
It3 : R=0,94 → I4
It4 : R=0.47 → I2

ENSIT, 2024-2025 Soft Computing, B.FAYECH 18

  La sélection par les restes (stochastique)
 Sur une population de N individus, deux phases :
 sélectionner l’individu i autant de fois que la partie entière du nombre Ei
avec : Ei = Npi
 La population intermédiaire n’étant pas totalement complète, la
probabilité de sélection de l’individu i est égale à la différence ou au reste
Ri avec Ri = Ei − ent(Ei ) où ent(Ei) est la partie entière de Ei.
 Avantage : la chance qui est attribuée aux moins bons individus d’être
sélectionnés, ce qui procure une meilleure diversité dans la population
intermédiaire.
 Exemple : (population de 100)
 Supposons que l’individu 0 a une probabilité de sélection p0=0,046
 E0 devient égal à 4,6.
 Donc : 4 copies de cet individu dans la population intermédiaire.
 Il peut être sélectionné plus que 4 fois avec une probabilité de R0=0,6.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 19

  Exercice
En considérant les nombres suivants tirés successivement au
hasard, donner la population résultante d’une sélection par les
restes : (0.3, 0.65, 0.47, 0.21,0.87).
Ind pi Ei Ent(Ei) Ri
1 0,186 0,744 0 0,744
2 0,322 1,288 1 0,288
3 0,085 0,34 0 0,34
4 0,407 1,628 1 0,628
1 - 2 -

Première phase : sélection de 2 individus à partir des ent(Ei) → I2 et I4

Deuxième phase : sélection à partir des Ri (deux individus manquants)

I1 : aléa=0,3 < R1=0,744 → I1
I2 : aléa=0,65>R2=0,288 → non
I2 I4 I1 I4
I3 : aléa=0,47>R3=0,34 → non
I4 : aléa=0,21<R4=0,628 → I4

ENSIT, 2024-2025 Soft Computing, B.FAYECH 20

  Elitisme
 A la création d’une nouvelle population, il y a de grandes chances que les
meilleurs chromosomes soient perdus après les opérations de croisement et de
mutation.
 Copie d’un ou plusieurs des meilleurs chromosomes dans la nouvelle
génération, le reste de la population est généré selon l’algorithme de
reproduction.
 Amélioration de l’AG : ne pas perdre les meilleures solutions.

 L’inconvénient de la sélection réside dans le choix exclusif des meilleurs individus de la

population au détriment de la diversité des solutions. L’algorithme risque ainsi de
converger prématurément.

 Pour avoir une bonne exploration de l’espace de recherche, des opérateurs de croisement
et de mutation sont appliqués aux individus sélectionnés pour en créer des nouveaux.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 21

  Il permet l’exploration de l’espace de recherche.
 Une fois la population intermédiaire déterminée, les individus sont aléatoirement répartis
en couples. Les chromosomes sont alors copiés et recombinés de façon à former deux
descendants possédant des caractéristiques issues des deux parents. On forme ainsi la
génération suivante.
 L’opérateur de croisement opère avec une probabilité pc
 Plus ce taux est élevé, plus il y a de nouvelles structures qui apparaissent dans la
population.
 S’il est trop élevé, les bonnes solutions risquent d’être cassées trop vite par rapport à
l’amélioration que peut apporter la sélection.
 Si le taux de croisement est très faible, la recherche risque de stagner à cause du faible
taux d’exploration.
 Les méthodes de croisement les plus utilisées sont le croisement à un point, le croisement
multi-points et le croisement uniforme.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 22

  Croisement à un point :
 Choisir au hasard, un point de croisement pour chaque couple de
chromosomes et effectuer un échange des ensembles d’allèles se trouvant
de part et d’autre de ce point entre les deux parents

ENSIT, 2024-2025 Soft Computing, B.FAYECH 23

  Croisement multi-points :
 Plusieurs points de croisement sont sélectionnés et il y a un échange des
différentes parties d’allèles cernées par ces points, entre les parents.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 24

  Croisement uniforme :
 A l’aide d’un masque qui représente les tirages aléatoires pour
décider de la transmission de la valeur de l’allèle à l’un ou l’autre des
descendants.
 Si, à la même position que l’allèle, la valeur du masque est égale à 1,
l’allèle du parent 1 passe à celui de l’enfant 1 et l’allèle du parent 2
passe à l’enfant 2. Sinon, c’est l’inverse qui se produit.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 25

  Exemple : Croisement deux points avec corrections aléatoire

 Correction : Supprimer à l’extérieur des points de coupe les villes déjà

placées à l’intérieur et remplir les trous aléatoirement par les villes
manquantes

ENSIT, 2024-2025 Soft Computing, B.FAYECH 26

  Exemple du Croisement PMX (Partially Mixed Crossover) :
On remplace le double par la valeur qui était à sa place dans la partie interne sans créer de
nouveaux doublons.
P1 0 7 5 9 2 4 6 8 3 1

P2 7 9 2 3 1 6 5 4 0 8

Croisement et détection
des doubles

E1 0 7 2 3 1 4 6 8 3 1

E2 7 9 5 9 2 6 5 4 0 8

correction

E1 0 7 2 3 1 4 6 8 9 5

E2 7 3 5 9 2 6 1 4 0 8

ENSIT, 2024-2025 Soft Computing, B.FAYECH 27

  Exemple du Croisement OX (Ordred Crossover) :
 On remplie les parties externes avec les villes dans l’ordre dans lequel elles se
trouvent dans le parent correspondant, à partir du deuxième point de coupure sans
créer de doublons.
P1 0 7 5 9 2 4 6 8 3 1

P2 7 9 2 3 1 6 5 4 0 8

Croisement des parties

internes

E1 2 3 1

E2 5 9 2

Remplissage des
parties externes

E1 5 9 2 3 1 4 6 8 0 7

E2 3 1 5 9 2 6 4 0 8 7

ENSIT, 2024-2025 Soft Computing, B.FAYECH 28

  La modification aléatoire de la valeur d’un allèle dans un chromosome.
 Elle joue le rôle de bruit et empêche l’évolution de se figer et garantit que l’optimum
global peut être atteint.
 Cet opérateur évite une convergence prématurée vers les optima locaux.
 Il est appliqué avec une probabilité fixée, pm.
 Le taux de mutation rend la recherche trop aléatoire s’il est trop élevé.
 S’il est trop faible, la recherche risque de stagner.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 29

  Il existe d’autres façons d’effectuer des mutations : transposition de deux allèles
consécutifs, transposition d’allèles dans un chromosome, inversion de l’ordre des allèles
présents entre deux coupes, insertion, etc.

 Il est aussi possible d’associer une probabilité de mutation différente à chaque gène,
selon le principe de l’auto-adaptation, où chaque variable est soumise au processus
d’évolution. L’individu possède ainsi un second chromosome codant ces probabilités.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 30

  Les AGs sont capables de s’adapter à n’importe quel espace de recherche.
 Grâce à leur caractère modulaire, ces algorithmes ont une indépendance presque
totale du problème à optimiser.
 Ils demandent une mesure de la qualité de la solution et nécessitent la définition de
l’espace par un codage et des opérateurs qui lui permettent de le parcourir
efficacement.

 Le principal avantage des AGs par rapport aux autres techniques d’optimisation
(énumératives, « hill-climbing », etc.) consiste en une combinaison de :
 l’exploration de l’espace de recherche, basée sur des paramètres aléatoires, grâce à
une recherche parallèle,
 l’exploitation des meilleures solutions disponibles à un moment donné.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 31

  MAIS
 Il faut tenir compte des spécificités du problème pour concevoir ou choisir le
codage et les opérateurs les plus adéquats.
 Il est nécessaire d’effectuer plusieurs expérimentations pour ajuster les
paramètres de l’algorithme
 taille de la population
 probabilités de croisement et de mutation
 nombre de générations
 technique de remplacement,
 etc.

ENSIT, 2024-2025 Soft Computing, B.FAYECH 32

 1. Ecrire en pseudo code, le corps de l’algorithme génétique de base réalisant G générations et
affichant à la fin la valeur du fitness du meilleur individu rencontré Best, en ayant comme
constantes, types, et fonctions prédéfinis :
- les types chrom (un tableau de L valeurs binaires), population (un tableau de N chromosomes de
type chrom) ;
- les fonctions :
- initialisation : qui crée aléatoirement un chromosome de taille L ;
- eval : qui évalue le fitness d’un chromosome et renvoie un réel ;
- croisement : qui prend deux chromosomes de tailles L, les croise et les remplace par leurs
enfants selon une probabilité pc (le croisement sera réalisé par paires de chromosomes
successifs) ;
- mutation : qui mute un chromosome de taille L avec une probabilité pm ;
- select : qui à partir d’une population pop, sélectionne N chromosomes et renvoie une autre
population (npop) remplie ces derniers.
Pour i de 1 à N
pop[i] initialisation(L)
Fin pour
Best eval(pop[1],L)
Pour i de 2 à N
Si eval(pop[i])>Best alors Best eval(pop[i]) Fin Si
Fin pour
Pour i de 1 à G
npopselect(pop,N)
pour i de 1 à N-1 pas(2)
croisement(npop[i], npop[i+1],L, pc)
Fin pour
pour i de 1 à N
mutation(npop[i],L,pm)
Fin pour
popnpop
Pour i de 1 à N
Si eval(pop[i])>Best alors Best eval(pop[i]) Fin Si
Fin pour
Fin Pour
Ecrire (Best)

Soft Computing, B.FAYECH 33

ENSIT, 2024-2025