A hybrid algorithm based on tabu search and ant colony optimization for k-minimum spanning tree problems

被引：30

作者：

Katagiri, Hideki ^{[1
]}

Hayashida, Tomohiro ^{[1
]}

Nishizaki, Ichiro ^{[1
]}

Guo, Qingqiang ^{[1
]}

机构：

[1] Hiroshima Univ, Fac Engn, Hiroshima 7398527, Japan

来源：

EXPERT SYSTEMS WITH APPLICATIONS | 2012年 / 39卷 / 05期

关键词：

k-Minimum spanning tree; Tabu search; Ant colony optimization; Hybrid algorithm; Approximate solution;

D O I：

10.1016/j.eswa.2011.11.103

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper considers an efficient approximate algorithm for solving k-minimum spanning tree problems which is one of the combinatorial optimization in networks. A new hybrid algorithm based on tabu search and ant colony optimization is provided. Results of numerical experiments show that the proposed method updates some of the best known values with very short time and that the proposed method provides a better performance with solution accuracy over existing algorithms. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：5681 / 5686

页数：6

共 25 条

[1] Using Ant Colony Optimization algorithm for solving project management problems
Abdallah, Hazem
Emara, Hassan M.
Dorrah, Hassan T.
Bahgat, Ahmed
[J]. EXPERT SYSTEMS WITH APPLICATIONS, 2009, 36 (06) : 10004 - 10015
[2] The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem
Aladag, Cagdas Hakan
Hocaoglu, Gulsum
Basaran, Murat Alper
[J]. EXPERT SYSTEMS WITH APPLICATIONS, 2009, 36 (10) : 12349 - 12356
[3] [Anonymous], 1997, TABU SEARCH
[4] New metaheuristic approaches for the edge-weighted k-cardinality tree problem
Blum, C
Blesa, MJ
[J]. COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (06) : 1355 - 1377
[5] Bornd'orfer R., 1997, Matrix decomposition by branch-and-cut
[6] Decomposing matrices into blocks
Borndörfer, R
Ferreira, CE
Martin, A
[J]. SIAM JOURNAL ON OPTIMIZATION, 1998, 9 (01) : 236 - 269
[7] Hybrid tabu search for re-entrant permutation flow-shop scheduling problem
Chen, Jen-Shiang
Pan, Jason Chao-Hsien
Wu, Chien-Kuang
[J]. EXPERT SYSTEMS WITH APPLICATIONS, 2008, 34 (03) : 1924 - 1930
[8] Parallelized genetic ant colony systems for solving the traveling salesman problem
Chen, Shyi-Ming
Chien, Chih-Yao
[J]. EXPERT SYSTEMS WITH APPLICATIONS, 2011, 38 (04) : 3873 - 3883
[9] Cheung S. Y., 1994, P INFOCOM LOS AL US
[10] Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892

← 1 2 3 →