|
|||||
|
|
| 一种基于随机化均匀设计点集的遗传算法用于求解MVCP | |
| 引用本文： | 任哲,周本达,陈明华. 一种基于随机化均匀设计点集的遗传算法用于求解MVCP[J]. 模式识别与人工智能, 2010, 23(2): 284-290 |
| 作者姓名： | 任哲 周本达 陈明华 |
| 作者单位： | 1.合肥学院 数理系 合肥 230022 2.皖西学院 数理系 六安 237012 3.皖西学院 计算机科学与技术系 六安 237012 |
| 基金项目： | 安徽省高校省级自然科学研究项目，安徽省教育厅自然科学研究项目，安徽省高校青年教师计划项目 |
| 摘 要： | 基于理想浓度模型的机理分析，利用随机化均匀设计的理论和方法，对遗传算法中的交叉操作进行重新设计，并在分析图最小顶点覆盖问题特点的基础上，结合扫描-修正和局部改进策略，给出一个解决图最小顶点覆盖问题的遗传算法，称之为基于随机化均匀设计点集的遗传算法。通过将该算法与简单遗传算法和佳点集遗传算法进行求解图最小顶点覆盖问题的仿真模拟比较，可看出该算法提高求解的质量、速度和精度。 |
| 关 键 词： | 最小顶点覆盖问题(MVCP) 遗传算法(GA) 随机化均匀设计(RUD) 随机化均匀设计遗传算法(RGA) |
| 收稿时间： | 2009-08-28 |
A Genetic Algorithm Based on Random Uniform Design Point Set for Solving MVCP |
|
| REN Zhe,ZHOU Ben-Da,CHEN Ming-Hua. A Genetic Algorithm Based on Random Uniform Design Point Set for Solving MVCP[J]. Pattern Recognition and Artificial Intelligence, 2010, 23(2): 284-290 | |
| Authors: | REN Zhe ZHOU Ben-Da CHEN Ming-Hua |
| Affiliation: | 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. |
| Keywords: | Minimum Vertices Covering Problems (MVCP) Genetic Algorithm (GA) Random Uniform Design (RUD) Genetic Algorithm Based on Random Uniform Design (RGA) |
| 本文献已被 万方数据 等数据库收录！ | |
| 点击此处可从《模式识别与人工智能》浏览原始摘要信息 | |
| 点击此处可从《模式识别与人工智能》下载全文 | |