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

被引:10
作者
Kolen, Antoon [1 ]
机构
[1] Univ Maastricht, Fac Econ & Business Adm, NL-6200 MD Maastricht, Netherlands
关键词
genetic algorithm; constraint satisfaction problem; frequency assignment problem;
D O I
10.1111/j.1467-9574.2007.00357.x
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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.
引用
收藏
页码:4 / 15
页数:12
相关论文
共 4 条
[1]   Algorithms for radio link frequency assignment: The CALMA project [J].
Aardal, K ;
Hurkens, C ;
Lenstra, JK ;
Tiourine, S .
OPERATIONS RESEARCH, 2002, 50 (06) :968-980
[2]   Models and solution techniques for frequency assignment problems [J].
Aardal, Karen I. ;
van Hoesel, Stan P. M. ;
Koster, Arie M. C. A. ;
Mannino, Carlo ;
Sassano, Antonio .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (04) :261-317
[3]  
Goldberg D.E, 1989, GENETIC ALGORITHMS S
[4]   The partial constraint satisfaction problem: Facets and lifting theorems [J].
Koster, AMCA ;
van Hoesel, SPM ;
Kolen, AWJ .
OPERATIONS RESEARCH LETTERS, 1998, 23 (3-5) :89-97