1.1引言 人工智能在经历了20世纪80年代整整10多年的繁荣之后，随着人类探索脚步的不断前进，其复杂性、非线性、系统性的问题越来越多地呈现在人们眼前，面对系统的复杂性，由于在方法论上始终没有改变和突破经典计算的思想，已经逐渐陷入了困境。与此同时，随着人们对生命本质的不断了解，生命科学却以前所未有的速度迅猛发展，使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索起新的非经典计算模式。在这种背景下，社会性动物(如蚁群、蜂群、鸟群)的自组织行为吸引着越来越多的学者进入到这个领域，研究这些简单的个体如何通过协作呈现出如此复杂而奇妙的行为，同时通过计算机模拟来探索其中的可循规律，并用于指导和解决一些常规方法没有解决的传统问题以及实际应用中出现的新问题，这就产生了一种新型的智能计算技术，即所谓的“群智能(swarm intelligence, SI)”，或称为“群集智能”\[1,2\]。 群智能算法与人工生命，特别是进化策略以及遗传算法(genetic algorithm, GA)有着特殊的联系，目前已引起了越来越多研究者的关注，并成为一个研究热点。在群智能中，群体指的是一组相互之间可以通过直接通信或间接通信从而能够达成合作以对分布式问题进行求解的主体。为此，在不存在集中控制和不提供全局模型的前提下，群智能为寻找复杂的分布式问题求解方案提供了研究基础和技术支持。粒子群优化(particle swarm optimization, PSO)算法和蚁群(ant colony optimization, ACO)算法是目前群智能研究领域的两种主要算法，前者是对鸟群觅食过程的模拟，而后者主要是对蚂蚁群落食物采集过程的模拟。 群智能算法仅涉及各种基本的数学运算，对计算机性能要求不高，是一种简单且易于实现的算法。群智能算法基于概率搜索的算法，只需目标函数的输出值，并不需要相关的梯度信息，这也是与多数基于梯度应用的优化算法不同的地方。虽然概率搜索算法通常采用较多评价函数，但与梯度方法及传统的演化算法相比，由于其所具有的分布式、自组织性、协作性、鲁棒性和实现简单等特点，使其在没有全局信息的情况下，为寻找复杂问题特别是典型的系统复杂性问题(如NP问题等)的求解方案提供了快速、可靠的基础，为人工智能、认知科学等领域的基础理论问题的研究开辟了新的途径，同时也为诸如实际优化、工业动态生产控制、工程设计优化、数据挖掘、电子系统优化等实际工程问题提供了新的解决方案。因此，无论从理论研究还是应用研究的角度出发，群智能理论及其应用研究都是具有重要学术意义和现实价值的，它也越来越受到国际智能计算等相关研究领域学者的关注，逐渐成为一个新的重要的研究方向。 1.2基本粒子群优化算法 1995年，Kennedy博士和Eberhart博士受自然界中鸟群运动模型的启发提出了一种新的基于种群的搜索算法——PSO算法\[3\]。在PSO算法中，它把所求解问题空间中可能解的位置看成是鸟群运动模型中的栖息地，然后通过个体之间的信息交互，逐步提高在求解过程中发现较好解的可能性，并指引群体中所有的粒子朝着可能解的位置不断聚集。PSO算法相对于其他进化算法的最大优势在于实现简单和具有更强的全局优化能力。为此，算法一经提出，立刻引起了学术界的广泛关注，并在短短的几年时间里出现大量的研究成果，形成了一个研究热点。大量实验结果表明，PSO算法能够解决GA所能解决的各类优化问题，也显示出PSO算法确实具有强大的生命力\[4\]。 1.2.1粒子群优化算法的基本原理 PSO算法的思想来源于社会认知理论，体现了群智能的特征——简单智能的主体通过简单合作表现出复杂智能行为。根据社会认知理论，可以将PSO算法的求解概括为评价、比较和模仿三个过程\[2\]： (1)评价过程对各种激励进行评估，根据正反馈或负反馈、吸引或排斥等激励特性对其进行排序。这种行为特征在自然界中普遍存在，有机生命只有通过对外部激励的评价，才能完成对环境的学习。PSO算法中对环境的自适应学习过程也包含了这种评价过程。 (2)比较过程指粒子群中的个体对其他个体标准进行测量，并与自身条件相比较，从而确立自身的学习和修正动机。 (3)模仿过程粒子群中的个体根据自身判断模拟其他个体行为的过程，这是自然界中普遍存在的一种非常有效的学习模式，通常只模拟那些优于自身的个体。 通过以上三个过程的有机结合即可构成能适应复杂环境变化、解决困难问题的简单社会个体，并以计算机程序的形式实现。 在PSO算法中，可以将种群中的每个个体看成是在寻优空间中的一个没有质量，也没有体积的粒子，个体在搜索空间中以一定的速度飞行，根据个体与群体的飞行经验的综合分析结果动态调整飞行速度，逐渐向问题空间的更好区域移动。可以用粒子的位置来表示被优化问题在搜索空间中的潜在解，粒子飞翔的方向和距离可以通过粒子的速度来加以控制，而每个粒子的优劣则可以通过一个适应度值(fitness value)函数来加以评价。PSO算法初始化为一群随机粒子，然后通过追随当前最优粒子进行不断迭代的搜索直至找到最优解或有效解。在每一次迭代过程中，算法主要是通过跟踪个体极值pbest和全局极值gbest来更新各个粒子。其中，个体极值是目前粒子本身所找到的最优解，而全局极值则是整个种群目前所找到的最优解。 文献\[5\]指出PSO算法与其他进化算法之间存在许多不同之处。首先，GA等一些进化算法主要是通过交叉(crossover)和变异(mutation)等遗传操作来控制算法的运作，而PSO算法则是通过粒子的速度来决定粒子的搜索过程，从而PSO算法不但要维护位置信息，还要维护飞行矢量。其次，PSO算法具有记忆能力这一重要特点，算法中的每个粒子可以保存各自搜索到的最好位置，所得到的新的全局最优位置虽然对历史记录毫无影响，但却会影响其飞行矢量，从而使搜索和记忆在某种程度上分离\[6\]。最后，PSO算法还拥有与GA等其他进化算法不同的信息共享机制。前者是通过gbest和pbest这两个极值来传递信息给其他粒子，这是一个通过追随当前最优粒子的单向信息流动过程，而后者则主要是通过染色体(chromosomes)来实现，从而是一个整个种群比较均匀地向最优区域进行移动的过程。 1.2.2基本粒子群优化算法模型 PSO算法最初应用于连续空间的优化，在连续空间中，算法的数学描述如下： 设粒子群的种群规模为M，决策空间n维，其中粒子i在时刻t的坐标位置可以表示为Xti=(xti1,xti2,…,xtin),i=1,2,…,M，粒子i的速度定义为每次迭代中粒子移动的距离，用Vti=(vti1,vti2,…,vtin)表示，则粒子i在时刻t的第j(j=1,2,…,n)维子空间中的飞行速度和位置根据下式进行调整：vtij=wvt-1ij+c1r1(pij-xt-1ij)+c2r2(gj-xt-1ij)(1.1) vtij=vmax ,[]vtij>vmax -vmax ,[]vtij<－vmax (1.2) xtij=xt－1ij+vtij(1.3)其中，w为惯性权值(inertia weight)，c1和c2为加速因子(acceleration constants)，r1和r2是在\[0,1\]范围内的两个随机数，通常使用一个常量Vmax，即最大速度来限制粒子的速度，以改善搜索结果。gj既可以表示整个群体中的历史最优位置记录，即全局极值gbest，也可以是局部粒子群的历史最优位置。此时gj可改为lj，即表示局部极值lbest，公式中是采用全局极值gbest还是局部极值lbest主要是由PSO算法的邻近拓扑结构来决定，具体分析可见133节，而pij则是当前粒子的历史最优位置记录，即个体极值pbest。 粒子的运动过程由公式(1.1)~公式(1.3)共同作用，粒子在运动过程中的速度增量与其自身的历史飞行经验和群体飞行经验紧密相关，并受最大飞行速度的限制。以二维空间为例，图1.1描述了PSO算法中粒子根据公式(1.1)~公式(1.3)移动的原理。 图1.1粒子运动原理 vt—当前速度；vt+1—改进后的速度；xt—目前搜索到的点；xt+1—改进后的搜索点； vpbest—基于个体极值的速度；vgbest—基于全局极值的速度 从公式(1.1)可以看出，粒子的速度更新模型主要由以下三个部分组成\[2\]：①第一部分为粒子以前的速度对粒子飞行轨迹的影响，主要表示粒子对当前自身运动状态的信任，它主要是一个通过对粒子前一时刻的速度乘一个称为“惯性权值”的控制因子来实现惯性运动的过程；②第二部分为“认知(cognition)”部分，表示粒子自身经验对粒子运动轨迹的影响，也就是对粒子本身的思考，具体体现在粒子自身最优位置与当前位置之间的距离；③第三部分为“社会(social)部分”，表示群体经验对粒子运动轨迹的影响，也就是粒子之间的信息共享与相互合作，具体体现在群体最优位置与粒子当前位置之间的距离。后面这两个部分主要是通过两个称为“加速因子”的控制因子来进行调整。 1.2.3基本粒子群优化算法流程 基本的粒子群优化算法流程可具体描述如下\[2\]： Step 1： 初始化所有粒子(群体规模为M)，在允许范围内随机设置粒子的初始位置和速度，每个粒子的局部最优解pbest 设为其初始位置，pbest中的最好值设为gbest； Step 2： 评价每个粒子的适应值，根据适应度函数计算每个粒子的目标函数； Step 3： 更新每个粒子所经过的最好位置pbest； Step 4： 更新群体所经历过的最好位置gbest； Step 5： 根据公式(1.1)~公式(1.3)更新当前粒子的速度和位置； Step 6： 检查终止条件(通常为达到最大迭代次数，或者取得足够好的适应值，或者最优解停滞不再变化)是否满足，如果满足则终止迭代，否则返回Step 2。 图1.2基本粒子群优化算法流程图基本PSO算法流程图如图1.2所示。 1.2.4参数分析与设置 在PSO算法中存在几个显参数和隐参数，它们的值可以被调整，以产生算法搜索问题空间的方式变化。算法参数分析是PSO算法研究中的重要问题之一，许多研究人员对参数的选择及其对算法性能的影响进行了大量的分析和实验，为PSO算法的理论和应用研究奠定了坚实的基础。在基本PSO算法中，需要调节的参数主要有种群规模M、最大速度Vmax、惯性权值w以及加速因子c1和c2等。 1. 种群规模 一般情况下，种群规模在20~40区间取值就能保证对解空间进行充分的搜索，而且对于大部分问题，种群规模取10就足以取得较好的结果，但对于一些特定类别或者比较难的问题，种群规模甚至有时需要在100~200区间取值。 2. 最大速度 最大速度Vmax决定当前位置与最好位置之间区域的分辨率(或精度)。如果Vmax太大，粒子可能会飞过好解；如果Vmax太小，粒子不能在局部好区域之外进行足够的探索，导致容易陷入局部最优值。Vmax通常设定为粒子的范围宽度，例如，粒子 (x1，x2，x3)，x1 属于\[-10，10\]，那么Vmax的大小就是10。 3. 惯性权值 在公式(1.1)中，如果没有后面两个部分，即c1=c2=0，粒子将一直以当前的方向飞行，直到到达边界。由于它只能搜索有限区域，所以很难找到较好的解，而加上后面两部分之后，粒子则有扩展搜索空间的趋势。 性质1.1\[7\]惯性权值的设置影响了粒子的全局搜索能力与局部搜索能力之间的平衡。 从速度更新模型的公式(1.1)可以看出，公式的第一部分是PSO算法中的一个关键部分，它主要提供了粒子在搜索空间中飞行的动力，并表示了粒子以前的速度对粒子飞行轨迹的影响，而惯性权值就是一个用来表征粒子以前经历过的速度对当前速度的影响程度的数字量。因此，惯性权值的设置影响了粒子的全局搜索能力与局部搜索能力之间的平衡。 性质1.2\[7\]使用较大的惯性权值，算法具有较强的全局搜索能力。 从公式(1.1)和性质1.1可知，惯性权值是决定保留多少上一时刻的速度，从而取较大的值可以加强搜索以前所未能达到区域的能力，有利于增强算法的全局搜索能力并跳出局部极小点。而取较小的值则说明当前算法主要是停留在当前解的附近搜索，从而有利于提高算法的局部搜索能力，并加速算法的收敛。 因此，该参数对算法的性能影响很大，其大小控制着以前速度对当前速度的影响，体现了全局搜索与局部搜索的一个折衷\[8\]，对PSO算法的收敛性起着至关重要的作用。目前对惯性权值w的调整策略主要有线性变化、模糊自适应和随机变化等。其中应用最多的是线性递减策略，Shi认为这样可以在开始优化时搜索较大的解空间，得到合适的粒子，然后在后期逐渐收缩到较好的区域进行更精细的搜索，以加快收敛速度\[9\]。 4. 加速因子 加速因子c1和c2是一组调整粒子自身经验与群体经验影响粒子运动轨迹的重要参数。如果c1值为0，则粒子仅有群体经验作用于粒子的运动，这时它的收敛速度可能较快，但对一些复杂问题可能容易导致局部收敛；如果c2值为0，则仅有自身经验对粒子的运动起作用，群体中的粒子之间不具备信息交互的能力，那么，一个规模为M的群体就等同于运行了M次单个粒子，这就失去了群智能算法本身所具备的特性，从而难以得到最优解；如果c1和c2均为0，则粒子不包含任何的经验信息并只能搜索有限区域，从而难以找到较好的解。 可以把加速因子c1和c2看成一个控制参数，即φ=c1+c2。如果φ=0，粒子的坐标值X只是简单的线性增加。如果φ非常小，则对粒子速度的控制很微弱，因此群体的运动轨迹随时间推移而变化得非常缓慢。当φ较大时，粒子的空间位置变化频率增大，粒子变化步长也随之增大。一般情况下，当φ＝4.1时，具有较好的收敛效果。 1.3粒子群优化算法的改进综述 在现实生活中，不同领域的优化问题不但种类极其繁多，而且具备各自不同的特点。为此，PSO算法自提出至今，引起了学术界的广泛关注并开展了大量的研究工作，这也有力地推动了该算法的发展。目前对PSO算法的改进研究主要体现在算法的参数选择与设计、领域拓扑结构、群体组织与进化、融合进化计算等概念的混合算法等几个方面，然而正如文献\[10\]中的“没有免费的午餐”这一理论所认为的，这些改进算法都需要根据具体问题的领域知识等对算法参数进行相应的设置，从而在提高某种性能的同时也付出其他代价。 1.3.1基于惯性权值的改进 从前面的分析可以知道，公式(1.1)的第一部分主要提供了粒子在搜索空间飞行的动力，其中的惯性权值用来表征粒子以前经历过的速度对当前速度的影响程度，于是，惯性权值的设置影响了粒子的局部搜索能力与全局搜索能力之间的平衡\[6,7\]。 这里可以通过令c1 = c2 =0来简要解释惯性权值w的效果。假设初始速度非零，则当w大于1.0时，算法将使粒子的速度不断增大直至速度达到最大速度Vmax为止；而当w小于1.0时，算法将使粒子的速度不断减小直至粒子最终速度为0，停止粒子的运动过程。Shi和Eberhart在文献\[11\]中研究了w在范围\[0, 1.4\]内的影响，并声称选择\[0.8, 1.2\]范围内的w值会导致收敛加速，而选择大于1.2的w值则会导致收敛失败。 基于惯性权值的设置对PSO算法的性能起着至关重要的作用，目前已有很多研究者针对惯性权值的改进研究开展了一系列工作，并对算法作了不同程度的改进\[7,8,11\|15\]，同时也取得了一些研究成果。 1. 惯性权值线性递减 Shi和Eberhart在文献\[11\]中所取得的研究成果，对于洞察惯性权值在PSO算法中的运作机理起到了一定的作用，在此研究的基础上，他们继而提出了一种基于惯性权值线性递减的PSO算法\[8,12\]。该算法为了保证算法的全局搜索能力，在算法运行初期使用较大的惯性权值，而为了保证算法的局部搜索能力，则在算法运行后期使用较小的惯性权值，惯性权值的具体计算公式如下：w=(w1－w2)×MaxIter-CurIter〖〗MaxIter+w2(1.4)其中，w1和w2是惯性权值的初始值和最终值，CurIter和MaxIter是算法的当前代数和最大迭代次数。 为验证该方法的有效性，文献中使用了4个不同的基准函数进行模拟仿真实验，发现这种参数调整方法确实提高了算法的性能和收敛速度，并且在w1 =0.9和w2=0.4时，算法的前1500次迭代效果更好。然而，该方法在解决多峰值函数问题时却容易陷入局部最优。 2. 模糊惯性权值 在文献\[13,14\]中，Shi和Eberhart提出了一种利用模糊控制系统对惯性权值进行自适应调整的方法，其基本思想就是利用模糊控制系统将对一个问题的语言描述转化成为一个具体的模型，然后通过数字输入来描述变量该如何调整\[15\]。 Shi和Eberhart把当前惯性权值以及与函数值所对应的目前为止发现的最优解f()作为模糊控制系统的两个输入，之后根据该系统所得到的输出结果来对惯性权值进行动态修正。由于不同范围的问题具有不同的函数值，Shi和Eberhart采用了公式(1.5)的规划方法对函数值f()进行规范化：fnorm()=f()－fmin 〖〗fmax －fmin (1.5)其中，fmax 和fmin 值与具体问题有关，须事先获知或能够预先估计值的大小。 为了对应输入变量所属的低、中、高三种模糊设置，Shi和Eberhart使用了以下3个隶属度函数： fleft_triangle(x)=1,[]xx1 x2－x〖〗x2－x1,[]x1≤x≤x2 0,[]xx2(1.6) ftriangle(x)=0,[]xx1 2x－x1〖〗x2－x1,[]x1≤x≤x2+x1〖〗2 2x2－x〖〗x2－x1,[]x2+x1〖〗2≤x≤x2 0,[]xx2(1.7) fright_triangle(x)=1,[]xx1 x－x1〖〗x2－x1,[]x1≤x≤x2 0,[]xx2(1.8)其中，x1和x2为决定函数形状位置的重要参数。 为了说明所提算法的有效性，Shi和Eberhart通过与线性递减惯性权值的PSO算法的实验结果进行比较，发现在确定的参数设置情况下，该算法对某些测试函数具有更好的效果。然而，该算法虽然在单峰值函数的表现相当优异，但对于多峰值函数，却难以找到最佳的惯性权值，并且模糊控制系统也难以区分算法的状态到底是陷入局部最小值还是靠近单峰值函数的最小值。此外，这种方法中的fmax 和fmin 值事先也很难预知，从而实现起来比较困难。 3. 随机惯性权值 现实中所存在的许多环境随时间不断改变的动态优化问题需要构建具有一定非线性搜索能力的算法，为此，文献\[16\]提出了一种基于随机惯性权值方法的PSO算法，算法中的惯性权值按照下式进行随机调整：w=0.5+rand()〖〗2(1.9)其中，rand( )为0~1之间的一个随机数。 为了说明这种参数调整策略的有效性，文献\[16\]采用了一些著名的基准函数进行测试，实验结果表明，该策略在算法初期确实能够加速粒子的收敛，且对大部分优化函数都能找到相当好的解。 4. 惯性权值自适应调整策略 上述的改进算法确实能够提高算法的性能，并在单峰问题的测试中表现优异，但在多峰函数的测试中却出现算法容易过早收敛的现象。另外，上述所有的算法在同一代种群的速度更新过程中均使用同一惯性权值，也就是都把惯性权值作为一个全局参数。为此，我们在进一步分析惯性权值关键作用的基础上，提出了一种在同一代种群中使用不同的惯性权值进行更新的调整策略，并给出了一种相应的PSO算法\[6,7\]。 性质1.3如果某个粒子的适应度较高，则意味着该粒子的当前位置比其他粒子更靠近全局最优解。 通过前面的分析可以知道，粒子的适应度值大小影响到在该粒子的周围区域发现全局最优解的概率，较高适应度值的粒子比其他粒子更靠近全局最优解，从而可以吸引其他粒子向该粒子周围区域搜索，这时就可能需要相应地提高其局部搜索能力以求能够对周围区域进行细致的搜索，而为了增大适应度值较低的粒子搜索到最优解的概率，则应尽快将它们加入到对较优粒子周围区域的搜索行列中，以提高算法的收敛速度。 性质1.4粒子间的差异性逐渐缩小，算法有可能在局部最优解的附近停止。 随着所有粒子在算法运行后期逐渐聚集在一起，粒子之间的差异性也逐渐缩小，从而造成速度逐渐趋于0并很有可能陷入局部最优解。这时可以通过对不同粒子使用不同的惯性权值，以增大粒子之间的差异，并可以很好地控制粒子的全局搜索能力与局部搜索能力之间的平衡。 定义1.1(佳粒子距)\[17\]在粒子群的优化过程中，可以根据适应度值的大小对当前群体中的全体粒子集(形如f1f2…fM)进行降序排序，并形成一个排好序的新粒子集(形如g1g2…gM)，其中M为种群规模，fi为第i个粒子的适应度值，gj∈{f1,f2,…,fM}，1≤i, j≤M。这里，相应地把新粒子集中处于第一个位置的粒子称为佳粒子，从而可以把第i个粒子在新粒子集中的位置(即下标)称为个体i的佳粒子距离(简称佳粒子距)，并记为di。 通过引入佳粒子距的概念，我们相应地建立了一个具体的惯性权值调整模型，具体形式如下：w(i,x)=u(di,x)*［w1+(w2－w1)*CurIter/MaxIter］(1.10)其中，MaxIter为最大迭代次数，CurIter为当前迭代次数，w1、w2分别为w的初始值和最终值，而u(di, x)为粒子个体惯性权值的控制因子，具体形式如下：u(di,x)=1+α,[]di≤S1M 1,[]S1M0，β>0。 为了说明该策略的有效性，在文献\[7,17\]中，作者分别通过使用多种基准函数和典型TSP问题与惯性权值线性递减PSO算法作测试比较，实验结果表明，该惯性权值调整策略确实能够在一定程度上很好地控制算法全局收敛能力和局部收敛能力之间的平衡，从而能够加快算法的收敛速度，并能跳出局部最优解。 1.3.2基于加速因子的改进 公式(1.1)的第二部分和第三部分分别代表了粒子的自身经验和群体经验对粒子飞行轨迹的影响，其中第二部分主要是促使粒子朝着自身所经历过的最好位置进行移动，而第三部分则是促使粒子向群体发现的最好位置进行移动，而这两部分主要是通过加速因子c1和c2来进行控制和调整的。 由此可见，加速因子c1和c2主要反映了粒子群之间的信息交流，设置较大的c1值会使粒子过多地依赖自身的经验信息，从而造成过多地在局部范围内徘徊，而设置较大的c2值则会促使粒子过早收敛于局部最优值。为了平衡这种随机因素，Shi和Eberhart在文献\[8\]中建议，在一般情况下c1和c2均设为2。目前大部分算法都采用了这个建议，不过也有文献采用不同的c1和c2设置方法，但是它们一般在0~4范围内并取相同的值。 为了进一步考查加速因子的作用，Suganthan在文献\[18\]中提出了一种线性递减的加速因子调整策略，虽然实验结果表明这种调整策略并不如使用加速因子均为2的调整策略，但作者通过对实验结果进行仔细分析之后，认为其实在整个搜索过程中加速因子不必一直保持不变。 基于此理念，Ratnaweera和Halgamuge提出了一种在算法初期使用较大c1值与较小c2值而后期逐渐减小c1值并增大c2值的加速因子调整策略\[19\]，这样可以保证算法初期能够在局部范围内进行比较细致的搜索，不必直接向全局最优位置移动，而在算法后期则尽量加快算法收敛的速度。具体的加速因子调整公式如下所示：c1=(c1e－c1s)CurIter〖〗MaxIter+c1s(1.12) c2=(c2e－c2s)CurIter〖〗MaxIter+c2s(1.13)其中，MaxIter为最大迭代次数，CurIter为当前迭代次数， c1s，c1e分别为c1的初始值和最终值，c2s，c2e则分别为c2的初始值和最终值。 通过实验结果作者发现，当c1由2.5线性递减至0.5而c2由0.5线性递增至2.5时，算法获得的适应度值是最优的。然而，这种方法虽然在单峰值函数的测试中表现突出，但在多峰值函数的测试中表现并不是很理想，且容易导致过早收敛。 为了解决上述问题，与文献\[19\]相反，文献\[20\]考虑了c1和c2的非对称变化情况，并发现，当c1由2.75线性递减至1.25，c2由0.5线性递增至2.25时，对大多数基准函数都能得到相对较好的适应度值，且比文献\[19\]的结果略好。 1.3.3基于邻近群拓扑的改进 根据公式(1.1)中对群体的全局最优位置的选择方法，PSO算法可以分为全局gbest模型和局部lbest模型两种模式\[6\]： (1)gbest模型该模型将整个种群中的最优粒子作为整个算法的唯一最优解，群体中的所有粒子都使用该最优值(gbest)来更新各自的速度和位置，并向这个最优粒子的方向不断靠拢。 (2)lbest模型该模型首先根据所选的拓扑结构将整个种群划分为若干个子种群，然后种群中的每个粒子都根据各自所属子种群的局部最优解(lbest)来不断更新自己的速度和位置。由此可见，该模型的每个粒子在进行速度和位置更新时所选择的局部最优值可能并不一样。 在上述两种不同邻近群拓扑的PSO算法中，粒子之间的信息流向如图1.3所示。 从图1.3(a)可以看出，每个粒子的信息可以被其他所有粒子获得，从而算法会促使它们追随发现较好位置的那个粒子移动并不断向该粒子靠拢以寻求最优解，这种方式虽然能够加速算法的收敛速度，但却容易陷入局部最优解。而从图1.3(b)中可以看出，每个粒子所获得的群体最优位值不尽相同，从而导致不同粒子的收敛方向也不一定相同，这种方式的收敛速度虽然比前一种方式要慢，但却不容易陷入局部最优解。从上面的分析可知，选择不同的邻近群拓扑会在一定程度上影响算法的性能。基于lbest模型产生了多种变形拓扑，图1.4为其中的两种变形拓扑。 图1.3两种不同邻近群拓扑的PSO []图1.4两种变形拓扑 文献\[21，22\]分别对不同连接拓扑的PSO算法进行了测试，实验结果都表明，选择一种合适的邻近群拓扑对于提高算法的性能至关重要，但如何选择邻近群拓扑与具体的问题关系很大，且无法很好地找到一种对所有基准函数都最适合的邻近群拓扑。例如，使用基于信息交流率高的轮形拓扑虽然能够在很大程度上提高算法的收敛速度，但却只适用于单峰函数。 1.3.4基于种群规模的改进 从前面的PSO算法参数分析可知，种群规模的大小也是标准PSO算法的关键参数之一，算法在通常情况下使用的粒子数取值范围为20~40。 同样地，如何设定种群规模的大小也与具体问题有关\[23\]。一般地，种群规模的大小在算法的运行过程中是保持不变的，但至今为止仍无法给出一个最具优势的值。为此，文献\[24\]尝试提出了一种不断在算法运行过程中动态调整种群规模的思路： (1)如果种群的改进质量达不到预先所设置的阈值，那么可以通过为邻近群中的最优粒子增加一个自己的“复制”来扩大种群规模； (2)如果种群的改进质量达到了预先所设置的阈值，那么可以通过删除邻近群中的最差粒子来缩小种群规模。 Clerc在文献\[24\]中还通过设置一个能量函数来评价动态规模PSO算法和固定规模PSO算法的性能变化，其中，单个粒子和整个种群的能量计算公式分别如公式(1.14)和公式(1.15)所示，具体含义可参见文献\[24\]。ep,i(t)=f(xi(t))－s〖〗ε(1.14) Ep(t)=G∑iep,i(t)(1.15)