蚁群算法求解TSP综述

蚁群算法是一种群智能算法,可用于求解图模型最优化路径的计算问题.它于1992年由Dorigo M.提出,借鉴蚂蚁在蚁群与食物之间寻找最短路径.本文集中讨论了几种典型的求解旅行商问题的蚁群算法扩展,讨论其相应的优缺点,并对其学术与工业的应用领域与合理发展进行了总结与展望.     

基于改进蚁群算法的有时间窗车辆路径优化

针对物流配送中的有时间窗车辆路径问题（VRPTW）,提高优化性能,提出了一种改进的最大最小蚁群算法,并引入了局部搜索策略2-opt．在客户数目给定的情况下,本算法能够得到所求VRPTW的全局较优解,与基本蚁群算法和未改进的最大最小蚁群算法比较,具有更快的收敛速度和更高的收敛精度,并可扩展到一类相关的路径优化问题中．实验结果表明,本算法对于求解VRPTW效果很明显．     

基于改进蚁群算法的物流配送路径优化

建立了带约束条件的物流配送问题的数学模型,运用蚁群算法解决物流配送路径优化问题,将遗传算法的复制、交叉和变异等遗传算子引入蚁群算法,以提高算法的收敛速度和全局搜索能力;改进了信息素的更新方式,以提高蚁群算法的自适应性,使得算法在执行过程中能根据收敛和进展情况,相应地调整信息残留程度,从而提高收敛速度或全局搜索能力;引入了一种确定性搜索方法,加快启发式搜索的收敛速度.经过多次对比实验表明,使用改进的蚁群算法优化物流配送线路,可以有效而快速地求得问题的最优解或近似最优解     

基于改进蚁群算法的移动机器人全局路径规划

对已栅格化的机器人运动空间中的障碍物预处理,在蚁群算法原理的基础上,改进了伪随机比例规则,使蚂蚁的下一节点选择更加倾向于目标点,提高了蚂蚁的搜索效率。引入最优一最差蚂蚁思想来更新全局信息素轨迹的强度,增强搜索过程的指导性。为了防止早熟收敛现象的发生,采用最大一最小蚂蚁思想来限制信息素的强度。仿真研究表明：该算法具有高适用性和灵活性,对解决静态路径规划问题是可行的,有效的。     

一种基于无相交搜索策略的蚁群算法

针对蚁群算法容易过早收敛和停滞的现象,通过判断路径相交信息,并调整信息素的挥发系数ρ,动态地对迭代最优解进行优化改进,从而使算法局部优化能力更迅速,同时提高最优解搜索的多样性,有效地控制算法过早收敛的问题,增强了算法的寻优性能。通过使用TSPLIB中的范例,与蚂蚁系统算法进行仿真实验比较。结果表明,该算法改进效果明显。     

基于蚁群算法的自适应动态路由算法

针对传统的路由算法收敛速度慢且易产生路由振荡的问题，利用蚁群能够发现从巢穴到食物源之间较短路径的 特性，提出了一种自适应动态路由(ADR) 算法.ADR中的人工蚂蚁同时搜索网络，并以一种间接、异步的方式相互交换所 收集到的网络状态以及数据流量信息.网络每个节点的路由表用信息素表来代替，表中的信息素浓度以概率值的形式表示 ，利用再励学习机制，人工蚂蚁以一定的周期更新信息素表.算法具有自适应性、鲁棒性及本质上的并行性.仿真结果表 明，所提出的算法能有效提高网络吞吐量、降低平均时延.     

求解TSP问题的改进最大最小蚁群算法

针对基本蚁群算法搜索时间长,易产生停滞现象等缺点,提出一种求解旅行商问题的改进最大最小蚁群算法.通过对有优质解的蚂蚁个体所走路径的信息素τ的最大最小值进行固定及信息素的更新方式的改变,可以避免在算法运行过程中信息素轨迹的差异过大.仿真结果表明,该改进算法有更高的执行效率和更好的计算稳定性.     

高校多媒体教室开放式管理运行模式探析

高校多媒体教室传统的封闭式管理方式存在着使用程序复杂、缺乏灵活性,设备运行状态无法及时反馈,使用环境恶劣,缺乏统一管理标准,无法可持续建设和发展等弊端,应予改革。实施开放式管理运行模式,需要制度保障、硬件支撑、软件整合等三方面的条件支持。该模式具有系统融合、使用简单,设备运行可实时监控,全封闭设计、运行安全稳定,扩展性强等优势,是多媒体教室管理方式改革的方向。     

蚁群算法在最小极大流问题中的应用

针对最小极大流网络优化问题,采用一个已知定理将最小极大流问题化为线性优化问题的方法,并结合蚁群算法的网络性,进行算法设计研究,以解决最小极大流问题.数值实验表明,所提出的结合蚁群算法的新算法对该问题有较好的实用性.     

基于改进蚁群算法的移动机器人路径规划方法

针对蚁群算法收敛速度慢、效率低、容易陷入局部最优解的不足,本文提出一种自适应变化信息素总量的方式,使算法获得较快收敛速度.通过对启发函数的改进,增加蚁群搜索的目的性,降低陷入局部最优解的概率.仿真结果表明,改进的蚁群算法提高了搜索能力和收敛速度,验证了算法的有效性和优越性.     

求解TSP问题的快速蚁群算法

针对蚁群算法求解旅行商问题时存在收敛速度慢并容易陷入局部最优的问题,提出了一种改进的蚁群算法。改进算法采用信息素挥发因子自适应调整机制,调节算法收敛速度,保证算法的全局搜索能力。同时根据公共路径降低蚁群算法运算时间,诱导蚁群寻找更优解。实验结果表明,改进算法在迭代次数相对较少的情况下求得的平均解与已知最优解偏差为0.46%,最优解与已知最优解偏差为0.23%,在收敛速度及求解精度上均取到了较好的效果。     

成本优化问题的蚁群算法

为了确定施工项目工期 成本均衡曲线，从而为施工项目计划和控制决策提供有效依据，提出了施工项目工期成本优化问题的蚁群算法.该方法利用施工项目工期成本优化问题的组合优化问题本质，将其转化为旅行商问题，利用自适应权重方法将工期、成本两个目标综合成单目标，采用蚁群算法进行Pareto解的搜索.通过两个实例的计算结果表明，该方法可以有效地确定具有实用价值的Pareto解，且具有较高的全局寻优能力和搜索效率，对于具有大规模网络计划的工期成本优化问题的求解是十分适用的.     

Global optimal path planning for mobile robot based on improved Dijkstra algorithm and ant system algorithm

A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps： the first step is adopting the MAK-LINK graph theory to establish the free space model of the mobile robot, the second step is adopting the improved Dijkstra algorithm to find out a sub-optimal collision-free path, and the third step is using the ant system algorithm to adjust and optimize the location of the sub-optimal path so as to generate the global optimal path for the mobile robot. The computer simulation experiment was carried out and the results show that this method is correct and effective. The comparison of the results confirms that the proposed method is better than the hybrid genetic algorithm in the global optimal path planning.     

粒子群优化的多群蚂蚁算法

设计多蚁群算法的关键是群间的信息交换规则.利用粒子群优化中粒子移动的基本思想研究了蚁群间信息交换的新规则,定义了新的多蚁群优化算法.新算法的信息交换所占用的数据通信量要远低于现有的信息交换方法.将新算法用于求解带时间窗的车辆路由问题并和以前的最好的多蚁群算法做比较,计算结果表明:新算法的性能超过了已有的方法.采用群体智能中个体的移动思想来设计群间信息交换规则能改进多蚁群算法的求解性能.     

一种机场终端区飞机排序问题的蚁群算法研究

飞机排序问题（ASP）属于NP难问题，解决比较困难．本文首先将ASP表示成一个特殊的车间作业调度问题（JSP），以减少着陆飞机队列完成时间为优化目标，设计了求解ASP的蚁群算法．通过正交试验确定了ASP蚁群算法的最佳性能参数组合．通过比较FCFS调度方法和ASP蚁群算法对不同航班队列的排序结果验证了ASP蚁群算法求解问题的可行性和求解效果．结果表明，ASP蚁群算法优于FC舟调度方法，可以使着陆队列完成时间减少约14％．ASP蚁群算法的CPU时间较短，可以在合理的时间内求解出合适的飞机队列，为实时在线的自动化交通管制提供了支持．     

两轮差速机器人运动学分析和控制研究

为了解决机器人路径规划模块在为非完整轮式移动机器人规划路径时,若要实现规划轨迹平滑且完全满足机器人的运动学约束,则需要精确的机器人工作环境的地图信息,从而大幅度地增加了路径规划算法的计算量的问题,首先利用较为粗略的环境地图信息规划路径,再将机器人转弯部分的路径进行函数插值,使整个路径规划满足机器人运动学约束且计算量增加较少.现有的机器人轨迹描述方程不能满足对机器人转弯轨迹进行精确插值的需要,因此提出分别利用曲线拟合法和泰勒插值法来构建非完整轮式移动机器人转弯轨迹的时域非微分描述方程.实验结果显示,所述机器人轨迹非微分时域描述方程可以用于对机器人路径规划的插值,降低了算法的计算量.

     

基于改进蚁群算法的外卖配送路径规划研究

从外卖配送员角度出发提出一种改进蚁群算法(Improved Ant Colony Optimization, IACO),在此基础上进行外卖配送路径规划研究.首先通过蚁群算法(Ant Colony Optimization, ACO)求解得到初始规划路径,然后通过大规模邻域搜索算法(Large Neighborhood Search, LNS)优化初始规划路径,通过将ACO和LNS算法结合,提高求解质量.为了验证方法的有效性,对外卖配送过程进行仿真,并且选用不同订单数量场景进行对照分析.根据最优配送方案路线图和目标罚函数的最优值可以得出,IACO算法是有效的,且可以提高外卖配送员外卖配送的效率.IACO算法不但能够提升配送的智能化水平,还从外卖配送员的角度提出一种更为人性化的配送方法,支持网络互联外卖平台派送系统的可持续化发展.     

一种求解旅行商问题的迭代改进蚁群优化算法

传统的蚁群优化算法每次都从头开始构造新解,无条件地接收选择的解部件,该策略削弱了算法的局部求精能力。针对该不足,提出了一种求解旅行商问题的迭代改进蚁群优化算法。在构造解的过程中,蚂蚁始终记忆一个完整的解,并且只接受能够改进解的候选城市。使用解的部分重构策略来保持种群的多样性,以避免早熟收敛。仿真结果表明迭代改进蚁群优化算法能在更少的迭代次数内获得更好的解。