基于模拟退火思想的最优最差蚁群算法求解的TSP问题.pdf

收稿日期：基金项目：年安徽省省级质量工程项目（）；年 度 铜 陵 职 业 技 术 学 院 科 学 研 究 项 目（）作者简介：李眩（），男，湖南湘潭人，安徽省铜陵职业技术学院经贸系讲师，硕士，主要从事系统工程、人工智能方面的研究 ：山西师范大学学报（自然科学版）第 卷第 期 年 月 文章编号：（）基于模拟退火思想的最优最差蚁群算法求解的 问题李 眩，童百利，方婷婷安徽省铜陵职业技术学院经贸系，安徽 铜陵 摘要：蚁群算法是受蚂蚁寻找最短觅食路径行为启发的智能仿生优化算法 在分析基本蚁群算法的基础上，针对基本蚁群算法易于陷入停滞的缺陷，结合模拟退火思想和最优最差策略对基本蚁群算法作出改进，并将混合改进的蚁群算法与基本蚁群算法解决旅行商问题的实验结果进行对比分析，最终验证了混合改进蚁群算法的有效性和合理性，同时应用实例也表明混合改进蚁群算法在解决复杂优化问题上比基本蚁群算法具有优势关键词：蚁群算法；信息素；模拟退火；问题；最优最差中图分类号：文献标识码：引言旅行商问题（，）是组合优化中最典型的问题之一 以 问题为基础可以衍生出车辆导航路径规划、导弹无人机航迹规划等多约束非线性的复杂优化问题，因此它的求解对许多实际问题具有十分重要的理论和现实意义 运用传统方法如穷举法、动态规划等都面临同样的难题，随着问题的规模变大，算法复杂度将呈现指数级增长导致产生“组合爆炸”的问题，不能有效迅速地求解 考虑到求解 问题的实际情况，更多的是采用群体智能算法求取问题的最优解 在这些群智能算法中，蚁群算法具有鲁棒性强、求解组合优化问题效率高的特点，故被广泛应用于解决 等优化问题 蚁群算法是受蚂蚁觅食行为启发而提出的启发式智能优化算法，近年来将其应用于交通、通信、电力等领域，解决了许多组合优化问题，例如旅行箱、网络路由、工厂作业调度等问题，在解决组合优化问题上有较为理想的表现 但基本蚁群算法存在着收敛速度慢，易陷于停滞等不足 为了克服基本蚁群算法存在的缺陷，本文运用最优最差策略和模拟退火思想混合改进蚁群算法，削弱最差解，增强最优解，根据蚂蚁构建的路径质量对不同路径进行信息素差异化更新，同时随着进化过程对最差解进行自适应惩罚处理，有效兼顾了算法对解的多样性和引导性的要求，来获得较好的全局求解能力和算法效率 问题描述 问题是已知包含 个城市的集合 ，和任意城市之间的距离 （，），（）（）槡，即欧式距离，其中（，）代表城市的坐标 随机选择一个城市作为起点城市，确定一条遍历各个城市当且仅当一次的最终回到起点城市的最短闭合路径 ，其图论描述为：给定赋权完全图 （，），为所有城市构成的顶点集，为各顶点相互连接组成的边集，已知各顶点的连接距离 ，确定一条最小权重的 回路 该问题用数学简单描述为：（，）（，）其中，为选定的出发城市，（，）为待遍历的城市 蚁群算法基本思想受蚁群觅食寻找最短路径行为的启发，意大利学者 等人提出了模仿蚁群觅食行为的蚁群算法（简称 算法）蚂蚁个体行为很简单，它们之间通过信息素来相互通讯和进行信息的传递，共同协作完成复杂任务，能在没有任何先行提示的情况下找到巢穴到食物的最短路径，并能跟随环境变化搜索新的路径 蚁群算法的出现为解决复杂困难的系统优化问题提供了新的求解方法，其应用从最初的 问题扩展到了网络路由、车辆调度、路径规划等应用领域 算法求解 问题可以简要阐述如下：设将 只蚂蚁随机放置在 个城市上，集合 为所有城市的节点集合；用 （，）表示城市 和城市 之间的距离；（）为 时刻时路径（，）上的信息素值，初始时刻，各个城市间连接路径上的信息素浓度相同，设 （），（）为能见度函数，反映 时刻蚂蚁由城市 转移到城市 的期望程度，通常取 蚂蚁 根据城市间路径上的信息素计算移动概率来决定其下一个访问城市，设 （）表示 时刻蚂蚁 从城市 转移到城市 的概率，其计算公式为：（）（）（）（）（），为蚂蚁 待访问城市的集合，开始时，中有 个元素，包括了除蚂蚁 出发城市的其他所有城市 为了让蚂蚁遍历所有城市结点，为其建立一个禁忌表 ，存放了已经访问过的城市，禁止在以后再次访问这些城市 为信息素重要程度因子，其值越大表示信息素的浓度在转移中起到的作用就越大；为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率转移到距离短的城市 从转移概率计算公式来看，哪条路径的信息素浓度大，到哪个城市距离短，蚂蚁往该方向的转移概率就大在算法运行时，大量蚂蚁在许多城市节点构成的网络中行走并在行走过程中留下信息素，以此来调整蚂蚁的路径选择 在路径长度越短耗时越小的路径上蚂蚁将留下越多的信息素，最终在长度最短的路径上形成清晰的蚁路 但蚂蚁在路径上铺放信息素的同时，路径上的信息素也会逐渐挥发消失，这种机制可以使蚂蚁逐渐忘记过去，不受以往经验的过分约束 信息素和真实情况下一样存在挥发的情形，设信息素的挥发系数为 ，这样设定范围和信息素的挥发机制可以防止路径上的信息素无限量累积，减少路径寻找陷入局部最优的可能 完成一次循环，各路径上的信息素浓度进行实时更新 其更新策略如下：（）（）（）（）其中，（）（）为原有信息素的残存值，表示蚂蚁 在城市 和城市 之间路径上铺放的信息素量，路径越短，信息素铺放的量就越多；表示本次循环中蚁群在城市 和城市 之间路径上累计铺放的信息素增量和 针对蚂蚁释放的信息素浓度问题，在本文采用蚁周模型，其计算公式如下：第 期李眩，等：基于模拟退火思想的最优最差蚁群算法求解的 问题 ，蚂蚁 经过城市 和城市 之间的路径，蚂蚁 不经过城市 和城市 之间的路径其中，表示蚂蚁循环一次所释放的信息素总量，为蚂蚁 经过路径的总长度 该模型中利用蚂蚁经过路径的整体信息（经过路径的总长度）来计算释放的信息素浓度 蚁周模型的信息素更新体现了经过的整体路径越短，蚂蚁释放的信息素量就越大 在路径变迁中，那些耗时少、长度短的路径在路径变迁中体现出了较强的优势，从而能够引导更多蚂蚁在该路径上形成清晰的蚁路 从蚂蚁寻找最优路径的原理看出，信息素起到关键作用，可以进一步对信息素更新的方式进行改进，使其更有效地引导蚂蚁搜索行为向最优路径移动 对不同路径的信息素根据路径长短进行更新的同时，可以削减最差路径的信息素，增强最优路径的信息素，使得最优路径和最差路径的信息素差异进一步扩大，能增强对蚂蚁的搜索行为的指导性，使其更快收敛于最优解 混合改进蚁群算法求解 问题的基本思路基本蚁群算法在解决小规模的优化组合问题时取得的效果比较令人满意，但是随着问题规模的扩大，算法复杂度将呈现指数级增长，蚁群算法很难在较短时间内找到问题的最优解，而且存在收敛速度慢，易陷入停滞的不足 针对基本蚁群算法的不足，在此引入模拟退火思想和最优最差策略混合改进蚁群算法，提高算法的自适应能力 基于模拟退火思想的动态自适应惩罚因子蚁群当前找到的最差解不利于引导算法向最优方向进化，但在算法初期又要考虑到对解的多样性要求防止不成熟收敛，不能完全抛弃当前最差解；而在算法后期接近全局收敛时，群体当前最差解对蚁群搜索帮助不大，算法应当在最优解附近展开精细搜索，提高算法效率 当前最差解信息素量进行额外削弱时，在算法初期要考虑算法对解多样性的要求，这个削减量不宜太大，而在后期接近全局收敛时，应对最差解施加严厉惩罚，引导算法更快向全局最优解进化 所以要适时适度地动态自适应调整这个额外的削弱量，既兼顾了蚂蚁种群的多样性要求，又能适当降低最差解对蚁群搜索的干扰 因此在每次对解的信息素更新时，引入动态自适应的惩罚因子对当前最差解给予适当惩罚在此参考模拟退火思想来设计惩罚因子，其思路如下：假设时刻 的温度用 （）来表示，则快速模拟退火算法的降温方式为：（）（）利用模拟退火算法的快速降温方式来构造最差解的信息素惩罚因子 ，当蚁群算法迭代到第 代时的惩罚因子 为：（）其中 为初始系数，经过程序多次运行实验，取 算法效率较高，为迭代次数 在算法进化初期，并不能将当前最差解所处区域完全排除在搜索范围之外，故 较小对较差解的惩罚较小，使局部最优解和最差解的信息素差异保持在较小的范围，利于保持可行解的多样性，以扩大算法的探索区域，避免算法早熟 在算法后期接近全局收敛，即 较大时，对最差解处以严厉惩罚大幅削减其信息素含量，更能有效引导蚂蚁个体向最优解方向聚集，降低蚁群搜索的随机性，促进算法更快收敛 对蚁群算法增加基于模拟退火思想且随进化过程动态自适应调节的惩罚因子，能有效增强算法的全局搜索能力和效率 基于最优最差策略的差异化信息素更新策略从蚂蚁搜寻最优解的原理可看出，信息素起到了很大的引导作用 为增强最优解区域对蚂蚁的吸引力和削弱最差解区域对蚂蚁的吸引力，提高算法效率，对蚁群算法进行有目的的信息素强制性差异化更新蚁群算法在进化过程中，总是趋向于信息素浓度最大的路径方向移动，如果任何一次循环只要所利用的信息接近平均地分布在各个方向上，可能导致各个方向上信息素量存在的差异不大，那么每次循环所释放的信息素就有可能对以后蚁群的决策产生误导 信息量最强的当前最优路径并不一定是最终的全局最优路径，所以在算法前期不能将蚁群找到的众多潜在可行解一并而论地进行削弱排除在最终解之外，要尽可能保持可行解的多样性，又要增强对蚂蚁搜索行为的引导性，在此对算法引入最优最差信息素差异处理策略 这种差异化强制更新策略可以较好的兼顾解的多样性，同时又能很好的引导蚁群向最优方向搜索，有山西师范大学学报（自然科学版）年效防止算法不成熟收敛 因此，蚁群所找到的当前最优解因为其在众多解中突出的优异性，其信息素通过一定的方法进行额外增强，强制加大其对蚂蚁个体更具吸引力；而当前最差解则进行适当削弱，并且削弱量是自适应动态变化的，而普通解的信息素含量则按上述正常方式更新 这种跟随迭代次数的信息化差异更新策略使得最优路径上的信息素与最差路径上的信息素差异不会瞬间拉大，而是使蚂蚁的搜索逐渐集中到最优解的领域内，又最大限度地不会错失潜在的可行解如果第 只蚂蚁为最优蚂蚁，找到的解为群体当前最优解，解的信息素按下式更新：（）（）（）（）（）（）为群体所有蚂蚁找到解的适应度值之和，（）为第 只蚂蚁所找到的路径对应的信息素浓度值，（）（）为原有信息素的残存值，（）为给予该优质解额外的信息素增量如果第 只蚂蚁非最优亦非最差蚂蚁，所找到解的信息素仍按（）式更新如果是最差蚂蚁，找到的解为群体当前最优解，解的信息素按（）式更新：（）（）（）()（）（）其中，为当前循环次数，()为依据模拟退火思想构建的惩罚因子，()（）为该解的动态自适应削减量 问题求解仿真分析为了证明基于模拟退火思想和最优最差策略改进蚁群算法的有效性和合理性以及改进蚁群算法相对于基本蚁群算法应用于求解现实中比较复杂优化问题的优越性，在此以 问题的求解为例，采集了 个城市的位置坐标，将城市坐标数据输入到 文件中，在 里通过调用 数据文件，即可获取城市坐标数据（如表 所示）：表 城市坐标 城市序号坐标（，）城市序号坐标（，）城市序号坐标（，）城市序号坐标（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）为了比较分析基本蚁群算法，本文的改进算法与改进算法的求解性能，在内存为 ，（）的 机上进行实验，测试平台为 两种算法都选取同样参数，排除参数对算法求解结果带来的影响 蚂蚁数量 ，信息素重要程度因子 ，启发函数重要程度因子 ，信息素挥发因子 ，启发函数定义为距离的倒数，信息素总量 为 ，最大迭代次数为 图 是基于模拟退火思想的最优最差蚁群算法的 求解结果第 期李眩，等：基于模拟退火思想的最优最差蚁群算法求解的 问题图 基于模拟退火思想的最优最差蚁群算法的求解结果 图 普通蚁群算法的求解结果 通过上述的求解结果来看，基于模拟退火思想和最优最差策略改进蚁群算法求解 问题时，耗时 ，运行时间稍长于普通蚁群算法，求得的最短路径长度为 ，算法求解精度较普通蚁群算法显著提高，求解精度优于普通蚁群算法 从侧面也证明模拟退火思想和最优最差策略用于改进蚁群算法是合理可行的 结束语本文提出了基于模拟退火思想的最优最差蚁群算法，根据解的质量对信息素进行差异化更新，同时在进化过程中适时调整惩罚因子值，改进了算法的求解质量，出色的解决较为复杂的 问题 基于退火思想的最优最差蚁群算法亦可求解比其更复杂多约束的导弹、无人机航迹规划、物流 问题等复杂优化问题，为求解这些问题提供较为理想高效的解决思路和方法参考文献：肖根福，刘欢，张祥明，等 基于混合粒子群算法的农情监测无人机路径规划 井冈山大学学报（自然科学版），（）：覃远年，梁仲华 蚁群算法研究与应用的新进展 计算机工程与科学，（）：程亚南，王晓峰，刘淞佐，等 一种求解旅行商问题的信息传播算法 郑州大学学报（理学版）：（）：冷煌 蚁群优化算法的若干研究 吉林：吉林大学，赵又群，闫茜，葛召浩，等 基于改进蚁群算法的汽车避障路径规划 重庆理工大学学报（自然科学版），（）：王鹏飞 群智能优化算法及在流水车间调度问题中的应用研究 吉林：吉林大学，山西师范大学学报（自然科学版）年 段海滨 蚁群算法原理及其应用 科学出版社（北京），李士勇，等 蚁群算法及其应用（第一版）哈尔滨：哈尔滨工业大学出版社，王晓婷，钱谦 基于搜索集中度和动态信息素更新的蚁群算法 电子测量技术，（）：张松灿，普杰信，司彦娜，等 蚁群算法在移动机器人路径规划中的应用综述 计算机工程与应用，（）：闫天泽，邱晓燕，刘延博，等 基于引入模拟退火思想的改进粒子群算法的电动汽车充电站最优规划 电测与仪表，（）：胡平志，李泽滔 基于改进蚁群算法的四足机器人步态规划 计算机工程与科学，（）：，（，）：，：；檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵殝殝殝殝 本 刊 编 辑 部 重 要 声 明山西师范大学学报编辑部现出版有 山西师大学报（社会科学版）山西师范大学学报（自然科学版）体育研究与教育 三个有国内外正式刊号的期刊 近来我们发现在互联网上有人假冒我编辑部和编辑名义在网上组约稿件，并收取版面费 为此，我编辑部郑重声明：我部所属三个期刊自创刊以来，一直按照国家有关政策法规进行出版，从未授权任何单位和个人进行征稿事宜，也未委托任何机构、中介进行组稿，请作者谨防受骗，如有意投稿请直接投至编辑部电子邮箱：山西师大学报（社会科学版）：山西师范大学学报（自然科学版）：体育研究与教育：山西师范大学学报编辑部第 期李眩，等：基于模拟退火思想的最优最差蚁群算法求解的 问题