Sélection topologique dans les algorithmes évolutionnaires cellulaires : étude du compromis exploration exploitation
Institution:
NiceDisciplines:
Directors:
Abstract EN:
Evolutionary algorithms are stochastic optimization methods manipulating a population of solutions. Their behaviour is inspired by Darwin's theory of evolution. The combined application of stochastic operators and selection mechanisms allow renewing the population by exploring the search space and exploiting the already found solutions. The convergence speed of an evolutionary algorithm relies on its ability to generate efficient solutions by leading the search toward promising regions of the search space, and the ability of solutions to survive according to their fitness defined by the selective pressure. The latter allows dealing with the exploration / exploitation trade-off and prevents the algorithm from converging prematurely toward a local optimum. Evolutionary cellular algorithms introduce a notion of geographical neighborhood by embedding the solution on a grid. This adds a topological level between the phenotypical and genotypical ones. In this context, we define new selection methods that allow controlling the topology and obtain complex dynamics thanks to a single continuous and bounded parameter. Instead of restricting solutions to evolve on a uniform grid, we propose to enhance the topology with notions of anisotropy and locality. We study the influence of the topological selection on the preservation of genotypic diversity. Experiences made on two classes of NP-complete problems show that taking into account the topological level leads to a fine equilibrium between exploration and exploitation. In order to study the search dynamic and especially to analyze the efficiency of the observed trade-offs, we define a model based on the notion of punctuated equilibria. Finally, we propose adaptive algorithms in the intent of dynamically controlling the selective pressure and thus dealing with the relation between exploration and exploitation phases without any knowledge on the studied problems.
Abstract FR:
Les algorithmes évolutionnaires sont des méthodes d'optimisation approchées manipulant une population de solutions. Leur fonctionnement s'inspire de la théorie de l'évolution de Darwin. L'application combinée d'opérateurs stochastiques et de mécanismes de sélection permet de renouveler la population en explorant l'espace de recherche et en exploitant la qualité des solutions déjà découvertes. La vitesse de convergence d'un algorithme évolutionnaire dépend de sa capacité à générer de nouvelles solutions performantes en se dirigeant vers des régions prometteuses de l'espace de recherche et de celles des solutions à survivre en fonction de leur qualité déterminée par la pression de sélection. Celle-ci permet de contrôler le compromis entre exploration et exploitation et d'éviter une convergence prématurée vers un optimum local. Les algorithmes évolutionnaires cellulaires introduisent une notion de voisinage géographique en structurant spatialement les solutions sur une grille. Cela permet d'ajouter un niveau topologique entre les niveaux phénotypique et génotypique. Dans ce contexte, nous définissons de nouvelles méthodes de sélection permettant à l'aide d'un paramètre continu et borné de contrôler la topologie et ainsi d'obtenir des dynamiques plus complexes. Plutôt que de restreindre les solutions à évoluer sur une grille régulière où chaque cellule est indifférenciée, nous proposons d'enrichir la topologie en introduisant des notions d'anisotropie et de localité. Nous étudions l'influence de la sélection topologique sur la préservation de la diversité génotypique. Les expériences menées sur deux classes de problèmes NP-complets montrent que la prise en compte d'un point de vue topologique permet d'obtenir un bon équilibre entre exploration et exploitation. Dans le but d'étudier la dynamique de recherche et en particulier d'analyser l'efficacité des compromis observés, nous définissons un modèle théorique basé sur la notion d'équilibres ponctués. Enfin, nous proposons des algorithmes de contrôle utilisant la sélection topologique afin de réguler dynamiquement la pression de sélection et ainsi de gérer le rapport entre phases d'exploration et d'exploitation sans connaissance a priori sur les problèmes étudiés.