Design of multiobjective optimization algorithms and theoretical analysis of evolution strategies

Conception d'algorithmes d'optimisation multiobjective et analyse théorique des stratégies d'évolution Ce travail concerne les algorithmes d'optimisation de type black-box, où seulement une suite des valeurs de la fonction à optimiser est disponible pour mettre à jour l'instance de l'algorithme d'optimisation. Les algorithmes évolutionnaires ont une bonne réputation pour la résolution de ce genre de problèmes, notamment le CMA-ES. Des aspects particuliers du CMA-ES sont le mécanisme de recombinaison et la sélection non-élitiste, qui sont cruciaux pour l'optimisation des fonctions irrégulières et multimodales. Un CMA-ES multiobjectif (avec recombinaison et sélection non-élitiste) est ainsi en forte demande pour les applications du monde réel, notamment pour résoudre les problèmes multiobjectifs avec des fronts de Pareto locaux.Nous concevons ce type d'algorithmes. Plus spécifiquement, un nouvel indicateur multiobjectif appelé Uncrowded Hypervolume Improvement (UHVI) est proposé, de même qu'un cadre d'algorithmes multiobjectifs appelé Sofomore. En instanciant Sofomore avec CMA-ES, nous obtenons COMO-CMA-ES. Ce nouvel algorithme multiobjectif est testé sur les fonctions bi-objectives quadratiques et convexes, que nous analysons en détail dans cette thèse. Nous observons une convergence linéaire, ce qui est le comportement optimal pour un CMA-ES multiobjectif puisque le CMA-ES converge linéairement sur les fonctions quadratiques strictemement convexes. Un package Python appelé pycomocma et une interface Matlab sont développés pour COMO-CMA-ES et pour Sofomore.D'un point de vue théorique, nous analysons la convergence linéaire de stratégies d'évolution avec recombinaison contenant des algorithmes d'optimisation très connus, sur une classe de fonctions large constituée des fonctions scaling-invariant. Notre principale condition de convergence est que l'espérance du logarithme du step-size doit croître sur les fonctions linéaires non triviales, ce qui est optimal comme condition. Nous analysons la classe de fonctions scaling-invariant et mettons l'accent sur les propriétés qu'elle partage avec les fonctions homogènes.