蚁群算法与遗传算法的融合与性能研究

作     者：刘敏俊 

作者单位：中国地质大学（北京） 

学位级别：硕士

导师姓名：王祖朝

授予年度：2013年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：正反馈 蚁群算法 遗传算法 信息素 全局搜索 

摘      要：蚁群算法是通过模拟蚂蚁觅食过程中的群体行为而产生的算法，具有良好的分布式并行机制、过程中提供正反馈信息、易与其它方法结合以及有较强的鲁棒性等优点，但是存在搜索时间长、易陷入局部最优等缺点;遗传算法则是基于生物群体的进化过程而形成的算法，同样具有并行、自适应等特点，还有良好的全局搜索能力以及确保种群多样性的特点。于是本文就根据蚁群算法和遗传算法各自的优势和特点，针对离散域和连续域两种情况分别将两算法按独特的方式融合生成遗传蚁群算法。 关于离散域的遗传蚁群算法思想，主要是在基本蚁群算法的基础上，对算法中的3个参数α、 β、ρ利用遗传算法进行优化求解，以期获得问题的较优解，同时还可以对蚁群算法寻优问题中的参数组合进行了初步分析。论文在matlab编程环境下将算法针对TSP问题进行了实验，在验证算法可行性后还针对具体TSP案例Eil51问题进行了参数的性能分析，发现随着内外部蚁群算法和遗传算法迭代次数的增加：1、算法可以求得的路径长度的收敛域逐渐靠近最优解，并且极差越来越小;2、算法求得结果的标准差也逐渐变小，越来越稳定;3、算法的寻优精度也在递增，误差逐个递减。 连续域遗传蚁群算法的算法思想由三部分构成，开始先对区域利用遗传算法获取蚁群算法的初始信息素分布，达到有目标地指引蚂蚁群体初始分布的效果;然后再利用蚁群算法进行主要寻优过程;最后为防止算法过早陷入局部最优，在固定次数迭代后又引入遗传操作来加大种群分布的多样性。文章中利用matlab对融合算法实现后，并同单独的遗传算法和蚁群算法针对测试函数Ackley进行了试验对比。令α=1, β=3, M=N=10, ρ=0.6, Q=1，粒子规模为100，迭代次数为50的前提下发现：融合算法耗时1.468秒;蚁群算法耗时1.31秒;遗传算法耗时1.266秒。虽然融合算法时间略劣于其它算法，但是融合算法20次最优均值为19.634，优于蚁群算法的19.6255以及遗传算法的19.5735，且融合算法求解结果稳定分布在19.63-19.64之间，故其稳定性优于另两种单独的算法。