Design of stacked self-healing rings using a genetic algorithm

Ring structures in telecommunications are taking on increasing importance b ecause of their "self-healing" properties. We consider a ring design proble m in which several stacked self-healing rings (SHRs) follow the same route, and, thus, pass through the same set of nodes. Traffic can be exchanged am ong these stacked rings at a designated hub node. Each non-hub node may be connected to multiple rings. It is necessary to determine to which rings ea ch node should be connected, and how traffic should be routed on the rings. The objective is to optimize the tradeoff between the costs for connecting nodes to rings and the costs for routing demand on multiple rings. We desc ribe a genetic algorithm that finds heuristic solutions for this problem. T he initial generation of solutions includes randomly-generated solutions, c omplemented by "seed" solutions obtained by applying a greedy randomized ad aptive search procedure (GRASP) to two related problems. Subsequent generat ions are created by recombining pairs of "parent" solutions. Computational experiments compare the genetic algorithm with a commercial integer program ming package.