Using a hybrid of exact and genetic algorithms to design survivable networks

Wide-band technology has the capability to carry many services such as voice, video and other web-site technology on one link. Therefore these networks differ significantly from traditional dense copper-based networks. These networks are sparse and tree-like, and there are few disjoint paths (links) between a pair of nodes (space and/or terrestrial stations). Therefore connectivity has become a very important issue for survivability of these networks. Survivable networks are ones which can remain suitably connected after the incapacitation of a node or a link. Finding subgraphs that meet survivability requirements is (NP) hard on general graphs. However there are polynomial time algorithms available when these problems are solved on special graphs, including ones known as k-trees. We present a hybrid method for finding approximate optimal solutions for survivable network problems on complete graphs that takes advantage of k-tree solvability. A genetic algorithm generates ‘good’ 3-tree subgraphs of the underlying network, where goodness is measured by the exact optimal survivable subgraph of the given 3-tree. The best such subgraph is taken as an approximate optimum for the full problem. Sufficient conditions for existence of a partial 3-tree optimal solution to the full survivable network problem validate the approach, and some computational experience is reported.