Node-Based Genetic Algorithm for Communication Spanning Tree Problem

Lin LIN; Mitsuo GEN

doi:10.1093/ietcom/e89-b.4.1091

Node-Based Genetic Algorithm for Communication Spanning Tree Problem

Lin LIN, Mitsuo GEN

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Communications Vol.E89-B No.4 pp.1091-1098

Publication Date: 2006/04/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1093/ietcom/e89-b.4.1091

Type of Manuscript: Special Section PAPER (Special Section on Internet Technology VI)

Category

Cite this

Copy

Lin LIN, Mitsuo GEN, "Node-Based Genetic Algorithm for Communication Spanning Tree Problem" in IEICE TRANSACTIONS on Communications, vol. E89-B, no. 4, pp. 1091-1098, April 2006, doi: 10.1093/ietcom/e89-b.4.1091.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1093/ietcom/e89-b.4.1091/_p

Copy

@ARTICLE{e89-b_4_1091,
author={Lin LIN, Mitsuo GEN, },
journal={IEICE TRANSACTIONS on Communications},
title={Node-Based Genetic Algorithm for Communication Spanning Tree Problem},
year={2006},
volume={E89-B},
number={4},
pages={1091-1098},
abstract={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.},
keywords={},
doi={10.1093/ietcom/e89-b.4.1091},
ISSN={1745-1345},
month={April},}

Copy

TY - JOUR
TI - Node-Based Genetic Algorithm for Communication Spanning Tree Problem
T2 - IEICE TRANSACTIONS on Communications
SP - 1091
EP - 1098
AU - Lin LIN
AU - Mitsuo GEN
PY - 2006
DO - 10.1093/ietcom/e89-b.4.1091
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E89-B
IS - 4
JA - IEICE TRANSACTIONS on Communications
Y1 - April 2006
AB - 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.
ER -