Genetic Algorithms and Network Design: An Analysis of Factors Influencing GA's Performance

Authors: Hsinghua Chou, G. Premkumar, Chao-Hsien Chu

In recent years genetic algorithms (GA) are being extensively used in optimization problems as an alternative to traditional heuristics. The results have been mixed. However, no systematic research has been performed on the impact of various GA factors on GA's performance. In this study, we explore the use of GA for solving a network optimization problem, the degree constrained minimum spanning tree (DCMST) problem, and examine the impact of encoding, crossover, and mutation on the performance of the genetic algorithm. A specialized repair heuristic is used to improve the performance of the algorithm. An experimental design with 48 cells and 10 data points in each cell is used to examine the impact of two encoding methods - Prufer and determinant encoding; three crossover methods - one-point, two-point, and uniform; two mutation methods - insert and exchange; and four networks of varying node sizes - 20, 40, 60, 80. Two performance measures, solution quality and computation time, are used to evaluate the performance of the algorithm. The results indicate that network size has the greatest effect on solution quality, followed by encoding and mutation, and finally crossover. Among the various options the combination of determinant encoding, exchange mutation and uniform crossover provides better results than other combinations most of the time. Keywords: Genetic Algorithms, Network design, Degree Constrained minimum spanning tree, GA operators.