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.6 Les techniques non élitistes

4.3.6.1. Algorithme MOGA (Multiple Objective Genetic Algorithm)

En 1993 Fonseca et Fleming ont proposé une méthode, dans laquelle chaque individu de la population est rangé en fonction du nombre d'individus qui le dominent [Fonseca et Fleming, 1993]. Ensuite; ils utilisent une fonction de notation permettant de prendre en compte le rang de l'individu et le nombre d'individus ayant le même rang.

Soit un individu x à la génération t, dominé par p (t) individus. Le rang de cet individu est :

rang(x ,t) = 1 + p (t) (4.11)

Tous les individus non dominés sont de rang 1. Les auteurs calculent la fitness de chaque individu de la façon suivante :

Calcul du rang de chaque individu.

Affectation de la fitness de chaque individu par application d'une fonction de changement d'échelle sur la valeur de son rang. Cette fonction est en général linéaire. Suivant le problème, d'autres types de fonction pourront être envisagés afin d'augmenter ou de diminuer l'importance des meilleurs rangs ou d'atténuer la largueur de l'espace entre les individus de plus fort rang et de plus bas rang.

L'utilisation de la sélection par rang a tendance à répartir la population autour d'un même optimum. Or cela n'est pas satisfaisant pour un décideur car cette méthode ne lui proposera qu'une seule solution. Pour éviter cette dérive, les auteurs utilisent une fonction de partage. L'objectif est de répartir la population sur l'ensemble de la frontière de Pareto.

La technique de partage agit sur l'espace des objectifs. Cela suppose que deux actions qui ont le même résultat dans l'espace des objectifs ne pourront pas être présentes dans la population.

Cette méthode obtient des solutions de bonne qualité et son implémentation est facile. Mais les performances dépendent de la valeur du paramètre óshare utilisé dans la technique de partage. Dans leur article Fonseca et Flaming proposent une méthode de sélection de la meilleure valeur de óshare.

4.3.6.2. Algorithme NSGA (Non dominated Sorting Genetic Algorithm)

Dans la méthode proposée par [Srivinas et Deb 1993], le calcul de fitness s'effectue en séparant la population en plusieurs groupes en fonction du degré de domination au sens de Pareto de chaque individu.

1. Dans la population entière, on recherche les individus non dominés. Ces derniers constituent la première frontière de Pareto.

2. On leur attribue une valeur de fitness factice, cette valeur est supposée donner une chance égale de reproduction à tous ces individus. Cependant pour maintenir la diversité dans la population, il est nécessaire d'appliquer une fonction de partage sur cette valeur.

3. Ce premier groupe d'individu est ensuite supprimé de la population.

4. On recommence cette procédure pour déterminer la seconde frontière de Pareto. La valeur factice de fitness attribuée à ce second groupe est inférieure à la plus petite fitness après application de la fonction de partage sur le premier groupe. Ce mécanisme est répété jusqu'à ce que l'on ait traité tous les individus de la population.

L'algorithme se déroule ensuite comme un algorithme génétique classique. Srivinas et Deb utilisent une sélection basée sur le reste stochastique. Mais leur méthode peut être utilisée avec d'autres heuristiques de sélections (tournoi, roulette pipée, etc.).

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