粒子群在虚拟现实与人工智能应用技术中的研究

粒子群优化（Particle Swarm Optimization，PSO）算法是通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法。粒子群优化与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索。不同的是将群体中的个体看作是在D维搜索空间中没有质量和体积的粒子，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置Pbest和邻域历史最佳位置Nbest聚集，从而实现对候选解的进化。

在算法开始时，随机初始化粒子的位置和速度构成初始种群，初始种群在解空间中为均匀分布。其中第i个粒子在n维解空间的位置和速度可分别表示为和，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己的速度和位置。一个极值是粒子本身到目前为止所找到的最优解，这个极值称为个体极值Pbi=（Pbi 1，Pbi2，…，Pbid）；另一个极值是该粒子的邻域到目前为止找到的最优解，这个极值称为整个邻域的最优粒子Nbesti =（Nbest i1，Nbesti2，…，Nbestid）。粒子根据下式来更新自己的速度和位置：

式中，C1和C2是加速常量，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长。若太小，则粒子可能远离目标区域；若太大则会导致突然向目标区域飞去，或飞过目标区域。合适的C1、C2可以加快收敛且不易陷入局部最优。rand（）是0～1之间的随机数。粒子在每一维飞行的速度不能超过算法设定的最大速度Vmax。设置较大的Vmax可以保证粒子种群的全局搜索能力，Vmax较小则粒子种群优化算法的局部搜索能力加强。

在速度更新式中由3个部分构成：第一部分是Vi，表示粒子在解空间有按照原有方向和速度进行搜索的趋势，这可以用人在认知事物时总是用固有的习惯来解释；第二部分是c1·rand（）·（Pbesti-Xi），表示粒子在解空间有朝着过去曾碰到的最优解进行搜索的趋势，这可以用人在认知事物时总是用过去的经验来解释；第三部分是c2·rand（）·（Nbesti-Xi），表示粒子在解空间有朝着整个邻域过去曾碰到的最优解进行搜索的趋势，这可以用人在认知事物时总可以通过学习其他人的知识，也就是分享别人的经验来解释。粒子群优化算法如下：

1.初始化。设t=0，对每个粒子Pi，在允许范围内随机设置其初始位置xi（t）和速度vi（t），每个粒子Pi的Pbesti设置为其初始位置适应值，Pbesti 中的最好值设为Gbest。

2.计算每个粒子适应值τ（xi（t））。

3.评价每个粒子Pi，如果τ（xi（t））＜Pbesti，则Pbesti=τ（xi（t）），xPbesti=xi（t）。

4.对每个粒子Pi，如果τ（xi（t））＜Gbest，则Gbest=τ（xi（t）），xGbest=xi（t）。

5.调整当前粒子的速度vi（t）：

vi(t)=vi(t-1)+ρ(xPbesti-xi(t))

其中，ρ为一位置随机数。(www.xing528.com)

6.调整当前粒子的位置xi（t）：

xi(t)=xi(t-1)+vi(t)Δt

t=t+1

其中，Δt=1。

7.若达到最大迭代次数，或者满足足够好的适应值，或者最优解停滞不再变化，则终止迭代，输出最优解；否则，返回步骤（2）。

鸟群觅食的过程中，通常飞鸟并不一定看到鸟群中其他所有飞鸟的位置和动向，往往只是看到相邻的飞鸟的位置和动向。因此研究粒子群算法时，可以有两种模式：全局最优和局部最优。

基本粒子群优化算法就是全局最优的具体实现。在全局最优中每个个体被吸引到由种群任何个体发现的最优解。该结构相当于一个完全连接的社会网络，每一个个体都能够与种群中所有其他个体进行性能比较，模仿真正最好的个体。每个粒子的轨迹受粒子群中所有粒子的影响。全局模式有较快的收敛速度，但容易陷入局部极值。

而在局部模式中，粒子总根据它自己的信息和邻域内的最优值信息来调整它的运动轨迹，而不是群体粒子的最优值信息，粒子的轨迹只受自身的认知和邻近的粒子状态的影响，而不是被所有粒子的状态影响。这样，粒子就不是向全局最优值移动，而是向邻域内的最优值移动。而最终的全局最优值从邻域最优值内选出，即邻域最优值中适应值最高的值。在算法中，相邻两邻域内部分粒子有重叠，这样两相邻邻域内公共粒子可在两个邻域间交换信息，从而有助于粒子跳出局部最优，达到全局最优。

局部模式本身存在着两种不同的方式。一种方式是由两个粒子空间位置决定“邻居”，它们的远近用粒子间距离来度量；另一种方式是编号方法，即粒子群中的粒子在搜索之前就被编以不同的号码，形成环状拓扑社会结构。对于第一种方式，在每次迭代之后都需要计算每个粒子与其他粒子间的距离来确定邻居中包括哪些粒子，这导致算法的复杂度增加，算法运行效率降低；而第二种方式由于事先对粒子进行了编号，因而在迭代中粒子的邻域不会改变，这导致在搜索过程中，当前粒子与指定的“邻居”粒子迅速聚集，而整个粒子群就被分成几个小块，表面上看似乎是增大了搜索的范围，实际上大大降低了收敛速度。局部最优模式收敛速度较慢，但具有较强的全局搜索能力。

粒子群优化算法的优势在于算法的简洁性，易于实现，没有很多参数需要调整，且不需要梯度信息。粒子群优化算法是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具。粒子群优化算法的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策和机器人应用等。具体应用实例有模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测和时频分析等。