Thao Duong

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.

Stochastic perturbation on variable flipping is the key idea of local search for SAT. Observing that variables are flipped several times in an attempt to escape from a local minimum, this paper presents a duplication learning mechanism in stagnation stages to minimise duplicative variable flipping. The heuristic incorporates the learned knowledge into a variable weighting scheme to effectively prevent the search from selecting duplicative variables. Additionally, probability-based and time window smoothing techniques are adopted to eliminate the effects of redundant information. The integration of the heuristic and gNovelty +  was compared with the original solvers and other state-of-the-art local search solvers. The experimental results showed that the new solver outperformed other solvers on the full set of SAT 2011 competition instances and three sets of real-world verification problems.