求解旅行商问题的一种改进粒子群算法

本文研究了求解旅行商问题的粒子群算法。针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点,提出了一种改进的粒子群算法。首先,在初始种群的选取过程中,利用改进的贪婪策略直接获得具有较高性能的初始种群以提高算法的搜索效率。其次,通过引入次优吸引子,使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能,有效抑制收敛过程中的停滞现象,提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性,对TSPLIB标准库中的多个实例进行了测试,并给出了数值结果。     

旅行商问题的交叉粒子群优化算法

本文将粒子群优化算法(PSO)应用于求解旅行商问题(TSP),结合遗传算法的交叉算子,建立了求解此问题的交叉粒子群优化算法,数值模拟结果表明了该算法的有效性.     

基于最小调整法求解旅行商问题

介绍了一种求解旅行商问题的新算法"最小调整法",给出了该算法求解旅行商问题的具体步骤以及有效性证明,对算法的复杂性及近似程度进行了分析.最后通过典型算例进行了检验说明.与经典算法相比,新算法体现了简单易行的特点,对求解旅行商问题具有一定的启发意义.     

非对称距离的旅行商问题的构造算法

章分析了非对称距离的旅行商问题,讨论了节约算法与最小生成树算法两种启发式方法,并用实例进行了说明,最后对算法的有效性进行了说明。     

一个关于非对称距离的旅行商问题的迭代算法

本对非对称距离的旅行商问题，给出了一个迭代算法，并分析了此迭代算法的复杂度为M^nO(N^4)，其中，N是问题中旅行商所要经过的城镇数，M是两城镇间的最大距离。最后用实例对此算法进行了验算和说明。     

用列队竞争算法解旅行商问题

给出了列队竞争算法解组合优化问题的框架和确定变异邻域的两条原则。用列队竞争算法解旅行商问题获得了满意的结果,显示出列队竞争算法良好的全局搜索性能。     

改进的二进制粒子群算法求解车辆路径问题

设计了一种改进的二进制粒子群优化算法来求解车辆路径问题,算法基于粒子群算法的寻优模式充分考虑粒子之间的导向作用,改进二进制粒子群算法的位取值方式,减小了在进化过程中停滞于局部最优解的概率,并通过构造辅助函数处理优化问题的约束条件,基于分层次实现多个目标的思路来寻优,提高了算法的搜索效率和计算速度.实验测试结果验证了该算法对求解车辆路径问题的适用性和有效性.     

改进遗传算法求解旅行商问题

针对采用自然编码的遗传算法在求解旅行商问题(TSP)过程中初始群体设置过于复杂的问题,采用了Grefenstette编码设置初始群体,有效保证了初始群体的随机性和多样性.同时,在遗传算法实施过程中采用了自然编码,吸取边重组交叉算子和简单交叉算子的优点,提出一种新的交叉算子.这种处理解决了Grefenstette编码在遗传算法的交叉和变异过程中只能部分遗传父代的优良特性的问题.对TSP试算结果表明,采用这种遗传算法策略有利于问题的求解.这种实施的策略可以大量用于加工领域和交通领域以及其他规划领域的路径规划中.     

求解多维背包问题的改进二进制粒子群算法

针对二进制粒子群算法在求解大规模多维背包问题时存在迭代次数过多、精度不高的不足,提出一种改进的二进制粒子群算法,新算法利用种群个体极值的平均信息和粒子的个体极值决定粒子当前取值的概率,使粒子可以充分利用整个种群的信息,避免算法陷入局部极值,并利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正.通过对典型多维背包问题的仿真实验和与其它算法的比较,表明算法有良好的全局优化能力和较好的收敛速度.     

基于混合的细菌觅食算法求解TSP问题

针对求解经典NP问题—旅行商难题(TSP),在标准细菌觅食算法上进行改进,提出了混合的细菌觅食算法(HBFA).一方面引入编码交叉思想对趋势步进行改进,使算法能更有效地处理离散优化问题;另一方面采用了自适应迁徙算子,使新生个体带有最优个体启发式信息的同时也增强了算法跳出局部最优能力.最后通过对TSPLIB中若干实例的实验仿真以及多种算法对比,验证了算法的可行性和有效性.     

用嵌套插队算法解决TSP问题

本提出了一种求解TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的。TSP问题，直接用插队算法(QJA)就能以很大的概率获得已知最优解。对于规模较大的问题实例。嵌套插队算法(NQJA)能获得质量高于名的启发式算法的解。另外，用嵌套插队算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的，但其思想也可以给求解其他NP难解的组合优化问题以启发。     

Random Tours in the Traveling Salesman Problem: Analysis and Application

Random solutions to the traveling salesman problem (TSP) exhibit statistical regularities across problem instances. These patterns can assist heuristic search for good solutions by providing easy estimates of the length of the optimal tour.     

A New Memetic Algorithm for the Asymmetric Traveling Salesman Problem

This paper introduces a new memetic algorithm specialized for the asymmetric instances of the traveling salesman problem (ATSP). The method incorporates a new local search engine and many other features that contribute to its effectiveness, such as: (i) the topological organization of the population as a complete ternary tree with thirteen nodes; (ii) the hierarchical organization of the population in overlapping clusters leading to the special selection scheme; (iii) efficient data structures. Computational experiments are conducted on all ATSP instances available in the TSPLIB, and on a set of larger asymmetric instances with known optimal solutions. The comparisons show that the results obtained by our method compare favorably with those obtained by several other algorithms recently proposed for the ATSP.     

Analysis of Random Restart and Iterated Improvement for Global Optimization with Application to the Traveling Salesman Problem

The optimization method employing iterated improvement with random restart (I2R2) is studied. Associated with each instance of an I2R2 search is a fundamental polynomial, in which the coefficient p_k is the probability of starting a search k improvement steps from a local minimum. The positive root of f can be used to calculate the convergence and speedup properties of that instance.Since the coefficients of f are naturally related to the search, it is possible to estimate them online if an a priori estimate of the size of the goal basin is available, for example by analysis or prior experience. In this case, the runtime statistical estimate of converges many times faster than the estimates of the coefficients themselves.The foregoing is illustrated with an application to the traveling salesman problem (TSP) using the k-change as the improvement discipline. Among other things, it is shown that a k-change improvement can be affected by k 2-changes, that =1 for convex city sets, and that good estimates of can be made from a reduced TSP related to the given one.This research was partially supported by the National Sciences and Engineering Research Council of Canada (NSERC) in the form of a discovery grant. The authors thank the referees for helpful suggestions and timeliness.     

带有配额的在线Nomadic旅行商问题

由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了社会的广泛重视,而应急车辆尽快地将应急物资送到受灾点显得尤为重要。针对应急车辆装载物资能力有限和应急车辆不必返回出发点的情形,提出了带有配额的在线Nomadic旅行商问题。分析了该问题在正半轴和一般网络上的下界,针对受灾点仅在正半轴上的情形设计了WTAIB算法,针对受灾点在一般网络上设计了WSB算法,并进一步分析了两个算法的竞争性能。