For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2001/06/01
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>>
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.