用蚂蚁算法和模拟退火算法解大规模TSP问题的研究

TSP问题是一个NP完全问题。随着问题规模的增大,其解空间呈指数增长,无法在多项式时间内完成问题的求解。近几十年来,人们提出了许多基于生物理论的解决该问题的 新方法。本文应用蚂蚁算法、模拟退火算法对TSP问题进行求解。在求解过程中对各算法中参数的作用和设置方法作了一些分析,使用不同参数进行多次实验,验证参数设置原则;对不同规模的TSP问题进行实验,比较两个算法的性能,分析造成其性能差异的原因,并提出了改进建议。     

旅行商问题(TSP)算法比较

将求解TSP问题的算法分为两大类:仿生算法和非仿生算法.通过实验比较两类算法在解决TSP问题时的优劣.实验结果表明,仿生算法是解决TSP问题的有效方法,在问题规模较大时,能够在允许的时间和误差内求得问题的解;而非仿生算法或者求解问题的规模很小,或者无法满足误差要求,因此都无法有效求解TSP问题.基于仿生算法在解决大规模组合优化问题时的有效性,论文提出了将仿生算法应用于云计算这一当今IT界热门话题的猜想.     

基于禁忌表的定位算法求解TSP问题

本文提出了一种基于禁忌表的定位算法求解TSP问题的快速、高效近似算法。这种算法结合了禁忌搜索算法中禁忌表及大规模构造算法和定位改进算法求解规模较大的TSP问题。计算机实例仿真证明,算法在求解质量和求解速度两方面高于著名的启发式算法的解。该算法针对TSP问题提出,是非常有效的。     

一种并行ACS-2-opt算法处理TSP问题的方法

针对基本ACS算法模型求解TSP问题的缺陷,对ACS算法添加2-opt邻域搜索策略,增强算法对TSP问题解的构造能力,提高算法对TSP问题的求解精度。同时,根据ACS算法易于并行化的特点,使用并行化ACS算法与算法参数优化混合方案,提高ACS算法求解TSP问题的速度。最终实现了对中等规模TSP问题具有较好求解性能的并行ACS-2-opt算法。实验结果表明,2-opt策略对于提升ACS算法的求解精度具有明显的效果;采用不同参数设定信息素启发因子时,求解时间具有较大差异;在采用节点距离倒数作为期望启发值时,ACS算法模型呈现退化性;在并行条件下,ACS-2-opt算法处理TSP问题时具有良好的并行性能。     

仿生蚊子追踪算法

旅行商问题(Traveling Salesman Problem,TSP)是NP完全问题中最为著名的问题,它易于陈述而难于求解,至今尚未找到准确有效的求解大规模TSP问题的方法.文中提出了能求出TSP有效近似最优解的新的蚊子追踪(Mosquito Host-Seeking,MHS)算法,证明了蚊子的目标追踪行为和MHS数学模型的一致性、蚊子追踪算法的收敛性,并通过理论证明确定了MHS算法中各参数的选择范围.蚊子追踪算法是一个全新的仿生算法.文中以TSP问题为载体,详细提出了蚊子追踪算法的动机、生物学模型、数学模型、算法、理论基础(数学证明)及大量实验结果.从理论和实验两方面证明了蚊子追踪算法能够求出TSP问题理论上的优化解.     

求解旅行商问题的几种智能算法

旅行商问题（TSP）是一个典型的组合优化问题,易于描述却难于求解。对于大规模TSP问题,目前仍未有非常有效的方法,如何快速有效的求解TSP问题有着重要的理论价值和实际意义。文章介绍了什么是TSP,论述了目前求解旅行商问题较为有效的六种智能算法（遗传算法、蚁群算法、Hopfield神经网络算法、模拟退火算法、人工免疫算法、混合优化算法）,并简单阐述了其优缺点,给出了未来针对TSP问题的研究重点。     

基于改进遗传算法的大规模TSP问题求解方案

TSP问题不仅描述旅行商周游城市的问题,也是许多工程领域中复杂问题的抽象形式,找到一种有效的TSP问题求解方案具有十分重要的意义。针对大规模TSP问题中最小回路代价的求解问题,提出一种基于遗传算法的大规模TSP问题的求解方案,采用分而治之的思想,并对传统遗传算法的初始化和遗传算子进行改进,提高了算法性能。多个数据集上的实验结果证明了提出的算法能够优化收敛结果,一定程度上解决过早收敛的问题。     

蚁群与粒子群混合算法求解TSP问题

旅行商问题（TSP）是最古老而且研究最广泛的组合优化问题。针对TSP问题,提出一种蚁群与粒子群混合算法（HAPA）。HAPA首先将蚁群划分成多个蚂蚁子群,然后把蚂蚁子群的参数作为粒子,通过粒子群算法来优化蚂蚁子群的参数,并在蚂蚁子群中引入了信息素交换操作。实验结果表明,HAPA在求解TSP问题中比传统算法和同类算法更具优越性。     

文化基因算法求解TSP问题的研究

TSP是组合优化问题中著名的NP-hard问题。针对粒子群算法求解离散的TSP问题收敛速度慢,求解精度低,易于陷入局部最优和模拟退火算法的性能与参数初始值有关及参数敏感等不足,提出了将改进的粒子群算法作为全局搜索策略,改进的模拟退火算法作为局部搜索策略的文化基因算法。介绍了两种算法的协同方法,定义了局部搜索邻域的确定以及在新种群产生中引入自组织随机移民策略。仿真结果表明,改进算法在求解TSP问题中具有很快的收敛速度,且能搜索到最优解。     

蚂蚁算法中参数的设置及其影响分析

蚂蚁算法作为一类启发式算法,在离散型组合优化问题中表现突出.文章通过求解TSP(Traveling Salesman Problem)问题,分析蚂蚁算法中信息素启发因子α、期望启发因子β、信息素挥发因子ρ蚂蚁数量M、总信息量Q这几个参数对算法求解性能的影响.根据实验数据,得出了一些能够得到算法较好解的参数值或者范围,给出了蚂蚁算法各参数的经验取值,同时对参数设置提出了初步的改进设想.     

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

TSP问题是一个经典的NP难度的组合优化问题，遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛，给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。     

一种改进的求解TSP问题的演化算法

演化算法是解决组合优化问题的高效搜索算法．该文在现有求解TSP问题的演化算法的基础上,通过引入映射算子、优化算子以及增加一些控制策略,提出了一种高效的演化搜索算法．实验表明,该算法是有效的,通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明,其中实例CHN144得到的最短路径为30353．860997,优于吴斌等运用分段算法得到的最短路径30354．3,亦优于朱文兴等人的结果,实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同,实例pr136得到的最短路径值为96770．924122,优于TSPLIB中提供的最短路径96772,对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径,该算法不仅很容易收敛到问题的最优解,而且求解速度极快．     

对一类带聚类特征TSP问题的并行遗传算法求解

提出了一种带聚类处理的并行遗传算法,该算法首先对大规模TSP问题进行聚类处理,将其分解成一些小规模TSP问题,然后分别对每个小规模TSP问题利用遗传算法并行求解,最后将所有小规模TSP问题的解按一定规则合并成大规模TSP问题的解。对大规模TSP问题的模拟实验表明该算法极大地提高了遗传算法的收敛速度。     

用随机神经网络优化求解改进算法的研究

随机神经网络是一种仿照实际的生物神经网络的生理机制而定义的网络，其网络结构及应用具有自身的特点。在详细讨论了动态随机神经网络求解典型NP优化问题TSP的算法的同时，特别提出了一种有效改进算法，使得参数在简单选取的情况下保证能量函数的下降，在组合优化问题上具有普遍意义，并且在10城市TSP对改进算法进行验证，指出RNN是解决TSP问题的有效途径。     

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

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

Discrete cuckoo search algorithm for the travelling salesman problem

In this paper, we present an improved and discrete version of the Cuckoo Search (CS) algorithm to solve the famous traveling salesman problem (TSP), an NP-hard combinatorial optimisation problem. CS is a metaheuristic search algorithm which was recently developed by Xin-She Yang and Suash Deb in 2009, inspired by the breeding behaviour of cuckoos. This new algorithm has proved to be very effective in solving continuous optimisation problems. We now extend and improve CS by reconstructing its population and introducing a new category of cuckoos so that it can solve combinatorial problems as well as continuous problems. The performance of the proposed discrete cuckoo search (DCS) is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that DCS is superior to some other metaheuristics.     

A hybrid heuristic for the traveling salesman problem

The combination of genetic and local search heuristics has been shown to be an effective approach to solving the traveling salesman problem (TSP). This paper describes a new hybrid algorithm that exploits a compact genetic algorithm in order to generate high-quality tours, which are then refined by means of the Lin-Kernighan (LK) local search. The local optima found by the LK local search are in turn exploited by the evolutionary part of the algorithm in order to improve the quality of its simulated population. The results of several experiments conducted on different TSP instances with up to 13,509 cities show the efficacy of the symbiosis between the two heuristics     

Runtime Analysis of an Ant Colony Optimization Algorithm for TSP Instances

Ant colony optimization (ACO) is a relatively new random heuristic approach for solving optimization problems. The main application of the ACO algorithm lies in the field of combinatorial optimization, and the traveling salesman problem (TSP) is the first benchmark problem to which the ACO algorithm has been applied. However, relatively few results on the runtime analysis of the ACO on the TSP are available. This paper presents the first rigorous analysis of a simple ACO algorithm called (1 + 1) MMAA (Max-Min ant algorithm) on the TSP. The expected runtime bounds for (1 + 1) MMAA on two TSP instances of complete and non-complete graphs are obtained. The influence of the parameters controlling the relative importance of pheromone trail versus visibility is also analyzed, and their choice is shown to have an impact on the expected runtime.     

一种简单有效的求解TSP的混合差分进化算法

设计了基于标准差分进化算法(differential evolution,DE)与遗传算法(genetic algorithm,GA)的混合差分进化算法(hybrid DE,HDE),同时用典型的测试函数对HDE进行性能测试。针对旅行商问题(traveling salesman problem,TSP)的求解难题,给出了采用位置—次序转换策略和HDE的有效求解方法,并测试了Oliver 30个城市的TSP。仿真结果表明,与DE和GA相比,HDE的优势在收敛率、平均最优解以及耗时上都很明显,证明了HDE在解决TSP问题上的有效性和稳定性。