A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem

Sang-Moon SOAK

doi:10.1093/ietfec/e89-a.10.2882

A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem

Sang-Moon SOAK

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.10 pp.2882-2893

Publication Date: 2006/10/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.10.2882

Type of Manuscript: PAPER

Category: Algorithms and Data Structures

Cite this

Copy

Sang-Moon SOAK, "A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 10, pp. 2882-2893, October 2006, doi: 10.1093/ietfec/e89-a.10.2882.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.10.2882/_p

Copy

@ARTICLE{e89-a_10_2882,
author={Sang-Moon SOAK, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem},
year={2006},
volume={E89-A},
number={10},
pages={2882-2893},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.10.2882},
ISSN={1745-1337},
month={October},}

Copy

TY - JOUR
TI - A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2882
EP - 2893
AU - Sang-Moon SOAK
PY - 2006
DO - 10.1093/ietfec/e89-a.10.2882
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2006
AB - 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.
ER -