粒子群优化算法及其参数设置

2010届信息与计算科学专业毕业设计

3.粒子群优化算法的改进策略

由于PSO中粒子向自身历史最佳位置和邻域或群体历史最佳位置聚集，形成粒子种群的快速趋同效应，容易出现陷入局部极值、早熟收敛或停滞现象[12-14]。同时，PSO的性能也依赖于算法参数[15]。为了克服上述不足，各国研究人员相继提出了各种改进措施。本文将这些改进分为4类：粒子群初始化、邻域拓扑、参数选择和混合策略。

3.1 粒子群初始化

研究表明，粒子群初始化对算法性能产生一定影响[16]。为了初始种群尽可能均匀覆盖整个搜索空间，提高全局搜索能力，Richard 和Ventura[17]提出了基于centroidal voronoi tessellations (CVTs)的种群初始化方法；薛明志等人[18]采用正交设计方法对种群进行初始化；Campana 等人[19]将标准PSO迭代公式改写成线性动态系统，并基于此研究粒子群的初始位置，使它们具有正交的运动轨迹；文献[16]认为均匀分布随机数进行初始化实现容易但尤其对高维空间效果差，并另外比较了3种初始化分布方法。

3.2 邻域拓扑

根据粒子邻域是否为整个群体，PSO分为全局模型gbest和局部模型gbest [20]。对于gbest模型，每个粒子与整个群体的其他粒子进行信息交换，并有向所有粒子中的历史最佳位置移动的趋势。Kennedy[21]指出，gbest模型虽然具有较快的收敛速度，但更容易陷入局部极值。为了克服gbest全局模型的缺点，研究人员采用每个粒子仅在一定的邻域内进行信息交换，提出各种gbest局部模型[21,]。根据现有的研究成果，本文将邻域分为空间邻域(spatial neighborhood)、性能空间(performance space)邻域和社会关系邻域(sociometric neighborhood)。空间邻域直接在搜索空间按粒子间的距离(如欧式距离)进行划分，如Suganthan[23]引入一个时变的欧式空间邻域算子：在搜索初始阶段，将邻域定义为每个粒子自身；随着迭

9

任侃：粒子群优化算法及其参数设置

代次数的增加，将邻域范围逐渐扩展到整个种群。性能空间指根据性能指标(如适应度、目标函数值)划分的邻域，如文献[24]采用适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。社会关系邻域通常按粒子存储阵列的索引编号进行划分

[25]

，这也是研究最多的一种划分手段，主要有[21]：环形拓扑(ring or circle topology)、

轮形拓扑(wheel topology)或星形拓扑(star topology)、塔形拓扑(pyramid topology)、冯－诺以曼拓扑(Von Neumann topology)以及随机拓扑(random topology)等。针对不同的优化问题，这些拓扑的性能表现各异；但总的来说，随机拓扑往往对大多数问题能表现出较好的性能，其次是冯－诺以曼拓扑[22]。M. Clerc[25]对随机拓扑进行了进一步分析，并在2006年版和2007年版的标准PSO[23]中采用了随机拓扑。此外，文献[21]提出动态社会关系拓扑(Dynamic sociometry)，初始阶段粒子采用环形拓扑(ring-type topology)，随着迭代次数的增加，逐渐增加粒子间连接，最后形成星形拓扑(star-type topology)。

此外，还有其它一些主要对群体进行划分的邻域结构(本文暂称“宏观邻域”；则上述邻域称为“微观邻域”)。文献[19]引入了子种群，子种群间通过繁殖(Breeding)实现信息交流。Kennedy[20]提出了社会趋同(Stereotyping)模型，使用簇分析将整个粒子群划分为多个簇，然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置。X. Li[21]根据粒子相似性动态地将粒子群体按种类划分为多个子种群，再以每个子种群的最佳个体作为每个粒子的邻域最佳位置。Stefan Janson等人[22]提出等级PSO(hierarchical particle swarm optimizer, HPSO)，采用动态等级树作为邻域结构，历史最佳位置更优的粒子处于上层，每个粒子的速度由自身历史最佳位置和等级树中处于该粒子上一个节点的粒子的历史最佳位置决定。文献[13]采用主－仆模型(master–slaver model)，其中包含一个主群体，多个仆群体，仆群体进行独立的搜索，主群体在仆群体提供的最佳位置基础上开展搜索。文献[14]将小生境(niche)技术引入到PSO中，提出了小生境PSO(Niching Particle Swarm Optimizer)。文献[15]采用多群体进行解的搜索。文献[14]则每间隔一定代数将整个群体随机地重新划分，提出动态多群体PSO。

在标准的PSO算法中，所有粒子仅仅向自身和邻域的历史最佳位置聚集，而没有向邻域内其他个体(即使这些个体很优秀)学习，造成信息资源的浪费，甚至因此而陷入局部极值；考虑到此因素，Kennedy 等人[17]提出了全信息粒子群(fully informed particle swarm, FIPS)，在FIPS中，每个粒子除了自身和邻域最佳历史位置外，还学习邻域内其他粒子的成功经验。

上述粒子间学习是在整个D维空间中构造邻域进行的，这样当搜索空间维数较高时往往容易遭受“维数灾(curse of dimensionality)”的困扰[14]。基于这方面的考

10

2010届信息与计算科学专业毕业设计

虑，Van den Bergh等人[18]提出了协作PSO(Cooperative PSO)算法，其基本思路就是采用协作行为，利用多个群体分别在目标搜索空间中的不同维度上进行搜索，也就是一个优化解由多个独立群体协作完成，每个群体只负责优化这个解矢量部分维上的分量。Baskar和Suganthan[19]提出一种类似的协作PSO，称为并发PSO(concurrent PSO， CONPSO)，它采用两个群体并发地优化一个解矢量。近来，El-Abd 等人[20]结合文献[18,19]的技术，提出了等级协作PSO(hierarchal cooperative PSO)。

无论是粒子群在D-维的搜索还是多个粒子群在不同维上的协作搜索，其目的都是为了每个粒子能够找到有利于快速收敛到全局最优解的学习对象。J. Liang 等人[4]提出了一种既可以进行D-维空间搜索、又能在不同维上选择不同学习对象的新的学习策略，称为全面学习PSO (Comprehensive Learning Particle Swarm Optimizer，CLPSO)。与传统PSO只向自身历史最佳位置和邻域历史最佳位置学习不同，CLPSO的每个粒子都随机地向自身或其它粒子学习，并且其每一维可以向不同的粒子学习；该学习策略使得每个粒子拥有更多的学习对象，可以在更大的潜在空间飞行，从而有利于全局搜索。CLPSO的速度更新公式为：

） vij(t)?wvij(t?1)??r(pfi(j),j)?x（ （3.1） ijt?1其中?为加速因子，r为[0,1]内的均匀随机数，fi(j)表示粒子i在第维的学习对象，它通过下面的策略决定：产生[0,1]内的均匀随机数，如果j该随机数大于为粒子i预先给定的学习概率pci，则学习对象为自身历史最佳位置；否则，从种群内随机选取两个个体，按锦标赛选择(tournament selection)策略选出两者中最好的历史最佳位置作为学习对象。同时，为了确保粒子尽可能向好的对象学习而不把时间浪费在较差的对象上，上述学习对象选择过程设定一个更新间隔代数(refreshing gap)，在此期间的学习对象保持上次选择的学习对象不变。

以上的各种邻域结构，无论是微观拓扑还是宏观邻域，也无论是在整个搜索空间进行信息交流还是以空间的不同维分量为单位协作搜索，都不主动改变邻域状态，而只是在给定的邻域内进行学习交流，本文称之为PSO的被动局部模型。还有一类局部模型就是主动改变粒子邻域空间，避免碰撞和拥挤，本文称之为PSO的主动局部模型。Blackwell 等人[3]将粒子分为自然粒子和带电粒子，当带电粒子过于接近时产生斥力，使之分开以提高粒子多样性；L?vbjerg 等人为每个粒子引入与相邻粒子距离成反比的自组织危险度(self-organized criticality)指标，距离越近

11

任侃：粒子群优化算法及其参数设置

则危险度越高，当达到一定阈值后，对该粒子进行重新初始化或推开一定距离降低危险度，达到提高群体多样性的目的；文献[15]提出一种带空间粒子扩展的PSO，为每个粒子赋一半径，以检测两个粒子是否会碰撞，并采取随机弹离、实际物理弹离、简单的速度—直线弹离等措施将其分开。

3.3 混合策略

混合策略混合PSO就是将其它进化算法或传统优化算法或其它技术应用到PSO中，用于提高粒子多样性、增强粒子的全局探索能力，或者提高局部开发能力、增强收敛速度与精度。这种结合的途径通常有两种：一是利用其它优化技术自适应调整收缩因子/惯性权值、加速常数等；二是将PSO与其它进化算法操作算子或其它技术结合。文献[16]将蚂蚁算法与PSO结合用于求解离散优化问题；Robinson 等人[17]和Juang[18]将GA与PSO结合分别用于天线优化设计和递归神经网络设计；文献

[19]

将种群动态划分成多个子种群，再对不同的子种群利用PSO或GA或爬山法进行

独立进化；Naka等人[10]将GA中的选择操作引入到PSO中，按一定选择率复制较优个体；Angeline [11]则将锦标赛选择引入PSO 算法，根据个体当前位置的适应度，将每一个个体与其它若干个个体相比较，然后依据比较结果对整个群体进行排序，用粒子群中最好一半的当前位置和速度替换最差一半的位置和速度，同时保留每个个体所记忆的个体最好位置；El-Dib 等人[12]对粒子位置和速度进行交叉操作；Higashi [13]将高斯变异引入到PSO中；Miranda等人[14]则使用了变异、选择和繁殖多种操作同时自适应确定速度更新公式中的邻域最佳位置以及惯性权值和加速常数；Zhang等人[8]利用差分进化(DE)操作选择速度更新公式中的粒子最佳位置；而Kannan 等人[18]则利用DE来优化PSO的惯性权值和加速常数。

此外，其它一些搜索技术与PSO结合以提高算法的局部搜索能力，如文献[9]提出一种基于PSO和Levenberg-Marquardt的混合方法;文献[10]将PSO与单纯形法相结合；文献将PSO与序贯二次规划相结合；文献[12]将模拟退火与PSO结合；文献[13]将禁忌技术与PSO结合；文献[8]将爬山法与PSO结合；文献[15]将PSO与拟牛顿法结合。

还有作者引入其它一些机制，以改进PSO的性能。文献[6]根据耗散结构的自组织性，提出一种耗散粒子群优化算法(dissipative PSO)。该算法通过附加噪声持续为粒子群引入负熵(negative entropy)，使得系统处于远离平衡态的状态，又由于群体中存在内在的非线性相互作用，从而形成自组织耗散结构，使粒子群能够“持续进化”，抑制早熟停滞。文献[7]将自然进化过程中的群体灭绝现象引入PSO，在微

12