求解旅行商问题的微粒群算法研究

【作者】 王蒙；

【导师】 介婧； 王丽芳；

【作者基本信息】 太原科技大学 ， 计算机软件与理论， 2009， 硕士

【摘要】 旅行商(TSP)问题,是一个古老而又典型的NP-hard组合优化问题。该问题的有效求解,不仅有着重要的理论和学术价值,同时对于许多实际工程应用问题有着重要的指导意义。因此,寻求高效的TSP优化算法一直是优化领域的一个热点课题。微粒群算法是一种新型的群智能计算方法,算法模型简单、操作便捷,具有自组织、自适应、自学习等智能特性,已被证明是一种求解大规模复杂问题的有效工具,因此也是求解TSP问题的一种智能计算方法。然而,面对复杂的离散组合优化问题,现有的微粒群算法模型存在着效率低下,求解精度不高,易于早熟等缺陷。为此,本论文基于TSP优化问题,着重围绕离散微粒群算法的模型设计和性能改进,进行以下内容的研究:一、基于微粒群算法的优化机理,分析了离散微粒群算法设计的主要方法和基本原则,进而研究了离散微粒群算法的关键技术,包括离散问题的编码、个体微粒的评价及其主要进化操作,为后续的研究提供技术基础。二、为提高离散微粒群算法的全局收敛性,提出了一种引入局部扰动策略的改进微粒群算法。首先基于整数编码,并结合遗传算法中的PMX算子,对离散微粒群算法中的速度、位置及其进化操作进行了重新定义,其次引入微粒的活力信息来实现控制参数的自适应调节,构造局部扰动策略以避免群体局部收敛。改进算法被用于典型TSP测试问题,其仿真结果表明该算法的有效性。三、为提高离散微粒群算法对复杂问题的求解能力,提出一种基于边编码,采用表示边的两城市点之间所有点依次倒置插入的微粒更新操作的改进离散微粒群算法。并在对算法方程进行重新定义的基础之上,加入微粒适应值变优则更新,变差按一定概率更新的策略。通过在典型中型TSP问题上进行的实验,求解时间、求解精度上均令人满意。然后在这个改进算法的基础之上加入多级规约策略,为微粒群算法求解大规模问题提供了一种思路。更多还原

【Abstract】 Traveling salesman problem (TSP) is an old and typical NP-hard combinatorial optimization problem, its valid and effective solutions not only has important theoretical and academic values, but also has important guiding significance for many practical engineering applications. So TSP is a hot topic in optimization field. Particle swarm optimization (PSO) is a new method based on swarm intelligence, which are characterized mainly by simple model, convenient operation, self-organizing, self-adaptive, self-learning, etc. Particle swarm optimization has been proved to be an effective technique to solve large-scale complex problems. Therefore, it is also an efficient method to solve TSP. However, the existing PSO also suffers from some shortcomings, such as low efficiency, low accuracy, premature convergence, etc., especially for the large scale and complex discrete combinatorial optimization problems.The dissertation focuses on the model designing and performance improving of discrete particle swarm algorithm (DPSO) based on TSP, its main researches are listed as the following:1. Based on the optimization mechanisms of swarm intelligence, the dissertation makes an analysis of the primary design methods and the basic principles for discrete particle swarm optimization firstly. After that, the key techniques of DPSO also are analyzed in details, including the code methods for discrete optimization problems, the evolutionary operations in discrete solution space, etc., which provide a valid technical foundation for the following study.2. To improve the global convergence of DPSO, The dissertation develops an adaptive DPSO to solve TSP. Firstly, the improved DPSO adopts the integer code method and redesigns the particles’velocity, location, and their discrete evolution operations based on the PMX operator of genetic algorithm. Secondly, the improved DPSO introduces a local adjustment strategy for the parameters to avoid the local convergence of the swarm, which is controlled by the dynamic information of particles. The simulation results based on the typical TSP problems show that the proposed algorithm validly improves the global performance of PSO in discrete optimization problems.3. To develop the performance of DPSO for complex discrete optimization problems, the dissertation proposed another improved DPSO, which takes advantage of side-code technique and a multilevel reduction strategy. The improved DPSO redesigns the particles’velocity, location, and their discrete evolution operations based on the side-code technique. After that, a multilevel reduction strategy is introduced to improve the global convergence of the algorithm. Finally, the improved algorithm is applied to solve medium or large scale TSP problems, the simulation results show that the proposed algorithm is a valid technique for complex TSP problems.更多还原