The authors introduce a new optimization method based on a genetic algorithm (GA) mixed 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 fitness are computed through the resolution of the corresponding ?sub-CSPs? which are somehow much easier than the original problem. They provide basic and dedicated recombination and mutation operators with various degrees of robustness. The first set of experimentations adresses a naive formulation of the vehicle routing problem (VRP) and the radio link frequency assignment problem (RLFAP). The results are quite encouraging as one outperforms CSP techniques and genetic algorithm alone.
Publié le : 1998-05-04
Classification:
constraint optimization,
cost function,
genetic algorithms,
genetic mutations,
optimization methods,
radio link,
robustness,
routing,
space exploration,
subspace constraints,
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
@article{hal-00937716,
author = {Barnier, Nicolas and Brisset, Pascal},
title = {Optimization by hybridization of a genetic algorithm with constraint satisfaction techniques},
journal = {HAL},
volume = {1998},
number = {0},
year = {1998},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00937716}
}
Barnier, Nicolas; Brisset, Pascal. Optimization by hybridization of a genetic algorithm with constraint satisfaction techniques. HAL, Tome 1998 (1998) no. 0, . http://gdmltest.u-ga.fr/item/hal-00937716/