基于粒子群优化的旅行售货商问题求解算法_信息与计算科学.rar

摘 要:粒子群优化算法(Particle Swarm Optimization，简称PSO)是一种基于群体的进化算法，算法通过粒子间的相互合作来寻找复杂搜索空间中的最优区域，属于智能算法中的一种.后来研究学者引入惯性权重这个概念来更好的控制粒子的收敛和探索，形成了当前的标准PSO算法.由于该算法实现简单，需要调整的参数个数少，已经被广泛地应用于函数优化、通信、电子系统设计以及经济管理等领域.旅行售货商问题（Traveling Salesman Problem, 简称TSP）是组合优化中最著名最经典的问题之一，它综合了一大类组合优化问题的典型特征，并以不同的形式存在于许多高科技领域.

首先本文分析了粒子群优化算法的原理，并介绍了粒子群优化算法的基本公式和算法流程，以及算法中几个参数的设置问题；本文分析了粒子群优化算法的离散化，从离散二进制和算法的重新定义两个视角介绍了离散粒子群算法；总结了目前 PSO 算法研究的成果，简单介绍了目前对粒子群优化算法的多种改进.

其次对旅行售货商问题进行了介绍，TSP是一个典型的NP难问题，也是一个离散优化问题.针对TSP问题的离散特点，本文介绍一种求解TSP问题的离散粒子群算法，算法重新定义了粒子的位置和速度及其与粒子位置的相关算子，并对公式中的参数进行了重新定义，改进了原有的基本公式；用TSPLIB中的部分案例进行实验.实验结果表明，该算法在求解小规模的旅行商问题上有很好的性能，能够快速的收敛，求出最优解.

最后本文探究了不同的参数设置对算法的收敛性的影响，设定了固定参数，线性参数和非线性参数三种不同的参数策略，分别用于解决Burma14城市问题.分析和对比实验结果，设定线性参数更有利于算法快速收敛到最优解.

关键词：粒子群优化算法；离散粒子群优化算法；智能算法；旅行售货商；组合优化；NP完全问题；NP难问题

目 录

摘 要

ABSTRACT

第1章 绪论-1

1.1引言-1

1.2 研究背景-1

1.2.1组合优化-1

1.2.2智能算法-2

1.2.3粒子群优化算法-2

1.2.4旅行售货商问题-3

1.2.5P、 NP、NPC、NP-hard问题-4

1.3粒子群算法的国内外的研究现状-4

1.4旅行售货商问题的研究现状-5

1.5本文的研究思想和主要解决的问题-5

第2章 粒子群优化算法-7

2.1 粒子群算法的简介-7

2.2 标准粒子群算法-7

2.2.1 粒子群算法的基本形式-7

2.2.2 粒子群算法的基本流程-8

2.3 离散粒子群算法-9

2.3.1离散二进制PSO算法-9

2.3.2重新定义PSO算法操作算子-10

2.4 粒子群算法的改进-10

2.4.1基于惯性权重的改进-10

2.4.2基于加速因子的改进-11

2.4.3基于种群规模以及邻域的大小的改进-11

第3章 粒子群算法解决TSP问题-13

3.1 粒子群算法解决TSP-13

3.1.1 算法的重新定义-13

3.1.2 算法的基本流程-14

3.2 参数设置-14

第4章 实验结果与分析-17

4.1 粒子群算法解决TSP问题的结果-17

4.2 参数实验结果与对比-19

第5章 结论与展望-21

5.1总结-21

5.2不足之处及未来展望-21

5.2.1不足之处-21

5.22 未来的工作展望-21

参考文献-23

致  谢-25