PASCP在大规模TSP中的应用

蚂蚁系统是由M．Dorigo等人首先提出的一种新型的模拟进化算法，初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力，但同时也存在收敛速度慢等缺点。该文提出了一种带聚类处理的并行蚂蚁系统，该算法首先将大规模TSP问题通过聚类处理分解成一些小规模，ISP问题，然后对每一个小规模TSP问题分别使用蚂蚁系统并行求解，最后将所有小规模TSP问题的解合并成TSP问题的解。对带聚类特征的大规模TSP问题的仿真实验表明该算法极大地提高了蚂蚁系统的收敛速度。     

具有多态特征和聚类处理的蚁群算法

现实蚁群中,蚁群的觅食是一种典型的聚类行为,文中针对一些带聚类特征的TSP,提出了新型的带聚类处理的多态蚁群算法。该算法思想是根据聚类特征对TSP中的城市进行处理．将待求问题分成许多小规模的子问题。对于每个子问题,融合多态蚁群算法,引入不同种类的蚁群。通过对每个子问题进行求解,得到类内最短距离。最后按文中给出的规则合并所有子问题的解得到最优解。算法实验测试结果表明,该算法能将局域搜索与全局搜索相结合,极大提高了算法的收敛速度和求解速度。     

基于混合并行遗传算法的文本聚类研究

针对传统K-Means聚类算法对初始聚类中心的选择敏感,易陷入局部最优解的问题,提出一种基于混合并行遗传算法的文本聚类方法。该方法首先将文档集合表示成向量空间模型,并在文档向量中随机选择初始聚类中心形成染色体,然后结合K-Means算法的高效性和并行遗传算法的全局优化能力,通过种群内的遗传、变异和种群间的并行进化、联姻,有效地避免了局部最优解的出现。实验表明该算法相对于K-Means算法、简单遗传算法等文本聚类方法具有更高的精确度和全局寻优能力。     

分层递进的改进聚类蚁群算法解决TSP问题*

随着旅行商问题(TSP)规模的增大,传统蚁群算法的运行时间会增大,算法的解精度也会降低,并且算法很容易陷入局部最优的情况。提出的分层递进算法的思想源于分工合作的产品线组装流程,首先利用改进的密度峰聚类算法确定拐点,从而选举出聚类中心,根据聚类中心确定包含的数据点;其次将初始的TSP问题分割成较小的簇,这些簇称为二类TSP问题;再经自适应信息素更新策略的蚁群算法运算,找出每个簇的最优解,进一步将簇与簇之间相近的节点构成的边断开;然后两簇之间断开的节点重组成全局最优解;最终通过局部优化策略对重组的优化解进一步优化,从而在保证算法解质量的前提下有效地缩短了运行时间。从TSPLIB中选取小规模、大规模基准案例,通过Matlab仿真验证了改进算法具有更好的鲁棒性,特别是在大规模基准案例中显著地减少了算法运行时间。     

一种改进并行遗传算法解决TSP

针对旅行商问题（Travelling Salesman Problem,TSP）的遗传算法的大规模操作,需要大量运算时间而且容易造成局部最优解,提出一种并行混合遗传算法。该方法基于MPI并行环境,利用种群中选择、交叉、变异操作的并行化,将种群中个体平均的分配到处理器中进行操作,有效地避免局部最优解的出现和减少算法的运行时间。实验证明该方法相对于简单遗传算法具有更强全局寻优能力以及耗费更少的操作时间。     

基于路径共同顺序的TSP遗传算法

遗传算法是一种解决TSP问题的有效算法。文章提出了一种基于路径共同顺序的新型遗传操作方法,即首先寻找父辈的共有路径信息,然后构建后代,该方法缩小了搜索优解的范围,加快了优化过程的收敛速度。在此基础上针对TSP实例,实现了基于共同顺序的优化方法来解决小规模TSP问题,以及更有效的基于共同顺序的循环优化方法来解决大规模TSP问题。实验结果验证了该方法的有效性。     

一种基于聚类技术的Hopfield网络求解TSP方法

Hopfiled神经网络方法已被广泛用于求解旅行商问题（TSP），但对于解中规模和大规模的TSP，存在效果不理想甚至难以求解的问题。为了较好地解决这个问题，该文提出一种K-Means聚类算法与Hopfield网络方法相结合求解TSP的新方法，先应用聚类算法对所给城市进行聚类以获得几组规模较小的城市，然后对每一组城市应用Hopfield网络方法进行求解，最后把求解后的每组城市连接起来。计算机仿真结果表明，该方法可以获得最优有效解，并且解的质量明显提高，对求解中大规模的TSP比较有效。     

基于并行遗传算法的K-means聚类研究

针对传统K-means聚类算法对初始聚类中心的选择敏感,以及聚类数K难以确定的问题,提出一种基于并行遗传算法的K-means聚类方法.该方法采用一种新型的可变长染色体编码方案,随机选择样本点作为初始聚类中心形成染色体,然后结合K-means算法的高效性和并行遗传算法的全局优化能力,通过种群内的遗传、变异和种群间的并行进化、联姻,有效地避免了局部最优解的出现,同时得到了优化的聚类数目和聚类结果.实验表明该方法是一种精确高效的聚类方法.     

基于聚类集成的蚁群算法求解大规模TSP问题

ACA（Ant Colony Algorithm）是一种可以有效求解组合优化的TSP（Travelling Salesman Problem）问题的方法。然而,当TSP问题的规模较大时,该算法的求解性能将会明显减弱。本文针对大规模TSP问题提出一种基于聚类集成的蚁群算法IAPACA（Improved AP Ant Colony Algorithm）的求解方法。利用AP（Affinity Propagation）聚类对大规模旅行商问题进行处理,将大规模旅行商问题分为若干子问题,并对每个子问题用蚁群算法进行寻优。然后用改进的集成方案对子问题进行组合,得到问题的结果。最后进行TSPLIB标准库测试算例的实验仿真,实验结果表明,基于聚类集成的蚁群算法具有更好的求解效果。     

基于Hadoop的改进型遗传聚类算法

针对经典K-means聚类算法存在易陷入局部最优解的缺点,提出并实现了一种基于Hadoop的改进型遗传聚类算法.该算法利用遗传算法具有全局性和并行性的特点去处理K-means聚类算法易陷入局部最优的缺点,在此基础上对遗传算法进行改进,然后将改进后的遗传算法与K-means算法相结合,为提高算法执行效率,将其基于Hadoop平台进行了实现.通过实验将该改进方法与经典聚类算法进行对比分析,实验结果表明该方法在聚类准确性和聚类效率上均有较大的提高.     

一种求解TSP问题的多种群并行遗传算法

遗传算法是一种基于自然群体遗传机制的有效搜索算法,由于它在搜索空间中同时考虑许多点.减少了收敛于局部极值的可能,也增加了处理的并行性.因此可以利用并行遗传算法研究典型的TSP问题的求解.提出一种有效的多种群并行算法求解旅行商(TSP)问题,应用多种群遗传并行进化的思想,并在种群之间进行遗传信息交流,以解决经典遗传的收敛到局部最优值问题.仿真实验结果表明,方法在解的精度上以及解的质量上优于经典的遗传算法.     

Implementation of an Effective Hybrid GA for Large-Scale Traveling Salesman Problems

This correspondence describes a hybrid genetic algorithm (GA) to find high-quality solutions for the traveling salesman problem (TSP). The proposed method is based on a parallel implementation of a multipopulation steady-state GA involving local search heuristics. It uses a variant of the maximal preservative crossover and the double-bridge move mutation. An effective implementation of the Lin-Kernighan heuristic (LK) is incorporated into the method to compensate for the GA's lack of local search ability. The method is validated by comparing it with the LK-Helsgaun method (LKH), which is one of the most effective methods for the TSP. Experimental results with benchmarks having up to 316 228 cities show that the proposed method works more effectively and efficiently than LKH when solving large-scale problems. Finally, the method is used together with the implementation of the iterated LK to find a new best tour (as of June 2, 2003) for a 1 904 711-city TSP challenge     

旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。     

旅行商问题的一种插入交叉算子

求解TSP问题是遗传算法应用的一个重要领域,其本质是TSP问题中巡回路径编码串的组合最优化问题。对于符号编码方式的遗传算法,通常需要设计特定的交叉算子以提高算法的运行效率和性能。该文针对自然数编码的方式,提出了一种较适合于大规模TSP问题求解的遗传交叉算子:插入交叉(InsertCrossover,简称IX)算子。该算子以优良的交叉策略,保证了算法的快速收敛和全局寻优。仿真实验结果证明,IX算子对于大规模TSP问题具有比较好的性能。     

一种基于GPU加速的细粒度并行蚁群算法

为改善蚁群算法对大规模旅行商问题的求解性能,提出一种基于图形处理器(GPU)加速的细粒度并行蚁群算法.将并行蚁群算法求解过程转化为统一计算设备架构的线程块并行执行过程,使得蚁群算法在GPU中加速执行.实验结果表明,该算法能提高全局搜索能力,增大细粒度并行蚁群算法的蚂蚁规模,从而提高了算法的运算速度.     

求解TSP 问题的模式学习并行蚁群算法

针对大规模旅行商问题(TSP)会遇到计算时间过长以及计算效率降低的问题，将并行计算和模式学习引入蚁群算法，通过各个节点机提取模式，在各节点问筛选和交流优良模式，以改变计算粒度，达到缩短计算时间、提高计算效率的目的．实验结果表明该算法取得了较好的效果。     

一种面向对象的多角色蚁群算法及其TSP 问题求解

蚁群算法的改进大多从算法本身入手或与其他算法相结合,未充分利用待解决问题所包含的信息,提升效果较为有限.对此,提出一种面向对象的多角色蚁群算法.该算法充分利用旅行商问题(TSP)对象的空间信息,采用k-均值聚类将城市划分为不同类别;同时,对蚁群进行角色划分,不同角色的蚁群针对城市类别关系执行各自不同的搜索策略,增强了蚁群的搜索能力,较大幅度地提高了求解质量.每进行一次迭代,仅各角色最优个体进行信息素更新,防止算法退化为随机的贪婪搜索.将精英策略与跳出局部最优相结合可避免算法的停滞.50个经典TSP实例仿真实验表明:所提出的算法可以在较少的迭代次数内获得或非常接近于问题的已知最优解;对于大规模TSP问题所得结果也远超所对比的算法.     

A novel two-stage hybrid swarm intelligence optimization algorithm and application

This paper presents a novel two-stage hybrid swarm intelligence optimization algorithm called GA–PSO–ACO algorithm that combines the evolution ideas of the genetic algorithms, particle swarm optimization and ant colony optimization based on the compensation for solving the traveling salesman problem. In the proposed hybrid algorithm, the whole process is divided into two stages. In the first stage, we make use of the randomicity, rapidity and wholeness of the genetic algorithms and particle swarm optimization to obtain a series of sub-optimal solutions (rough searching) to adjust the initial allocation of pheromone in the ACO. In the second stage, we make use of these advantages of the parallel, positive feedback and high accuracy of solution to implement solving of whole problem (detailed searching). To verify the effectiveness and efficiency of the proposed hybrid algorithm, various scale benchmark problems from TSPLIB are tested to demonstrate the potential of the proposed two-stage hybrid swarm intelligence optimization algorithm. The simulation examples demonstrate that the GA–PSO–ACO algorithm can greatly improve the computing efficiency for solving the TSP and outperforms the Tabu Search, genetic algorithms, particle swarm optimization, ant colony optimization, PS–ACO and other methods in solution quality. And the experimental results demonstrate that convergence is faster and better when the scale of TSP increases.