RELIABLE COMMUNICATION NETOWRK DESIGN WITH EVOLUTIONARY ALGORITHMS

摘要

For the reliable communication network design (RCND) problem unreliable links are available, each bearing several options which have different levels of reliability and varying costs. The goal is to find the most cost-effective communication network design that satisfies a predefined overall reliability constraint. This paper presents two new evolutionary algorithm (EA) approaches to solving the RCND problem: LaBORNet and BaBORNet. LaBORNet uses an encoding that represents the network topology as well as the used link options while repairing infeasible solutions using an additional repair heuristic (CURE). BaBORNet encodes only the network topology and determines the link options by using the repair heuristic CURE as a local search method. The experimental results show that the new EA approaches using repair heuristics outperform existing EA approaches from the literature using penalties for infeasible solutions. They also find better solutions for existing problems from the literature, as well as for new and larger test problems.