Designing reliable communication networks with a genetic algorithm using a repair heuristic
This paper investigates GA approaches for solving the reliable communication network design problem. For solving this problem a graph with minimum cost must be found that satisfies a given network reliability constraint. To consider the additional reliability constraint different approaches are possible. We show that existing approaches using penalty functions can result in invalid solutions and are therefore not appropriate for solving this problem. To overcome these problems we present a repair heuristic, which is based on the number of spanning trees in a graph. This heuristic always generates a valid solution, which when compared to a greedy cheapest repair heuristic shows that the new approach finds better solutions with less computational effort.
In geänderter Fassung erschienen als : Working papers / Lehrstuhl für ABWL und Wirtschaftsinformatik ; 2003,14 Mannheim: Universität Mannheim / Fakultät für Betriebswirtschaftslehre, 2003