A hybrid metaheuristic algorithm for generalized vertex cover problem

• DOI: 10.1007/s12293-016-0216-z
• Publication Date: 2016-11-12T18:56:39Z
• Authors: Shuli Hu; Ruizhi Li; Peng Zhao; Minghao Yin
• Keywords: 0211 other engineering and technologies; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

The generalized vertex cover problem (GVCP) extends classic vertex cover problems to take both vertex and edge weights into consideration in the objective function. The GVCP consists in finding a vertex subset such that the sum of vertex weights together with all the corresponding edge weights is minimized. In this paper, we proposed a hybrid metaheuristic algorithm to solve GVCP (MAGVCP for short) that is based on evolutionary search and iterated neighborhood search. The algorithm uses population initializing procedure to produce high quality solutions, applies a dedicated crossover to generate offspring solutions, and finally utilizes an iterated best chosen neighborhood search to find better solutions. Experiments carried on random instances and DIMACS instances demonstrate the effectiveness of the proposed algorithm.