|
|
Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems |
Lamia SADEG-BELKACEM1,2,3( ),Zineb HABBAS3,Wassila AGGOUNE-MTALAA4 |
1. Ecole Militaire Polytechnique, Algiers 16111, Algeria 2. Ecole nationale Supérieure d’Informatique, Algiers 16309, Algeria 3. Université de Lorraine, Metz 57045, France 4. Luxembourg Institute of Science and Technology, Luxembourg L-4362, Luxembourg |
|
|
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)
|
Corresponding Author(s):
Lamia SADEG-BELKACEM
|
Just Accepted Date: 01 December 2015
Online First Date: 12 June 2016
Issue Date: 11 October 2016
|
|
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
https://doi.org/10.1504/IJOR.2005.007435
|
2 |
Tate D M, Smith A E. A genetic approach to the quadratic assignment problem. Computers and Operations Research, 1995, 22(1): 73–83
https://doi.org/10.1016/0305-0548(93)E0020-T
|
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
https://doi.org/10.1103/physreve.69.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
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
|
15 |
Stoer M , Wagner F. A simple min-cut algorithm. Journal of the ACM, 1997, 44(4): 585–591
https://doi.org/10.1145/263867.263872
|
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
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|