改进的离散粒子群算法在TSP中的应用研究

发布时间：2018-06-15 00:43

本文选题：粒子群算法 + 旅行商问题　；参考：《江南大学》2017年硕士论文

【摘要】：粒子群优化算法(Particle Swarm Optimization,简称PSO)是一种基于群体的进化算法,是一种有效的全局优化算法。PSO因实现简单、需要调整的参数少、收敛速度快等优点被广泛应用于函数优化、数据挖掘及电力系统等领域。旅行售货商问题(Traveling Salesman Problem,简称TSP)是运筹学中的经典组合优化问题之一,已被证明为NP完全问题。它综合了一大类组合优化问题的典型特征,并以不同的形式存在于交通运输、印制电路板及数据串聚类等许多领域。通过对PSO算法和TSP的分析和研究,本文提出了三种改进的粒子群优化算法:基于优秀系数的局部搜索混沌离散粒子群优化算法(ILCDPSO)、基于自适应优秀系数的粒子群算法(SECPSO)以及基于柯西分布和3-opt的自适应粒子群算法(SCLPSO)。用TSPLIB中的经典测试案例对这些算法进行了测试,并与其他算法的求解结果进行了比较。文章的主要工作概括如下:(1)针对基本离散粒子群算法收敛速度慢、易于陷入局部最优等问题,提出了一种基于优秀系数的局部搜索混沌离散粒子群优化算法。提出了优秀系数的概念,给每条边设定合理的优秀系数,以提高短边被选择的概率,从而有利于提高算法的寻优能力和收敛速度;在算法机制中添加了局部搜索策略,提高算法的局部搜索能力;另外,在算法的迭代公式中加入了混沌序列来提高粒子的随机性和多样性,增强算法的全局搜索能力。研究结果表明,ILCDPSO算法在收敛速度、全局寻优能力以及稳定性方面均优于其他算法。(2)为了利用问题领域的启发式信息,本文在ILCDPSO算法的基础上进行改进,提出了一种基于自适应优秀系数的粒子群算法(SECPSO)。SECPSO算法对静态的优秀系数进行修改,使之可根据解的搜索过程进行自适应动态调整;另外,为了进一步提高解的精确性和算法的收敛速度,添加了3-opt搜索机制,以提高算法的局部搜索能力。实验结果表明,SECPSO算法在全局寻优能力和更快的收敛速度方面表现更优。(3)为了进一步提高SECPSO算法的求解精度和稳定性,利用柯西分布对惯性权重进行了改进,提出了基于柯西分布和3-opt的自适应粒子群算法SCLPSO。加入柯西分布可以使算法在初期阶段搜索范围更广,并且具有更高的算法稳定性。实验结果表明SCLPSO算法的收敛次数比明显增加,能快速收敛到最优解,且收敛精度进一步提高,从而算法的综合性能得到了较大提升。
[Abstract]:Particle Swarm Optimization (PSO) is a group based evolutionary algorithm. It is an effective global optimization algorithm (.PSO), which is widely used in function optimization, data mining and power system, etc. because of its simple implementation, less parameters and faster convergence speed. Traveli Ng Salesman Problem, referred to as TSP), is one of the classical combinatorial optimization problems in operational research. It has been proved to be a complete problem of NP. It combines the typical features of a large class of combinatorial optimization problems and exists in many fields, such as transportation, printed circuit board and data string clustering in a variety of forms. Through the analysis and research of PSO algorithm and TSP, In this paper, three improved particle swarm optimization algorithms are proposed: local search chaotic discrete particle swarm optimization (ILCDPSO) based on excellent coefficients, particle swarm optimization based on adaptive excellent coefficients (SECPSO) and adaptive particle swarm optimization (SCLPSO) based on Cauchy distribution and 3-opt. These algorithms are used in the classical test cases of TSPLIB. The main work of the paper is summarized as follows: (1) in view of the slow convergence speed of the basic discrete particle swarm optimization algorithm and easy to fall into the local optimal problem, a local search chaotic dispersion particle swarm optimization algorithm based on the excellent coefficient is proposed. The concept of the excellent coefficient is proposed. In order to improve the searching ability and convergence speed of the algorithm, the local search strategy is added in the algorithm mechanism to improve the local search ability of the algorithm. In addition, the chaos sequence is added to the iterative formula of the algorithm to improve the randomness of the particle and the randomness of the particle. The results show that the ILCDPSO algorithm is superior to other algorithms in the convergence speed, global optimization ability and stability. (2) in order to use the heuristic information in the problem domain, this paper is modified on the basis of the ILCDPSO algorithm, and proposes a particle based on the adaptive excellent coefficient. The group algorithm (SECPSO).SECPSO algorithm modifies the excellent static coefficient to make adaptive and dynamic adjustment according to the search process of the solution. In addition, in order to further improve the accuracy of the solution and the convergence speed of the algorithm, the 3-opt search mechanism is added to improve the local search ability of the algorithm. The experimental results show that the SECPSO algorithm is all in the whole. (3) in order to further improve the accuracy and stability of the SECPSO algorithm, the Cauchy distribution is used to improve the inertia weight, and an adaptive particle swarm optimization (SCLPSO.) distribution based on Cauchy distribution and 3-opt is proposed to make the algorithm in the initial stage of the search model. The experimental results show that the convergence times of SCLPSO algorithm are significantly increased, and the convergence of the algorithm can be quickly converged to the optimal solution, and the convergence precision is further improved. Thus the comprehensive performance of the algorithm has been greatly improved.
【学位授予单位】：江南大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】