 |
Poster
Combine & conquer : genetic algorithm and CP for optimization
Abstract : We introduce a new optimization method based on a Genetic Algorithm (GA) combined with Constraint Satisfaction Problem (CSP) techniques. The approach is designed for combinatorial problems whose search spaces are too large and{/}or objective functions too complex for usual CSP techniques and whose constraints are too complex for conventional genetic algorithm. The main idea is the handling of sub-domains of the CSP variables by the genetic algorithm. The population of the genetic algorithm is made up of strings of sub-domains whose adaptation are computed through the resolution of the corresponding ''sub-CSPs'' which are somehow much easier than the original problem. We provide basic and dedicated recombination and mutation operators with various degrees of robustness. The first set of experimentations adresses a naïve formulation of a Vehicle Routing Problem (VRP). The results are quite encouraging as we outperform CSP techniques and genetic algorithm alone on these formulations.
https://hal-enac.archives-ouvertes.fr/hal-00937732
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : jeudi 17 avril 2014 - 16:27:06
Dernière modification le : mardi 19 octobre 2021 - 11:02:56
Archivage à long terme le : : dimanche 9 avril 2017 - 01:51:21
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : jeudi 17 avril 2014 - 16:27:06
Dernière modification le : mardi 19 octobre 2021 - 11:02:56
Archivage à long terme le : : dimanche 9 avril 2017 - 01:51:21
Fichier
280.pdf
Fichiers produits par l'(les) auteur(s)