Optimisation par hybridation d'un CSP avec un algorithme génétique

Abstract : Within the framework of Constraint Logic Programming on finite domains CLP(FD), we introduce a new optimization method based on a 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 fitness 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 the Vehicle Routing Problem (VRP) and the Radio Link Frequency Assignement Problem (RLFAP). The results are quite encouraging as we outperform CLP(FD) techniques and genetic algorithm alone.