Improving evolutionary algorithms by MEANS of an adaptive parameter control approach

Résumé

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.

Date	7 déc. 2012
langue originale	Anglais américain
Établissement diplômant	École de technologie supérieure
Superviseur	Raynald Guilbault (Directeur(-trice)) & Antoine Tahan (Codirecteur(-trice))