Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems

Abstract

This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly generic, meaning that any decompositionmethod and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future.

Keywords

optimization problems / partial constraint satisfaction problems / frequency assignment problems / graph decomposition / adaptive genetic algorithm (AGA) / AGA guided by decomposition (AGAGD)

References

[1] Kochenberger G, Gloverand F, Alidaee B, Lewis K. Using the unconstrained quadratic program to model and solve max 2-sat problems. International Journal of Operational Research, 2005, 1(1): 89–100

[2] Tate D M, Smith A E. A genetic approach to the quadratic assignment problem. Computers and Operations Research, 1995, 22(1): 73–83

[3] Sadeg-Belkacem L, Habbas Z, Benbouzid-Sitayeb F, Singer D. Decomposition techniques for solving frequency assigment problems (fap) a top-down approach. In: Proceedings of International Conference on Agents and Artificial Intelligence. 2014, 477–484

[4] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review, 2004, 69(6): 066133

[5] Sadeg-Belkacem L, Habbas Z, Aggoune-Mtalaa W. AGAGD: an adaptive genetic algorithm guided by decomposition for solving PCSPs. In: Proceedings of International Conference on Agents and Artificial Intelligence. 2015

[6] Freuder E, Wallace R. Partial constraint satisfaction. In: Proceedings of International Joint Conference on Artificial Intelligence. 1989, 278–283

[7] Koster A, Van Hoesel S, Kolen A. The partial constraint satisfaction problem: facets and lifting theorems. Operations Research Letters, 1998, 23(3): 89–97

[8] Koster A. Frequency assignment-models and algorithms. Dissertation for the Doctoral Degree. Maastricht: Maastricht University, 1999

[9] Allouche D, Givry S, Schiex T. Towards parallel non serial dynamic programming for solving hard weighted CSP. Lecture Notes in Computer Science, 2010, 6308: 53–60

[10] Colombo G, Allen SM. Problem decomposition for minimum interference frequency assignment. In: Proceedings of the IEEE Congress on Evolutionary Computation. 2007, 3492–3499

[11] Loudni S, Boizumault P, Levasseur N. Advanced generic neighborhood heuristics for VNS. Engineering Applications of Artificial Intelligence, 2010, 23(5): 736–764

[12] Loudni S, Fontaine M, Boizumault P. DGVNS guidée par les séparateurs. In: Proceedings of 9-émes Journées Francophones de Programmation par Contrainte. 2013, 205–214

[13] Koster A, Van Hoessel S, Kolen A. Solving partial constraint satisfaction problems with tree decomposition. Network Journal, 2002, 40(3): 170–180

[14] Habbas Z, Martin S, Sadeg-Belkacem L, Singer D. Approche unifiée pour la décomposition et la résolution de pcsp: étude expérimentale sur fap. In: Proceedings of Journées Francophones de Programmation par Contraintes. 2013

[15] Stoer M , Wagner F. A simple min-cut algorithm. Journal of the ACM, 1997, 44(4): 585–591

[16] Koster A, Van Hoessel S, Kolen A. The partial constraint satisfaction problems : factes and lifting theorem. Operations Research Letters, 1998, 23(3–5): 89–97

[17] Csardi G, Nepusz T. The igraph software package for complex network research. InterJournal, Complex Systems, 2006, 1695(5): 1–9

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg