承接上一节的内容，这一节我们用粒子群优化算法(PSO)来解决TSP问题。
背景介绍
粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation），源于对鸟群捕食的行为研究。基本思想是是通过群体中个体之间的协作和信息共享来寻找最优解（感觉有点像蚁群算法）。但较之蚁群算法，PSO的优势在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。
算法实现
数学基础
在这个问题中，我们把要拿来解决问题的抽象对象设置成一群鸟（上一例是一群蚂蚁），而且这一群鸟会互相配合。鸟被抽象为没有质量和体积的(点)，并延伸到维空间，粒子在维空间的位置表示为矢量，飞行速度表示为矢量。每个粒子都有一个由目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)，这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。
PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest，gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度，位置以及参数。
符号说明： ，N是此群中鸟的总数。
，第只鸟的速度。
，之间的随机数。
，粒子的当前位置。
，学习因子。
，最大迭代次数。
，初始惯性权值。
，迭代至最大循环次数时的惯性权值。
，非负值惯性因子。其值大小与全局寻优能力成正相关，局部寻优能力呈负相关。一般按照线性递减权值(Linearly Decreasing Weight)策略更新值使其能够获得比固定值更好的寻优结果。
参数典型值：
，，
算法流程
在搭建好了以上基础后，尝试用伪代码表述蚁群算法对于TSP问题的求解流程：
1）初始化一群微粒(群体规模为N)，包括随机位置和速度；
2）评价每个微粒的适应度；
3）对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest；
4）对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest；
5）根据公式2)、3)调整微粒速度和位置；
6）未达到结束条件则转第2)步。
代码实例
以下为在Python上的代码实例，运行用图为下图：
需要注明，addEdge函数是负责将图的各边输入，应当将每一节点的索引均输入完。 但在日常上这种直接给出距离的实例还是比较少，考虑优化如下：
同样，PSO也可以用于函数数值近似解计算，
下为Python的实现流程：
结语
在经过了昨日的建模基础后，今天的分析过程就进步神速，仅仅用了一个早上就完成了PSO这篇文档的编写。至此智能算法算是告一段落了。
- Author:Peter Kam
- URL:https://blog.petergam.top//article/study-of-TSP-problem-2
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
