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

4.3.7.3. Algorithme PESA (Pareto Envelope based Selection Algorithm)

La méthode PESA a été également proposée par Knowles et corne [Knowles et al., 2000]. Elle reprend approximativement le principe de crowding développé dans PAES et définit un paramètre appelé "squeeze_factor" qui représente la mesure d'encombrement d'une zone de l'espace. Alors que PAES est basé sur une stratégie d'évolution, PESA est une méthode basée sur les algorithmes génétiques. Elle définit deux paramètres concernant la taille des populations d'individus : PI (taille de la population interne) et PE (taille de la population externe ou archive).

4.3.7.4. Modèle NSGA II

Dans cette deuxième version de NSGA [Deb, 2000]; l'auteur tente de résoudre les problèmes liés à l'approche NSGA : complexité, non élitisme et utilisation du partage.

La complexité de l'algorithme NSGA est notamment due à la procédure de création des différentes frontières. Pour diminuer la complexité de calcul de NSGA, Deb propose une modification de la procédure de tri de la population en plusieurs frontières.

La deuxième difficulté liée à l'approche NSGA est l'utilisation de la méthode de partage qui exige le réglage d'un ou plusieurs paramètre(s) et qui nécessite un temps de calcul important. Dans NSGA II, Deb remplace la fonction de partage par une fonction de remplissage.

Enfin, le modèle proposé utilise une sélection par tournoi pour permettre la conservation des meilleurs individus d'une génération à l'autre.

4.3.7.5. Modèle PESA II (Region-based Selection)

PESA II est une technique de sélection basée sur l'utilisation d'hypercubes dans l'espace des objectifs [Corne, 2001]. Au lieu d'effectuer une sélection en fonction de la fitness des individus comme dans PESA, cette méthode effectue une sélection par rapport aux hypercubes occupés par au moins un individu. Après avoir sélectionné l'hypercube, on choisit aléatoirement l'individu dans l'hypercube. Cette méthode se montre plus efficace à repartir les solutions sur la frontière de Pareto. Cela est dû à sa capacité de choisir avec une plus grande probabilité que le tournoi classique, des individus situés dans des zones désertiques.

4.3.7.6. Algorithme Micro-GA (Micro-Genetic Algorithm)

Coello trouve que les recherches actuelles n'accordent pas assez d'importance à l'efficience des méthodes d'optimisation multiobjectifs. Dans [Coello et al., 2001], il propose une méthode basée sur une population avec un nombre très faible d'individus. Cette technique se base sur les résultats théoriques obtenus par Goldberg [Goldberg, 1989b].

Coello applique le mécanisme suggéré par Goldberg aux problèmes d'optimisation multiobjectifs en utilisant un algorithme génétique avec une petite taille de population associée à une archive et une heuristique de distribution géographique. Il définit une population extérieure divisée en deux parties : une partie remplaçable et une partie non remplaçable. La portion non remplaçable ne change pas durant le processus de modification et sert à maintenir la diversité. Elle ne sera mise à jour que lorsque le micro algorithme génétique aura convergé. La portion remplaçable est totalement modifiée à intervalle régulier. Ce dernier est défini en nombre de cycles du micro GA.

Au début de l'algorithme du micro GA, la population est constituée à l'aide d'individus sélectionnés aléatoirement dans la population externe. Ensuite l'algorithme se déroule de manière classique. En fin de cycle, lorsque la population du micro GA a perdu sa diversité, deux individus non dominés sont sélectionnés pour mettre à jour l'archive. L'approche utilisée est similaire à celle de PAES. Ensuite ces deux mêmes individus sont comparés à deux individus de la partie non remplaçable. Si l'un des deux premiers domine l'un des deux autres alors il le remplace dans la partie non remplaçable.

Les tests effectués par l'auteur montrent que cette approche est capable de converger plus rapidement vers la surface de Pareto (en terme de temps CPU). Mais pour le cas de fonctions avec contraintes, la méthode a été moins bonne que NSGA II. Dans quelque cas, cette méthode produit une meilleure distribution des points sur la surface de Pareto.

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