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: | Kolen Antoon |
Keywords: | heuristics: genetic algorithms, programming: branch and bound |
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.