Topology And Survivability Design Of Broadband Communication Networks Using Genetic Algorithms - Hameida , Sayoud (2002)
The efficient design of telecommunication networks has long been a challenging task. It is made difficult by the conflicting and interdependent requirements necessary to optimize network performances. Since most aspects of the network design problem are NP-hard, traditional deterministic solution methods fail to reach good quality solutions. However , heuristics have emerged as powerful techniques able to reach near-optimum solutions in reasonable amounts of time. In this dissertation, we report on our efforts to investigate the applicability , develop and test simple, speciation and hybrid genetic algorithms (GA) to solve two difficult NP-hard combinatorial optimization problems solved by telecommunication and broadband networking companies to minimize investment costs and maximize network reliability. These problems address two issues found in the planning and management stages of a network. The first aims at designing minimum cost networks considering physical topology, capacity assignment and traffic routing with and without QoS constraints. The second deals with broadband network survivability and reliability issues considering different component failures scenarios. It tries to ensure a 100% restorability and minimizes either the overall spare capacity or network cost required for a full restorable network with link(s), node(s), and /or both link/node failures(s) by finding a set of backup paths that enable the minimization of shared space capacity among these and satisfy QoS constraints before and after the failure(s). Binary coding for these two problems were developed and solved first with generational "simple" and steady state GAs. Performance comparisons between these two with evidences of possible improvements in the solution quality led to the investigation and development of speciation "niching" and hybrid algorithms. Able to introduce better diversity into the solution space and enhance the exploration/exploitation capabilities of these algorithms, speciation algorithms based on sequential niching, deterministic crowding, fitness sharing and restriction mating were investigated. Hybridization was investigated in two approaches, the first modified the mutation operator to include hill climbing capabilities while the second combined GA capabilities with Nelder and Mead's simplex downhill local search to form an integrated search algorithm able to take advantage of the strengths of both algorithms and hence efficiently explore and exploit the genetic search space.