An ant colony optimization approach to the degree-constrained minimum spanning tree problem

被引：0

作者：

Bau, YT ^{[1
]}

Ho, CK ^{[1
]}

Ewe, HT ^{[1
]}

机构：

[1] Multimedia Univ, Fac Informat Technol, Cyberjaya 63100, Selangor, Malaysia

来源：

COMPUTATIONAL INTELLIGENCE AND SECURITY, PT 1, PROCEEDINGS | 2005年 / 3801卷

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents the application of an Ant Colony Optimization (ACO) algorithm approach for communications networks design problem. We explore the use of ACO's for solving a network optimization problem, the degree-constrained minimum spanning tree problem (d-MST), which is a NP-Hard problem. The effectiveness of the proposed algorithm is demonstrated through two kinds of data set: structured hard (SHRD) complete graphs and misleading (M-graph) complete graphs. Empirical results show that ACO performs competitively with other approaches based on evolutionary algorithm (EA) on certain instance set problem.

引用

页码：657 / 662

页数：6

共 8 条

[1]

Dorigo M., 1999, NEW IDEAS OPTIMIZATI

[2] A new evolutionary approach to the degree-constrained minimum spanning tree problem [J].

Knowles, J ;

Corne, D .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2000, 4 (02) :125-134

[3] Comparison of algorithms for the Degree Constrained Minimum Spanning Tree [J].

Krishnamoorthy, M ;

Ernst, AT ;

Sharaiha, YM .

JOURNAL OF HEURISTICS, 2001, 7 (06) :587-611

[4] A parallel algorithm for the degree-constrained minimum spanning tree problem using nearest-neighbor chains [J].

Mao, LJ ;

Deo, N ;

Lang, SD .

FOURTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS, AND NETWORKS (I-SPAN'99), PROCEEDINGS, 1999, :184-189

[5]

Raidl GR, 2000, IEEE C EVOL COMPUTAT, P104, DOI 10.1109/CEC.2000.870282

[6] EDGE EXCHANGES IN THE DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM [J].

SAVELSBERGH, M ;

VOLGENANT, T .

COMPUTERS & OPERATIONS RESEARCH, 1985, 12 (04) :341-348

[7]

ZHOU G, 1996, IEEE INT C SYST MAN, V4, P2683

[8]

[No title captured]

← 1 →