A new genetic algorithm with local search method for degree-constrained minimum spanning tree problem

Author

Zeng, Yong ; Wang, Yu-Ping

Author_Institution

Fac. of Sci., Xidian Univ., Xi´´an, China

fYear

2003

fDate

27-30 Sept. 2003

Firstpage

218

Lastpage

222

Abstract

A new evolutionary algorithm for degree-constrained minimum spanning tree problem, which is an NP-complete problem, is proposed, and Prufer encoding method is adopted to encode the solutions of the problem. To enhance the algorithm, two new genetic operators are specifically designed, which can avoid producing infeasible solutions. In addition, two novel local search operators are designed and combined into the algorithm to further improve the quality of solutions. As a result, the proposed evolutionary algorithm can efficiently explore the search space.

Keywords

computational complexity; genetic algorithms; minimisation; search problems; trees (mathematics); NP-complete problem; Prufer encoding method; degree-constrained problem; evolutionary algorithm; genetic algorithm; genetic operators; local search method; local search operators; minimum spanning tree; search space exploration; Algorithm design and analysis; Decoding; Encoding; Evolutionary computation; Genetic algorithms; NP-complete problem; Network topology; Search methods; Space exploration; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Intelligence and Multimedia Applications, 2003. ICCIMA 2003. Proceedings. Fifth International Conference on

Print_ISBN

0-7695-1957-1

Type

conf

DOI

10.1109/ICCIMA.2003.1238128

Filename

1238128