Combine & conquer : genetic algorithm and CP for optimization - Archive ouverte HAL Accéder directement au contenu
Poster De Conférence Année : 1998

Combine & conquer : genetic algorithm and CP for optimization

(1) , (2)
1
2

Résumé

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.
Fichier principal
Vignette du fichier
280.pdf (321.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00937732 , version 1 (17-04-2014)

Identifiants

Citer

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⟩
220 Consultations
430 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More