An Evolutionary Algorithm Approach to the Design of Minimum Cost Survivable Networks with Bounded Rings

Beatrice M. OMBUKI  Morikazu NAKAMURA  Zensho NAKAO  Kenji ONAGA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.6   pp.1545-1548
Publication Date: 2001/06/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Papers Selected from 2000 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2000))
two-connected network design,  genetic algorithm,  combinatorial optimization,  

Full Text: PDF>>
Buy this Article

This paper presents a genetic algorithm for designing at minimum cost a two-connected network topology such that the shortest cycle (referred to as a ring) to which each edge belongs does not exceed a given maximum number of hops. The genetic algorithm introduces a solution representation in which constraints such as connectivity and ring constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided thus resulting in increased efficiency. Experimental evaluation shows the effectiveness of the proposed GA.