|Affiliations:||Mathematical Institute of the Serbian Academy of Sciences and Arts||Title:||A genetic algorithm for the biconnectivity augmentation problem||Journal:||Proceedings of the 2000 Congress on Evolutionary Computation, CEC 2000||Volume:||1||First page:||89||Last page:||96||Conference:||2000 Congress on Evolutionary Computation, CEC 2000; San Diego, CA; United States; 16 July 2000 through 19 July 2000||Issue Date:||1-Jan-2000||Rank:||M30||DOI:||10.1109/CEC.2000.870280||Abstract:||
In this paper we present a genetic algorithm (GA) for the NP-hard biconnectivity problem for graphs. Suppose a 2-connected, undirected weighted graph G(V,E) and a spanning subset of edges E/sub 0//spl sub/E are given. The goal is to augment set E/sub 0/ with a set AUG/spl sub/E-E/sub 0/ of minimal weight, such that graph G(V,E/sub 0//spl cup/AUG) is biconnected. To our knowledge, this is the first time a GA is applied to this problem. First, a straight-forward "pure" GA improved with caching is introduced, which is then hybridized with a greedy, problem dependent heuristic. The proposed approaches are problem instances with up to 1160 feasible edges. While the pure GA performs well, significantly better solutions can be obtained by the hybrid strategy.
Show full item record
checked on Mar 26, 2023
checked on Mar 27, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.