基于多头绒泡菌模型的优化蚁群算法及其在旅行商问题中的运用

摘要

NP-难问题是计算机科学研究中的主要研究问题之一。Garey提出了若一个问题被定义为NP-难问题，则无法用计算机进行精确求解的论断。该论断为研究人员奠定了计算难解的界限，避免了研究人员为解决此类问题而做出大量而无效的工作。但是在实际问题当中，NP-难问题又是不可避免的，如在路网规划、工业控制、网络构建等实际问题上都要涉及到NP-难问题。既然已有论断表明计算机无法精确求解NP-难问题，研究人员均将目光转向了近似求解NP-难问题，并取得了较大的进展。作为经典的NP-难问题----（多目标）旅行商问题在真实世界中具有广泛的应用，例如车辆调度问题、路线推荐问题。理论界和工程界对能够高效求解（多目标）旅行商问题的算法具有迫切的需求。当前，群体智能算法已成为求解（多目标）旅行商问题的主流算法，其中包括遗传算法、粒子群算法、蚁群算法等。蚁群算法在求解经典旅行商问题时体现出了良好的鲁棒性和可行性，因此，研究人员将蚁群算法运用到了求解多目标旅行商问题上来。当前求解多目标旅行商问题的蚁群算法主要分为三类：基于目标转化、基于种群和基于帕累托最优三类。尽管当前利用蚁群算法解决多目标旅行商问题已经有了很大进展，但是由于蚂蚁之间的信息素正反馈交流方式使蚂蚁群体倾向于集中选取帕累托前沿的某个可行空间，产生解分布过于集中、解空间的覆盖率过低和局部最优解等问题；且蚁群算法在求解初期搜索盲目性强，导致搜索效率低下。综上，蚁群算法还有进一步优化的空间。研究人员在生物实验中发现，一种单细胞多核黏菌----多头绒泡菌,拥有优秀的路径寻优能力和路网导航能力。Tero发现多头绒泡菌在觅食过程中呈现出了一种“重点管道重点培养”的正反馈机制，并对该机制进行了建模分析。基于该模型，本文提出利用多头绒泡菌模型优化蚁群算法。
　　本文利用多头绒泡菌模型对多目标旅行商问题中的各目标进行分别得粗略求解，得到大致的“地图”----信息素矩阵，虽然这张“地图”并不一定准确，但是却有一定的指向性。同时，利用该“地图”参与初始化蚁群算法的信息素矩阵，解决蚁群算法求解多目标旅行商问题前期的盲目性问题。在每次迭代过程中，因为信息素具有挥发性，所以该“地图”的偏差并不会严重地影响蚁群算法的寻优效率，同时，虽然该“地图”携带的信息素会挥发，但是并不会迅速消失，所以，该“地图”能够在一定程度上扩大蚂蚁的搜索范围，使得解的可行性更高、在帕累托前沿上的分布更加广泛。通过大量的仿真实验发现，新算法在解分布的广泛性、解空间的覆盖率和解的可行性等方面都有了显著的提升。随后，本文将山西十大景点旅游路线推荐问题转换成为一个多目标旅行商问题，综合考虑距离和时间两大因素。利用本文所提出的优化算法进行路径推荐，所得结果可行性和满意度高。该应用表明，优化算法不仅具有理论上的有效性，同时也具有现实中的实用性。将优化算法与另一种多头绒泡菌模型优化算法进行对比分析，实验结果显示在求解结果的精确性、扩展性、空间覆盖率方面更加优秀，同时，在求解时间方面，iPM-P-ACO算法远远领先于PM-P-ACO算法。

目录

封面

声明

目录

中文摘要

英文摘要

第1章 绪论

1.1 研究现状

1.2 研究内容

1.3 论文组织结构

第2章 蚁群算法解决旅行商问题

2.1旅行商问题

2.2 蚁群算法

2.3本章小节

第3章 基于多头绒泡菌模型优化蚁群算法

3.1 多头绒泡菌模型分析

3.2 多头绒泡菌模型优化多目标蚁群算法

3.3 仿真实验结果

3.4求解旅游路线推荐问题

3.5 本章小结

第4章 与其他多头绒泡菌模型优化算法的对比

4.1 PM-P-ACO算法

4.2 仿真实验

4.3 本章小结

第5章 总结与展望

5.1 工作总结

5.2 未来工作展望

参考文献

致谢

硕士期间发表的论文目录