Int. J. of Wireless and Mobile Computing   »   2016 Vol.11, No.1

 

 

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

 

Author: Geng Lin

 

Address: 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

 

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

 

Submission date: 22 May 2016
Date of acceptance: 27 Jun 2016
Available online: 27 Sep 2016

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article