粒子群优化算法
（一）算法起源
粒子群算法（Particle Swarm Optimization，PSO）是由Eberhart和Kennedy于1995年提出的一种进化计算技术，该算法受到鸟群早捕食活动过程中相互传递信息的启发，进而利用群体智能优化建立一个易于计算的简化模型。粒子群算法在对生物集群活动行为观察的基础之上，利用群体中的个体信息共享机制促使整个群体的活动在问题的求解空间中产生解空间，最终通过迭代寻优获得最优解。粒子群算法在操作上易于实现，精度高、收敛性快等优点收到了学术界和工业界的重视，并在解决工程实践问题中表现出一定的优越性。
（二）算法模型
设想存在这样一个鸟群捕食的情景：一群鸟在捕食区域随机寻找食物源，并且在这个区域里只有一个食物源。假定所有鸟都不知道食物源在哪里，但通过信息交互它们知道当前的位置距离食物源还有多远。如何简单有效的对食物源进行搜索呢？我们首先想到的是寻找鸟群中离食物最近的鸟来进行搜索。于是，我们可以用一种粒子来表征上述情景中的鸟类个体，把每个粒子视为N维搜索空间中的一个搜索个体，其当前所处的具体位置可以作为对用优化问题中的一个具体的候选解。其中，粒子的飞行过程即为该个体的搜索过程，粒子的飞行速度可根据粒子历史最优位置和种群历史最优位置进行动态调整。因此，粒子具有两个属性：速度和位置，速度代表寻找最优解移动的快慢，位置代表移动的方向。而粒子群中每个粒子单独搜寻的最优解叫做个体值，粒子群中最优的个体值作为当前全局最优解。通过不断迭代上述过程，更新粒子的速度和位置，最终可以得到满足终止条件的最优解。
（三）算法具体流程
1.初始化
首先，根据最优化问题设置目标函数的自变量个数（搜索空间维数）D，粒子群的个数N，最大迭代次数M，位置信息为整个搜索空间，我们在速度区间和搜索空间上随机初始化速度和位置，为每个粒子初始化一个飞行速度和位置（随机解）。
2.个体极值和全局最优解
定义一个适应度函数。在每一次迭代过程中，粒子通过跟踪两个极值来更新自己的状态：一个是粒子更新本身状态寻找到的最优解，这个解称之为个体极值；另一个是通过整个群体目前找到的最优解，这个极值我们称之为本次全局最优解。另外也可以通过整个群体中的部分粒子作为邻居，此时在所有邻居中的极值就是局部极值。
3.更新速度和位置公式
假设在一个D维目标搜索空间中，有N个粒子组成的一个群落，其中第i个粒子表示为一个D维向量：
第i个粒子的飞行速度也是一个D维向量，可以表示为：
第i个粒子目前为止搜索到的最优位置称为个体机制，可以表示为：
整个群体目前为止搜索到的最优位置为全局机制，可以表示为
在找到这两个最优值时，粒子可以根据如下公式来更新自己的飞行速度和位置：
其中，w称之为惯性因子，其值非负，可以通过调整w的值来对局部寻优和全局寻优进行调整，其值较大时，全局寻优能力强，局部寻优能力弱；其值较小时，全局寻优能力弱，局部寻优能力强。c1和c2称为学习因子，也称之为加速常数，前者为每个粒子的个体学习因子，或者为整个粒子群的群体学习因子。r1，r2为［0，1］范围内的均匀随机数。式子vid=w*vid+c1r1（pidxid）+c2r2（pgd-xid）右边三部分含义如下：
w*vid反应粒子的运动惯性，代表粒子维持原有先前速度的趋势，我们称之为惯性部分
c1r1（pid-xid）反应粒子对自身历史经验的综合，代表粒子向自身历史最佳位置逼近的趋势。
c2r2（pgd-xid）反应粒子群之间协同合作与知识共享的群体历史经验，代表粒子有向整个群体或邻域历史最佳位置运动的趋势。
每个粒子的更新方式可以用如下图2-8直观表示。
图2-8 粒子群更新的方式
粒子群算法具有较强的搜索能力，在求解多目标最优解时表现出快速的收敛能力。通过代表整个解集种群，按照并行方式可以同时搜索多个pareto最优解。同时，粒子群算法的移植性和通用性比较好，适合处理多种类型的目标函数和约束，并且容易与传统的优化方法想结合，从而改进自身的局限性，更高效的解决实际问题。因此，将粒子群算法应用解决多目标优化问题具有较强的优势。
4.程序设计
粒子群算法的基本流程图如图2-9所示，其具体过程可作如下解释：
（1）初始化粒子群，给定每个粒子速度vi和位置xi的初值，并当前位置设置为历史最优值pbset，群体中的最优个体作为当前的gbest；
（2）在每一次迭代进化中，计算出每个粒子的适应度函数值；
（3）如果当前适应度函数值优于历史最优值，则更新个体极值pbest；
（4）如果当前适应度函数值优于全局历史最优值，则更新全局极值gbest
（5）对每个粒子的第d维的速度和位置分别按照速度和位置更新公式更新；
（6）如果满足终止条件（误差能够满足条件或者达到最大迭代循环次数）则退出，否则继续返回步骤二。
图2-9 粒子群算法流程图