A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem

This paper presents a new variant of Ant Colony Optimization (ACO) for the Traveling Salesman Problem (TSP). ACO has been successfully used in many combinatorial optimization problems. However, ACO has a problem in reaching the global optimal solutions for TSPs, and the algorithmic performance of ACO tends to deteriorate significantly as the problem size increases. In the proposed modification, adaptive tour construction and pheromone updating strategies are embedded into the conventional Ant System (AS), to achieve better balance between intensification and diversification in the search process. The performance of the proposed algorithm is tested on randomly generated data and well-known existing data. The computational results indicate the proposed modification is effective and efficient for the TSP and competitive with Ant Colony System (ACS), Max-Min Ant System (MMAS), and Artificial Bee Colony (ABC) Meta-Heuristic.     

一种改进的蚁群算法在TSP问题中的应用研究

蚁群算法是近几年发展起来的一种新型的拟生态启发式算法,它已经被成功地应用在旅行商(TSP)问题上.由于基本蚁群算法存在过早陷入局部最优解和收敛性较差等缺点,文中对基本蚁群算法在基于蚁群系统的基础上进行了改进,在信息素的更新和解的搜索过程中更多地关注了局部最优解的信息,以使算法尽可能地跳出局部最优,并且改进后的算法对一些关键参数更容易控制.多次实验表明改进的蚁群算法在解决TSP问题上与基本蚁群算法相比有较好的寻优能力和收敛能力.这种算法可以应用在其它组合优化问题上,有一定的工程应用价值.     

改进的求解TSP问题文化蚁群优化方法

在文化算法基础上提出了一种改进的用于求解TSP问题的蚁群优化算法。改进算法采用新的双层进化机制对文化算法的种群空间与信念空间进行了重新设计,用最大最小蚁群系统（MMAS）构建种群空间,在信念空间中对当前最优解进行改进的3-OPT交叉变换操作,由于采用了这种双层进化机制,种群空间获得了更高的进化效率。通过仿真实验结果表明,改进算法比传统的蚁群算法（ACO）、文化蚁群算法（CACS）效果更好,收敛速度更快,精确度更高。     

增强型的蚁群优化算法

旅行商问题是一个NP-Hard组合优化问题。根据蚁群优化算法和旅行商问题的特点,论文提出了对蚁群中具有优质解的蚂蚁个体所走路径上的信息素强度进行增强的方法,并同其他的优化算法进行了比较,仿真结果表明,对具有全局和局部最优解的个体所走路径上的信息素强度进行增强的蚁群优化算法比标准的蚁群优化算法和其他优化算法在执行效率和稳定性上要高。     

求解旅行商问题的多尺度量子自由粒子优化算法

针对目前元启发式算法在求解组合优化问题中的旅行商问题(TSP)时求解缓慢的问题,受量子理论中波函数的启发提出一种多尺度自适应的量子自由粒子优化算法。首先,在可行域中随机初始化表示城市序列的粒子,作为初始的搜索中心;然后,以每个粒子为中心进行当前尺度下的均匀分布函数的采样,并交换采样位置上的城市编号产生新解;最后,根据新解相较上一次迭代中最优解的优劣进行搜索尺度的自适应调整,并在不同的尺度下进行迭代搜索直到满足算法结束条件。将该算法和混合粒子群优化(HPSO)算法、模拟退火(SA)算法、遗传算法(GA)和蚁群优化算法应用在TSP上进行性能测试,实验结果表明自由粒子模型算法适合求解组合优化问题,在TSP数据集上相比目前较优算法在求解速度上平均提升50%以上。     

Exchange strategies for multiple Ant Colony System

In this paper we apply the concept of parallel processing to enhance the performance of the Ant Colony System algorithm. New exchange strategies based on a weighting scheme are introduced under three different types of interactions. A search assessment technique based on a team consensus methodology is developed to study the influence of these strategies on the search behavior. This technique demonstrates the influence of these strategies in terms of search diversity. The performance of the Multiple Ant Colony System algorithm, applied to the Vehicle Routing Problem with Time Windows as well as the Traveling Salesman Problem, is investigated and evaluated with respect to solution quality and computational effort. The experimental studies demonstrate that the Multiple Ant Colony System outperforms the sequential Ant Colony System. The studies also indicate that the weighting scheme improves performance, particularly in strategies that share pheromone information among all colonies. A considerable improvement is also obtained by combining the Multiple Ant Colony System with a local search procedure.     

基于自适应转移概率的蚁群优化算法

为避免蚁群优化算法容易早熟的缺点,在转移概率公式中引入一个新的自适应因子。随着迭代次数的增加,该因子有利于蚂蚁探索有较弱信息素浓度的边而避免一些边上信息素的过度积累。该特点使蚂蚁在迭代后期仍能以较高概率搜索到更好的解从而避免早熟。仿真实验结果表明,该算法对解决旅行商问题具有更优的全局搜索能力。     

改进的智能蚁群算法在TSP问题中的应用

研究旅行商领域优化路径问题,解决目前蚁群算法易陷入局部最优、搜索时间长等问题.为加快算法的速度优化结果,提出了一种改进的求解TSP问题的智能蚁群优化算法.算法前期采用了一种最近节点选择策略对路径进行优化,提高了搜索效率,使之适应大规模问题求解;后期改进了基本蚁群算法中信息素、挥发因子的更新规则,通过改进使得每轮搜索后信息素的增量能更好地反映求解的质量,有效地避免陷入局部最优,加快了收敛.通过改进后的蚁群算法,对TSPLIB中部分问题的仿真结果表明,在避免陷入局部最优和缩短搜索时间方面都取得了很好的效果.证明采取的优化蚁群算法,是可行有效的.     

基于群智能算法的玻璃切割问题求解研究

通过对玻璃切割问题的研究,提出一种融合量子粒子群优化和蚁群优化的混合算法(QPSO-ACO算法)。该算法对QPSO及ACO的模型进行必要的修改,以实现对玻璃切割中的旅行商问题的较好求解。同时充分利用QPSO的快速性、全局收敛性和ACO的正反馈性及求精解效率高等特点,达到优势互补。实验结果表明,QPSO-ACO算法寻优能力较强,是解决玻璃切割问题的有效方法。     

结合B样条优化的UAV多区域路径规划融合算法

为解决无人机(UAV,Unmanned Aerial Vehicle)在多个目标区域之间快速找到最佳遍历路径的类旅行商问题(TSP,Travelling Salesman Problem),设计一种基于蚁群算法、A*算法以及三次B样条优化的融合规划算法;尽管蚁群算法相对其他优化算法在解决TSP问题上有较为良好的表现,但其规划路径处理时间长、生成路径转折多、路径质量和安全性较差;算法首先改进传统A*算法的节点扩展方式,快速生成两两目标区之间的局部路径,然后将蚁群算法和改进A*算法融合使用进行全局路径规划,最后结合改进三次B样条对路径进行平滑处理;基于栅格地图的仿真结果证明了该算法相比传统算法具有更好的高效性和稳定性。     

蚁群系统(ACS)及其收敛性证明

蚁群系统(ACS)是解决旅行商问题(TSP)的最好方法之一,它是在蚂蚁系统的基础上作了许多改进之后得到的一种优化算法。这些改进在一定程度上避免了过早停滞现象的发生,是一种较好的协作式搜索算法。通过与蚂蚁系统的比较,系统地介绍了蚁群系统(ACS)所作出的种种改进,并且在理论上证明了该算法的收敛性。     

TSP问题的算法与应用的研究

TSP问题是一个典型的组合优化问题.针对TSP问题的两种主要算法:遗传算法和蚁群算法,进行了分析和研究.并且提出了网络浏览器运行的实现方法,给出了系统实现的B/S三层架构.最后,运用本算法和实现的技术,作为应用实例实现了ERP物流配送路径决策支持系统的原型.     

基于Spark的蚁群优化算法

为应对大数据时代中组合优化问题的求解,基于云计算框架Spark,借助其基于内存、分布式的特定,提出一种并行蚁群优化算法。其思路是通过将蚂蚁构造为弹性分布式数据集,由此给出相应的一系列转换算子,实现了蚂蚁构造解过程的并行化。通过在旅行商问题(TSP)求解的仿真实验结果说明了所提出的并行算法的可行性;并在同等实验环境下对比基于MapReduce的蚁群优化算法,优化速度提升达10倍以上。     

求解旅行商问题的高效自适应混合蚂蚁算法

在目前求解TSP问题效果最好的混合算法——最大最小蚂蚁算法和3-opt局部搜索算法的基础上,提出了一种改进的混合蚂蚁算法。算法前期使用局部搜索的解初始化信息素矩阵,加快收敛速度,后期依Metropolis接受准则概率接受局部优化解,有效地避免陷入局部最优,自适应的信息素调节机制使算法更加灵活,而K近邻候选集则使之适应大规模问题求解,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性。     

求解旅行商问题的改进型量子蚁群算法

针对传统量子蚁群算法在求解TSP时容易陷入局部最优以及收敛速度较慢,提出了一种求解旅行商问题的改进型量子蚁群算法（IQACA）。该算法设计了一种新信息素挥发因子的自适应动态更新策略,对信息素进行动态更新;并采用一种新的量子旋转门对量子概率幅值的收敛趋势进行改变。通过三个基本函数极值优化仿真与传统量子蚁群算法进行对比,证明算法性能较优。基于TSPLIB的仿真实验与其他几种算法进行比较,结果表明,算法具有较快的收敛速度,提高了解的全局性,有效避免了算法陷入局部最优。     

Parallel Ant Colony Optimization on Graphics Processing Units

The purpose of this paper is to propose effective parallelization strategies for the Ant Colony Optimization (ACO) metaheuristic on Graphics Processing Units (GPUs). The Max–Min Ant System (MMAS) algorithm augmented with 3-opt local search is used as a framework for the implementation of the parallel ants and multiple ant colonies general parallelization approaches. The four resulting GPU algorithms are extensively evaluated and compared on both speedup and solution quality on a state-of-the-art Fermi GPU architecture. A rigorous effort is made to keep parallel algorithms true to the original MMAS applied to the Traveling Salesman Problem. We report speedups of up to 23.60 with solution quality similar to the original sequential implementation. With the intent of providing a parallelization framework for ACO on GPUs, a comparative experimental study highlights the performance impact of ACO parameters, GPU technical configuration, memory structures and parallelization granularity.     

一种新的求解TSP问题智能蚁群优化算法

提出了一种新的用于求解TSP问题的智能蚁群优化算法。新算法从TSP问题本身出发,提取出了该问题的一种本质特征,并赋予蚁群算法中的精英蚂蚁以识别该固有特征的能力,以提高精英蚂蚁的搜索质量,进而使得新算法整体的求解能力得以提高。文章中不仅阐述了新算法的原理,而且进行了仿真实验,实验结果表明新算法在求解时间和求解质量上都取得了很好的效果。     

基于多蚁群的并行ACO算法

通过改变蚁群优化(ACO)算法行为,提出一种新的ACO并行化策略——并行多蚁群ACO算法。针对蚁群算法存在停滞现象的缺点,改进选择策略,实现具有自适应并行机制的选择和搜索策略,以加强其全局搜索能力。并行处理采用数据并行的手段,能减少处理器间的通信时间并获得更好的解。以对称TSP测试集为对象进行比较实验,结果表明,该算法相对于串行算法及现有的并行算法具有一定的优势。     

基于视觉抓取的并联桁架机器人最优路径控制

针对元件的抓取路径规划问题,提出一种以最小化时间为目的,结合蚁群算法和禁忌搜索算法的混合优化算法。首先,将基于机器视觉抓取元件的问题确定为有约束的旅行商问题（TSP）;然后,分析了元件大小和抓取放置过程对于路径规划的综合影响,对路径选择概率和禁忌域进行了适应性改进;其次,一方面引入了2-opt局部优化以及信息素惩罚、奖励机制以改善蚂蚁的搜索能力,另一方面对信息挥发因子作适应性改进以提高蚂蚁的自适应能力;最后,针对基本算法和改进的混合优化算法,仿真实验和平台实验分别进行了性能指标和抓取时间的对比分析。实验结果表明,仿真环境下,与蚁群优化（ACO）算法和禁忌搜索（TS）算法相比,混合优化算法的平均迭代次数降低了约50%,且其他性能较为优越,平台测试的抓取用时测试结果也说明了混合优化算法较随机结果和基本算法的优越性,可以快速完成元件抓取任务。     

基于启发式变异的蚁群算法

提出一种基于启发式变异的蚁群算法,结合传统蚁群算法和遗传变异算法的优点,利用蚁群算法找到一条全局近优解,采用启发式变异进行路径优化,并将优化信息以信息素的方式传递给下一代,从而快速得到全局最优解。以旅行商问题为例进行仿真实验,结果表明该算法比其他同类算法具有更好的性能。