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

In this paper the solution of the survivability problem of broadband communication network is continued. The problem is treated as a combinatorial optimization problem solved a hybridised version of genetic algorithms that has both the advantages of GA and local search methods. The MSCC formulation of this problem is treated here along with the MSC with constraints using the proposed HGA of part 1 of this paper. In contrast to the MSC solutions, most of the algorithms showed more robustness in solving MSCC in that their results are less affected to the number of deleted links, which is due to the constraints imposed on link demands. Since there are no delay or maximum hop limit constraints, we opted to constraint expensive link capacities even if these would increase the average path length for traffic to flow from one end to the other. This however results in different topologies with different link capacities. Due to the tight boundary imposed by new constraints on the MSC problem, all algorithms faced a problem of generating infeasible solutions especially at the first few hundred generations. Since these infeasible solutions are used to create new individuals through crossover and mutation, this process continued until a build up of diversity has grown to a point were genetic diversity outweighed the infeasibilities of the first few hundred generations. This diversity was introduced through elitism as in SSGA or exploited from the niching characteristics of speciation algorithms as in SNGA, SGGA, and the others or through the modified mutation/hill climbing characteristics for LSGA.