A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem

A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20072932
Country: Netherlands
Volume: 61
Issue: 1
Start Page Number: 4
End Page Number: 15
Publication Date: Feb 2007
Journal: Statistica Neerlandica
Authors:
Keywords: heuristics: genetic algorithms, programming: branch and bound
Abstract:

We describe a genetic algorithm for the partial constraint satisfaction problem. The typical elements of a genetic algorithm, selection, mutation and cross-over, are filled in with combinatorial ideas. For instance, cross-over of two solutions is performed by taking the one or two domain elements in the solutions of each of the variables as the complete domain of the variable. Then a branch-and-bound method is used for solving this small instance. When tested on a class of frequency assignment problems this genetic algorithm produced the best known solutions for all test problems. This feeds the idea that combinatorial ideas may well be useful in genetic algorithms.

Reviews

Required fields are marked *. Your email address will not be published.