| 遗传算法与蚂蚁算法融合的马尔可夫收敛性分析 |
| |
| 引用本文： | 丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析[J].自动化学报,2004,30(4):629-634. |
| |
| 作者姓名： | 丁建立 陈增强 袁著祉 |
| |
| 作者单位： | 1.南开大学信息技术科学学院,天津 |
| |
| 基金项目： | 国家自然科学基金(60174021,60374037)，河南科技攻关项目(0124140141)资助~~ |
| |
| 摘 要： | 遗传算法具有快速随机的全局搜索能力,但不能很好地利用系统的反馈信息.蚂蚁系
统是一种并行的分布式正反馈系统,但初始求解速度慢.遗传算法与蚂蚁算法的融合,优势互
补.基于上述思想,提出遗传算法与蚂蚁算法融合的模型与方法,对该方法的收敛性进行了马尔
可夫理论分析,并证明其优化解满意值序列是单调不增的和收敛的.且对NP-hard问题中的30
城市TSP和中国CHNl44城市TSP两个实例进行了实验分析,仿真数据表明该方法不仅是一
个逐步收敛的过程,而且求解速度和求解效果都非常好.
|
| 关 键 词： | 遗传算法 蚂蚁算法 融合 马尔可夫过程 收敛性 |
| 收稿时间： | 2002-12-27 |
| 修稿时间： | 2002年12月27 |
On the Markov Convergence Analysis for the Combination of Genetic Algorithm and Ant Algorithm |
| |
| DING Jian-Li,CHEN Zeng-Qiang,YUAN Zhu-Zhi.On the Markov Convergence Analysis for the Combination of Genetic Algorithm and Ant Algorithm[J].Acta Automatica Sinica,2004,30(4):629-634. |
| |
| Authors: | DING Jian-Li CHEN Zeng-Qiang YUAN Zhu-Zhi |
| |
| Affiliation: | 1.College of Information Technology and Science,Nankai University,Tianjin |
| |
| Abstract: | Genetic algorithm has the ability of quickly and stochastically global search-ing, however, it can not make good use of enough output information for systems. Ant system is a parallel-process and distributive-forward system with a relatively slow veloc-ity for providing the solution. Combining genetic and ant algorithms can increase the merits each other. Based on the idea above, the model and method from the combination of genetic and ant algorithms are proposed, and the convergence of the method based on the Markov theory is analysed. Moreover, the conclusion can be drawn that the solution sequence is monotonically decreasing and convergent. The experiment and analysis are carried out for the cases of TSP30 and CHN144 on an NP-hard problem. The results of simulation show that not only the mixed algorithm is a step-by-step convergent process, but also its velocity and effect of solving are quite satisfactory. |
| |
| Keywords: | Genetic algorithm ant algorithm combination Markov process conver-gence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《自动化学报》浏览原始摘要信息 |
|
点击此处可从《自动化学报》下载全文 |
|
