Algorithme évolutif de Pareto fort

L’objectif de l’algorithme est de localiser et de maintenir un front de solutions non dominées, idéalement un ensemble de solutions optimales de Pareto. Ceci est réalisé en utilisant un processus évolutif (avec des procédures de substitution pour la recombinaison génétique et la mutation) pour explorer l’espace de recherche, et un processus de sélection qui utilise une combinaison du degré de domination d’une solution candidate (forte) et d’une estimation de la densité du front de Pareto comme une fitness assignée. Une archive de l’ensemble non dominé est maintenue séparée de la population de solutions candidates utilisées dans le processus évolutif, fournissant une forme d’élitisme.

La fonction CalculateRawFitness calcule la fitness brute comme la somme des valeurs de force des solutions qui dominent un candidat donné, où force est le nombre de solutions qu’une solution donnée domine. La fonction CandidateDensity estime la densité d’une zone du front de Pareto comme 1/(o^k + 2) où o^k est la distance euclidienne des valeurs objectives entre une solution donnée, le kème plus proche voisin de la solution, et k est la racine carrée de la taille de la population et des archives combinées. La fonction PopulateWithRemainingBest remplit de manière itérative l’archive avec les solutions candidates restantes par ordre de fitness. La fonction RemoveMostSimilar tronque la population d’archives en supprimant les membres avec les valeurs o^k les plus petites calculées par rapport à l’archive. La fonction SelectParents sélectionne les parents d’une population à l’aide d’une méthode de sélection de l’algorithme génétique telle que la sélection de tournois binaires. La fonction CrossoverAndMutation effectue les opérateurs génétiques de croisement et de mutation de l’algorithme génétique.

SPEA a été conçu et adapté aux instances de problèmes d’optimisation à objectifs multiples combinatoires et à fonction continue. Une représentation binaire peut être utilisée pour des problèmes d’optimisation de fonction continue en conjonction avec des opérateurs génétiques classiques tels que le croisement à un point et la mutation ponctuelle. Une valeur k de 1 peut être utilisée pour l’efficacité tout en fournissant des résultats utiles. La taille des archives est généralement plus petite que la taille de la population.