摘要： 为改善传统遗传算法求解最小顶点覆盖问题时的效果，基于理想浓度模型，利用均匀设计抽样的理论和方法，对遗传算法中的交叉操作进行重新设计，结合局部搜索策略，提出一种新的遗传算法UGA。与标准遗传算法及佳点集遗传算法进行实例仿真比较，结果证明该算法可以提高求解的质量、速度和精度。

关键词: 最小顶点覆盖问题, 遗传算法, 均匀设计抽样, 基于均匀设计抽样的遗传算法

Abstract: To improve the effect of traditional Genetic Algorithm(GA) in solving Minimum Vertices Covering Problem(MVCP), based on the mechanism of ideal density model and characteristic of MVCP, the crossover operation in GA is redesigned by using the principle of Uniform Design Sampling(UDS) and combining the locale search strategy. This paper proposes a Genetic Algorithm Based on Uniform Design Sampling(UGA) and applies it to solve MVCP. Compared with Simple GA(SGA) and Good Point-set GA(GGA), the simulation results show that UGA has superiority in speed, accuracy and overcoming premature.

Key words: Minimum Vertices Covering Problem(MVCP), Genetic Algorithm(GA), Uniform Design Sampling(UDS), Genetic Algorithm Based on Uniform Design Sampling(UGA)

中图分类号: 

• TP183