4.5.2.2. Les méta- heuristiques
évolutionnaires/génétiques
4.5.2.2.1. Origines
Les algorithmes génétiques appartiennent
à une famille d'algorithmes appelés méta- heuristique dont
le but est d'obtenir une solution approchée [25,26], en un temps
correct, à un problème d'optimisation, lorsqu'il n'existe pas de
méthode exacte pour le résoudre. Les algorithmes
génétiques utilisent la notion de sélection naturelle
développée par le scientifique Charles Darwin au XIXème
siècle.
Dans cette théorie, une population d'individus
évolue grâce au mécanisme de la reproduction sexuée.
Les individus les plus adaptés à leur milieu se reproduisent plus
que les autres, favorisant les caractères les plus adaptés. Ainsi
une girafe avec un cou plus long que les autres aura accès à plus
de nourriture, et aura donc plus de chances de survivre et de se reproduire.
Ses descendants auront un cou plus long, et en moyenne la population de girafe
aura un cou plus long.
L'utilisation d'algorithmes génétiques dans la
résolution de problèmes est à l'origine des recherches de
John Holland dès 1960. La nouveauté introduite a
été la prise en compte de l'opérateur crossing over en
complément des mutations, et c'est cet opérateur qui permet le
plus souvent de se rapprocher de l'optimum d'une fonction en combinant les
gènes contenus dans les différents individus de la population
[22,28,29].
4.5.2.2.2. Principe
Les algorithmes génétiques classiques introduits
par Holland s'appuient fortement sur un codage universel sous forme de
chaînes 0/1 de longueur fixe et un ensemble d'opérateurs
génétiques : les sélections, les crossing over ou
recombinaison et les mutations. Un individu sous ce codage, appelé un
chromosome, représente une configuration du problème. Les
opérateurs « génétiques » sont définis de
manière à opérer aléatoirement sur un ou deux
individus sans aucune connaissance sur le problème.
La génétique a mis en évidence
l'existence de plusieurs opérateurs au sein d'un organisme donnant lieu
au brassage génétique. Ces opérations interviennent lors
de la phase de reproduction lorsque les chromosomes de deux organismes
fusionnent.
Ces opérations sont imitées par les algorithmes
génétiques afin de faire évoluer les populations de
solutions de manières progressives.
Les sélections :
Pour déterminer quels individus sont plus enclins
à obtenir les meilleurs résultats, une sélection est
opérée. Ce processus est analogue à un processus de
sélection naturelle, les individus les plus adaptés gagnent la
compétition de la reproduction tandis que les moins adaptés
meurent avant la reproduction, ce qui améliore globalement
l'adaptation.
Il existe plusieurs techniques de sélection, les
principales sont :
1- Sélection par rang,
2- Probabilité de sélection proportionnelle
à l'adaptation,
3- Sélection par tournoi,
4- Sélection uniforme.
Les crossing over ou recombinaison :
Lors de cette opération, deux chromosomes
s'échangent des parties de leurs chaînes, pour donner de nouveaux
chromosomes. Ces crossing over peuvent être simples ou multiples. Dans le
premier cas, les deux chromosomes se croisent et s'échangent des
portions d'ADN en un seul point. Dans le deuxième cas, il y a plusieurs
points de croisement. Pour les algorithmes génétiques, c'est
cette opération qui est prépondérante. Sa
probabilité d'apparition lors d'un croisement entre deux chromosomes est
un paramètre de l'algorithme génétique. En règle
générale, on fixe la proportion d'apparition à 0.7.
Les mutations :
D'une façon aléatoire, un gène peut, au
sein d'un chromosome être substitué à un autre. De la
même manière que pour les crossing over, on définit ici un
taux de mutation lors des changements de populations qui est
généralement compris entre 0.001 et0.01. Il est nécessaire
de choisir pour ce taux une valeur relativement faible de manière
à ne pas tomber dans une recherche aléatoire et conserver le
principe de sélection et d'évolution. La mutation sert à
éviter une convergence prématurée de l'algorithme.
Codage :
Pour les algorithmes génétiques, un des facteurs
les plus importants, si ce n'est le plus important, est la façon dont
sont codés les solutions, c'est-à-dire les structures de
données qui coderont les gènes.
Codage binaire :
Le principe est de coder la solution selon une chaîne de
bit. Ce type de codage est le plus utilisé car il présente
plusieurs avantages [26,27,28,29]. Il existe au moins un coté
négatif qui fait que d'autres existent. Ce codage est peu naturel par
rapport à un problème donné.
Codage à caractère multiple :
Ce type de codage est plus naturel que le codage binaire. Il
est utilisé dans de nombreux cas poussés [26,27,28,29,30].
Codage sous forme d'arbre :
Ce codage utilise une structure arborescente avec une racine
de laquelle peuvent être issus un ou plusieurs fils. Un de leurs
avantages est qu'ils peuvent être utilisés dans le cas de
problèmes ou les solutions n'ont pas une taille finie. Les arbres de
tailles quelconque peuvent être formés par le biais de crossing
over et de mutations.
Le problème de ce type de codage est que les arbres
résultants sont souvent difficiles à analyser et que l'on peut se
retrouver avec des arbres dont la taille est importante.
Pour le choix du type de codage, il suffit de choisir celui
qui semble le plus naturel en fonction du problème à traiter et
développer ensuite l'algorithme de traitement.
Bien que les algorithmes génétiques soient
considérés aujourd'hui comme une méthode d'optimisation,
l'objectif initial consistait à concevoir des systèmes
d'apprentissage généraux, robustes et adaptatifs, applicables
à une large classe de problèmes.
L'universalité d'un tel algorithme pose
évidemment des problèmes d'efficacité en pratique. En
effet, en tant que méthode d'optimisation, un algorithme
génétique classique se base uniquement sur des opérateurs
« aveugles ». Une autre voie intéressante pour
améliorer l'efficacité des algorithmes génétiques
consiste à combiner le cadre génétique avec d'autres
méthodes de résolution [28].
| 
