一种求解TSP问题的单亲遗传算法

1 前言 TSP问题可描述为:给定一个城市的集合,寻找一条从集合中的某个城市出发,访问每个城市一次且仅一次,最后回到出发点的最短路径。这已被证明是一个NP难解问题。求解TSP问题,遗传算法通常采用序号编码和非序号编码两种解表达方式。其中序号编码相对简单直接,其代表性的有“邻接表达”、“普通表达”和“路径表达”等几种编码方式,后者是最自然的表达方式。序号编码方式的杂交算子难于设计,杂交后解的合法性是需着重考虑的问题。虽然目前已提出了一些基于路径表达的杂交算子,如PMX、OX和CX,但普遍计算额外开销很大,而且杂交算子的使用对群体的多样性存在很大影响,容易使算法过早收敛。     

基于蚁群算法的聚类新算法

提出了一种基于蚁群算法的聚类新算法。按分类的样本数N和类别数p,设计N+1层城市,除第1层城市外,其余城市均有p个城市。蚂蚁每次从第1层城市开始到最后一层城市的移动,就完成对所有样本的分类。访问城市的选择受路径信息素和样品类信息素的共同作用,每次完成层间城市的访问,需要对路径信息素更新;完成一次循环,分别对路径信息素和样本类信息素更新。通过实例分析,该算法能够得到较为满意的结果。     

旅行商问题的近优解评价方法--浅析启发式算法的有效性

1引言 旅行商问题(Traveling Salesman Problem,TSP)的描述如下:给定N个城市,已知它们之间的距离矩阵,寻求一条经过所有城市一次且仅一次的最短Hamilton回路.TSP已被证明属于NP完全问题,由于启发式算法具有计算复杂性与算法所得近优解的"质量"折中性好的特点,它在TSP算法的研究中占有重要的地位[1],启发式算法的有效性表现在两方面:一是计算复杂性低,二是近优解"质量"高.启发式算法的上界收敛性,即准收敛性的研究是评价启发式算法的一个重要问题.本文以评价近优解为中心,通过总结、归纳已有方法,整理各种典型算法的评价结果,对现有方法的适用范围和评价结果的意义作了分析讨论,其结论对于改善现有算法以及评价新算法有一定的指导作用.启发式算法的准收敛性仍旧是一个正在研究中的问题.     

水流启发式算法求解Euclid TSP

1.思想来源旅行商问题(TSP)可以简单表述如下:给定一组N个城市和它们之间的两两距离,找出一个闭合的旅程,使得每个城市刚好经过一次且总的旅程距离最短。旅行商问题已经被证实是一个NP难解问题。虽然欧氏平面上的TSP有PTAS,但运算时间和精度呈指数函数关系,所以找一个快速的近似算法仍然具有很大的意义。近年来提出的逼近最优解的算法如遗传算法、模拟退火算法、神经网络算法本质上都是进行随机搜索,本文是用确定性的启发式算法求解TSP。     

遗传算法在旅行商问题中的实践与探究

TSP问题是组合优化领域的经典问题之一,旨在求出遍历若干个城市的最短路径。本文通过遗传算法GA的选择和变异算子的确定和、交叉算子的改进,并在TSP问题中的实践来探索这个经典的NP(Nondeterministic Polynomial)难题。     

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

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

多目标路径规划方法的研究

在环境中存在障碍物的情况下,为实现航行器完成任务时路径消耗最优,提出了一种对多个目标进行遍历的路径规划算法。该算法在初始计算时根据目标点间的估计距离构建TSP回路,并随着航行器的运行,动态地对TSP回路进行优化;同时,航行器根据TSP回路的顺序对目标进行访问,降低了初始计算量。通过仿真验证,该算法可以在实现规划目标的同时,明显地降低路径目标点的路径消耗。     

基于改进演化算法的最短路径问题研究

针对最短路径问题TSP(Traveling Salesman Problem)的求解时,传统算法收敛慢,且求得的路径并不是所有行程的最短路径。提出用智能演化算法来求解,并对算法的演化算子进行改进和对各参数进行优化设置。结合10个城市和30个城市的仿真实例,分别进行传统算法、演化算法以及改进的演化算法进行对比。计算机仿真结果表明:改进后的演化算法收敛速度快,收敛精度高,鲁棒性好,寻求的最短路径明显优于传统算法。     

基于梯森分割的城市物流配送路线优化选择

物流配送车辆路径优化问题是一个典型的NP难题,也是近年来物流研究中的一个热点。文章利用先分组再排路线的思想,把城市零售商品物流配送车辆路径优化问题分解成一个分派问题和一个类似旅行商问题(TravelingSalesm an Problem,TSP)。应用空间分析中的梯森分割(Thiessen Tessellation)理论解决分派问题,同时改进用于求解TSP问题的插队算法,将其应用于对车辆巡回路线寻优问题的求解,最后,对此算法进行了应用举例。     

基于GA的MTSP问题实现

多旅行商问题(Multiple Traveling Salesperson Problem,简称MTSP)是讨论m位旅行商如何访问n座城市,要求每个城市都被访问,且仅被访问一次,求得所有旅行商经过的路径和最小。本文通过对MTSP特点的分析,依据遗传算法的基本思想,对编码和遗传算子进行合理选取。通过仿真表明,该优化方法能够取得较优解。     

遗传算法和模拟退火算法求解TSP的性能分析

旅行商问题（Traveling Salesman Problem,TSP）是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目是呈指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义。目前求解TSP问题的主要方法有模拟退火算法（Simulated Annealing,SA）、遗传算法（Genetic Algorithm,GA）和神经网络算法等。GA是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应的全局优化概率搜索算法。SA算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。文中将提出遗传算法和模拟退火算法求解TSP问题,通过试验比较两者求解TSP问题的性能,结果表明GA的性能要优于SA的性能。     

仓储系统拣货路径规划问题的研究

本文针对仓储系统的拣货路径规划问题展开研究。以拣货路径长度和拣货时间为评价指标,分别采用蚁群算法、遗传算法、禁忌搜索算法、模拟退火算法进行对比研究。把仓库内拣货路径规划问题转化为转换为N=M+1的TSP问题。经MATLAB仿真研究,获得最短路径和适应度进化曲线。经实验测试发现了当拣货数量较多即N值偏大时,蚁群算法得到的路径距离相对于遗传算法、模拟退火算法和禁忌搜索算法更加优化,同时蚁群算法得到最优解的迭代次数更少,拣货时间更短。     

旅行商问题(TSP)的几种求解方法

旅行商问题（TSP）是组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题，其可能的路径数目与城市数目是呈指数型增长的，求解非常困难。而快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。该文首先介绍了什么是TSP，接着论述了六种目前针对TSP比较有效的解决方法（模拟退火算法、禁忌搜索算法、Hopfield神经网络优化算法、蚁群算法、遗传算法和混合优化策略）的基本思想，并且简单阐述了它们的求解过程，最后分别指出了各自的优缺点并对解决TSP的前景提出了展望。     

基于模糊C-均值聚类的TSP演化算法

提出了一种基于FCM聚类的TSP演化算法。该算法以聚类中心为新的结点组成一个简单的TSP问题,用演化算法寻求其最短路径。在最短路径中,对于每一聚类,可寻求其距前面的聚类和后面的聚类最近的两结点之间的最短距离,若其中的结点较多,则再次演化得到其最短路径,若结点较少,则可用Warshall算法可得到最短路径。通过三个阶段的演化可得到较好的结果。     

基于规模压缩的混合蚁群算法

为了提高蚁群算法处理大规模问题的性能，提出一种基于规模压缩的混合蚁群算法．根据TSP问题的最优解与次优解共享部分路径片断的原理，设计城市压缩算法，减少了TSP问题的城市处理量．在求解过程中，引入最优解的区域特征的概念，采用优化状态转移规则，压缩了解空间．仿真实验结果证明，采用所提出算法得到解的质量和收敛速度都有显著提高．     

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

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

基于遗传算法的TSP优化问题

TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对BP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。     

改进蚁群优化方法求解立体表面TSP问题

给出立体表面TSP问题的数学模型,提出一种改进的蚁群优化算法,用于解决立体表面TSP问题。该算法能快速找到最优路径或近似最优路径,得到的解质量较高且计算时间短。实验方法表明,改进后的蚁群算法在TSP的求解中,收敛速度和全局寻优能力均得到较大的提高。     

基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法

旅行商问题(TSP)是组合优化中最典型的NP完全问题之一,具有很强的工程背景和应用价值.文章在分析了标准SOM(Self-Organizing Map)算法在求解TSP问题的不足和在寻求总体最优解的潜力的基础上,引入泛化竞争和局部渗透这两个新的学习机制,提出了一种新的SOM算法---渗透的SOM(Infiltrative SOM,ISOM)算法.通过泛化竞争和局部渗透策略的协同作用:总体竞争和局部渗透并举、先倾向总体竞争后倾向局部渗透、在总体竞争基础上的局部渗透,实现了在总体路径寻优指导下的局部路径优化,从而使所得路径尽可能接近最优解.通过对TSPLIB中14组TSP实例的测试结果及与KNIES、SETSP、Budinich和ESOM等类SOM算法的比较,表明该算法既简单又能使解的质量得到很大提高,同时还保持了解的良好的稳健特性.     

C919机载数据实时处理系统设计

对于无人机在输电线路杆塔精细化巡视的路径规划问题,提出了对杆塔巡视路径和杆塔间避障路径的两阶段优化策略。针对利用传统旅行商问题(TSP)求解杆塔巡视路径,在多项式时间无法求得全局最优解问题,研究了基于双调欧几里得TSP求解杆塔最优巡视路径的优化数学模型,以及基于动态规划算法的求解方法。在此基础上,进一步基于人工势场法建立了避开巡视路径障碍最优路径的优化模型及其求解方法。仿真结果表明,利用双调欧几里得TSP确定的巡视路径具有偏转角小、最优路径求解时间短的特点,利用所提两阶段优化策略确定的巡视路径长度较短且能有效避开障碍,有利于实现无人机安全高效巡视杆塔的目标。