计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (14): 27-29.
• 学术探讨 • 上一篇 下一篇
王成 周育人 涂卫平
收稿日期:
修回日期:
出版日期:
发布日期:
通讯作者:
Received:
Revised:
Online:
Published:
摘要： 顶点覆盖问题是一个NP难问题，在排序、计算机网络等现实生活中有许多的应用。使用基本遗传算法进行搜索时，存在着局部搜索能力较弱的不足，本文提出了一种新的求解最小顶点覆盖问题的混合遗传算法，将基本遗传算法与局部优化策略相结合，改善遗传算法的局部搜索能力，加快求解该问题的速度。对几种典型无向图的实验证实了新方法的有效性，其整体性能优于现有的一些顶点覆盖问题遗传算法。
关键词: 遗传算法, 顶点覆盖问题, 局部优化
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
王成 周育人 涂卫平. 一种求解顶点覆盖问题的混合遗传算法[J]. 计算机工程与应用, 2007, 43(14): 27-29.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://cea.ceaj.org/CN/
http://cea.ceaj.org/CN/Y2007/V43/I14/27
