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.
Publié le : 1998-10-26
Classification:
optimization,
genetic algorithms,
hybridization,
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
@article{hal-00937732,
author = {Barnier, Nicolas and Brisset, Pascal},
title = {Combine \& conquer : genetic algorithm and CP for optimization},
journal = {HAL},
volume = {1998},
number = {0},
year = {1998},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00937732}
}
Barnier, Nicolas; Brisset, Pascal. Combine & conquer : genetic algorithm and CP for optimization. HAL, Tome 1998 (1998) no. 0, . http://gdmltest.u-ga.fr/item/hal-00937732/