Evolutionary local search for the edge-biconnectivity augmentation problem

✍ Scribed by Günther R. Raidl; Ivana Ljubić

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 91 KB
• Volume: 82
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00285-x

✦ Synopsis

This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph edge-biconnected. An application is the extension of an existing communication network to become robust against single link-failures. An evolutionary algorithm (EA) is presented which includes an effective preprocessing of the problem data and a local improvement procedure that is applied during initialization, recombination, and mutation. In this way, the EA searches the space of feasible, locally optimal solutions only. The variation operators were designed with particular emphasis on low computational effort and strong locality. Empirical results indicate the superiority of the new approach over two previous heuristic methods.