Summary
|
For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE. |
|
A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem Sang-Moon SOAK Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E89-A No.10 pp.2882-2893 Publication Date: 2006/10/01 Online ISSN: 1745-1337 DOI: 10.1093/ietfec/e89-a.10.2882 Print ISSN: 0916-8508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: optimum communication spanning tree problem, evolutionary algorithm, genetic encoding method, Full Text: PDF(811KB)>>
Summary: 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. | ||||||||||
| ||||||||||
