一种基于随机化均匀设计点集的遗传算法用于求解MVCP

摘要
图/表
参考文献
相关文章 (2)

全文: PDF (350 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要基于理想浓度模型的机理分析，利用随机化均匀设计的理论和方法，对遗传算法中的交叉操作进行重新设计，并在分析图最小顶点覆盖问题特点的基础上，结合扫描-修正和局部改进策略，给出一个解决图最小顶点覆盖问题的遗传算法，称之为基于随机化均匀设计点集的遗传算法。通过将该算法与简单遗传算法和佳点集遗传算法进行求解图最小顶点覆盖问题的仿真模拟比较，可看出该算法提高求解的质量、速度和精度。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	任哲¹
	周本达²
	陈明华³

关键词 ：最小顶点覆盖问题(MVCP), 遗传算法(GA), 随机化均匀设计(RUD), 随机化均匀设计遗传算法(RGA)

Abstract：Based on the mechanism analysis of ideal density model and by utilizing the principle and method of random uniform design (RUD), the crossover operation in genetic algorithm (GA) is redesigned. Then, on the basis of characteristic analysis of the minimum vertices covering problem (MVCP) in graph and combining scan-repair and local improvement techniques, a GA based on RUD point set is presented to solve the MVCP. Compared with simple GA and Good Point GA for solving this problem, the simulation results show that the presented GA has superiority in speed, accuracy and overcoming premature.

Key words： Minimum Vertices Covering Problems (MVCP) Genetic Algorithm (GA) Random Uniform Design (RUD) Genetic Algorithm Based on Random Uniform Design (RGA)

收稿日期: 2009-08-28

ZTFLH:

TP301

基金资助:安徽省高校省级自然科学研究项目(No.KJ2007B152)、安徽省教育厅自然科学研究项目(No.2006KJ046B)和安徽省高校青年教师计划项目(No.2007jql180)资助

作者简介: 任哲，女，1957年生，教授，主要研究方向为优化算法、非参数统计和大样本理论.E-mail:renzhe@hfuu.edu.cn.周本达，男，1974年生，副教授，硕士，主要研究方向为计算智能、多Agent系统建模.陈明华，男，1954年生，教授，主要研究方向为概率统计的大样本理论、人工智能和遗传算法.

引用本文:

任哲，周本达，陈明华. 一种基于随机化均匀设计点集的遗传算法用于求解MVCP[J]. 模式识别与人工智能, 2010, 23(2): 284-290. REN Zhe,ZHOU Ben-Da,CHEN Ming-Hua. A Genetic Algorithm Based on Random Uniform Design Point Set for Solving MVCP. , 2010, 23(2): 284-290.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/ 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2010/V23/I2/284

[1] Singh A, Gupta A K. A Hybrid Heuristic for the Minimum Weight Vertex Cover Problem. Asia-Pacific Journal of Operational Research, 2006, 23(2): 273-285
[2] Pelikan M, Kalapala R, Hartmann A K. Hybrid Evolutionary Algorithms on Minimum Vertex Cover for Random Graphs // Proc of the 9th Annual Conference on Genetic and Evolutionary Computation. London, UK, 2007: 547-554
[3] Mazbic-Kulma B, Sep K. Some Approximation Algorithms for Minimum Vertex Cover in a Hypergraph. Heidelberg, Germany: Springer, 2007: 250-257
[4] Tinhofer G. Computational Graph Theory. Heidelberg, Germany: Springer-Verlag, 1990
[5] Golumbic M C. Algorithmic Graph Theory and Perfect Graph. New York, USA: Academy Press, 1980
[6] Vinnakota B, Andrews J. Repair of RAMs with Clustered Faults // Proc of the International Conference on Computer Design. Cambridge, USA, 1992: 582-585

[7] Lorena L A N, Lopes F B. A Surrogate Heuristics for Set Covering Problems. European Journal of Operational Research, 1994, 79(1): 138-150
[8] Koumousis V K, Katsaras C P. A Saw-Tooth Genetic Algorithm Combining the Effects of Variable Population Size and Reinitialization to Enhance Performance. IEEE Trans on Evolutionary Computation, 2006, 10(1): 19-28
[9] Lee C Y, Yao Xin. Evolutionary Programming Using the Mutations Based on the Lévy Probability Distribution. IEEE Trans on Evolutionary Computation, 2004, 8(1): 1-13
[10] Ho S Y, Shu Lisun, Chen J H. Intelligent Evolutionary Algorithms for Large Parameter Optimization Problems. IEEE Trans on Evolutionary Computation, 2004, 8(6): 522-541
[11] Dai Chaohua, Zhu Yunfang, Chen Weirong. Adaptive Genetic Algorithm Based on Cloud Theory. Control Theory Applications, 2007, 24(4): 646-650 (in Chinese)
(戴朝华,朱云芳,陈维荣.云自适应遗传算法.控制理论与应用, 2007, 24(4): 646-650)
[12] Li Hong, Jiao Yongchang, Zhang Li, et al. Novel Hybrid Genetic Algorithm for Global Optimization Problems. Control Theory Applications, 2007, 24(3): 343-348 (in Chinese)
(李宏,焦永昌,张莉,等.一种求解全局优化问题的新混合遗传算法.控制理论与应用, 2007, 24(3): 343-348)
[13] Wu Shaoyan, Zhang Qingfu, Chen Huowang. A New Evolutionary Based on Family Eugenics. Journal of Software, 1997, 8(2): 137-144 (in Chinese)
(吴少岩,张青富,陈火旺.基于家族优生学的进化算法.软件学报, 1997, 8(2): 137-144)
[14] Zhang Bo, Zhang Ling. Good Point Set Based Genetic Algorithm. Chinese Journal of Computers, 2001, 24(9): 917-922 (in Chinese)
(张铃,张钹.佳点集遗传算法.计算机学报, 2001, 24(9): 917-922)
[15] Hua Luogen, Wang Yun. Applications of Number-Theoretic Methods in Approximate Analysis. Beijing, China: Science Press, 1978 (in Chinese)
(华罗庚,王元.数论在近似分析中的应用.北京:科学出版社, 1978)
[16] Huo Hongwei. Genetic Algorithms in Graph Theory and Optimization. Ph.D Dissertation. Xian, China: Xidian University. College of Computer Science and Technology, 2005: 23-40 (in Chinese)
(霍红卫.遗传算法在图论和优化中的应用.博士学位论文.西安:西安电子科技大学.计算机学院, 2005: 23-40)
[17] University of Greenwich. Partition [EB/OL]. [2008-04-22]. http://www.gre.ac.uk/~c.walshaw/partition
[18] Wang Zhaojun, Zhang Renchu. Discrepancy of Uniform Design Sampling. Acta Mathematica Scientia, 1997, 17(2): 207-217 (in Chinese)
(王兆军,张润楚.均匀设计抽样的偏差.数学物理学报, 1997, 17(2): 207-217)