蚁群算法组合优化旅行商问题度限制最小生成树

来源：互联网   发布日期：2011-09-07 14:50:37   浏览：8441次  

摘要:组合优化是优化领域中的一个重要分支，具有非常强的实际应用背景从蚂蚁群体寻找最短路径的行为受到启发，意大利学者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的具体步骤标题:蚁群算法组合优化旅行商问题度限制最小生成树专业:应用数学学位:硕士单位:西安电子科技大学@关键词:蚁群算法　组合优化　旅行商问题　度限制最小生成树　论文时间:2006分类:O224 TP301.6 导师:刘三阳 语种:中文文摘URL:

赞助本站