Behavior study of an evolutionary design for permutation problems
Institution:
Bourgogne Franche-ComtéDisciplines:
Directors:
Abstract EN:
This thesis studies an evolutionary representation - crossover combination for permutation problems. These are widely studied in literature due to their hardness and the diversity of their application fields. Efficient methods exist to solve permutation problems. But several recent surveys show that real applications induce new instances that are strongly dynamic and characterized by the conjunction of particular constraints and objectives, particularly synchronization. This contribution focuses on evolutionary approaches. It explores in details the behaviour of a given representation crossovercombination. The goal is to check if this evolutionary design could be an interesting complementary way to tackle efficiently some of the constraints. This work studies the link between the representation used, the chosen recombination operators and the characteristics of the problem to be solved, focusing on Lehmer code representation and kpoint crossover. This review permits to deduce some assumptions (some of them being contradictory) regarding the behaviour of the Lehmer Code representation k-point crossover combination. Experiments are used to verify these assumptions, performed by comparison with permutation encoding coupled with PMX crossover. Measurements are used to observe the behavior of evolutionary mechanisms, both in the search space (in terms of genotype) and in the objective space ( in terms of phenotype and associated quality criterion). Concluding remarks, implications and future research directions conclude the work.
Abstract FR:
Cette thèse étudie une combinaison évolutionnaire représentation_croisement pour des problèmes de permutation. Ceux-ci sont très étudiés dans la littérature en raison de leur complexité et de la diversité de leurs applications. Des méthodes efficaces existent pour résoudre les problèmes de permutation. Mais les états de l’art récents montrent que les applications réelles font émerger de nouvelles instances qui sont fortement dynamiques et conjuguent de nombreux objectifs et contraintes, notamment de synchronisation. Cette contribution se concentre sur les approches évolutionnaires. Elle explore en détail le comportement d’une combinaison représentation_croisement donnée. Le but est de vérifier si cette conception évolutive pourrait constituer un moyen complémentaire intéressant de s’attaquer efficacement à certaines contraintes. Ce travail étudie le lien entre la représentation utilisée, les opérateurs de recombinaison choisis et les caractéristiquesdu problème à résoudre, en se focalisant sur une représentation par code de Lehmer et le croisement à k-points. Ceci permet de déduire certaines hypothèses (certaines d’entre elles étant contradictoires) concernant le comportement de lacombinaison de croisements k-points appliqués à la représentation Lehmer. Une phase d’expérience est utilisée pour vérifier ces hypothèses. Elle est réalisée par comparaison avec un codage direct de permutation classique, couplé à un croisement PMX. Des mesures sont utilisées pour observer le comportement des mécanismes évolutifs, à la fois dans l’espace de recherche (en termes de génotype) et dans l’espace objectif (en termes de phénotype et de critère de qualité associé). Les remarques de conclusion, les implications et les directions de recherche futures concluent le travail.