Étude et exploitation des réseaux de neutralité dans les paysages adaptatifs pour l'optimisation difficile
Institution:
NiceDisciplines:
Directors:
Abstract EN:
The concept of fitness landscape was introduce in the field of biology in 1930's to explain the evolution of individuals. In the field of combinatorial optimization by metaheuristic, it is also used and allows to study the link between geometrical description of optimization problem and the dynamic of search algorithms. This thesis propose to deeper study neutral fitness landscapes, point out in molecular evolution by neutral theory, in the context of optimization and to design new metaheuristics according to those landscapes. In the first one, we present the main results about fitness landscapes and more particularly about neutral fitness landscapes. In the second part, we develop the concept of neutral set by introducing the notion of 'fitness cloud' which allows to study the correlation of performance between two neighbor solutions and we measure this correlation on 'embedded fitness landscapes' as an extension of NK landscapes and Max-SAT problems. In the third part, we summarize the set of measures on neutral networks and we propose the new measure. Experimental study is performed on three family of landscapes for which the neutrality is and two classical problems. Then, a new metaheuristic adapted of neutral fitness landscapes inspired by the new measure is proposed and evaluated on different landscapes. We studied the massively neutral fitness landscapes from the learning problem of a rule of cellular automata which perform the density task, in order to improve the best metaheuristics known.
Abstract FR:
Le concept de paysage adaptatif a été introduit dans le domaine de la biologie dans les années 1930 pour modéliser l'évolution d'une population d'organismes. Dans le domaine de l'optimisation combinatoire par métaheuristiques, il est également utilisé et permet de lier une description géométrique d'un problème d'optimisation avec la dynamique des algorithmes de recherche. Cette thèse se propose d'approfondir l'étude des paysages adaptatifs neutres, mise en avant par la théorie de la neutralité en évolution moléculaire, dans le contexte de l'optimisation et de proposer de nouvelles métaheuristiques adaptées à ce type de paysages. Dans une première partie, nous présentons les principaux résultats concernant les paysages adaptatifs et plus particulièrement les paysages adaptatifs neutres. Dans une deuxième partie, nous introduisons la notion de 'nuage adaptatif' qui permet d'étudier la corrélation de performance entre solutions et nous l'appliquons à la classe des paysages 'embarqués' qui regroupe les paysages NK et Max-SAT. Dans une troisième partie, nous résumons l'ensemble des mesures relatives aux réseaux de neutralité et nous proposons une nouvelle mesure. Une étude expérimentale est réalisée sur trois familles de paysages de neutralité ajustable et deux problèmes classiques. Enfin, un nouvel algorithme de recherche adapté aux paysages neutres lié à la nouvelle mesure est proposé et évalué sur différents paysages neutres. Nous réalisons l'étude du paysage adaptatif massivement neutre issu du problème d'apprentissage de la règle d'un automate cellulaire réalisant la tache de classification par la densité, afin d'en améliorer les métaheuristiques connues existantes.