Chapitre III Introduction aux algorithmes génétiques 39
IV.1. Concepts et principe des algorithmes génétiques :
Les algorithmes génétiques sont des algorithmes évolutionnistes d’optimisation stochastique
inspirés des mécanismes de l’évolution naturelle (sélection, adaptation, reproduction,
recombinaison, mutation) élaborés par Charles Darwin. Ils sont des algorithmes itératifs de
recherche globale dont le but est d’optimiser une fonction prédéfinie appelée critère ou fonction
coût "fitness". Ils permettent de faire évoluer un ensemble initial de solutions vers un ensemble
final. Les algorithmes génétiques sont utilisés dans l’automatique, le but de cette utilisation est
d’optimiser au maximum les gains des régulateurs utilisés dans la commande. A partir des années
1990, quelques publications évoquent l’utilisation des AG pour la résolution de problèmes
d’optimisation dans le domaine de la commande de systèmes électromécaniques.
Un algorithme génétique recherche le ou les extrema d’une fonction définie sur un espace de
données. Pour l’utiliser, on doit disposer des cinq éléments suivants :
1. Un principe de codage de l’élément de population.
2. Un mécanisme de génération de la population initiale.
3. Une fonction à optimiser appelée fitness ou fonction de l’évaluation des individus.
4. Des opérateurs permettant de diversifier la population au cours des générations et d’explorer
l’espace d’état. L’opérateur de croisement recompose les gènes d’individus existant dans la
population, l’opérateur de mutation a pour but de garantir l’exploration de l’espace d’état.
5. Des paramètres de dimensionnement: taille de la population, nombre total de générations ou
critère d’arrêt, probabilités d’application des opérateurs de croisement et de mutation.
Figure. IV.1. Principe des algorithmes génétiques
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 40
Afin de trouver la solution optimale d’un problème en utilisant l’algorithme génétique, on
commence par générer un ensemble de solutions (population d’individus) de façon aléatoire.
L’évolution d’une génération à la suivante, utilise les trois opérations (Sélection, Croisement et
Mutation) qui sont appliquées à tous les éléments de populations. Des couples de parents P1 et P2
sont sélectionnés en fonction de leurs adaptations. L’opérateur de croisement est appliqué avec une
probabilité Pc et génère des couples d’enfants E1 et E2. Ensuite, l’opérateur de mutation est appliqué
′ ′
aux enfants avec la probabilité Pm et génère des individus mutés et qui vont être insérés dans
la nouvelle population. Parmi les critères d’arrêt qui peuvent être choisis pour l’algorithme, on peut
citer :
• L’atteinte d’un nombre maximal de générations fixé à priori.
• L’obtention après un certain nombre de générations, d’un degré d’uniformité des individus
de la population supérieur à un seuil souhaité.
IV.1.1 La mise en œuvre d’un algorithme génétique :
La mise en œuvre d’un algorithme génétique est réalisée suivant les étapes suivantes :
1. Création d’une population initiale.
2. Evaluation des individus de la population.
3. Sélection des meilleurs individus.
4. Reproduction (Croissement et mutation).
5. Formation d’une nouvelle génération.
La figure suivante montre l’organigramme de fonctionnement d’un algorithme génétique.
Figure IV.2. Organigramme de l’algorithme génétique
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 41
IV.1.2 Vocabulaires des algorithmes génétiques :
Dans cette section nous introduisons quelques vocabulaires utilisés dans la mise en œuvre des
algorithmes génétiques.
• Individu : représenté par un chromosome (génome).
• Un chromosome est une chaîne de gènes.
• Génotype : l’ensemble des gènes représentés par un chromosome.
• Phénotype : l’ensemble des valeurs observables prises par chaque gène.
• Fonction d’adaptation : fitness.
• Opération de reproduction :
Le croissement.
La mutation.
• Génération : l’ensemble de la population à un moment donné du processus.
IV.2. Le codage :
Le codage est une modélisation d’une solution d’un problème donné sous forme d’une séquence
de caractères appelée chromosome où chaque caractère, dit aussi gène, représente une variable ou
une partie du problème. La tâche principale consiste à choisir le contenu des gènes qui facilite la
description du problème et respecte ses contraintes. Il utilise principalement deux types de codage :
le codage binaire, le codage réel :
IV.2.1 Codage binaire :
Dans ce type de codage le chromosome représente simplement une suite de 0 et de 1. Le
codage binaire est également indépendant des opérateurs génétiques (croisement et mutation) du
moment où ces derniers ne nécessitent aucune spécification. En effet, toute manipulation d’un
chromosome donne naissance à un nouveau chromosome valide. Cependant, ce type de codage n’est
pas toujours bon, il est parfois très difficile ou très lourd de coder des solutions de cette manière. En
outre, dans certain cas la taille mémoire requise peut devenir prohibitive.
IV.2.2 Codage réel :
Dans ce type de codage, chaque chromosome est un vecteur dont les composantes sont les
n variables ( , ,…, , ), on peut utiliser tout simplement un chromosome contenant les n
paramètres du processus d’optimisation. Par exemple, si on recherche l’optimum d’une fonction de
variables : ( , ,…, , ), avec ce type de codage, la procédure d’évaluation des
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 42
chromosomes est plus rapide vu l’absence des étapes de codage et de transcodage (du réel vers le
binaire et vice-versa).
IV.3. La population initiale :
Le choix de la population initiale d’individus conditionne fortement la rapidité de l’algorithme.
Pour générer la population initiale, nous avons, deux possibilités. Dans le cas où aucune
information sur la position de la solution n’est disponible, le but est de recouvrir au mieux l’espace
d’état. Une génération aléatoire est donc engendrée par des tirages uniformes sur chaque gène du
chromosome. Dans le cas où l’utilisateur connaîtrait un sous-domaine de l’espace d’état où la
solution se trouve, la population initiale est générée dans ce sous-espace.
Dans le cas d’une génération engendrée de façon aléatoire, il existe deux éventualités. Soit il est
possible de savoir à l’avance si un point respecte les contraintes du problème d’optimisation, la
population est alors générée aléatoirement dans le domaine admissible. Soit il n’est pas possible de
le savoir, le respect des contraintes sera alors assuré via l’ajout d’une pénalisation dans la fonction-
objectif et la population est uniformément distribuée sur tout l’espace d’état.
IV.4. Fonction d’évaluation (fitness) :
L’évaluation de l’adaptation de chaque individu à l’environnement est réalisée au moyen d’une
fonction d’adaptation (fitness). Cette fonction attribue à chaque individu une valeur qui représente
son niveau d’adaptation. La fonction d’adaptation peut affecter directement la qualité des résultats
obtenus par l’AG ainsi que le temps d’exécution. Elle est fonction du critère à minimiser. En raison
de l’analogie avec la théorie de l’évolution (survie des individus les mieux adaptés à leur
environnement), l’algorithme génétique est naturellement formulé en terme de maximisation. Etant
donné une fonction réelle à une ou plusieurs variables, le problème d’optimisation sur l’espace de
( )
recherche s’écrit de la manière suivante :
∈ ( . 1)
coût ℎ :
Dans beaucoup de problèmes, l’objectif est exprimé sous forme de minimisation d’une fonction
∈ ℎ( ) ( . 2)
transformation de la fonction ℎ selon la relation suivante :
Le passage du problème de minimisation à un problème de maximisation est obtenu par
1
( )= ( . 3)
1 + ℎ( )
IV.5 Les opérateurs de base d’un AG:
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 43
Les opérateurs sont fondamentaux pour implanter le processus reproductif caractéristique d’un
AG. De nombreux opérateurs génétiques existent ainsi que différentes stratégies d’implantation. Par
contre, dans ce paragraphe nous n’abordons que les opérateurs les plus simples et les plus utilisés à
savoir : l’opérateur de sélection, de croisement et de mutation, pour ne pas complexifier la méthode
et perdre le sens physique des paramètres de réglage.
IV.5.1 Le croissement :
La naissance d’un nouvel individu, nécessite la prise aléatoire d’une partie des gènes de chacun
des deux parents. Ce phénomène, issu de la nature est appelé croisement (crossover). Il s’agit d’un
processus essentiel pour explorer l’espace des solutions possibles. Une fois la sélection terminée,
les individus sont aléatoirement répartis en couples. Les chromosomes parents sont alors copiés et
recombinés afin de produire chacun deux descendants ayant des caractéristiques issues des deux
parents. Dans le but de garder quelques individus parents dans la prochaine population, on associe à
l’algorithme génétique une probabilité de croisement, qui permet de décider si les parents seront
croisés entre eux ou s’ils seront tout simplement recopiés dans la population suivante. Il existe
plusieurs types de croissement parmi lesquels on trouve : le croissement en 1 point, le croissement
en deux points et le croissement en N points, ces types sont résumés dans la figure suivante :
Figure IV.3 Exemples d’opération de croissement
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 44
IV.5.2 La mutation :
L’opérateur de mutation, en générant de nouveaux gènes, a pour rôle de permettre d’explorer la
totalité (en théorie) de l’espace d’état, ce qui correspond à la propriété d’ergodicité de parcours
d’espace, essentielle aux AG pour leurs propriétés de convergence. En effet les preuves théoriques
de convergence des AG peuvent fonctionner sans croisement, mais pas sans mutation.
L’opérateur de mutation fonctionne comme suit. Pour les problèmes discrets, un gène du
chromosome est tiré aléatoirement et sa valeur est remplacée par une des autres valeurs possibles
(tirée aléatoirement elle aussi). Dans le cas des problèmes continus, le gène est également tiré
aléatoirement, et remplacé par une valeur aléatoire du domaine d’extension des gènes (espace
d’état). La figure suivante montre un exemple de mutation.
x y z t u
Parent 1 1 1 0 1 1 00 0 0 1 0 0 1 1 1 1 0 0 1
14 12 2 7 9
x y z t u
Enfant 1 1 1 0 1 1 10 0 0 1 0 0 1 1 1 1 0 0 1
14 12 2 7 9
Figure IV.4 Exemple de mutation
IV.5.1 La sélection
L’opérateur de sélection est chargé de “ favoriser” les meilleurs individus. Plus formellement,
l’opérateur de sélection va générer à partir de la population courante une nouvelle population par
copie des individus choisis de la population courante. La copie des chaînes s’effectue en fonction
des valeurs de la fonction d’adaptation. Ce procédé permet de donner aux meilleures chaînes, une
probabilité élevée de contribuer à la génération suivante. Cet opérateur est bien entendu une version
artificielle de la sélection naturelle, la survie darwinienne des chaînes les plus adaptées. Plusieurs
stratégies sont possibles pour effectuer une telle sélection parmi lesquelles nous abordons :
La sélection par classement : elle consiste à ranger les individus de la population dans un
ordre croissant (ou décroissant selon l’objectif) et à retenir un nombre fixé de génotypes.
Ainsi, seuls les individus les plus forts sont conservés. L’inconvénient majeur de cette
méthode est la convergence prématurée de l’algorithme génétique.
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 45
La sélection par tournoi : le tournoi le plus simple consiste à choisir aléatoirement un
nombre k d’individus dans la population et à sélectionner celui qui a la meilleure
performance. Les individus qui participent à un tournoi sont remis ou sont retirés de la
compétition, le meilleur gagne avec une probabilité p ∈ [0, 5; 1] ;
population, selon le choix de l’utilisateur. Avec le tournoi binaire, sur deux individus en
IV.6 La convergence d’un AG :
Le cycle de génération et de sélection de population est répété jusqu’à ce qu’un critère d’arrêt
soit satisfait ; ce critère peut être notamment un nombre maximum de générations, un temps
maximal de calcul, une valeur de fitness minimale, ou/et une convergence vers une solution
satisfaisante. Les valeurs de tels paramètres dépendent fortement de la problématique étudiée. Ainsi
il n'existe pas de paramètres qui soient adaptés à la résolution de tous les problèmes qui peuvent être
posés à un algorithme génétique. Cependant, certaines valeurs sont souvent utilisées (définies dans
la littérature) et peuvent être de bons points de départ pour démarrer une recherche de solutions à
l'aide d’un AG.
La probabilité de croissement est choisie dans l’intervalle [0.7, 0.99].
La probabilité de mutation est choisie dans l’intervalle [0.001, 0.01].
IV.7 Exemple simple d’algorithme génétique :
Problématique : On veut trouver l’entier (de 0 à 16) qui maximise la fonction
f ( x) = 1
4 15 x 2 − x3 + 4 .
Population : 6 chromosomes de 4 bits (codage), représentant sous forme binaire les entiers
(individus) qu’ils représentent.
Fonction de qualité : f ( x ) = 1
4 15 x 2 − x3 + 4
Opérateurs génétiques : enjambement : Il y a 50% de chance qu’un bit soit échangé avec son
homologue sur l’autre chromosome.
mutation : Chaque bit a 3% de chance de muter (passer de 1 à 0 ou de 0 à
1).
Population initiale :
Étiquette du Chaîne du Entier décodé Qualité Chances de
Chromosome chromosome (fitness) reproduction
(%)
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 46
X1 0100 4 48 13,58
X2 0000 0 4 1,13
X3 1110 14 53 14,99
X4 0001 1 7,5 2,12
X5 1000 8 116 32,81
X6 1011 11 125 35,36
Moyennes de la qualité (average fitness): 58,917.
Sélection et opérateurs génétiques:
Chromosome enjambement mutation chromosomes finaux
Couple 1 : X5 1000 1000 1010 1010
X3 1110 1110 1100 1100
Couple 2 : X5 1000 1000 1011 1011
X6 1011 1011 1000 1000
Couple 3 : X6 1011 1011 1000 1001
X1 0100 0100 0111 0111
Population pour la génération 2 :
Étiquette du Chaîne du Entier décodé Qualité Chances de
Chromosome chromosome (fitness) reproduction
(%)
X1’ 1010 10 129 18,18
X2’ 1100 12 112 15,79
X3’ 1011 11 125 17,62
X4’ 1000 8 116 16,35
X5’ 1001 9 125,5 17,69
X6’ 0111 7 102 14,38
Moyennes de la qualité (average fitness): 118,25.
La population de la deuxième génération peut maintenant servir pour engendrer une troisième
génération. Bien qu’ici, on ait trouvé la solution optimale (10) en une seule génération, on
remarque quand même que la moyenne des chances de survie a augmenté considérablement. De
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 47
cette façon, on peut conclure que l’algorithme génétique encourage le « perfectionnement de la
race ».
IV.8 Application des AG à l’optimisation du régulateur PID pour la commande
d’une machine synchrone :
Dans cette partie nous détaillons les aspects de la mise en œuvre de l’optimisation des
paramètres du PID par l’utilisation des AG. La structure du régulateur est la même que celle qui a
été présentée dans la section précédente. L’objectif est toujours de trouver l’ensemble des
paramètres optimisés P = [ , , ] de façon à ce que la réponse en vitesse du système
MSAPCEL en boucle fermée soit stable et la plus robuste possible pour toute variation de Jl
appartenant à l’intervalle (II.2). Nous considérons le paramètre du filtre du régulateur PID constant
(a = 0, 5).
Avec l’utilisation de l’AG il est possible de réaliser la recherche de la solution optimale dans un
espace tridimensionnel au détriment de la recherche quasi unidimensionnelle qui a été mise en
œuvre à partir de l’approche itérative. Chaque dimension de l’espace de recherche tridimensionnel
correspond à une variable de l’individu x que nous cherchons à optimiser.
, , == , , ( . 4)
où l’indice i représente un individu quelconque de la population. A titre d’exemple, si la population
est formée par 10 individus, l’indice i varie entre 1 et 10.
Figure IV.5 Principe de l’optimisation d’un correcteur PID par algorithme génétique
De la même façon, que nous avons borné l’incertitude de l’inertie de la charge mécanique Jl
selon l’intervalle définie dans le cours, une région d’espace D limite les valeurs possibles des
paramètres du régulateur PID, défini par les meilleurs coefficients pour les bornes Jmin d’une part et
Jmax d’autre part. A partir de quelques connaissances sur le système à régler et sur la conception
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 48
d’un régulateur de type PID, nous pouvons borner la région de recherche de la solution optimale
tout en garantissant l’optimisation de l’approche, de façon à ce que le temps de convergence de
l’AG soit largement réduit.
= ∗ ∗ = ∗ ∗ , ( . 5)
L’approche d’optimisation du régulateur PID par AG est définit dans les étapes suivantes :
a) Définition de la population initiale
La population initiale est choisie de façon aléatoire dans un espace de recherche de solutions.
L’intervalle de variation de chaque variable de D est définit de la façon suivante :
= (1)
1 Nous adoptons l’extrémité de la plage de variations de Jl comme référence pour le système :
= (2)
•
•
2 Pour chaque référence d’inertie nous calculons, à partir des simulations du système de
commande de la machine synchrone complet en boucle fermée, les valeurs maximales de
chaque coefficient , et en respectant le critère de robustesse et stabilité. Comme
résultat nous avons deux ensembles de paramètres du régulateur :
, ,
, ,
• Ensemble (1) :
• Ensemble (2) :
3 L’espace de recherche D est définit par :
= 0 max , ∗ 0 max , ∗ 0 max , ( . 6)
Pour la définition des limites de l’espace de recherche D la seule contrainte physique
imposée étant la tension maximale du bus continu de l’onduleur de tension. Aucune
limitation en ce qui concerne le couple ou le courant statorique maximum n’a été imposée.
De cette façon nous garantissons que les valeurs optimales du régulateur PID sont incluses
= ∈ [0 max ( , )]
dans l’espace de recherche D.
= ∈ 0 max , ( . 7)
= ∈ [0 max ( , )]
b) La fonction d’adaptation
L’inverse de l’intégrale de l’erreur quadratique (ISE) entre la vitesse de référence de la charge
mécanique et la vitesse réelle est utilisé comme fonction d’adaptation à maximiser sur un
intervalle T :
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 49
1
( , , )= ( . 8)
1
−
La fonction d’adaptation des individus qui génèrent des pôles du système positifs (instabilité) ou
qui génèrent un couple moteur supérieur à deux fois Cem doit permettre de fortement les pénaliser.
De plus, l’adaptation de chaque individu d’une population doit être calculée sur toute la plage de
variation de l’inertie de la charge mécanique. En sachant que le système en boucle fermée a un
comportement linéaire sur la variation paramétrique, nous calculons la fonction d’adaptation de
1
chaque individu selon l’équation suivante :
( , , )= ( . 9)
1
∑ − [ ( , )] ∗
Où représente la transformation inverse de Laplace, et * représente une convolution temporelle.
La fonction de transfert incertaine entre le couple moteur et la vitesse de la charge ( , ), est
( , )
donnée par :
1
= ( . 10)
+ ( + ) +
( + ) + + +1
( + ) ( + ) ( + )
c) L’opérateur de sélection
Nous utilisons la méthode de sélection géométrique normalisée qui est une méthode de
sélection de rang basée sur une distribution géométrique normalisée. Cette méthode limite la
probabilité de sélection du meilleur individu au début des premières générations. Avec cette
è
méthode, la probabilité de sélection du individu dans une population de taille est donnée
par:
(1 − )
= ( . 11)
1 − (1 − )
où est un coefficient de sélection du meilleur individu et est son rang. Le rang d’un individu est
l’indice de la population dans laquelle il a été remarqué comme n’étant dominé par aucun autre
individu. De l’ensemble d’individus d’une population, vous sortez ceux qui ne sont dominés par
aucun autre individu, et vous leur attribuez le rang 1. Sur les individus qui ne sont pas sortis du lot,
vous recommencez l’opération, en cherchant ceux qui ne sont dominés par aucun des individus
restants et vous leur attribuez le rang 2 et ainsi de suite jusqu’à épuisement de la population. Les
individus jugés les meilleurs sont ceux de rang le plus faible.
d) L’opérateur de croisement
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 50
Dans le cadre de notre étude nous utilisons le croisement arithmétique. Les croisements sont
envisagés avec deux individus d’une même population ( , ), généralement appelés pères.
Comme résultat de ce croisement, nous avons deux nouveaux individus ( , ), lesquels sont
= + (1 − )
appelés fils. Ce type de croisement est défini de la façon suivante :
( . 12)
= (1 − ) +
où est une variable de pondération aléatoire, comprise entre 0 et 1. Le nombre de fois que le
croisement arithmétique doit être appliqué à chaque génération est défini par la probabilité de
croisement .
e) L’opérateur de mutation
Nous utilisons une mutation réelle du type uniforme. Chaque individu d’une population quelconque
est changé selon une certaine probabilité par une valeur aléatoire tirée suivant une distribution
uniforme sur l’intervalle des solutions possibles ou sur un intervalle spécifique de mutation .
Dans notre cas de figure, nous considérons que l’intervalle est identique à l’intervalle .
f) L’itération
Les étapes de l’Algorithme Génétique (a)-(e) sont exécutées jusqu’au moment où la valeur de
la fonction d’adaptation des individus n’évoluent plus, ou lorsque le nombre maximum de
générations est atteint.
Le tableau IV.1 présente les valeurs des principaux paramètres utilisés pour l’exécution de
l’algorithme génétique proposé. Le choix de ces paramètres est aussi basé sur de nombreux essais
de performance et de convergence de l’AG.
Tableau IV.1 Paramètres de l’algorithme génétique.
Paramètre
Paramètres Symbole
Symboles Valeur
Valeurs
Taille de la population 50
Nombre de génération 100
Coefficient de sélection 0.08
Probabilité de croissement 0.7
Probabilité de mutation 0.05
Les simulations de la commande de la machine synchrone sont réalisées à l’aide du logiciel
Matlab/Simulink. Nous avons évalué les réponses du système à un échelon de vitesse et nous nous
Chargé de cours : Dr. Mohamed Assaad HAMIDA
Chapitre III Introduction aux algorithmes génétiques 51
avons observé le comportement du système. Les gains des correcteurs PID classique et PID par
algorithme génétique sont mentionnés sur le tableau IV.1. La réponse du système en utilisant le
régulateur basé sur l’AG est relativement meilleure (moins de dépassement, temps de réponse
inférieur à 0,3s) que celle obtenue avec le régulateur classique. Le tableau IV.2 résume les résultats
obtenus.
Tableau IV.2 Résumé des résultats des simulations, d’un régulateur PID optimisé
PID classique PID
PID AG
AG
Dépassement maximum 14,2 % 5,64 %
Temps de réponse maximum ( ) 0.345s 0.209s
Temps de réponse minimum ( ) 0.029s 0.021s
Variation du temps de réponse 1.117% 996%
Ces résultats montrent clairement l’intérêt de l’utilisation des algorithmes génétiques pour obtenir
une optimisation optimale du correcteur PID.
Chargé de cours : Dr. Mohamed Assaad HAMIDA
