A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem(Algorithms and Data Structures)

スポンサーリンク

概要

• 論文の詳細を見る

• This paper deals with the Optimum Communication Spanning Tree Problem (OCST) which is well known as an NP-hard problem. For solving the problem, we uses an evolutionary approach. This paper presents a new effective tree encoding and proposes a tree construction routine (TCR) to generate a tree from the encoding. The basic principle is to break a cycle. We also propose a new crossover operator that focuses on the inheritance of parental information and the use of network information. Consequently, we confirm that the proposed algorithm is superior to other algorithms applied to the OCST problem or other tree problems. Moreover, our method can find a better solution than the solution which was previously known as the best solution. In addition, we analyzed the locality and diversity property of encoding and observed that the proposed method has high locality and at the same time it preserves population diversity for many generations. Finally, we conclude that these properties are the main reasons why the proposed method outperforms the other encodings.

• 社団法人電子情報通信学会の論文
• 2006-10-01

著者

• Soak Sang-moon

  Information Examination Team Korean Intellectual Property Office (kipo)

• Soak Sang-moon

  Information Systems Examination Team Kipo Gov. Complex Daejeon

関連論文

• 'Adaptive Link Adjustment' Applied to the Fixed Charge Transportation Problem(Numerical Analysis and Optimization)
• A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem(Algorithms and Data Structures)

スポンサーリンク