自适应蚁群算法在求解TSP问题中的应用

围绕蚁群优化算法的理论及应用,针对蚁群算法在TSP规划中求解能力不足的难题,运用了一种基于自适应的蚂蚁算法,并对TSP规划进行了设计。为了提高路径规划的效率,将自适应与传统的蚂蚁算法相结合形成了自适应蚁群算法。仿真实验结果表明,改进后算法能够在较短时间内找到全局最优路径,相对于基本的蚁群算法在收敛速度、搜索质量和局部寻优方面都有了明显的提高。     

一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用

采用蚁群算法求解复杂环境下移动机器人路径规划问题时,会出现运算时间过长、求解精度不高等问题,对此,定义一种新的动态搜索诱导算子以改进蚁群算法性能.重点设计了动态搜索模型,即:在进化初期设定较大阈值以增加种群的多样性;而伴随进化过程,利用衰减模型动态调整为较小阈值以加快收敛速度.TSP测试实验结果表明,该改进蚁群算法不仅能加快收敛速度,而且有效提高了优化解的质量.复杂环境中机器人路径规划问题的求解验证了所提出算法的实际应用效果.     

蚁群算法与遗传算法对TSP的一种融合

蚁群算法是通过信息素的累积和更新收敛于最优路径上,求解速度慢,而遗传算法具有快速随机的局部搜索能力。为此本文将遗传算法和蚁群算法相融合,给出一种改进的算法并用于TSP问题的求解。在问题求解中,用蚁群算法迭代每只蚂蚁走过的路径序列作为遗传算法的初始种群,克服随机选择的盲目性,从而提高算法的性能。模拟结果显示该算法是有效的和可行的。     

一种改进的智能蚁群优化算法

为了提高基本蚁群算法（Ant Colony Algorithm）的全局求解能力,对基本蚁群算法进行了改进,提出了一种高效的智能蚁群优化算法。它修改了基本蚁群算法中信息素、挥发因子的更新规则,使得每轮搜索后信息素的增量能更好地反映解的质量,有效地避免陷入局部最优,以加快收敛;另外,采用了一种最近节点选择策略使之适应大规模问题求解,对路径进行优化,提高搜索效率。通过对TSP问题的仿真结果表明,改进后的蚁群算法在求解最优解和收敛性能方面都取得了很好的效果。     

并行设计任务调度的自适应蚁群算法

针对将蚁群算法应用于任务规划调度问题求解时存在的计算时间长、易出现停滞等缺陷,提出一种具有自适应功能的蚁群算法.通过设计一种路径选择机制来提高蚁群路径的多样性;以蚁群目标值作为路径信息素变化的依据,设计一个动态因子更新路径信息素;使用变异蚂蚁以一个动态比率替换策略更新蚁群.实例仿真结果表明,文中算法具有较强的全局寻优能力和较高的搜索效率,较好地解决了快速收敛与停滞现象之间的矛盾.     

改进蚁群算法求解TSP

针对蚁群算法存在易陷入局部寻优、收敛缓慢等缺陷,提出一种基于邻接矩阵的两层搜索决策来选择转移路径的方法对蚁群算法进行改进,求解TSP问题。通过实验及分析,验证了该算法具有较好性能。     

基于种群熵的改进自适应蚁群算法

针对标准蚁群算法(ACO)在求解旅行商问题(TSP)时出现的早熟收敛、易陷入局部极值点的缺点,提出了基于种群熵的改进自适应蚁群算法求解方法.通过种群熵来衡量算法是否陷入局部最优,直接交换部分边上的信息素以增加解的多样性.通过对解TSP的实验仿真表明,改进后的算法提高了搜索效率和全局收敛性能,该算法是可行和有效的.     

基于变异和启发式选择的蚁群优化算法

为了解决传统蚁群算法求解TSP问题的求解时间较长、易于局部收敛的问题,提出了一种基于变异和启发式选择的蚁群优化算法。利用较优路径中城市相互之间的邻接特点,避免了大范围搜索求解,使得能具有较好的初始解,将算法的时间复杂度大大降低;同时为了加快算法的收敛速度,对于路径的启发式选择进行重新定义;引入变异机制,充分利用2-交换法简洁高效的特点,既提高了变异效率,也改进了变异质量。实验结果证明,在一些经典TSP问题上新算法表现出很好的性能。     

基于蚁群优化算法的TSP问题研究

通过介绍蚁群觅食过程中基于信息素的最短路径的搜索策略,给出蚁群算法在TSP问题中的应用.针对基本蚁群算法求解速度缓慢、容易陷入局部最优等特点,提出了一种改进的蚁群算法,同时保持蚁群算法自己的收敛速度和路径的多样性.在TSP旅行商问题上的仿真验证表明它是可行性和有效性的.     

一种人工势场导向的蚁群路径规划算法

针对复杂环境下的机器人路径规划问题,提出一种势场法优化的蚁群路径规划算法。为提高算法收敛速度,将人工势场法的规划结果作为先验知识,对蚁群初始到达的栅格进行邻域信息素的初始化,并通过构建势场导向权改变蚂蚁概率转移函数,使其作用于蚂蚁路径搜索的始终,从而改善蚁群路径搜索的盲目性。仿真结果表明,新算法具有收敛速度快、规划路径短以及环境自适应的优点。     

基于拥挤度的改进蚁群算法

针对蚁群算法在求解旅行商问题时收敛时间长,且易陷入局部最优状态的缺陷,提出一种基于拥挤度的动态信息素蚁群优化策略。该算法引入静态拥挤度和动态拥挤度算子,主动提前预防停滞现象。将拥挤度与状态转移规则相结合,使蚁群状态实时跟随路径搜索情况而改变,提高蚁群自适应能力。针对蚁群路径搜索情况,加入邻域搜索优化规则,缩小搜索区域,结合2-opt局部优化策略,加快蚁群收敛速度。仿真结果表明,本算法既有较高的搜索效率又有较强的全局搜索能力。对比其他优化算法,无论是求解质量、稳定性还是收敛速度都能达到令人满意的效果。     

改进的重叠蚁群优化算法

针对蚁群优化算法在进行全局最优解搜索时容易陷入局部最优解和收敛速度缓慢等缺陷,提出了一种有效求解全局最优解搜索问题的重叠蚁群优化算法。该算法通过设置多个重叠的蚁群系统,并对每一个蚁群初始化不同的参数,之后在蚁群之间进行信息素的动态学习,增强了不同蚁群对最优解的开采能力,避免了算法出现早熟现象。仿真实验结果表明,重叠蚁群优化算法在避免陷入局部最优解方面具有良好的效果,是一种提高蚁群算法性能的有效的改进算法。     

带有狮王竞比参数的蚁群优化算法

由于蚁群算法采用随机选择策略,使得进化速度较慢,容易出现停滞现象,从而不能对解空间进一步进行搜索,不利于发现更好的解.针对以上问题,提出了一个带有狮王竞比参数的蚁群优化算法.该算法借鉴狮子种群生存竞争中狮王法则的作用,减少大量不必要的搜索,从而大大缩短了求解时间,同时又引用了最大—最小蚂蚁系统(MMAS)算法对信息素的限制,有效地控制了搜索停滞的问题.通过结合MMAS算法的仿真,结果表明:带有狮王竞比参数的改良算法,在求解同样TSP问题时,大大地缩短了优化时间,并且得到了更优的解.     

区域破坏重建的蚁群优化算法

传统蚁群算法在解决旅行商问题（TSP）有较大的优势，但也存在一些不足，如收敛速度慢、易陷入局部最优等。针对这些问题，提出区域破坏重建的蚁群优化算法（RDRACO）。RDRACO应用区域破坏重建算法解决因信息素积累而陷入局部最优的问题，并将蚁群算法的信息素更新规则和全局更新策略进行了调整，使之与该算法匹配。另外在蚁群路径选择中加入2-Opt算子，加快收敛速度和提高收敛精度。实验采用TSPLIB中的20个经典TSP数据集对RDRACO进行仿真实验，仿真结果表明：RDRACO算法通过较少的迭代次数就可找出数据集较小TSP的已知最优路径，并在数据集较大TSP收敛精度上有显著的优化。RDRACO在提高收敛速度的同时具有较高的精度和较好的鲁棒性。     

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

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

A memetic ant colony optimization algorithm for the dynamic travelling salesman problem

Ant colony optimization (ACO) has been successfully applied for combinatorial optimization problems, e.g., the travelling salesman problem (TSP), under stationary environments. In this paper, we consider the dynamic TSP (DTSP), where cities are replaced by new ones during the execution of the algorithm. Under such environments, traditional ACO algorithms face a serious challenge: once they converge, they cannot adapt efficiently to environmental changes. To improve the performance of ACO on the DTSP, we investigate a hybridized ACO with local search (LS), called Memetic ACO (M-ACO) algorithm, which is based on the population-based ACO (P-ACO) framework and an adaptive inver-over operator, to solve the DTSP. Moreover, to address premature convergence, we introduce random immigrants to the population of M-ACO when identical ants are stored. The simulation experiments on a series of dynamic environments generated from a set of benchmark TSP instances show that LS is beneficial for ACO algorithms when applied on the DTSP, since it achieves better performance than other traditional ACO and P-ACO algorithms.     

基于信息素负反馈的超启发式蚁群优化算法

针对蚁群算法应用于自动导引小车路径规划收敛速度慢、极易陷入局部最优的缺点，提出一种基于信息素负反馈的超启发式蚁群优化（ACONhh）算法。该算法充分利用历史搜索信息和持续获得错误经验，较快引导蚁群探索最优路径；分层化选择可行节点，加快算法初期收敛速度；设置挥发因子呈类抛物线变化以及调整信息素更新机制，改善路径全局的随机搜索特性。通过严格的数学方式证明了ACONhh算法具有收敛性。仿真和实验结果表明，该算法的收敛速度以及全局搜索性能显著优于目前流行的ACO、ACOhh和ACOihh算法。     

High speed ant colony optimization CMOS chip

Ant colony optimization (ACO) is an optimization computation inspired by the study of the ant colonies’ behavior. This paper presents design and CMOS implementation of the ant colony optimization based algorithm for solving the TSP problem. In order to implement ant colony optimization algorithm in CMOS, we will present a new algorithm. This algorithm is based on the original ant colony optimization but it can be implemented in CMOS. Briefly, pheromone matrix is transformed on the chip area and ants move up-down through the pheromone matrix and they make their decisions. Finally ants select a global path. In previous researches only pheromone values is used, but select the next city in this paper is based on heuristics value and pheromone value. In definition of problem, we use heuristics value as a matrix. Previous researches could not be used for wide type of optimization problem but our chip gives heuristics value initially and we can change initial value of heuristics value according to the optimization problem so this capability increases the flexibility of ACO chip. Simple circuit is used in blocks of our chip to increase the speed of convergence of ACO chip. We use Linear Feedback Shift Register (LSFR) circuit for random number generator in ACO chip. ACO chip has capability of solving the big TSP problem. ACO chip is simulated by HSPICE software and simulation results show the good performance of final chip.     

Population declining ant colony optimization algorithm and its applications

Population declining ant colony optimization (PDACO) algorithm is proposed and applied to the traveling salesman problem (TSP) and multiuser detection in this paper. Ant colony optimization (ACO) algorithms have already successfully been used in combinatorial optimization, however, as the pheromone accumulates, we may not get a global optimum because it stops searching early. PDACO can enlarge searching range through increasing the initial population of the ant colony, and the population declines in successive iterations. So, the performance of PDACO is superior with the same computational complexity. PDACO is applied to TSP and multiuser detection. Via computer simulations it is shown that PDACO has better performance in solving these two problems than ACO algorithms.     

改进蚁群算法FENA2O解决TSP问题研究

为了解决传统蚁群算法解决TSP问题时收敛速度慢、易陷入局部最优的问题,提出了一种名为FENA2O的改进蚁群算法。通过寻找并更新精英蚂蚁行走路径来提高收敛速度,通过规定蚂蚁数量来降低陷入局部最优的可能,配合2-Opt算法进一步优化所得路径。实验结果表明,算法改进后的收敛速度得到了较大提高,并能够有效解决局部最优。