基于MapReduce的动态自适应蚁群算法设计与实现

针对基本蚁群算法( ACO)在处理中等规模旅行商问题( TSP)上消耗时间过长的问题,提出一种基于MapReduce的动态自适应蚁群算法( MDACO)。该算法在信息素更新策略方面动态地调整信息素挥发系数,使蚁群能够自适应地寻找较优的路径结果,而且采用MapReduce计算模型将蚁群算法中循环迭代部分并行化,最终将其部署在Hadoop云计算平台上运行。当TSP节点数为150及以上时,该算法比基本蚁群算法的运行时间平均减少43.2%,路径寻优结果也得到进一步改善。仿真结果表明,该算法在保证问题求解质量以及提高求解速度方面具有优越性。     

蚁群优化算法及其应用研究进展

综述了近年来蚁群算法及其在组合优化中的应用研究成果。首先简述了蚁群的觅食行为及蚂蚁的信息系统，其次介绍了人工蚁群算法的基本原理及其主要特点。然后概述了这种算法在组合优化问题中的多种应用，诸如旅行商问题(TSP)、二次分配问题(QAP)、任务调度问题(JSP)、车辆路线问题(VRP)、图着色问题(GCP)、有序排列问题(SOP)及网络由问题等。最后对蚁群算法仍需要解决的问题和未来的发展方向进行了探讨。     

基于分布均匀度的自适应蚁群算法

针对蚁群算法加速收敛和早熟停滞现象的矛盾,提出一种基于分布均匀度的自适应蚁群算法,以求在加速收敛和防止早熟、停滞现象之间取得很好的平衡.该算法根据优化过程中解的分布均匀度,自适应地调整路径选择概率的确定策略和信息量更新策略.以数种对称和不对称TSP(traveling salesman problem)问题为例所进行的计算结果表明,该方法比一般蚁群算法具有更好的收敛速度和稳定性,更适合于求解大规模的TSP问题.     

增强型的蚁群优化算法

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

蚁群算法优化策略及其仿真研究

蚁群算法广泛应用于求解组合优化问题,但基本蚁群算法与其他模拟进化算法存在进化速度慢并易于陷入局部最小等缺陷。论文应用蚁群算法求解最短路径问题,从信息量的更新方式、局部搜索策略及参数选择等方面提出相应的改进策略。通过TSP问题的仿真表明,改进算法能够加快收敛速度,节省搜索时间,而且能够克服停滞行为的过早出现。     

基于MapReduce与蚁群优化的航路规划算法

航路规划是提高无人机生存能力的有效途径,可使其安全、快速到达目的地。为在云计算环境中分布式并行地求解航路规划问题,应用云计算技术提出基于MapReduce和多目标蚁群算法的航路规划算法( RPMA)。设计多目标蚁群算法,并采用多种优化策略对传统算法进行改进。 RPMA能预先规划出多条航迹,可根据不同的飞行任务选择不同的航路,并在飞行过程中根据不同需要临时确定合适的飞行航路。仿真实验结果表明, RPMA求解航路问题是可行、有效的,具有较好的收敛性和扩展性,以及对大规模数据的处理能力。     

求解TSP问题的一种改进蚁群优化算法

针对基本蚁群算法求解TSP问题时容易出现早熟和停滞现象的缺陷,提出了一种改进的蚁群算法。算法的基本思想是,将信息素分为局部和全局二种不同的信息素,在搜索过程中。对局部和全局信息素采用不同的更新策略和动态的路径选择概率,使得在搜索的中后期能更有效地发现全局最优解。以TSPLIB的数据进行实验的结果表明．在中大型问题上有着更好的发现最优解的能力。     

自适应蚁群算法

蚁群算法是由鄣大利得Ｍ．Ｄｏｒｉｇｏ等人首先提出的一种新型的模拟进化算法,初步的研究已经表明该算法具有许多优良的性质,为求解算杂的组合优化问题提供了一种新思路,此方法已经引起了众多学者的研究兴趣,但同时也存在着一些缺点,如需要较长的计算时间,容易出现停滞现象等,目前国内对此研究尚少,为此,本文对景中算法的研究现状作一综述,希望能够对相关研究起到一定的启发作用。     

基于MapReduce的混合蚁群算法研究

传统的蚁群算法在收敛速度上较慢且容易导致局部最优解,本文提出一种基于双模式的混合蚁群算法,即在算法的每次迭代中有比例地选择其中一种模式来获得蚂蚁的最优路径,可以实现在相对较少的时间内寻找出最优路径,且避免陷入局部最优解。由于蚁群算法天然具有并行化的特性,本文将混合蚁群算法与MapReduce结合,大大缩短了算法的执行时间。实验结果表明,基于MapReduce的混合蚁群算法可以实现在相对较少的时间内寻找出较优的路径。     

化学反应蚁群优化算法

针对化学反应优化对反馈信息利用不足导致后期求解效率低的问题,提出化学反应蚁群优化算法.该算法利用化学反应优化生成较优解,通过信息素转换策略将较优解转换为蚁群算法的初始信息素,最后由蚁群算法累积更新信息素得到最优解.以TSP为例进行仿真,结果表明,与化学反应优化、蚁群算法、模拟退火算法相比,所提算法具有更高的寻优能力、收敛效率和计算效率.     

基于多样信息素的蚁群算法

根据蚁群算法信息素更新的特性,提出了求解旅行商问题的多样信息素的蚁群算法。把蚁群的三种不同的信息素更新方式混合在一起,既利用了局部信息,又考虑了整体信息,将局部搜索和全局搜索相结合,使收敛性得到提高。针对旅行商问题的仿真实验结果,表明了该混合算法的有效性。     

蚁群优化算法的收敛性分析

有关蚁群优化算法收敛性分析的研究还很少．不利于进一步改进其算法．为此,较详细地分析了用蚁群优化算法求解TSP问题的收敛性．证明了当0〈q0〈1时．算法能够收敛到最优解．分析了封闭路径性质、启发函数、信息素和q0对收敛性的影响．据此给出了提高算法收敛速度的几点结论．     

小窗口蚁群算法

在蚁群算法的基础上，提出了小窗口蚁群算法。通过对旅行商问题解集的分析，找到其最优解的特点，通过限定蚂蚁每次只向距离最近的几个城市移动，大大缩小其搜索范围，减少对算法中主要参数的依赖，提高其搜索精度并减少搜索时间。实验结果表明该算法有较好的效果。     

基于邻域搜索的改进最大最小蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优的问题,提出一个改进的混合最大最小蚁群算法,并应用于求解旅行商问题.上述算法设计了一种新的信息素更新模型,单个蚂蚁每走一步就进行信息素局部更新,在所有的蚂蚁搜索一周后,最优路径蚂蚁进行全局信息素更新.提出一种新的邻域搜索模型,将邻域大小设置为原来的一半,提高了计算的效率.在每个蚂蚁的一个周期循环后,使用邻域搜索算法优化最优解的路径长度.仿真结果表明,改进算法具有较高的求解精度和收敛速度.     

基于粒子群优化的蚁群算法在TSP中的应用

结合粒子群算法的问题,提出用混合蚁群算法来求解著名的旅行商问题.问题的核心是应用粒子群算法对蚁群算法的控制参数:启发式因子、信息素挥发系数、随机性选择阈值进行优化,以及运用蚁群系统算法寻找最短路径.新算法对于蚂蚁算法中的参数调整大大减低,减少了大量盲目的实验,力求在开发最优解和探究搜索空间上找到平衡点.对旅行商问题的仿真实验表明,新算法的优化质量和效率都优于传统蚁群算法和遗传算法,接近理论最佳值.新算法也可推广用于其他NP问题的求解.     

基于混合行为的自适应蚁群算法

针对传统蚁群算法求解能力的不足,提出了一种基于混合行为的自适应蚁群算法(HBACA).通过引入具有多行为的混合蚂蚁来扩大解搜索空间,避免早熟和停滞现象;另外在每次迭代过程中具有不同行为的蚂蚁数目可以视具体情况而动态地进行调整,以便在加速收敛和防止早熟、停滞现象之间取得一个较好的平衡.实验表明,相比ACS、MMAS算法,改进算法求解TSP问题的性能得到了加强.     

蚁群算法在K-TSP问题中的应用

针对K-TSP(K—person Traveling Salesman Problem)问题,该文提出了一种利用蚁群算法求解该问题的新思路。该算法采用k只蚂蚁共同构造问题的一个解,并通过多组(每组k只)蚂蚁相互协作最终达到搜索最优解的目的。实验结果显示,该算法行之有效,是一种求解K-TSP问题的有效算法。     

一种基于蚁群优化算法的旅行Agent问题求解

旅行Agent问题解决移动Agent在不同主机间移动时如何规划最优的迁移路线，是复杂的组合优化问题。蚁群算法作为一种新的生物进化算法，具有并行、正反馈和启发式搜索等特点。本文在蚁群算法的基础上，通过修改它的信息素轨迹更新规则，并引入自适应的信息素挥发系数，来求解旅行Agent问题。实验结果表明了本文算法的可行性。     

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

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