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

doi:10.1007/s11704-016-4552-4

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-BELKACEM^1,^2,³(

),Zineb HABBAS³,Wassila AGGOUNE-MTALAA⁴

¹. Ecole Militaire Polytechnique, Algiers 16111, Algeria
². Ecole nationale Supérieure d’Informatique, Algiers 16309, Algeria
³. Université de Lorraine, Metz 57045, France
⁴. 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