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.
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: 27 Sep 2016 *