A hybrid metaheuristic algorithm for generalized vertex cover problem

作者：Hu, Shuli; Li, Ruizhi; Zhao, Peng; Yin, Minghao^*

来源：Memetic Computing, 2018, 10(2): 165-176.

DOI：10.1007/s12293-016-0216-z

• Hybrid metaheuristic algorithm
• Generalized vertex cover problem
• Neighborhood search
• Crossover

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.

• 出版日期2018-6
• 单位东北师范大学