Memetic Strategies for Network Design Problems

Mehrdad Amirghasemi, Thach-Thao Duong, Nathanael Hutchison, Johan Barthelemy, Yan Li, Pascal Perez

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


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.
Original languageEnglish
Title of host publicationFrontiers in Nature-Inspired Industrial Optimization
EditorsMahdi Khosravy, Neeraj Gupta, Nilesh Patel
Place of PublicationSingapore
Number of pages16
ISBN (Electronic)9789811631283
Publication statusPublished - 2022
Externally publishedYes

Publication series

NameSpringer Tracts in Nature-Inspired Computing


  • Memetic strategies
  • Network design problems
  • Steiner tree problem


Dive into the research topics of 'Memetic Strategies for Network Design Problems'. Together they form a unique fingerprint.

Cite this