Memetic Strategies for Network Design Problems

In this chapter, memetic strategies are analyzed for the Steiner tree problem in graphs as a classic network design problem. Steiner tree problems can model a wide range of real-life problems from fault recovery in wireless sensor networks through Web API recommendation systems. The Steiner tree problem is considered as a generalized minimum spanning tree problem. Whilst the objective function of the minimum spanning tree problems is to find the minimum-total-weight subset of edges that connects all the nodes, the Steiner tree problem does not include all the nodes. However, it still has the same objective function. It should be noted that this problem requires a subset of nodes, called terminals, to be connected and the rest of the nodes are optional for being included. The problem, unlike the minimum spanning tree, is NP-Complete, and hence necessitates the design of a hybrid metaheuristic as an appropriate solution strategy. We analyze memetic strategies, based on effective integration of different local search procedures into a genetic algorithm for tackling this very interesting problem. Computational experiments have been reported on evaluating the impact of individual components of the procedure and it is demonstrated that the proposed strategy is both effective and robust.