A Genetic Algorithm Based on Random Uniform Design Point Set for Solving MVCP
REN Zhe1,ZHOU Ben-Da2,CHEN Ming-Hua3
1.Department of Mathematics and Physics,Hefei University,Hefei 230022 2.Department of Mathematics and Physics,West Anhui University,Luan 237012 3.Department of Computer Science and Technology,West Anhui University,Luan 237012
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.
[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)
2010, Vol. 23 
