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

详细信息    查看全文

• 作者：Lamia Sadeg-Belkacem ; Zineb Habbas ; Wassila Aggoune-Mtalaa
• 关键词：optimization problems ; partial constraint satisfaction problems ; frequency assignment problems ; graph decomposition ; adaptive genetic algorithm (AGA) ; AGA guided by decomposition (AGAGD)
• 刊名：Frontiers of Computer Science in China
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：10
• 期：6
• 页码：1012-1025
• 全文大小：383 KB
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general
  Chinese Library of Science
  
• 出版者：Higher Education Press, co-published with Springer-Verlag GmbH
• ISSN：1673-7466
• 卷排序：10

文摘

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 decomposition method 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.