Improving evolutionary algorithms by MEANS of an adaptive parameter control approach

Corriveau, Guillaume (2012). Improving evolutionary algorithms by MEANS of an adaptive parameter control approach. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (6MB) | Prévisualisation
Prévisualisation	PDF Télécharger (1MB) | Prévisualisation

Résumé

Evolutionary algorithms (EA) constitute a class of optimization methods that is widely used to solve complex scientific problems. However, EA often converge prematurely over suboptimal solutions, the evolution process is computational expensive, and setting the required EA parameters is quite difficult. We believe that the best way to address these problems is to begin by improving the parameter setting strategy, which will in turn improve the search path of the optimizer, and, we hope, ultimately help prevent premature convergence and relieve the computational burden. The strategy that will achieve this outcome, and the one we adopt in this research, is to ensure that the parameter setting approach takes into account the search path and attempts to drive it in the most advantageous direction. Our objective is therefore to develop an adaptive parameter setting approach capable of controlling all the EA parameters at once. To interpret the search path, we propose to incorporate the concept of exploration and exploitation into the feedback indicator.

The first step is to review and study the available genotypic diversity measurements used to characterize the exploration of the optimizer over the search space. We do this by implementing a specifically designed benchmark, and propose three diversity requirements for evaluating the meaningfulness of those measures as population diversity estimators. Results show that none of the published formulations is, in fact, a qualified diversity descriptor. To remedy this, we introduce a new genotypic formulation here, the performance analysis of which shows that it produces better results overall, notwithstanding some serious defects.

We initiate a similar study aimed at describing the role of exploitation in the search process, which is to indicate promising regions. However, since exploitation is mainly driven by the individuals’ fitness, we turn our attention toward phenotypic convergence measures. Again, the in-depth analysis reveals that none of the published phenotypic descriptors is capable of portraying the fitness distribution of a population. Consequently, a new phenotypic formulation is developed here, which shows perfect agreement with the expected population behavior.

On the strength of these achievements, we devise an optimizer diagnostic tool based on the new genotypic and phenotypic formulations, and illustrate its value by comparing the impacts of various EA parameters. Although the main purpose of this development is to explore the relevance of using both a genotypic and a phenotypic measure to characterize the search process, our diagnostic tool proves to be one of the few tools available to practitioners for interpreting and customizing the way in which optimizers work over real-world problems.

With the knowledge gained in our research, the objective of this thesis is finally met, with the proposal of a new adaptive parameter control approach. The system is based on a Bayesian network that enables all the EA parameters to be considered at once. To the authors’ knowledge, this is the first parameter setting proposal devised to do so. The genotypic and phenotypic measures developed are combined in the form of a credit assignment scheme for rewarding parameters by, among other things, promoting maximization of both exploration and exploitation. The proposed adaptive system is evaluated over a recognized benchmark (CEC’05) through the use of a steady-state genetic algorithm (SSGA), and then compared with seven other approaches, like FAUC-RMAB and G-CMA-ES, which are state-of-the-art adaptive methods. Overall, the results demonstrate statistically that the new proposal not only performs as well as G-CMA-ES, but outperforms almost all the other adaptive systems. Nonetheless, this investigation revealed that none of the methods tested is able to locate global optimum over complex multimodal problems. This led us to conclude that synergy and complementarity among the parameters involved is probably missing.

Consequently, more research on these topics is advised, with a view to devising enhanced optimizers. We provide numerous recommendations for such research at the end of this thesis.

Résumé traduit

Les algorithmes évolutionnaires (AE) représentent une classe de méthodes d’optimisation couramment employée afin de résoudre divers problèmes scientifiques complexes. Cependant, les AE convergent souvent prématurément sur un optimum local, le processus évolutif est coûteux et les paramètres internes des AE sont difficilement réglables. Afin de pallier à ces problématiques et améliorer la performance des AE, il nous apparaît nécessaire d’aborder en premier lieu la question du réglage des paramètres. Pour ce faire, l’objectif de la thèse est de développer une méthode adaptative apte à contrôler l’ensemble des paramètres des AE, et ce, en utilisant comme indicateur de rétroaction le concept d’exploration et d’exploitation permettant d’interpréter le chemin de recherche poursuivi par l’optimiseur. Ainsi, le système adaptatif permettra de guider l’optimiseur vers sa direction de recherche optimale, ce qui offrira la possibilité de réduire le phénomène de convergence prématurée et qui devrait influencer positivement les coûts de calcul du processus évolutif.

Dans un premier temps, afin de caractériser l’exploration de l’espace de recherche offert par l’optimiseur, les mesures de diversité génotypique disponibles sont revues et étudiées. Pour ce faire, un banc d’essai spécialement dédié à cette fin est introduit et trois critères de diversité sont proposés pour évaluer la pertinence de ces mesures en tant qu’indicateur de diversité d’une population. Les résultats de cette étude montrent qu’aucune formulation publiée à ce jour n’est en mesure d’estimer adéquatement la diversité. Ce faisant, une nouvelle formulation génotypique est développée et l’analyse de ses performances révèle qu’elle offre généralement une meilleure description de la diversité malgré le fait qu’elle possède certaines lacunes importantes.

Pour caractériser l’exploitation des zones prometteuses pourvues par l’optimiseur, une étude similaire est conduite. Néanmoins, elle est maintenant orientée sur les mesures de convergence phénotypique disponibles puisque l’exploitation est principalement représentée par la réponse des individus. Encore une fois, l’analyse détaillée révèle qu’aucun descripteur phénotypique publié à ce jour n’est susceptible de représenter adéquatement la distribution de solutions d’une population donnée. Par conséquent, une nouvelle formulation phénotypique est développée dans le cadre de cette thèse et une analyse approfondie montre que cet indicateur exprime parfaitement le comportement escompté, et ce, en suivant une variété de populations.

Inspirés par ces réalisations, nous introduisons un outil de diagnostic basé sur la nouvelle formulation génotypique et phénotypique. L’utilité de cet outil est illustré en comparant l’impact que peut engendrer divers paramètres des AE sur le processus de recherche. Bien que le but principal de ce développement soit d’exposer la pertinence d’employer à la fois une mesure génotypique et une mesure phénotypique pour caractériser le processus de recherche, l’outil de diagnostic s’avère être l’un des rares outils à la disposition des utilisateurs des AE permettant d’améliorer le processus de recherche sur des problèmes d’optimisation réels.

Sur la base des connaissances acquises, l’objectif principal de cette thèse est finalement considéré par la mise en place d’une nouvelle approche adaptative permettant de contrôler les paramètres des AE. La proposition est fondée sur l’utilisation d’un réseau Bayesien permettant d’interagir simultanément sur l’ensemble des paramètres des AE. À notre connaissance, il s’agit du premier système adaptatif offrant de telles capacités. En ce qui concerne le schéma de récompense employé par le système pour juger de la productivité des paramètres, les mesures génotypique et phénotypique développées précédemment sont mises à contribution, et ce, en favorisant les paramètres offrant une maximisation de l’exploration et de l’exploitation. La performance de ce système est analysée à l’aide d’un algorithme génétique à état constant (SSGA), et ce, sur un banc d’essai reconnu dans le domaine (CEC’05). De plus, cette nouvelle approche est comparée à sept autres méthodes, dont FAUC-RMAB et G-CMA-ES représentant actuellement l’état de l’art en terme de système adaptatif. Dans l’ensemble, les résultats montrent statistiquement que l’approche proposée est comparable à G-CMA-ES et qu’elle surpasse la plupart des autres méthodes adaptatives. Toutefois, cette étude expose le fait qu’aucune des méthodes considérées n’est capable de localiser l’optimum global sur des problèmes hautement multimodaux. Ceci nous conduit à affirmer qu’il y a sans doute un manque de synergie et de complémentarité entre les différents paramètres impliqués.

Par conséquent, nous recommandons la poursuite des recherches sur ces thèmes avec la perspective d’obtenir de meilleurs algorithmes d’optimisation. Pour ce faire, diverses recommandations sont proposées à la fin de cette thèse.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillement of the requirements for the degree of doctor of philosophy" Bibliogr. : f. [219]-233.
Mots-clés libres:	Algorithmes. adaptatif, AE, contrôle, convergence, mesures de diversité, équilibre, évolutionnaire, exploitation, exploration, mesure, paramètre, prématuré.
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Guilbault, Raynald
Codirecteur:	Codirecteur Tahan, Souheil-Antoine
Programme:	Doctorat en génie > Génie
Date de dépôt:	18 févr. 2013 17:31
Dernière modification:	13 déc. 2016 15:31
URI:	https://espace.etsmtl.ca/id/eprint/1132

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt