求解TSP的新量子蚁群算法

鉴于蚁群算法（ACA）在求解TSP时表现出的优越性,以及量子进化算法（QEA）在求解组合优化问题时表现出的高效性,将ACA与QEA的算法思想进行融合,提出一种新的求解TSP的量子蚁群算法。该算法对各路径上的信息素进行量子比特编码,设计了一种新的信息素表示方式,即量子信息素;采用量子旋转门及最优路径对信息素进行更新,加快算法收敛速度;为了避免搜索陷入局部最优,设计了一种量子交叉策略,以改善种群信息结构。仿真实验结果表明了该算法具有较快的收敛速度和全局寻优能力,性能明显优于ACS。     

一种改进的量子蚁群算法及其应用

将量子群进化算法（QEA）与蚁群系统（ACS）进行融合,提出一种新的量子蚁群算法（QACA）。该算法的核心是在蚁群系统（ACS）中引入量子算法中的量子的态矢量和量子旋转门来分别表示和更新信息素,从而在全局寻优能力和种群多样性方面比蚁群算法有所改进。结合旅行商问题（TSP）,对算法进行了测试,得到了与现有文献结果相同或更好的解,表明该算法具有较强的问题求解能力。     

混合量子差分进化算法及应用

量子进化算法基于量子旋转门更新量子比特状态影响了算法搜索性能．提出一种差分进化（DE）与和声搜索（Hs）相结合更新量子比特状态的混合量子差分进化算法（HQDE）．该方法采用实数量子角形式编码染色体,设计一种由差分进化计算更新量子位状态的量子差分进化算法（QDE）和一种由和声搜索更新量子位状态的量子和声搜索（QHS）,并相互机制融合,采用两种不同进化策略共同作用产生种群新量子个体以克服常规算法中早熟及收敛速度慢等缺陷;在此基础上,算法还引入量子非门算子对当前最劣个体以一定概率选中的量子比特位进行变异操作增强算法跳出局部最优解能力．理论分析证明该算法收敛于全局最优解．0／1背包问题及旅行商问题实例测试结果验证了该方法有效性．     

通过多种群协进化Memetic算法求解TSP

针对对称TSP提出了多种群协进化Memetic算法（MCMA）．该算法以Memetic算法为基础,采用3个子种群协同进化的方式,克服了Memetic算法由于缺乏种群多样性而产生早熟收敛的缺陷．MCMA中对3个子种群分别引入了2-exchange、3-exchange和PCV三种不同的邻域搜索结构,非常有效地保持了种群的多样性,并且能快速收敛．文中通过对若干TSPLIB中TSP实例的实验仿真来说明所提算法的性能,并且与SGA、SMA和GGA算法进行了比较．通过仿真实验,该算法能够给出相当满意的结果,从而说明了该算法的有效性．     

新颖的阻塞流水车间调度量子差分进化算法

针对阻塞流水车间调度问题(BFSP),提出了一种新颖的量子差分进化(NQDE)算法,用于最小化最大完工时间。该算法将量子进化算法(QEA)与差分进化(DE)相结合,设计一种新颖的量子旋转机制控制种群进化方向,增强种群多样性;采用高效的基于变邻域搜索的量子进化算法(QEA-VNS)协同进化策略增强算法的全局搜索能力,进一步提高解的质量。基于Taillard's benchmark实例仿真,结果表明,所提算法在最优解数量上明显高于目前较好的启发式算法--INEH,改进了110个实例中64个实例的当前最优解;在性能上也优于目前有效的元启发式算法--新型蛙跳算法(NMSFLA)和混合量子差分进化(HQDE),产生最优解的平均百分比偏差(ARPD)均下降约6%。NQDE算法适合大规模阻塞流水车间调度问题。     

用MC-QPSO算法求解并行流水车间调度问题

针对并行流水车间调度问题的特点,提出了一种基于多种群协同进化的改进量子粒子群算法（MC-QPSO）进行求解。首先将整个量子粒子种群分解为多个子种群,然后各个子种群独立地演化,并通过周期性共享搜索信息,以获得对自身信息的更新。最后,通过具体仿真实例进行了求解验证,结果表明,在求解并行流水车间调度问题时,基于多种群协同的量子粒子群算法,在收敛速度、寻优性能等方面,都要优于遗传算法。     

求解TSP的改进量子蚁群算法

将量子群进化算法(QEA)与蚁群系统(ACS)进行融合,提出一种新的量子蚁群算法(QACA).该算法的核心是在蚁群系统(ACS)中引入量子算法中的量子的态矢量和量子旋转门来分别表示和更新信息素.该算法在全局寻优能力和种群多样性方面比蚁群算法有所改进,并结合TSP,对算法进行了测试,得到了与现有文献结果相同或更好的解,表明该算法是求解TSP的一种有效的算法.     

求解旅行商问题的人工协同搜索算法

针对传统人工协同搜索（ACS）算法求解精度不高、收敛速度慢等问题,提出一种基于Sigmoid函数的反向人工协同搜索（SQACS）算法求解旅行商问题（TSP）。首先,利用Sigmoid函数构造比例因子,增强算法的全局搜索能力;其次,在变异阶段,加入差分进化（DE）算法的DE/rand/1变异策略,对当前种群进行二次变异,提高算法的计算精度和种群的多样性;最后,在算法后期的开发阶段,引入拟反向学习策略,进一步提高解的质量。对TSP测试库TSPLIB中的4个实例进行仿真实验,结果显示,SQACS算法在最短路径与花费时间上均优于麻雀搜索算法（SSA）、DE、阿基米德算法（AOA）等7种对比算法,并且具有良好的鲁棒性;与其他求解TSP的改进算法综合对比,SQACS算法也显示了良好的性能。实验结果表明,SQACS算法在求解小规模TSP时是有效的。     

基于量子免疫算法的车辆调度问题优化

为优化带时间窗的车辆调度计算问题,引入量子进化算法,提出了一种混合量子免疫进化算法。首先对传统量子旋转门进行改进,使个体在进化过程中向全局最优位置靠近,从而避免算法早熟并保持种群多样性。其次在迭代过程中,引入免疫算子,提取优秀基因片段作为疫苗,接种到种群中其他个体,避免算法性能的倒退。最后,针对Solomon标准实例库实例数据进行多算法编码仿真实验,结果表明,所提混合量子免疫进化算法不仅能够有效解决类似问题,而且能够显著加速收敛。     

改进的求解TSP问题文化蚁群优化方法

在文化算法基础上提出了一种改进的用于求解TSP问题的蚁群优化算法。改进算法采用新的双层进化机制对文化算法的种群空间与信念空间进行了重新设计,用最大最小蚁群系统（MMAS）构建种群空间,在信念空间中对当前最优解进行改进的3-OPT交叉变换操作,由于采用了这种双层进化机制,种群空间获得了更高的进化效率。通过仿真实验结果表明,改进算法比传统的蚁群算法（ACO）、文化蚁群算法（CACS）效果更好,收敛速度更快,精确度更高。     

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

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

Bi-direction quantum crossover-based clonal selection algorithm and its applications

In order to improve the performance of quantum interference crossover, a bi-direction quantum crossover is proposed based on the quantum jump theory. The proposed crossover is inspired by the principle of quantum mechanics. That is, when an electron drops from a higher energy level to a lower energy level, energy is released by the atom. Also, energy is absorbed when it moves from a lower energy level to a higher energy level. The bi-direction quantum crossover is combined with clonal selection algorithm (CSA) to further enhance the performance of CSA. The effectiveness of the method is tested on a class of traveling salesman problems (TSP) and engineering practical problems of holes machining path planning (HMPP). Experimental results show that the proposed algorithm achieves a good balance between exploration and exploitation, and outweighs other CSAs and heuristic algorithms in terms of convergence speed and robustness.     

Embedded local search approaches for routing optimization

This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.     

运输调度问题的蚁群算法研究

蚁群算法是一种用于求解复杂组合优化的较新的启发式算法.本文简述了蚁群算法的基本原理及算法模型,通过分析研究现状指出了蚁群算法在实际应用中的局限性,最后给出解决一般运输调度问题的蚁群算法,并分析了其今后的发展方向.     

Tsp-based scheduling in a batch-wise hybrid flow-shop

In the past few years, flexible production systems have allowed an extensive exploitation of new technologies, but have also led to new difficulties in production planning management science. The model presented in this paper extends the traditional HFS (hybrid flow-shop) scheduling problem to the case in which jobs are due to follow strict precedence constraints and batch assignment constraints and the parallel machines at a stage are served by a bottleneck machine. A variant of the well-known TSP problem is used to develop an efficient heuristic solution for the problem. The effectiveness of the proposed approach is validated through a comparison with different heuristics traditionally used in HFS scheduling problems. Furthermore, a simple insertion heuristic based on the TSP model of the problem is tested. Finally, a MIP-based approach is also explored to provide the optimum solutions within much larger times for comparison.     

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     

Computation of the travelling salesman problem by a shrinking blob

The travelling salesman problem (TSP) is a well known and challenging combinatorial optimisation problem. Its computational intractability has attracted a number of heuristic approaches to generate satisfactory, if not optimal, candidate solutions. Some methods take their inspiration from natural systems, extracting the salient features of such systems for use in classical computer algorithms. In this paper we demonstrate a simple unconventional computation method to approximate the Euclidean TSP using a virtual material approach. The morphological adaptation behaviour of the material emerges from the low-level interactions of a population of particles moving within a diffusive lattice. A ‘blob’ of this material is placed over a set of data points projected into the lattice, representing TSP city locations, and the blob is reduced in size over time. As the blob shrinks it morphologically adapts to the configuration of the cities. The shrinkage process automatically stops when the blob no longer completely covers all cities. By manually tracing the perimeter of the blob a path between cities is elicited corresponding to a TSP tour. Over 10 runs on 20 randomly generated datasets consisting of 20 cities this simple and unguided method found tours with a mean average tour length of 6.41 % longer than the minimum tours computed by a TSP solver (mean best performance was 4.27 % longer and mean worst performance was 9.22 % longer). We examine the insertion mechanism by which the blob constructs a tour, note some properties and limitations of its performance, and discuss the relationship between the blob TSP and proximity graphs which group points on the plane. The method is notable for its simplicity, novelty and the spatially represented mechanical mode of its operation. We discuss similarities between this method and previously suggested models of human performance on the TSP and suggest possibilities for further improvement.     

An effective Discrete Bacterial Memetic Evolutionary Algorithm for the Traveling Salesman Problem

In recent years, a large number of evolutionary and other population‐based heuristics were proposed in the literature. In 2009, we suggested to combine the very efficient bacterial evolutionary algorithm with local search as a new Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA) (Farkas et al., In: Towards intelligent engineering & information technology, Studies in Computational Intelligence, Vol 243. Berlin, Germany: Springer‐Verlag; 2009. pp 607–625). The method was tested on one of Traveling Salesman Problem (TSP) benchmark problems, and a difference was found between the real optimum calculated by the new and the published result because the Concorde and the Lin–Kernighan algorithm use an approximation substituting distances of points by the closest integer values. We modified the Concorde algorithm using real cost values to compare with our results. In this paper, we systematically investigate TSPLIB benchmark problems and other VLSI benchmark problems ( http://www.math.uwaterloo.ca/tsp/vlsi/index.html ) and compare the following values: optima found by the DBMEA heuristic and by the modified Concorde algorithm with real cost values, run times of DBMEA, modified Concorde, and Lin–Kernighan heuristic. In this paper, for the evaluation of metaheuristic techniques, we suggest the usage of predictability of the successful run in addition to the accuracy of the result and the computational cost as third property. We will show that in the case of DBMEA, the run time is more predictable than in the case of Concorde algorithm, so we suggest the use of DBMEA heuristic as very efficient for the solution of TSP and other nondeterministic polynomial‐time hard optimization problems.     

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.