A multi-fault minimum cost spare capacity assignment of communication networks: a comparison between traditional genetic and niching algorithms

This paper investigates the possibility of using a new variation of genetic algorithms (GA) known as niching 'speciation' techniques to solve combinatorial NP-hard design problems encountered in real-life communication networks. Algorithms based on sequential niching, deterministic crowding, fitness sharing and restricted mating schemes were investigated and compared to more traditional GAs like the generational replacement, the steady-state and to a competing class of evolutionary algorithms like the tabu search. The necessity for this investigation arises from the fact that traditional GA without hybridization, albeit able deal with a variety of unimodal domains, as they have been successfully applied to identify, locate and lead candidates populations to converge to single global optimum are less likely to efficiently explore domains characterized with multiple optima (peaks). Populations of the traditional GA would eventually cluster around only one peak or a finite population in the absence of selection pressure due to noisy selection, leaving several equally attractive global optima in the search space unexplored, a phenomenon known as genetic drift. Extensive tests results on a twenty-node network have shown the ability of the proposed implementations to solve the proposed formulations efficiently. With varying results, these implementations have reached near-optimal/optimal solutions on the TDCA1 and TDCA2 problems and compared favorably with other similar heuristics found in the literature with cost improvement of up to 28%. Speciation based algorithms have shown superiority over GRGA, SSGA and tabu search (TS) algorithms in all solution trials. The proposed LSGA hybrid was found to perform better than all the other applications reported in this paper.