Hybrid evolutionary search for the minimum sum coloring problem of graphs

详细信息    查看全文

• 作者：Yan Jin^a ; ^b ; ^{yanjin.china@hotmail.com" class="auth_mail" title="E-mail the corresponding author} ; Jin-Kao Hao ; ^b ; ^c ; ^{jin-kao.hao@univ-angers.fr" class="auth_mail" title="E-mail the corresponding author} ; ^{hao@info.univ-angers.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Sum coloring ; Hybrid search ; Evolutionary computing ; Local optimization ; Tabu search
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：20 July 2016
• 年：2016
• 卷：352-353
• 期：Complete
• 页码：15-34
• 全文大小：812 K

文摘

Given a graph G, a proper k-coloring of G is an assignment of k   colors {1,…,k}$\left\{1,\dots ,k\right\}$ to the vertices of G such that two adjacent vertices receive two different colors. The minimum sum coloring problem (MSCP) is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices. This paper presents a stochastic hybrid evolutionary search algorithm for computing upper and lower bounds of this NP-hard problem. The proposed algorithm relies on a joint use of two dedicated crossover operators to generate offspring solutions and an iterated double-phase tabu search procedure to improve offspring solutions. A distance-and-quality updating rule is used to maintain a healthy diversity of the population. We show extensive experimental results to demonstrate the effectiveness of the proposed algorithm and provide the first landscape analysis of MSCP to shed light on the behavior of the algorithm.