This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Rothlauf, F. Search for Related Content

An Encoding in Metaheuristics for the Minimum Communication Spanning Tree Problem

Department of Information Systems, University of Mainz, 55099 Mainz, Germany
rothlauf{at}uni-mainz.de

Problem-specific encodings can improve the performance of metaheuristics, such as genetic algorithms or simulated annealing. This paper studies the link-biased (LB) encoding, which is a tree representation, and applies metaheuristics using this encoding to the minimum communication spanning tree (MCST) problem. Given the communication requirements of the nodes, the MCST problem seeks a communication spanning tree with minimum total cost. Optimal solutions for MCST problems are similar to minimum spanning trees (MSTs), and the LB encoding exploits this property by encoding trees similar to MSTs with higher probability. The paper investigates how to systematically design problem-specific encodings for MCST problems and how to set the encoding-specific parameter that controls the bias of the LB encoding towards MSTs; it then presents performance results for various MCST problems.

Key words: problem-specific representations; trees; metaheuristics; encodings; communication networks
History: received January 2005; revised August 2008; accepted September 2008.