Combine & conquer : genetic algorithm and CP for optimization

Nicolas Barnier 1 Pascal Brisset 2
1 MAIA-OPTIM - ENAC Equipe MAIAA-OPTIM
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
2 ENAC - Ecole Nationale de l'Aviation Civile
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.
Keywords : optimization genetic algorithms hybridization
Document type :
Poster communications
Complete list of metadatas
https://hal-enac.archives-ouvertes.fr/hal-00937732
Contributor : Laurence Porte <>
Submitted on : Thursday, April 17, 2014 - 4:27:06 PM
Last modification on : Wednesday, July 24, 2019 - 11:48:02 PM
Long-term archiving on: Sunday, April 9, 2017 - 1:51:21 AM

File

280.pdf
Files produced by the author(s)

Identifiers

Collections

MAIAA | MAIAA-OPTIM | INSMI | ENAC | TDS-MACS | OPTIM

Citation

Nicolas Barnier, Pascal Brisset. Combine & conquer : genetic algorithm and CP for optimization. CP 1998, 4th Conference on Principles and Practice of Constraint Programming, Oct 1998, Pisa, Italy. 1520, pp 463-477, 1998, ⟨10.1007/3-540-49481-2_34⟩. ⟨hal-00937732⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

595

Files downloads

135