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.
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
https://doi.org/10.1504/IJOR.2005.007435
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
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
https://doi.org/10.5220/0005196400780089
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
https://doi.org/10.1016/S0167-6377(98)00043-1
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
https://doi.org/10.1007/978-3-642-15396-9_7
10
Colombo G, Allen SM. Problem decomposition for minimum interference frequency assignment. In: Proceedings of the IEEE Congress on Evolutionary Computation. 2007, 3492–3499
https://doi.org/10.1109/cec.2007.4424925
11
Loudni S, Boizumault P, Levasseur N. Advanced generic neighborhood heuristics for VNS. Engineering Applications of Artificial Intelligence, 2010, 23(5): 736–764
https://doi.org/10.1016/j.engappai.2010.01.014
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
https://doi.org/10.1002/net.10046
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
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
https://doi.org/10.1016/S0167-6377(98)00043-1
17
Csardi G, Nepusz T. The igraph software package for complex network research. InterJournal, Complex Systems, 2006, 1695(5): 1–9
