An effective genetic algorithm approach to the quadratic minimum spanning tree problem

被引：63

作者：

Zhou, GG ^{[1
]}

Gen, M ^{[1
]}

机构：

[1] Ashikaga Inst Technol, Dept Ind & Syst Engn, Ashikaga 236, Japan

来源：

COMPUTERS & OPERATIONS RESEARCH | 1998年 / 25卷 / 03期

关键词：

D O I：

10.1016/S0305-0548(97)00039-7

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper we present a new approach to solve the q-MST problem by using a genetic algorithm. A skillful encoding for trees, denoted by Prufer number, is adopted for GA operation. On comparing with the existing heuristic algorithms by 17 randomly generated numerical examples from 6-vertex graph to 50-vertex graph, the new GA approach shows its high effectiveness in solving the q-MST problem and real value in the practical network optimization. (C) 1998 Elsevier Science Ltd. All rights reserved.

引用

页码：229 / 237

页数：9

共 15 条

[1]

ABUALI FN, 1995, P 6 INT C GEN ALG, P470

[2] ON LOWER BOUNDS FOR A CLASS OF QUADRATIC-0, 1 PROGRAMS [J].

ASSAD, AA ;

XU, WX .

OPERATIONS RESEARCH LETTERS, 1985, 4 (04) :175-180

[3]

Back T., 1991, P 4 INT C GEN ALG, P92

[4]

Dijkstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[5]

GEN M, 1997, GENETIC ALGORITHMS E

[6]

GRAHAM RL, 1985, ANN HIST COMPUT, V7, P43

[7]

IPCS, 1995, POIS INF MON PIM 141

[8]

Kershenbaum A., 1993, TELECOMMUNICATIONS N

[9]

Kruskal J. B., 1956, Proc. of American Mathematical Society, V7, P48, DOI [DOI 10.1090/S0002-9939-1956-0078686-7, 10.1090/S0002-9939-1956-0078686-7]

[10]

Michalewicz Z., 1994, GENETIC ALGORITHMS P

← 1 2 →