4.5 Les algorithmes génétiques
Les algorithmes génétiques 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. Ils appartiennent
á la classe des algorithmes évolutionnaires.
4.5.1 Présentation
Dans la nature, les êtres vivants croisent et
interagissent les uns avec les autres. Chaque individu est
caractérisé par un génotype indépendant de
l'environnement où il vit. Les opérateurs
génétiques fonctionnent au niveau génotypique tandis que
le mécanisme de sélection opère au niveau
phénotypique (le phénotype d'un individu est l'ensemble des
traits caractéristiques d'un individu, alors que le génotype est
le codage de ces traits en gènes). Les algorithmes
génétiques sont à la base des algorithmes d'optimisation
stochastiques, mais peuvent également servir pour l'apprentissage
automatique, par exemple. Les principes fondamentaux des algorithmes
génétiques dans le cadre de l'optimisation mathématique
ont été développés entre 1960 et 1970 par John
Holland. [13]
4.5.2 L'analogie entre la génétique
biologique et algorithme génétiques
On résume dans le tableau suivant l'analogie qui se
trouve entre les termes employés en génétique biologique
et ceux employés pour les algorithmes génétiques:
|
Problème d'optimisation
|
Système biologique.
|
|
Ensemble des points de l'espace de recherche
|
Génotype.
|
|
Ensemble particulier de points de l'espace de recherche
|
Population.
|
|
Un point particulier de l'espace de recherche
|
Individu.
|
|
Ensemble de variables caractérisant un point de
l'espace
|
Chromosome.
|
|
Une variable
|
Gène.
|
|
Valeur possible de la variable
|
Allèle.
|
TABLE 4.2 - Analogie génétique
biologique/algorithme génétiques
73
4.5. LES ALGORITHMES GÉNÉTIQUES
4.5.3 Le principe d'un algorithme
génétique
A. Initialisation
A.1. Codage des données
Le codage est une partie très importante des
algorithmes génétiques, il permet de représenter une
solution x du problème d'optimisation par une séquence (string)
de caractères, cette séquence sera appelée individu, elle
constitue l'ensemble des gènes du chromosome. Plusieurs codages sont
employés. Voici quelques exemples. [13]
· Le codage binaire : représente
une solution par une suite de variables binaires.
· Le codage par permutations de valeurs
entières : le gène est codé par une valeur
entière dans un ensemble de cardinalité égale au nombre de
gènes.
A.2. Fonction fitness d'un individu
A un individu donné est associée une fonction
fitness (forme physique), elle mesure la performance de cet individu et a pour
but d'évaluer si un individu est mieux adapté qu'un autre
à son environnement. Elle est évidemment étroitement
liée avec la fonction objectif du problème d'optimisation.
[13]
A.3. Population initiale
Différents individus sont considérés,
souvent générés aléatoirement afin d'assurer une
population diversifiée. La population initiale est ainsi
constituée d'un ensemble d'individus {1,...,N} et le
paramètre n est appelé taille de la population.
La taille N d'une population est un paramètre important
d'un algorithme génétique. Elle doit être fixée en
tenant compte de la longueur d'un individu, une taille grande favorise une
meilleur diversification mais au prix d'un plus grand temps de calcul pour une
itération. [13]
74
4.5. LES ALGORITHMES GÉNÉTIQUES
| 
