Genetic algorithms and network ring design

Optimal network ring design is a difficult problem characterised by the requirement to compare a large number of potential solutions (network designs). The problem of network ring design can be described as consisting of three parts: routing, link capacity assignment and ring determination. It has traditionally been broken down into a number of subproblems, solved in sequence, and usually by heuristics, thereby leading to locally-optimal design solutions. Genetic Algorithms (GAs) have shown themselves to be efficient at searching large problem spaces and have been successfully used in a number of engineering problem areas, including telecommunications network design. We present an approach of a GA to the network ring design problem in which the GA representation encapsulates all aspects of the problem and solves them simultaneously. A novel, hybrid bit and permutation representation is described, along with the fitness function for the design problem. Results of applying this representation to a number of test networks are presented and compared with heuristic design methods.