Title: A hybrid self-adaptive evolutionary algorithm for the minimum weight dominating set problem

Authors: Geng Lin

Addresses: Department of Mathematics, Minjiang University, Fuzhou, Fujian, China

Abstract: Given an undirected graph with weights associated with its vertices, the minimum weight dominating set problem (MWDSP) is to determinate a subset of vertices with minimum sum of weights such that each vertex of the graph either belongs to the subset or is adjacent to a vertex in the subset. This paper presents a hybrid self-adaptive evolutionary algorithm for the MWDSP. A greedy randomised adaptive construction procedure is used to generate an initial population. Then, a crossover operator and an adaptive mutation operator are employed to generate a new solution, which is further refined by an adaptive tabu search. These adaptive strategies make a good balance between intensification and diversification. Computational experiments on two types of benchmark instances prove that our proposed algorithm can find high quality solutions in a short computing time.

Keywords: self-adaptive evolutionary algorithms; dominating sets; combinatorial optimisation; undirected graphs; tabu search; intensification; diversification; minimum weight DSP; dominating set problem.

DOI: 10.1504/IJWMC.2016.079466

International Journal of Wireless and Mobile Computing, 2016 Vol.11 No.1, pp.54 - 61

Received: 24 May 2016
Accepted: 27 Jun 2016
Published online: 28 Sep 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article