求解TSP问题的改进遗传算法

旅行商问题(TSP)是遗传算法得以成功应用的典型问题.文章对遗传算法加以改进,提出了新的选择策略和交叉算子,并且引入了兄弟竞争的策略来加快收敛速度和全局搜索能力.把该算法应用在不同类型的TSP问题的求解上,表现出了比传统遗传算法更好的收敛性和计算效率.说明改进算法是有效的.     

一种改进的遗传算法及其在TSP中的实现

TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种方法.文章针对TSP问题,提出了一种改进的遗传算法.在遗传算法中引入进化算法的思想,在此基础上提出顶端培育策略和分阶段策略,以求在保证群体多样性的同时加快收敛速度.在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法.这表明,该算法具有良好的可行性和实用性.     

旅行商问题(TSP)的伪并行遗传算法

旅行商问题(TSP)是典型的NP完全组合优化问题．本文基于遗传算法求解TSP问题时的独特性,提出一种采用无性繁殖的改进伪并行遗传算法,避免了交叉算子对良好基因模式的破坏;初始种群通过贪婪算法得到并进行预处理,提高算法的收敛速度;伪并行遗传算法中子群体之间的信息交换采用孤岛模型．这些改进措施对降低算法的复杂程度、提高算法的收敛速度和全局搜索能力有重要意义．仿真研究结果表明,该算法的寻优效率较高,有效地克服了标准遗传算法的早熟收敛问题．     

一种基于改进遗传算法的TSP问题求解方法

通过改进经典遗传算法的交叉算子和变异算子,提出了一种改进遗传算法。介绍了该算法的基本步骤及特点,并对TSP问题进行了仿真实验。实验结果表明改进算法有效地提高了算法的收敛速度与寻优质量,在解决TSP问题时表现出良好特性,与经典遗传算法相比具有明显优势。     

基于遗传算法的避障TSP问题算法设计

主要探讨复杂环境下避障TSP问题的遗传算法的求解方法.针对TSP问题和避障TSP问题的不同,在染色体的编码方式、有效范围、基因选取、遗传算子等方面对传统遗传算法进行改进,同时引入了代价矩阵和基因库以提高算法的收敛速度.     

一种新的模糊自适应模拟退火遗传算法

针对遗传算法收敛速度慢、容易"早熟"等缺点,结合模糊推理、模拟退火算法和自适应机制,提出一种改进的遗传算法--模糊自适应模拟退火遗传算法(FASAGA),并分析了该算法的性能和特点,实验研究表明,该算法比标准的遗传算法(SGA)具有更快的收敛速度和寻优效果.     

融入遗传算法的混合蚁群算法

为了提高基本蚁群算法的收敛性能和全局求解能力,对基本蚁群算法进行了改进,提出了一类融入遗传算法的混合蚁群算法.在每代进化中保留最优解和次优解的公共解集后引入遗传操中的交叉算子和变异算子进行运算.对优秀解公共解集的保留加快了算法收敛速度,引入交叉和变异扩大了解的搜索空间,提高了解的全局性.通过对TSP问题的仿真运算表明,融入遗传算法的蚁群算法在收敛速度和解的全局性上都有较大的改善.     

求解TSP问题的一种改进的遗传算法

TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种理想方法。文章针对解决TSP问题,提出使用改进的遗传算法,即用浓度控制选择策略以保证群体的多样性,用贪婪交叉算子和启发式倒位变异算子来提高算法的收敛速度,较好地解决了群体的多样性和收敛速度的矛盾。算法的分析和测试表明,该文算法的改进是有效的。     

具有自识别能力的遗传算法求解旅行商问题

为解决基本遗传算法求解旅行商(TSP)问题收敛速度慢、种群过早成熟和局部搜索能力差的问题,提出了一种具有自识别能力的遗传算法。算法的主要改进手段是,通过双向贪婪算法来构建初始种群,以提高寻找到最优解的速度;建立个体之间相似度的概念,用自识别交叉算子进行交叉操作,避免种群过早成熟。实验结果表明,与基本遗传算法相比,该算法很好地保持了群体的多样性,并具有较好的收敛速度。仿真结果验证了算法的良好性能。     

应用改进的遗传算法求解TSP问题

旅行商问题,也称货郎担问题,属于完全NP问题,而遗传算法在解决组合排列问题方面占有很重要的地位.针对TSP问题,提出了一种改进的遗传算法.利用交换启发交叉算子和可变交叉概率实现局部搜索,加快算法的收敛速度,利用变换变异算子和可变变异概率维持群体的多样性防止算法早熟收敛.Java仿真实验结果表明,改进后的算法明显优于传统的遗传算法,说明该算法具有良好的有效性和可行性.     

求解TSP问题的自适应邻域搜索法及其扩展

TSP问题是测试组合优化领域算法性能的经典平台。提出了一种求解TSP问题的自适应邻域搜索算法,该算法通过为每个城市设定邻域来降低TSP问题的复杂度,并结合满意度和活跃度来构建一种自适应邻域搜索算子,使得其在局部优化的速度和收敛性方面取得了良好的效果。最后在该算法中融入遗传算法思想,将局部优化的高效性和遗传算法的鲁棒性有机结合起来构建成一种综合性能更好的混合优化算法。对eil75、CHN144和TSPLIB中的部分实例的仿真结果表明该算法在寻优度、收敛速度和稳定性等方面都优于目前一些比较常用的算法。     

旅行商问题(TSP)的一种改进遗传算法

传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子，这些算子实施起来很麻烦。针对TSP问题的求解，提出了一种新的改进遗传算法：单亲进化遗传算法(PEGA)，PEGA是利用父体所提供的有效边的信息，使用保留最小边的方法进行个体的进化。与传统的遗传算法相比，PEGA算法弥补了它们的不足之处，简化了遗传算法。给出了PEGA算法的数值算例，仿真实验表明了该算法对于对称的TSP和非对称的TSP问题，都具有收敛速度快的特点，证明了该算法的有效性。     

改进遗传模拟退火算法在TSP优化中的应用

针对旅行商问题(TSP)优化中,遗传算法(GA)容易陷入局部最优、模拟退火算法(SA)收敛速度慢的问题,提出一种基于改进遗传模拟退火算法(IGSAA)的TSP优化算法.首先根据优化目标建立数学模型;然后对遗传算法部分中的适应度函数、交叉变异算子进行改进,使算法能够更加有效地避免陷入局部最优;最后根据旧种群和新种群每个对应个体的进化程度提出一种改进自适应的Metropolis准则,使模拟退火算法部分的染色体跳变更具有自适应性,利于算法寻优.对不同TSP实例的实验结果表明,与其他路径优化算法优化结果相比,所提出的IGSAA算法能够对不同TSP实例优化得到更优的旅行路径.     

Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP

This paper first introduces the fundamental principles of immune algorithm (IA), greedy algorithm (GA) and delete-cross operator (DO). Based on these basic algorithms, a hybrid immune algorithm (HIA) is constructed to solve the traveling salesman problem (TSP). HIA employs GA to initialize the routes of TSP and utilizes DO to delete routes of crossover. With dynamic mutation operator (DMO) adopted to improve searching precision, this proposed algorithm can increase the likelihood of global optimum after the hybridization. Experimental results demonstrate that the HIA algorithm is able to yield a better solution than that of other algorithms, which also takes less computation time.     

面向组合优化问题的一种全新遗传算法

提出了一种全新的遗传算法，并结合组合优化领域的典型难题——TSP问题，设计了编码、交叉及变异等遗传算子，克服了传统遗传算法的编码及遗传操作未能够充分反映及利用道传信息的缺陷，较大程度上降低了传统遗传搜索中存在的盲目性，搜索速度得到明显提高。最后将本遗传算法应用于20个城市的TSP问题求解，计算结果证明了该遗传算法的收敛质量满足要求，收敛速度明显优于许多现有的算法。     

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

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

演化算法求解TSP问题的最新进展

TSP是一个著名的NP-hard问题.对近期出现的一些新的求解TSP问题的演化算法进行了比较全面的综述.其中有一类算法属于郭涛算法及其相应的改进算法,能够得到比传统演化算法更好的解,还有一类采用了实数编码的染色体表示方式,对求解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.     

求解TSP的交配算子设计策略

旅行商问题(TSP)是一类典型的NP完全问题,遗传算法(GA)是求解这类问题的常用方法之一.由于该问题的解是一种特殊的序列,一些典型的GA交配方法在求解该问题时的性能并不理想.通过多次对比两种常用的GA交配方法与3种专门为TSP作优化的交配方法,总结了一种对旅行商问题的交配算子的设计策略,即注重对双亲的边继承以及加入适当的贪心控制策略.通过对Gr17、Oliver30、Eil51、Eil76和Krob100等测试数据进行实验,证明了在该策略的指导下改进的两种交配算子具有更好的表现.