A Hybrid Algorithm Based on Memetic Algorithm and Tabu Search for k-Minimum Spanning Tree Problems

被引：0

作者：

Guo, Qingqiang ^{[1
]}

Katagiri, Hideki ^{[1
]}

Nishizaki, Ichiro ^{[1
]}

Hayashida, Tomohiro ^{[1
]}

机构：

[1] Hiroshima Univ, Grad Sch Engn, Dept Syst Cybernet, Hiroshima 730, Japan

来源：

INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTIST, IMECS 2012, VOL II | 2012年

关键词：

k-minimum spanning tree; memetic algorithm; tabu search; combinatorial optimization; hybrid algorithm; CARDINALITY TREE;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A combinatorial optimization problem, namely k-Minimum Spanning Tree Problem, is to find a subtree with exactly k edges in an undirected graph G, such that the sum of edges' weights is minimal. where graph G is made up of a set of vertices and weight attached edges. Since this problem is NP-hard, heuristic and metaheuristic methods are widely adopted for solving large instances. In this paper, we propose a new hybrid algorithm to solve this problem, by using Memetic Algorithm as a diversification strategy for Tabu Search. Especially, the genetic operator in our Memetic Algorithm is based on dynamic programming algorithm, which finds the optimal subtree in a given tree efficiently. The proposed algorithm is tested on the k Minimum Spanning Tree problems with other exiting algorithms, The experimental results show that the proposed algorithm is superior to all the exiting algorithms in precision and updates some of the best known results.

引用

页码：1611 / 1616

页数：6

共 23 条

[11] FUTURE PATHS FOR INTEGER PROGRAMMING AND LINKS TO ARTIFICIAL-INTELLIGENCE
GLOVER, F
[J]. COMPUTERS & OPERATIONS RESEARCH, 1986, 13 (05) : 533 - 549
[12] Glover F., 1998, Tabu Search, DOI DOI 10.1007/978-1-4615-6089-0_1
[13] Hamacher H.W., 1991, TECHNICAL REPORT
[14] HAMACHER HW, 1993, 793 NORW SCH EC BUS
[15] Katagiri Hideki, 2010, International Journal of Knowledge Engineering and Soft Data Paradigms, V2, P263, DOI 10.1504/IJKESDP.2010.035908
[16] Katagiri H, 2009, LECT NOTES ARTIF INT, V5861, P315, DOI 10.1007/978-3-642-04820-3_29
[17] Ma B, 2000, IEEE IMAGE PROC, P481, DOI 10.1109/ICIP.2000.901000
[18] MAFFIOLI F, 1991, 91041 POL MIL DIP EL
[19] PHILPOTT AB, 1997, OPTIMAL EXTRACTION O
[20] The k-Cardinality Tree Problem: Reformulations and Lagrangian Relaxation
Quintao, Frederico P.
da Cunha, Alexandre Salles
Mateus, Geraldo R.
Lucena, Abilio
[J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (12) : 1305 - 1314

← 1 2 3 →