Skip to Main content Skip to Navigation
Conference papers

Optimization by hybridization of a genetic algorithm with CSP techniques

Nicolas Barnier 1
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
Abstract : Within the framework of Constraint Logic Programming on finite domains (CLP(FD)), we introduce a new optimization method based on a Genetic Algorithm (GA) and designed for combinatorial problems whose search spaces are too large and/or objective functions too complex for usual Constraint Satisfaction Problem (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. 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 Vehicle Routing Problem (VRP) and the Radio Link Frequency Assignement Problem (RLFAP). The results are quite encouraging as we outperform CLP(FD) techniques and genetic algorithm alone.
Document type :
Conference papers
Complete list of metadata
Contributor : Laurence Porte Connect in order to contact the contributor
Submitted on : Thursday, April 17, 2014 - 4:33:32 PM
Last modification on : Tuesday, October 19, 2021 - 11:02:56 AM
Long-term archiving on: : Sunday, April 9, 2017 - 1:55:36 AM


Files produced by the author(s)


  • HAL Id : hal-00937706, version 1



Nicolas Barnier. Optimization by hybridization of a genetic algorithm with CSP techniques. ESSLLI 97, 9th European Summer School in Logic, Language and Information, Aug 1997, Aix-en-Provence, France. pp xxxx. ⟨hal-00937706⟩



Les métriques sont temporairement indisponibles