Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2016, Vol. 10 Issue (6) : 1012-1025    https://doi.org/10.1007/s11704-016-4552-4
RESEARCH ARTICLE
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
 Download: PDF(362 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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
 Cite this article:   
Lamia SADEG-BELKACEM,Zineb HABBAS,Wassila AGGOUNE-MTALAA. Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems[J]. Front. Comput. Sci., 2016, 10(6): 1012-1025.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-4552-4
https://academic.hep.com.cn/fcs/EN/Y2016/V10/I6/1012
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
[1]  Supplementary Material Download
[1] Lijin WANG,Yilong YIN,Yiwen ZHONG. Cuckoo search with varied scaling factor[J]. Front. Comput. Sci., 2015, 9(4): 623-635.
[2] Yong WANG, Zixing CAI. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems[J]. Front Comput Sci Chin, 2009, 3(1): 38-52.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed