TY - CHAP

T1 - Memetic Strategies for Network Design Problems

AU - Amirghasemi, Mehrdad

AU - Duong, Thach-Thao

AU - Hutchison, Nathanael

AU - Barthelemy, Johan

AU - Li, Yan

AU - Perez, Pascal

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Memetic strategies

KW - Network design problems

KW - Steiner tree problem

U2 - 10.1007/978-981-16-3128-3_3

DO - 10.1007/978-981-16-3128-3_3

M3 - Chapter

SN - 9789811631276

T3 - Springer Tracts in Nature-Inspired Computing

SP - 33

EP - 48

BT - Frontiers in Nature-Inspired Industrial Optimization

A2 - Khosravy, Mahdi

A2 - Gupta, Neeraj

A2 - Patel, Nilesh

CY - Singapore

ER -