Hybridizing genetic algorithms for a survivability study of broadband communication networks: solution of the MSC

Hybridising a GA with a local search (LS) heuristics combines the GA´s ability to widely sample a search space with a local search hill-climbing ability. This paper compares two distinct approaches for achieving these characteristics. The first approach combines the steady- state GA (SSGA) with a Neider and Mead downhill simplex method (DSM) to form an integrated solver taking advantage of both local exploitation and global exploration characteristics provided by the GA and the LS hill-climbing. This algorithm (LSGA1) is applied on two stages on the initial genetic population. First, an elite non-dominated set of solutions is selected, an intermediate population composed of the elite and the improved solutions by natural genetic operators is constructed and then the DSM is applied to some solutions of the intermediate population. The second approach (LSGA2) modifies the mutation operator of the GA in such a way that the new operator implements, in a certain manner, some basic principles for hill-climbing methods. The performance of these two algorithms is compared to traditional GAs like the generational replacement GA (GRGA), SSGA, more sophisticated speciating algorithms able to better sample the search space, introduce more diversity and deal efficiently with genetic drift like the struggle GA (SGGA) and tabu search, a similar evolutionary algorithm derived from natural processes. To test the applicability of these algorithms on real world NP-hard combinatorial optimization problems, survivability of broadband communication networks is addressed. Minimum spare capacity (MSC) is formulated as a multicommodity flow network design problem given the physical network topology, associated capacity allocation to meet normal traffic demands, traffic demand matrix, cost elements and the QoS requirements, and how much spare capacity should be provisioned in the network. This paper also answers the questions as to where it should be placed in order for the network to survive a set of link(s), node(s) or both link and node failure scenarios and as to what expense needed for a network to survive. Considering up to ten possible network failures at a time. Extensive test results have shown the ability of the proposed two algorithms to solve the presented formulation eff- iciently. With varying results, these two algorithms have reached optimal solutions on the MSC problem and compared favourably with other similar heuristics found in trie literature.