Advertisement
Published in:
2013 | OriginalPaper | Chapter
A New Crossover for Solving Constraint Satisfaction Problems
Authors : Reza Abbasian, Malek Mouhoub
Published in: Evolutionary Computation in Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we investigate the applicability of Genetic Algorithms (GAs) for solving Constraint Satisfaction Problems (CSPs). Despite some success of GAs when tackling CSPs, they generally suffer from poor crossover operators. In order to overcome this limitation in practice, we propose a novel crossover specifically designed for solving CSPs. Together with a variable ordering heuristic and an integration into a parallel architecture, this proposed crossover enables the solving of large and hard problem instances as demonstrated by the experimental tests conducted on randomly generated CSPs based on the model RB. We will indeed demonstrate, through these tests, that our proposed method is superior to the known GA based techniques for CSPs. In addition, we will show that we are able to compete with the efficient MAC-based Abscon 109 solver for random problem instances.