CHAPlTRE lll
Les méthodes
métaheuristiques
III --Les méthodes métaheuristiques
III - 1 Introduction
Ce chapitre est consacré à la
présentation les algorithmiques génétiques et la
méthode de particules d'essaim pour la résolution du
problème d'optimisation de
l'écoulement de puissance dans le système
électrique. Les algorithmes génétiques sont des
algorithmes d'optimisation s'appuyant sur des
techniques dérivées de la génétique et de
l'évolution naturelle1 : croisements, mutations,
sélection, etc. Les algorithmes génétiques ont
déjà une histoire relativement ancienne, puisque les premiers
travaux de John Holland sur les systèmes adaptatifs remontent à
1962.
III -2 Les algorithmes génétiques
Un algorithme génétique recherche le ou les extrema
d'une fonction défini 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. Cette étape
associe à chacun des points de l'espace
d'état une structure de données. Elle se place
généralement après une phase de modélisation
mathématique du problème traité. Le choix du codage des
données conditionne le succès des algorithmes
génétiques. Les codages binaires ont été
très employés à l'origine. Les codages
réels sont désormais largement utilisés, notamment dans
les domaines applicatifs, pour l'optimisation de
problèmes à variables continues.
2. Un mécanisme de génération de la
population initiale. Ce mécanisme doit être capable de produire
une population d'individus non homogène qui servira de
base pour les générations futures. Le choix de la population
initiale est important car il peut rendre plus ou moins rapide la convergence
vers l'optimum global. Dans le cas oft l'on
ne connaît rien du problème à résoudre, il est
essentiel que la population initiale soit répartie sur tout le domaine
de recherche.
3. Une fonction à optimiser. Celle-ci prend ses
valeurs dans R+ et est appelée fitness ou fonction
d'évaluation de l'individu. Celle-ci
est utilisée pour sélectionner et reproduire les meilleurs
individus de la population.
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 [18].
Principe
Un algorithme génétique est un algorithme
itératif de recherche d'optimum, il manipule une population de taille
constante. Cette population est formée de points candidats
appelés chromosomes. La taille constante de la population entraîne
un phénomène de compétition entre les chromosomes. Chaque
chromosome représente le codage d'une solution potentielle au
problème à résoudre, il est constitué d'un ensemble
d'éléments appelés gènes, pouvant prendre plusieurs
valeurs appartenant à un alphabet non forcément numérique
[19] [20].
A chaque itération, appelée
génération, est créée une nouvelle population avec
le même nombre de chromosomes. Cette génération consiste en
des chromosomes mieux "adaptés" à leur environnement tel qu'il
est représenté par la fonction sélective. Au fur et
à mesure des générations, les chromosomes vont tendre vers
l'optimum de la fonction sélective. La création d'une nouvelle
population à partir de la précédente se fait par
application des opérateurs génétiques que sont : la
sélection, le croisement et la mutation. Ces
opérateurs sont stochastiques [20].
III - 2.1 Codage des chromosomes et
décodage
Il y a plusieurs types de codage : binaire, réel, codage
de gray et codage dynamique des paramètres. Chacun ayant ses propres
avantages et inconvénients. Les plus utilisés sont
présentés ci-dessous.
| 
