Title :
Hybridizing genetic algorithms for a survivability study of broadband communication networks: solution of the MSCC
Author :
Hazem, M.M. ; Sayoud, H. ; Takahashi, K.
Author_Institution :
Malaya Univ., Kuala Lumpur, Malaysia
Abstract :
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.
Keywords :
broadband networks; combinatorial mathematics; genetic algorithms; quality of service; search problems; telecommunication network routing; telecommunication traffic; MSCC; QoS constraints; broadband communication networks; combinatorial optimization problem; genetic algorithms; genetic diversity; hill climbing characteristics; local search methods; minimum spare capacity; network failure; quality of service; survivability problem; traffic routing; Broadband communication; Communication networks; Delay; Genetic algorithms; Genetic mutations; Measurement standards; Multimedia systems; Robustness; Search methods; Topology;
Conference_Titel :
Communications, 2003. APCC 2003. The 9th Asia-Pacific Conference on
Print_ISBN :
0-7803-8114-9
DOI :
10.1109/APCC.2003.1274238