Node-Based Genetic Algorithm for Communication Spanning Tree Problem

• LIN Lin

  Graduate School of Information, Production and Systems, Waseda University

• GEN Mitsuo

  Graduate School of Information, Production and Systems, Waseda University

抄録

Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve constrained minimum spanning tree (MST) problems of the communication network design and also have been used extensively in a wide variety of communication network design problems. Choosing an appropriate representation of candidate solutions to the problem is the essential issue for applying GAs to solve real world network design problems, since the encoding and the interaction of the encoding with the crossover and mutation operators have strongly influence on the success of GAs. In this paper, we investigate a new encoding crossover and mutation operators on the performance of GAs to design of minimum spanning tree problem. Based on the performance analysis of these encoding methods in GAs, we improve predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. The proposed crossover and mutation operators offer locality, heritability, and computational efficiency. We compare with the approach to others that encode candidate spanning trees via the Pr?fer number-based encoding, edge set-based encoding, and demonstrate better results on larger instances for the communication spanning tree design problems.

収録刊行物

• IEICE transactions on communications

  IEICE transactions on communications 89 (4), 1091-1098, 2006-04-01

  一般社団法人電子情報通信学会

キーワード

• minimum spanning tree (MST)
• communication network design
• genetic algorithm (GA)
• node-based encoding

詳細情報

• CRID: 1571698602535983616
• NII論文ID: 110007502942
• NII書誌ID: AA10826261
• ISSN: 09168516
• 本文言語コード: en
• データソース種別:
  • CiNii Articles
  • KAKEN