论文部分内容阅读
组合优化是优化领域中的一个重要分支，具有非常强的实际应用背景。从蚂蚁群体寻找最短路径的行为受到启发，意大利学者Dorigo等人1991年提出一种模拟蚁群行为的启发式优化算法——蚁群算法。在过去十多年的时间里，它已经成功地用于求解旅行商问题(TSP)等多种组合优化问题。
本文首先概述了组合优化问题及其复杂性理论，接着围绕蚁群算法的原理、理论及其应用，就如何改进基本蚁群算法，进行了较为深入的研究。本文的主要研究成果包括：
1.将算法ACObs,τmin的收敛性定理进行推广，给出了蚁群系统(ACS)的收敛性证明。对ACS进行分析，总结出三种改进策略：候选集策略，局部搜索，信息素分布初始化策略。最后分析了三种策略对ACS收敛性的影响。
2.提出了三种求解TSP的改进算法：①基于受限制候选表的蚁群系统。该算法将一种新型的候选表RCL引入ACS中，可以随机调整RCL的大小，避免了多次实验设置候选表；②基于TSP几何结构的蚁群系统。该算法根据TSP的几何结构，定义了一种象限邻居候选表，并设计出一种对偶象限邻居的方法得到初始路径，用来设置初始阶段的信息素轨迹；③基于最小1-树动态候选集的蚁群系统。该算法将最小1-树的概念引入蚁群算法中，定义了α-动态候选集。在MATLAB环境下进行仿真实验，结果表明三种算法都优于基本ACS，在三种算法中，算法2好于其它算法。
3.提出了一种求解度限制最小生成树(DCMST)问题的改进算法。该算法针对DCMST的特点，设计了一种基于度的禁忌表，并提出了度信息的概念来改进转移概率，保证了所得解的可行性，然后使用变异思想局部优化生成树。实验结果表明，这些改进不仅提高解的质量，而且避免了早熟收敛。最后还将改进的算法进行适当推广，给出了求解多旅行商问题(MTSP)的具体步骤。