赵永乐 姜 军

（华中科技大学自动化学院 武汉 430074）

1 引言

在实际科学研究和工程应用中，通常将实际问题经过数学建模后转化为数值函数的优化问题［1］，而函数优化问题成为近十几年来研究热点。随着问题规模的不断增加，对优化方法的要求也越来越高。

传统优化算法，如梯度法、共轭梯度法、牛顿法、单纯形法等，通常针对一些确定形式且需要一定约束条件限制的问题时，如在对凸优化问题［2］等具有明确最优解的情况下，具有较好的性能。但在实际应用中出现越来越多的较大规模的、复杂的问题，具有高维度、多约束、多局部极值、非凸或者难以建立合适数学模型的特点，使得传统方法受到一定的限制。而启发式的优化算法如：遗传算法［3］、粒子群算法［4］、模拟退火算法［5］、蚁群算法［6］等便是应对这种问题的一种途径，其中的粒子群算法因其简单性和有效性的特点，更受到很多学者的关注和研究［7～8］。

粒子群算法是受到鸟群之间沟通方式的启发而提出的一种概率搜索优化算法，其源于群智能，因其简单性和有效性，具有很大的研究价值。但多数随机优化算法（包括粒子群算法）和遗传算法的性能会随着搜索空间的维度增加而急剧下降，计算时间会呈指数级增长，同时容易导致粒子的早熟而陷入局部最优，这种现象被称作“维数灾难［9］”。近年来国内外学者提出了很多改进算法［10～13］来试图解决这些问题。

文献［11］中提出一种协作进化遗传算法（co⁃operative coevolutionary genetic algorithm，CCGA）可以将整个问题空间分解成多个小维度的空间的组合，并使用遗传算法在每个小的搜索空间内进行搜索，再将各个子空间的结果组合成整个问题的解来进行评估。文中表明这种维度空间分解的方法对比基本GA算法获得了明显的性能提升。

文献［12］将上述思想应用到粒子群算法，提出两种协作PSO模型，分别为CPSO-Sk和CP⁃SO-Hk。CPSO-Sk算法直接将CCGA的思想应用到标准PSO算法，CPSO-Hk将标准PSO和CP⁃SO-Sk进行结合。这两种算法在多数测试函数上获得了明显的性能提升。

本文在上述思想的基础上，提出一种层级协作粒子群算法即CPSO-Hierarchy（Hierarchy coopera⁃tive particle optimization），设计出一种CPSO-Sk和标准PSO之间进行切换的层级策略，即每个种群所包含的维度逐渐增加，充分利用不同维度的子空间的信息，将标准PSO算法的开发能力和CPSO的探索能力进行结合，具有一定的跳出局部最优的能力，在9个标准函数中的大部分上获得了更好的收敛结果，提高了算法的鲁棒性。

2 粒子群算法

2.1 标准粒子群算法

粒子群（Particle Swarm Optimization，PSO）算法，由Kennedy和 Eberhart［4］于1995年提出，是一种受鸟群觅食行为启发的基于种群的优化技术。PSO是由一系列粒子组成的种群来进行整个优化过程，每一个粒子代表优→化问题的一个候选解。一个粒子由n维的向量 x来表示，代表这个粒子的位置；每一个粒子都具有一个由被优化函数决定的适应→值，代表这个候选解的质量；以及一个速度向量 v，决定粒子运动速度的大小和方向。每一个粒子可以记录其搜索到的最佳的位置pbest，同时可以获取邻近粒子发现的最佳位置gbest。PSO算法通过在整个搜索空间中移动粒→子来搜索最优值。在每次迭代t，通过增加速度vi(t)到t-1时刻的位置向量上来更新粒子i的位置x→(t)：

i

粒子的速度由下式来更新：

上式中ω是惯性权重，控制前一时刻的速度值对新速度的影响；加速因子c1是用来扩展粒子认知能力的参数（式（2）中的第二项），c2控制整体种群状态的影响（式（2）中的第三项）；r→(t)和r→(t)

12为服从均匀分布U(0 ，1)的随机值；yi(t)为粒子i的个体最优值，即该粒子当前时刻搜索到的最优位置；ŷ(t)为粒子i的邻域区域的所有粒子搜索到的最优位置。因此每个粒子逐渐被吸引到该粒子目前的最优位置以及种群整体最优位置的方向。

粒子群算法的流程如下图所示：

图1 PSO算法的伪代码

2.2 协作粒子群算法CPSO

协作学习的思想首先在文献［11］中被应用在GA领域。Potter认为适应函数的每一维均可以用一个独立的种群进行优化，这些种群可以共同协作产生整个问题的解向量。而文献［12］将这种协作学习的机制引入到PSO算法中，即使用N个各含M个1维粒子的种群进行优化，由于一个种群仅表示一维的搜索空间，无法直接得到这个种群中个体的适应值，文中设置了一个由每个种群中的最优粒子组成一个N维的背景向量。每个种群中的粒子只需替换背景向量中的对应维度，即可用其来评估该粒子的适应值。CPSO算法包含CPSO-S，CP⁃SO-Sk，CPSO-H和CPSO-Hk算法。其中CPSO-S把搜索空间的每一维作为一个种群进行优化，而CPSO-Sk算法把整个搜索空间分成k份，使用k个种群进行优化。因标准PSO算法具有跳出局部最优的特点，及CPSO-Sk算法更快的收敛速度，文中CPSO-H和CPSO-Hk算法就是将这两种优点结合在一起，使得CPSO-Hk包含两个阶段，第一阶段使用CPSO-Sk算法，第二阶段使用PSO算法，同时两个阶段进行一定的信息交互。

算法的流程如下图2所示。

图2 CPSO-S算法的伪代码

3 层级协作粒子群算法CPSOHierarchy

CPSO-Hk算法通过结合标准PSO算法和CP⁃SO-Sk算法的特点，获得了很好的效果提升，本文在此思想的基础上，将多个CPSO-Hk种群组以层级递进的方式连接起来，使用维度生长的策略，逐渐增加粒子的搜索维度，同时每个种群组之间的进行一定的信息交流，形成一种层级递进的结构，本文将此方法称作CPSO-Hierarchy算法。该算法充分利用不同维度尺度下的CPSO算法的特性，来增加整个种群的多样性。而如何确定多个k值成为一个难点，本文中根据文献［14］中实验得出的在k取6时获得相对较好的性能，设定多个种群中的k=｛6，3，1｝。

综合以上改进算法的描述，整个算法的流程如下图3所示：

图3 层次协同粒子群优化算法的流程图

4 实验设置与结果分析

文章使用［15］中的标准函数作为实验的对象，如下表1所示。所有的函数均为最小化问题定义如下：

D：问题维度；

所有的函数具有相同的搜索范围：[- 100，100]D

这些函数可以分成3组，单峰函数，基本多峰函数，复合函数。各组中使用的函数的特点如下表1所示。

对比方法和各自参数设置如下。

所有的方法迭代3×103次，或者达到一定的停止条件，所有的实验运行20次，结果取20次的平均值，并计算标准差来评估算法鲁棒性。分别针对30，60，90维的搜索空间。使用如下几种PSO算法进行试验：

标准PSO算法：参数设置为c1=1.49，c2=1.49，ω=0.72，vmax根据具体问题进行限制；

表1 Benchmark Functions

CPSO-S6：参数设置c1=1.49，c2=1.49，ω随时间线性下降，vmax根据具体问题进行限制，而搜索空间向量被分成6份；

CPSO-H6：一种混合方法，包含CPSO-S6种群和一个PSO种群，两个部分均使用参数为c1=1.49，c2=1.49，ω随时间线性下降，vmax根据具体问题进行限制。

CPSO-Hierarchy：同样为混合方法，包含多个CPSO-Sk种群和一个PSO种群，参数设置为c1=1.49，c2=1.49，ω随时间线性下降 vmax根据具体问题进行限制。

实验结果：表2、3、4分别列出各优化方法在30、60、90维Benchmark Functions的结果。

由表2、3、4分析可知，在9个测试函数上的结果显示文中提出的层次CPSO算法CPSO-Hierarchy在多数的函数上获得了最好的结果，CPSOH6算法在其他函数上获得较好的结果，而标准PSO算法的结果最差。结果验证了不同维度分组的策略可以很好的综合CPSO算法的快速收敛能力以及PSO算法跳出局部最小值能力的特性，并且充分利用在分组大小不同时这两种特性的不同特点，使得算法在陷入局部最优时，能够在不同维度分组的搜索空间中进行搜索，而发现在特定的维度分组时，可以影响整个维度空间的结果，并以此来跳出局部最优值。

本文分别使用标准PSO算法、CPSOH6算法和CPSO-Hierarch算法对9组特性各异的Benchmark Functions进行评估，以20次实验的均值和标准差来衡量算法的性能和鲁棒性，结果表明CPSO-Hi⁃erarch算法具有较好的结果，可以明显改进CPSOH6算法的优化能力，并且具有一定的鲁棒性。

表2 不同算法在30维Benchmark Functions上的结果

表3 不同算法在60维Benchmark Functions上的结果

表4 不同算法在90维Benchmark Functions上的结果

5 结语

本文在对CPSO算法中维度分组不同时算法表现出的不同性质进行分析的基础上，通过组合不同维度分组k的CPSO-Sk算法，得到比CPSOH6算法及标准PSO算法更好的收敛结果同时提高了算法的鲁棒性，使得算法更适用于不同的模型，增加算法的适用度。