Publication Type

Journal Article

Version

acceptedVersion

Publication Date

6-2001

Abstract

We explore the use of GAs for solving a network optimization problem, the degree-constrained minimum spanning tree problem. We also examine the impact of encoding, crossover, and mutation on the performance of the GA. A specialized repair heuristic is used to improve performance. An experimental design with 48 cells and ten data points in each cell is used to examine the impact of two encoding methods, three crossover methods, two mutation methods, and four networks of varying node sizes. Two performance measures, solution quality and computation time, are used to evaluate the performance. The results obtained indicate that encoding has the greatest effect on solution quality, followed by mutation and crossover. Among the various options, the combination of determinant encoding, exchange mutation, and uniform crossover more often provides better results for solution quality than other combinations. For computation time, the combination of determinant encoding, exchange mutation, and one-point crossover provides better results.

Keywords

encoding, genetic algorithms, telecommunication network planning, trees (mathematics)

Discipline

Computer Sciences | Theory and Algorithms

Research Areas

Information Systems and Management

Publication

IEEE Transactions on Evolutionary Computation

Volume

5

Issue

3

First Page

236

Last Page

249

ISSN

1089-778X

Identifier

10.1109/4235.930313

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Additional URL

https://doi.org/10.1109/4235.930313

Download

Share

COinS