Discrete optimization by optimal control methods. II. The static traveling salesman problem

The static minisum traveling salesman problem is formulated as an optimal control problem. Two-sided algorithms based on the sufficient conditions for global optimality for solving this problem and a new algorithm for approximating the quality criterion from above to its optimal value are designed.     

Hybrid control systems and the dynamic traveling salesman problem

A new approximate algorithm for solving the dynamic traveling salesman problem (DTSP) is proposed; the traveling salesman starting from the base city visits megapoleis and cities inside megapoleis and comes back to the base city. A specific feature of this variant of DTSP is the movement of cities inside megapoleis in time. To solve this problem, a general solution theory for hybrid (complicated) systems with “combinatorial” and “continuous” path segments is developed. The general theory is based on the sufficient optimality conditions known in the theory of optimal control.     

求解TSP 问题的离散狼群算法

通过定义反转算子, 对人工狼位置和智能行为重新进行整数编码设计, 并结合概率近邻初始化方法, 提出一种求解旅行商问题的离散狼群算法. 该算法保留了狼群算法基于职责分工的协作式搜索特性, 并较好地平衡了算法的广度开拓和深度开采能力. 采用C-TSP 问题和TSPLIB 数据库中的多组TSP 问题作为实验用算例, 并将所提出算法与其他5 种智能优化算法进行对比, 仿真结果表明, 所提出算法在求解准确率、稳定性和所需迭代次数等方面具有相对优势.

     

Discrete optimization by optimal control methods I. Separable problems

Two general solution schemes are designed for separable discrete optimization problems. Approximations from below and from above to the optimal value of the quality criterion are determined. These schemes are based on a unified theoretical base—sufficient conditions for the global optimal known in optimal control theory. Known and new methods for defining a resolving function, which is essential for applying these conditions, are described.     

深度强化学习解决动态旅行商问题

针对未设计启发式算法的组合优化问题设计统一的解决方案已成为机器学习领域的一个研究热点,目前成熟的技术主要针对静态的组合优化问题,但是对于加入动态变化的组合优化问题还没有得到充分的解决。为了解决以上问题,提出一个将多头注意力机制与分层强化学习结合来求解动态图上的旅行商问题的轻量级模型Dy4TSP。首先,用以多头注意力机制为基础的预测网络处理来自图卷积神经网络的节点表征向量输入;然后,借助分布式强化学习算法训练来快速地预估图中每个节点被输出作为最优解的可能性,使得模型在不同的可能性中全面探索问题的最优解决方案空间;最后,训练后的模型将实时地生成满足具体目标奖励函数的动作决策序列。该模型在3个组合优问题上进行了评估,实验结果表明,该模型在经典旅行商系列问题中解的质量比开源求解器LKH3高0.15~0.37个单位,明显优于带有边嵌入的图注意网络（EGATE）等最新的算法;并且在其他的动态旅行商问题中可以达到0.1~1.05的最优路径差距,结果也略胜一筹。     

Solving the dynamic traveling salesman game problem

A game problem of the successive capture of a team of evaders by a single pursuer under conditions of “simple motions” of the players is analyzed. The performance criterion is the total time all the evaders are captured. It is assumed that the pursuer is guided by the parallel pursuit law. In such a case, the optimal response of the evaders is the straightforward motion with maximum speed. The original infinite-dimensional problem can therefore be reduced to two finite-dimensional problems.     

改进粒子群优化算法求解TSP问题

针对粒子群优化算法易陷入局部极值的缺点,提出一种改进粒子群算法,该算法借鉴贪婪算法的思想初始化种群,利用两个种群同时寻优,并将遗传算法中交叉和变异操作引入其中,实现种群间的信息共享。用14点TSP标准数据对算法性能进行了测试,结果表明该算法能够较早跳出局部最优,具有较高的收敛速度和收敛率。     

求解旅行商问题的混合粒子群优化算法

结合遗传算法、蚁群算法和模拟退火算法的思想，提出用混合粒子群算法来求解著名的旅行商问题．与模拟退火算法、标准遗传算法进行比较，24种混合粒子群算法的效果都比较好，其中交叉策略D和变异策略F的混合粒子群算法的效果最好，而且简单有效．对于目前仍没有较好解法的组合优化问题，通过此算法修改很容易解决．     

基于LINGO的旅行商问题的建模方法

旅行商问题是图论中一类经典的最优化问题,其研究对于其他图优化问题的解决具有重要的理论意义和实际价值。针对旅行商问题建模中的困难之处--如何避免“分割”现象,提供了三种不同的解决方法,并给出了基于当今最流行的优化计算软件LINGO的实证分析。     

求解最小比率旅行商问题的离散蝙蝠算法

研究了以总路程与总收益之比为目标函数的最小比率旅行商问题,提出了求解该问题的离散蝙蝠算法。介绍了蝙蝠算法的基本思想,重新定义了位置与位置的减法操作算子、实数与位置的乘法操作算子以及速度与位置的加法操作算子,引入了城市子序列逆序策略来对线路进行局部搜索。给出了算法的具体实现方案,并通过仿真和比较实验验证算法的优化性能,实验结果表明该算法可以有效求解最小比率旅行商问题。     

改进的猫群算法求解TSP问题

针对了求解TSP问题给出一种新算法,改进的猫群算法。猫群算法,作为一种群智能优化算法,有较快的收敛速度、向“他人”学习等优点,但国内目前对它的研究还处在起步阶段,所以做这方面的尝试性研究。通过引入交换子概念和改进猫的行为模式将算法用于求解TSP问题。最后通过MATLAB仿真,并将实验结果与已知最优解相比较,验证了该算法的有效性。故不仅拓宽了猫群算法的应用范围,也给求解TSP等路径优化问题提供一种新的解决办法。     

求解旅行商问题的自学习粒子群优化算法

针对旅行商问题,提出了一种带自学习算子的粒子群优化算法,根据旅行商问题及离散量运算的特点,对粒子的位置、速度等量及其运算规则进行了重新定义,为抑制早熟停滞现象,定义了变异速度来保持粒子群的多样性,使用自学习算子来提高算法的局部求精能力,使算法在空间探索和局部求精间取得了较好的平衡,与领域中的其它典型算法进行了仿真比较,结果表明,该算法具有良好的性能.     

The generalized covering traveling salesman problem

In this paper we develop a problem with potential applications in humanitarian relief transportation and telecommunication networks. Given a set of vertices including the depot, facility and customer vertices, the goal is to construct a minimum length cycle over a subset of facilities while covering a given number of customers. Essentially, a customer is covered when it is located within a pre-specified distance of a visited facility on the tour. We propose two node-based and flow-based mathematical models and two metaheuristic algorithms including memetic algorithm and a variable neighborhood search for the problem. Computational tests on a set of randomly generated instances and on set of benchmark data indicate the effectiveness of the proposed algorithms.     

求解旅行商问题的混合粒子群优化算法

为高效解决旅行商问题,结合光学寻优算法、混沌优化算法、粒子群优化算法,提出了一种新的混合智能优化算法,应用光学寻优算法的优点,为粒子群中粒子找到了一组最优的初始值,引入交换子、交换序列、混沌序列,提出了适合旅行商问题的光学混沌粒子群算——并严格证明了新算法的稳定性、收敛性.数值实验仿真结果表明,该算法收敛速度快、迭代次数少,能快速找到令人满意的最优解,为解决旅行商问题提供了新的思路.     

基于自组织优化算法的一类多旅行商问题

多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组织优化算法进行了求解。虚拟城市局部适值的定义很好地处理了此类问题的能力约束,针对多旅行商问题的实例进行的仿真表明自组织优化算法可以很好地求解此类问题。     

基于文化混合优化算法的旅行商问题求解

为更好地求解TSP问题,将遗传算法与模拟退火算法结合并纳入文化算法体系,提出一种求解旅行商问题的文化混合优化算法。该算法空间可分为独立并行的两部分：种群空间和信度空间。种群空间按照遗传退火混合算法实现进化,并将进化中的较优个体提供给信度空间,信度空间提取并利用较优个体所包含的信息来引导种群进化。通过求解TSP标准测试问题,将文化混合优化算法所求得的最优路径与其他优化算法所求结果相比,算法偏差均可降低0.6%～13.01%,表明了文化混合优化算法求解TSP问题的有效性与优越性。     

The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem

Traveling salesman problem (TSP) is proven to be NP-complete in most cases. The genetic algorithm (GA) is improved with two local optimization strategies for it. The first local optimization strategy is the four vertices and three lines inequality, which is applied to the local Hamiltonian paths to generate the shorter Hamiltonian circuits (HC). After the HCs are adjusted with the inequality, the second local optimization strategy is executed to reverse the local Hamiltonian paths with more than 2 vertices, which also generates the shorter HCs. It is necessary that the two optimization strategies coordinate with each other in the optimization process. The two optimization strategies are operated in two structural programs. The time complexity of the first and second local optimization strategies are O(n) and O(n³), respectively. The two optimization strategies are merged into the traditional GA. The computation results show that the hybrid genetic algorithm (HGA) can find the better approximate solutions than the GA does within an acceptable computation time.     

An improved fruit fly optimization algorithm for solving traveling salesman problem

The traveling salesman problem (TSP), a typical non-deterministic polynomial (NP) hard problem, has been used in many engineering applications. As a new swarm-intelligence optimization algorithm, the fruit fly optimization algorithm (FOA) is used to solve TSP, since it has the advantages of being easy to understand and having a simple implementation. However, it has problems, including a slow convergence rate for the algorithm, easily falling into the local optimum, and an insufficient optimi-zation precision. To address TSP effectively, three improvements are proposed in this paper to improve FOA. First, the vision search process is reinforced in the foraging behavior of fruit flies to improve the convergence rate of FOA. Second, an elimination mechanism is added to FOA to increase the diversity. Third, a reverse operator and a multiplication operator are proposed. They are performed on the solution sequence in the fruit fly’s smell search and vision search processes, respectively. In the experiment, 10 benchmarks selected from TSPLIB are tested. The results show that the improved FOA outperforms other alternatives in terms of the convergence rate and precision.     

解决TSP问题的局部调整离散微粒群算法

微粒群算法提出以来一直不能较好的解决离散及组合优化问题,针对这个问题,通过对微粒群算法的优化机理的分析,对原有的微粒群进化方程中的速度和位置的更新等进行重新的定义,同时提出一种具有自适应能力的惯性因子,使其适合解决TSP这样的组合优化问题.针对过去的离散算法整体调整容易形成对路径的破坏这一缺点,在重新定义的算法上加入局部调整的策略,形成一种局部调整的离散微粒群算法(local adjustive discrete PSO,LADPSO),通过在ch31和ei151上的试验,证明了该算法在解决这一问题上是可行的.     

Honey bees mating optimization algorithm for the Euclidean traveling salesman problem

This paper introduces a new hybrid algorithmic nature inspired approach based on Honey Bees Mating Optimization for successfully solving the Euclidean Traveling Salesman Problem. The proposed algorithm for the solution of the Traveling Salesman Problem, the Honey Bees Mating Optimization (HBMOTSP), combines a Honey Bees Mating Optimization (HBMO) algorithm, the Multiple Phase Neighborhood Search-Greedy Randomized Adaptive Search Procedure (MPNS-GRASP) algorithm and the Expanding Neighborhood Search Strategy. Besides these two procedures, the proposed algorithm has, also, two additional main innovative features compared to other Honey Bees Mating Optimization algorithms concerning the crossover operator and the workers. The main contribution of this paper is that it shows that the HBMO can be used in hybrid synthesis with other metaheuristics for the solution of the TSP with remarkable results both to quality and computational efficiency. The proposed algorithm was tested on a set of 74 benchmark instances from the TSPLIB and in all but eleven instances the best known solution has been found. For the rest instances the quality of the produced solution deviates less than 0.1% from the optimum.