WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Contribution à  l'optimisation complexe par des techniques de swarm intelligence

( Télécharger le fichier original )
par Lamia Benameur
Université Mohamed V Agdal Rabat Maroc - Ingénieur spécialité : informatique et télécommunications 0000
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

1.2.3.2. Les algorithmes évolutifs (AE)

Les algorithmes évolutifs (Evolutionary Algorithms) sont des techniques de recherche inspirées de l'évolution biologique des espèces, apparues à la fin des années 1950. Parmi plusieurs approches [Holland, 1962], [Fogel et al, 1966], [Rechenberg, 1965], les algorithmes génétiques (AG) constituent certainement les algorithmes les plus connus [Goldberg, 1989a].

Le principe d'un algorithme évolutionnaire est très simple. Un ensemble de N points dans un espace de recherche, choisi a priori au hasard, constituent la population initiale; chaque individu x de la population possède une certaine performance, qui mesure son degré d'adaptation à l'objectif visé : dans le cas de la minimisation d'une fonction objectif f, x est d'autant plus performant que f(x) est plus petit. Un AE consiste à faire évoluer progressivement, par générations successives, la composition de la population, en maintenant sa taille constante. Au cours des générations, l'objectif est d'améliorer globalement la performance des individus; le but étant d'obtenir un tel résultat en imitant les deux principaux mécanismes qui régissent l'évolution des êtres vivants, selon la théorie de Darwin :

la sélection, qui favorise la reproduction et la survie des individus les plus performants,

la reproduction, qui permet le brassage, la recombinaison et les variations des caractères héréditaires des parents, pour former des descendants aux potentialités nouvelles.

En fonction des types d'opérateurs, i.e., sélection et reproduction génétique, employés dans un algorithme évolutif, quatre approches différentes ont été proposées [Bäck et al, 1997] : les algorithmes génétiques (AG), la programmation génétique (PG), les stratégies d'évolution (SE) et la programmation évolutive (PE) que nous

allons décrire par la suite. La structure générale d'un AE est donnée par le pseudo code (7).

algorithme 1 Structure de base d'un algorithme évolutif

Algorithme évolutif

t 4-- 0

Initialiser la population P(t)

Evaluer P(t)

Répéter

t 4-- t + 1

Sélectionner les parents

Appliquer les opérateurs génétiques

Evaluer la population des enfants crées

Créer par une stratégie de sélection la nouvelle population P(t) Tant que (condition d'arrêt n'est pas satisfaite)

a. Les algorithmes génétiques (Genetic Algorithms)

Les algorithmes génétiques sont des techniques de recherche stochastiques dont les fondements théoriques ont été établis par Holland [Holland, 1975]. Ils sont inspirés de la théorie Darwinienne : l'évolution naturelle des espèces vivantes. Celles-ci évoluent grâce à deux mécanismes : la sélection naturelle et la reproduction. La sélection naturelle, l'élément propulseur de l'évolution, favorise les individus, d'une population, les plus adaptés à leur environnement. La sélection est suivie de la reproduction, réalisée à l'aide de croisements et de mutations au niveau du patrimoine génétique des individus. Ainsi, deux individus parents, qui se croisent, transmettent une partie de leur patrimoine génétique à leurs progénitures. En plus, quelques gènes des individus, peuvent être mutés pendant la phase de reproduction. La combinaison de ces deux mécanismes, conduit, génération après génération, à des populations d'individus de plus en plus adaptés à leur environnement. Le principe des AG est décrit par le pseudo code (8).

algorithme 2 Structure de base d'un algorithme génétique

Algorithme Génétique

t 4-- 0

Initialiser la population P(t)

Evaluer P(t)

Répéter

t 4-- t + 1

P(t) = Sélectionner (P(t - 1)) Croiser (P(t))

Muter (P(t))

Evaluer P(t)

Jusqu'à (condition d'arrêt validée)

Dans leur version canonique, les AG présentent des limites qui conduisent le plus souvent à des problèmes de convergences lente ou prématurée. Pour pallier à ces inconvénients, des améliorations ont été apportées : e.g, codage, opérateurs biologiques, stratégie élitiste, etc. les détails de fonctionnement de ces algorithmes peuvent être trouvés dans plusieurs références principalement : [El Imrani, 2000], [Michalewicz, 1996].

b. Programmation génétique (Genetic Programming)

La programmation génétique est une variante, des algorithmes génétiques, destinée à manipuler des programmes [Koza, 1992] pour implémenter un modèle d'apprentissage automatique. Les programmes sont généralement codés par des arbres qui peuvent être vus comme des chaînes de bits de longueur variable. Une grande partie des techniques et des résultats concernant les algorithmes génétiques peuvent donc également s'appliquer à la programmation génétique.

c. Stratégies d'évolution (Evolutionary Strategy)

Les stratégies d'évolution forment une famille de métaheuristiques d'optimisation. Elles sont inspirées de la théorie de l'évolution. Ce modèle fut initialement proposé par Rencherberg [Rechenberg, 1965]. il constitue, à ce titre, la première véritable métaheuristique et le premier algorithme évolutif.

Dans sa version de base, l'algorithme manipule itérativement un ensemble de vecteurs de variables réelles, à l'aide d'opérateurs de mutation et de sélection. L'étape de mutation est classiquement effectuée par l'ajout d'une valeur aléatoire, tirée au sein d'une distribution normale. La sélection s'effectue par un choix déterministe des meilleurs individus, selon la valeur de la fonction d'adaptation.

Les strategies d'évolution utilisent un ensemble de u "parents" pour produire A "enfants". Pour produire chaque enfant, p parents se "recombinent". Une fois produits, les enfants sont mutés. L'étape de sélection peut s'appliquer, soit uniquement aux enfants, soit à l'ensemble (enfants + parents). Dans le premier cas, l'algorithme est noté (u, A)--ES, dans le second (u + A)--ES [Schoenauer et Michalewicz, 1997].

À l'origine, l'étape de recombinaison était inexistante, les algorithmes étant alors notés ((u, A)--ES ou (u + A)--ES. Les méthodes actuelles utilisent l'opérateur de recombinaison, comme les autres algorithmes évolutifs, afin d'éviter d'être piégées dans des optima locaux.

Une itération de l'algorithme général procède comme suit :

1. À partir d'un ensemble de u parents,

2. produire une population de A enfants:

a. choisir p parents,

b. recombiner les parents pour former un unique individu,

c. muter l'individu ainsi crée,

3. sélectionner les i meilleurs individus.

d. Programmation évolutive (Evolutionary Programming)

La programmation évolutive a été introduite par Laurence Fogel en 1966 [Fogel et al, 1966] dans la perspective de créer des machines à état fini (Finite State Machine) dans le but de prédire des événements futurs sur la base d'observations antérieures.

La programmation évolutive suit le schéma classique des algorithmes évolutifs de la façon suivante :

1. on génère aléatoirement une population de n individus qui sont ensuite évalués;

2. chaque individu produit un fils par l'application d'un opérateur de mutation suivant une distribution normale;

3. les nouveaux individus sont évalués et on sélectionne de manière stochastique une nouvelle population de taille n (les mieux adaptés) parmi les 2m individus de la population courante (parents + enfants);

4. on réitère, à partir de la deuxième étape, jusqu'à ce que le critère d'arrêt choisi soit valide.

La programmation évolutive partage de nombreuses similitudes avec les stratégies d'évolution : les individus sont, a priori, des variables multidimensionnelles réelles et il n'y a pas d'opérateur de recombinaison. La sélection suit une stratégie de type

(i + A).

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy