Optimization by hybridation of a genetic algorithm with constraint satisfaction techniques

Abstract- We introduce a new optimization method based on a Genetic Algorithm (GA) mixed with Constraint Sat-isfaction Problem (CSP) techniques. The approach is de-signed 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 han-dling 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 naive formulation of the Vehi-cle Routing Problem (VRP) and the Radio Link Frequency Assignement Problem (RLFAP). The results are quite en-couraging as we outperform CSP techniques and genetic al-gorithm alone. Kegwords- Optimization, Constraint Satisfaction, Hy-bridizatio