Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (14): 27-29.

• 学术探讨 • Previous Articles     Next Articles

A Hybrid Genetic Algorithm for Vertex Cover Problem

  

  • Received:2006-09-23 Revised:1900-01-01 Online:2007-05-10 Published:2007-05-10

一种求解顶点覆盖问题的混合遗传算法

王成 周育人 涂卫平   

  1. 华南理工大学计算机科学与工程学院 华南理工大学计算机科学与工程学院
  • 通讯作者: 王成

Abstract: Vertex cover problem (VCP) is an NP-hard problem and it has numerous real life applications in, for example, scheduling and computer networking, which is closely related to the important problems of independent set (IS) and maximum clique (MC). Because simple genetic algorithm is not good at local searching, this paper presents a new hybrid genetic algorithm (HGA) to solve minimum vertex cover problem. Combining SGA and local optimization technique (LOT), this improves local searching ability of SGA and gives near to optimal solution speedy. The results obtained show that the new approach is effective.

Key words: genetic algorithm, vertex cover problem, local optimization

摘要: 顶点覆盖问题是一个NP难问题,在排序、计算机网络等现实生活中有许多的应用。使用基本遗传算法进行搜索时,存在着局部搜索能力较弱的不足,本文提出了一种新的求解最小顶点覆盖问题的混合遗传算法,将基本遗传算法与局部优化策略相结合,改善遗传算法的局部搜索能力,加快求解该问题的速度。对几种典型无向图的实验证实了新方法的有效性,其整体性能优于现有的一些顶点覆盖问题遗传算法。

关键词: 遗传算法, 顶点覆盖问题, 局部优化