郭 成,张万达,王 波,王加富

(1.昆明理工大学电力工程学院,云南 昆明 650504; 2.昆明理工大学机电工程学院,云南 昆明 650504;3.成都国龙信息工程有限责任公司,四川 成都 610031; 4.云南电网有限责任公司楚雄武定供电局,云南 武定 651600)

0 引 言

目前，对于高维复杂优化问题，进化算法在求解时有较好的表现，然而随着近些年数学和工程问题的复杂程度增加，随着决策变量的增加，目标函数维度也急剧增加[1-4]。在求解高维复杂优化问题时常常会遭遇维数灾难的情况，随着优化问题维数的增大，进化算法的优化性能显著下降[5-6]。近年来，由于粒子群算法具有鲁棒性强、设置参数少、收敛速度快等优点引起学者的关注，成为智能进化算法的一个重要的研究热点[7-8]。

随着优化问题复杂性的增加，为了满足求解高维复杂优化问题的需求，国内外很多学者从不同的角度改进标准粒子群算法。例如，de Campos Jr等人[9]针对多目标优化问题提出了并行多种群PSO策略，利用多群落双粒子群并行策略的算法进行求解。伍大清等人[10]为了解决不同形态的复杂问题，在混合策略自适应学习的基础上提出了基于并行粒子群优化算法。阴艳超等人[11]提出了一种多群落双向驱动协作搜索算法，构建了一种多群落双向驱动的进化新模式求解复杂优化问题。在大规模优化问题上，龙文等人[12]提出了一种改进鲸鱼优化算法，梁静等人[13]对种群粒子和决策变量的双重分组，提出了一种协同进化动态粒子群优化算法。黄晨晨等人[14]通过使用Logistic映射初始化灰狼种群,改变线性减小的距离控制参数为非线性来提高算法的探索与开发能力，提出了一种求解高维复杂函数的混合蛙跳-灰狼优化算法。在提高人工蜂群算法求解高维复杂优化问题的收敛性上，王艳娇等人[15]提出了一种改进人工蜂群算法。

综上所述，求解高维复杂优化问题的方法可分为：1)将高维复杂优化问题分解为子优化问题，再利用优化算法进行求解。2)设计动态自适应演化算法，实时调整进化策略，开发自适应进化算法。3)分解求解问题的时间和空间，开发并行进化算法。但每种解决方法都具有一定的局限性，如现有的问题分解技术不能完全保证得到所需的子问题，许多复杂优化问题无法分解为子优化问题，故上述问题难以运用分解的方法进行求解。

作为进化算法的一个重要分支，粒子群算法可以在迭代过程中维持潜在解的种群，能够根据环境变化不断调整种群的适应度，具有较好的适应性，同时，粒子群算法具有实现简单、求解效率高、非线性优化性能强等优点，在各个领域进行了广泛应用，但在求解高维复杂优化问题上，标准粒子群算法搜索高维复杂优化问题全局最优值的过程往往会出现因为某几维陷入局部最优而导致整个算法陷入局部最优。

针对标准粒子群算法在求解高维复杂优化问题时易陷入局部最优的问题，本文提出一种多种群并行协作的粒子群算法，从粒子群算法拓扑优化的角度出发，利用拓扑动态变化实现粒子群协同进化，随着迭代次数的增加，算法不断地动态调整拓扑结构，为增强群落之间粒子的交流，设计群落之间粒子的广播-反馈规则，从而使粒子群算法在面对高维复杂优化问题时更容易跳出局部最优，有效降低算法陷入局部最优的概率，提高全局搜索能力，最终提升算法求解高维复杂优化问题的综合性能。

1 高维复杂优化问题描述

在智能优化领域，大多数优化问题最终归结为函数优化问题，而大多数优化函数具有规模大、决策变量多、优化问题维度高、非线性和不可微的特点，因此要解决高维复杂优化问题具有很大的挑战性和复杂性[16]。随着优化问题维度的增大，决策变量也随之增加，算法的搜索空间呈指数型扩展，因此，算法的优化性能大大降低，极易陷入局部最优。为了方便解决算法在解决高维复杂优化问题时的搜索精度和速度问题，将高维复杂优化问题做如下描述：

F(x)=min/maxf(xi),xi∈[xmin,xmax](i=1,2,…,D)

(1)

其中，F(x)为目标函数的最小值或最大值，即优化问题的最优值。f(xi)为目标函数，xi为某一维的决策变量，D为决策变量的个数，即总维度大小，xmin和xmax用来约束每个决策变量的可行域。针对上述高维复杂优化问题，许多传统优化算法收敛速度较快，计算精度高，但对初值敏感，易陷入局部最优，一些具有全局性的优化算法，受限于各自的机理和单一结构，对于高维复杂函数难以实现高效优化。

2 多种群并行协作的粒子群算法

2.1 标准粒子群算法

PSO算法是受鸟群寻觅食物的协作过程发展而来的[17]。PSO算法可以描述为n个粒子在D维搜索空间里，通过不断更新速度和位置来寻找最优解的过程。在D维搜索空间中有n个粒子，用vi=(vi1,vi2,…,viD)表示粒子的速度，用xi=(xi1,xi2,…,xiD)表示粒子的位置，粒子经历过的最优位置记为Pi=(pi1,pi2,…,piD)，其中个体极值为pbest。群体中所有粒子经历过的最好位置记为Pg=(pg1,pg2,…,pgD)，其中全部个体的最优位置为gbest。对于每一世代，粒子都通过跟踪pbest和gbest来更新自己位置和速度，进化如式(2)和式(3)所示：

(2)

(3)

式中，ω为惯性权重，c1和c2为加速常数，引入2个在[0，1]范围内变化的随机数rand1()和rand2()，t表示迭代次数。ω引导的是粒子当前的搜索速度，反映粒子的记忆性；c1引导的“认知”部分反映了粒子对自身的思考和肯定；c2引导的“社会”部分反映粒子间的信息共享与合作。

2.2 多种群并行协作的网络模型

标准粒子群算法的网络结构是一个单群落的全连接型网络，标准粒子群算法搜索高维复杂优化问题全局最优值的过程往往会出现因为某几维陷入局部最优而导致整个算法陷入局部最优。不同邻域拓扑结构的粒子群算法对同一个优化问题效果有很大的差异，常见的拓扑结构有全连接形拓扑、环形拓扑、冯诺依曼拓扑、星形拓扑和金字塔结构拓扑等[18-20]，不同的邻域拓扑是对不同交流模式的模拟，选择合适的拓扑结构对解决优化问题有很大的影响。常见拓扑结构中，全连接形拓扑信息传递的速度和算法收敛的速度较快，适合解决低维简单问题，但在求解高维问题时却很容易陷入局部最优。环形拓扑将所有的粒子首尾相连，从而相邻粒子得以保证更充分的信息交换，从而使信息在粒子间得到更好的分享，使算法充分搜索每个区域，不至于过早陷入局部最优，但也使得搜索速度变慢，收敛速度急剧下降。在冯诺依曼拓扑中，粒子形成立体网状结构，加强了对多个区域的搜索粒子之间的联系，使粒子更好地避开局部最优值。

高维复杂优化问题由于问题维度高，使得目标函数在搜索空间产生大量的局部最优值，粒子在搜索全局最优值时，某一维很容易陷入局部最优无法跳出[21]，求解困难。为了改善算法的寻优能力，提高算法跳出局部最优的成功率且兼具搜索速度，在全连接形拓扑、环形拓扑和冯诺依曼拓扑3种拓扑结构的基础上赋以不同的权重设计并行协作的网络模型。全连接形拓扑、环形拓扑和冯诺依曼拓扑如图1所示。

(a) 全连接形拓扑

(b) 环形拓扑

(c) 冯诺依曼拓扑图1 粒子群算法的3种拓扑结构

本文提出的多种群并行协作的网络(Multigroup Parallel Cooperation, MPC)是基于并行共享策略设计的，如图2所示。多种群并行协作的网络建立了冯诺依曼拓扑与环形拓扑、全连接形拓扑之间的通讯，使粒子在搜索的过程中考虑多种进化的可能性，以冯诺依曼拓扑为中心建立了拓扑之间的广播和反馈渠道。多种群并行协作的网络以冯诺依曼拓扑为核心，以全连接形拓扑和环形拓扑为参考更新全局最优值。在冯诺依曼拓扑中，当1个粒子找到较优解，会影响和它相连的3个粒子的寻优方向，这使粒子群算法保持了较好的寻优性能的同时维持其他粒子的多样性，这种结构不易陷入局部最优，也能保障较快的收敛速度。环形拓扑在算法进化过程中搜索精度高，全连接形拓扑搜索速度较快，使用上述2种结构与冯诺依曼拓扑达成协作进化策略，可以使粒子群算法的收敛性能得到全方位的提升。

(a) 种群之间的广播和反馈

(b) 接受其他种群的最优粒子图2 多种群并行协作的网络

在冯诺依曼拓扑结构中，对于每一次进化，粒子将当前迭代次数的全局最优值gbestv以广播的形式发送给环形拓扑和全连接形拓扑。环形拓扑和全连接形拓扑收到冯诺依曼拓扑广播的gbestv之后，与自身的全局最优值gbestr(环形拓扑)和gbestf(全连接形拓扑)比较。如果gbestv优于自身全局最优值，则调整进化规则，反之将信息反馈给冯诺依曼结构，调整冯诺依曼结构的进化规则。

搜索过程中，3种粒子群算法并行搜索，粒子群算法会根据3种拓扑中最好的全局最优值gbest进行调整进化策略。拓扑之间的信息共享采用二次通信策略，进化伊始，种群会平均分配给3种拓扑结构，在每一次迭代后，环形种群和全连接形种群都会与冯诺依曼种群进行信息共享。每次迭代时，当前种群都会检查本地种群是否需要更新进化规则，确保种群向跳出局部最优的方向进化。

定义1P表示种群中所有粒子的集合,pi表示集合中的一个粒子，用数学形式表示P⊇{p1,p2,…,pi,…,pn}，n为一个拓扑的粒子总数，则整个群落中的粒子总数为N=3n。其中，冯诺依曼拓扑中的粒子集合为P1⊇{p1,p2,…,pi,…,pn}，环形拓扑中的粒子集合为P2⊇{pn+1,pn+2,…,pn+i,…,p2n}，全连接形拓扑中的粒子集合为P3⊇{p2n+1,p2n+2,…,p2n+i,…,pN}。

根据定义1和使拓扑中的粒子更具探索性的原则，设计了MPC具体的拓扑进化步骤：

1)分别将N个粒子组成冯诺依曼拓扑、环形拓扑和全连接形拓扑结构。

2)初始化粒子3个种群的粒子速度和粒子位置，按照公式(2)和公式(3)进行迭代，得到当前迭代次数的全局最优值gbest。

3)将冯诺依曼拓扑中的全局最优值gbestv广播，与环形拓扑和全连接形拓扑中的全局最优值进行对比，根据对比结果设计了拓扑广播-反馈规则。

规则1 比较冯诺依曼拓扑中全局最优值gbestv与环形拓扑中的全局最优值gbestr，若gbestv>gbestr，将gbestr的值赋给gbestv，若gbestv

规则2 比较冯诺依曼拓扑中的全局最优值gbestv与全连接形拓扑中的全局最优值gbestf,若gbestv>gbestf，则将gbestf的值赋给gbestv，若gbestv

2.3 算法执行步骤

从改善算法的搜索能力，在解决高维复杂优化问题时跳出局部最优点的角度出发，考虑多种拓扑结构在进化过程中的特点，以冯诺依曼拓扑为主要拓扑结构，以环形拓扑和全连接形拓扑为种群探索补充结构，利用多群落粒子之间的信息共享特性，以粒子的适应度为基础，融合3种拓扑结构并行搜索，设计了群落之间粒子的广播-反馈规则。提出多种群并行协作粒子群(Multigroup Parallel Cooperation Particle Swarm Optimization， MPCPSO)算法。

由于MPCPSO是应用3种算法并行协作搜索的智能集群进化算法，基于上述并行思路，MPCPSO算法的流程如图3所示，具体步骤如下：

图3 MPCPSO算法流程图

步骤1 初始化MPCPSO中粒子的位置和速度；

步骤2 计算冯诺依曼拓扑、环形拓扑和全连接形拓扑结构的适应度fv、fr、ff；

步骤3 广播冯诺依曼拓扑中的全局最优值gbestv并执行拓扑广播-反馈规则；

步骤4 更新粒子的位置和速度。

步骤5 若满足终止条件，则输出全局最优值，反之则跳转到步骤2。

综上所述，本文算法可以根据不同种群粒子节点的连接强度，在不同的演化阶段自适应地调整进化拓扑结构，这样连接拓扑的动态演化可以解决高维决策变量间的相关性问题，而种群的动态分组可以解决多模态和算法收敛过快而陷入局部最优的问题。

3 仿真实验与结果分析

3.1 测试函数及其实验环境

为分析MPCPSO算法解决高维复杂问题的搜索速度、寻优精度等性能，测试算法跳出局部最优的能力，本文采用6个高维复杂多模变量维数可自行设定的单峰和多峰函数进行仿真分析，6个测试函数的图像如图4所示，测试函数名称和主要特征如表1所示。

(a) Ackley

(b) Griewank

(c) Powell

(d) Schwefel

(e) Rastrigin

(f) Sphere图4 6种测试函数的图像

表1 高维复杂测试函数

3.2 仿真实验

为了验证算法对于解决高维多模优化问题的优越性，本文选择环型拓扑-PSOr、全连接形拓扑-PSOf、冯诺依曼拓扑-PSOv的PSO算法和利用冯诺依曼拓扑与骨干粒子群算法改进的VBBPSO[22]与MPCPSO进行对比。

各算法的参数设置如下：

1)PSOr：ωmax=0.85、ωmin=0.4、Vmax=100、c1=2、c2=2、n=100;

2)PSOf：ωmax=0.85、ωmin=0.4、Vmax=100、c1=2、c2=2、n=100;

3)PSOv：ωmax=0.85、ωmin=0.4、Vmax=100、c1=2，c2=2、n=100;

4)VBBPSO：α=0.65、β=0.3、rows=5、cols=10、n=100;

5)MPCPSO：ωmax=0.85、ωmin=0.4、Vmax=100、c1=2、c2=2、n=100。

为了测试算法对高维复杂优化问题的寻优能力，将维数d设置为1000，最大迭代次数设置为500，各算法独立运行30次，记录算法寻优的平均最优值、最优值、方差和收敛代数，测试结果如表2所示。

表2 面向高维复杂优化问题的寻优能力对比实验结果

在此实验中产生了大量数据，为分析各算法在处理高维复杂优化问题的收敛性能和实验结果的准确性给出了各算法的收敛性能对比图，图5为5种算法的6个测试函数的平均最优值收敛图。

(a) f1

(b) f2

(c) f3

(d) f4

(e) f5

为证明算法有效性，针对具体应用，采用PSOr、PSOf、PSOv、VBBPSO和MPCPSO算法对IEEE30电力系统有功网损优化30次，结果对比如表3所示，各控制变量状态见表4。

表4 MPCPSO控制变量优化后的结果(标幺值)

从表中可以发现，MPCPSO优化后的最优网损、最差网损以及平均网损的值都是最小的，PSOr的平均网损是5.231，PSOf的平均网损是5.195，PSOv的平均网损是5.150，VBBPSO的平均网损是5.162，MPCPSO的平均网损是5.138，相对PSOr降低了1.78%，相对PSOf降低1.10%，相对PSOv降低0.23%，相对VBBPSO降低了0.46%。说明MPCPSO降低有功网损的效果比较好。此外，实验运行30次，MPCPSO运行的结果在5.138周围，比PSOr、PSOf、PSOv、VBBPSO收敛的状态更加稳定，遇到局部最优情况能够及时跳出，摆脱局部最优的干扰，继续寻找全局最优解。MPCPSO不仅优化结果不错，而且优化的电力系统各状态值都在要求的范围内，且有裕度。

在IEEE30电力系统中，PSOr、PSOf、PSOv、VBBPSO和MPCPSO对目标函数进行优化，优化的网损最小化可以用公式(4)表示[23]：

(4)

则有功网损的收敛曲线如图6所示。

图6 对比算法收敛曲线

在图6中观察各算法优化后，从有功网损的收敛曲线中发现，MPCPSO优化后的有功网损值最小。PSOr在对无功问题的优化过程中，往往就陷入局部最优值中，停滞不前。PSOf、PSOv和VBBPSO虽然在优化的前期，收敛的速度或精度都比较不错，但随着迭代次数的增加，种群的多样性减少，进行局部搜索的能力减弱，因此收敛的速度变得缓慢，寻优的精度也不是很高。对比发现，MPCPSO在优化无功问题时，不仅大幅降低了有功网损，而且花费的时间也最短。

3.3 结果分析

分析表2中的实验数据和图5的收敛效果，可以得出，环型拓扑-PSOr、全连接形拓扑-PSOf、冯诺依曼拓扑-PSOv的算法在面对高维复杂优化问题时，6个测试函数全部未达到理想的全局最优值，明显表现出不佳的收敛性能。尤其在处理多峰的高维测试函数f1、f4和f5时表现出很差的收敛效果，由此可以看出标准粒子群算法无论在采取环形拓扑、全连接形拓扑和冯诺依曼拓扑都难以获得较好的收敛效果。从图5来看，VBBPSO和MPCPSO表现出相似的收敛效果，但分析表2可以得出，MPCPSO随着迭代次数的增加，不断动态调整拓扑的结构，加强了群落之间粒子的交流，表现出较强的适应能力，在收敛精度和收敛代数上要普遍优于VBBPSO，但是在算法执行速度方面稍逊于VBBPSO。从收敛效果可以得出，MPCPSO在解决高维复杂优化问题时，有很强的跳出局部最优值的能力，能够在较小的迭代次数求得比较理想的全局最优值。

4 结束语

本文在对高维复杂优化问题进行分析的基础上，提出了多种群并行协作网络MPC，结合粒子群算法的环形拓扑、全连接形拓扑和冯诺依曼拓扑的优点，分析算法的收敛性能，制定了MPC的动态进化策略，提出了一种以冯诺依曼拓扑为核心，以环形拓扑和全连接形拓扑为辅助的动态拓扑进化算法MPCPSO，考虑了环形拓扑粒子群算法、全连接形拓扑粒子群算法和冯诺依曼拓扑粒子群算法在寻优过程中的特点和关系，设计了多种群的广播-反馈的拓扑协作模式，动态调整拓扑中粒子的搜索方向，提高了多种群的协作能力，加深了粒子之间的信息共享。仿真实验结果表明，针对高维复杂优化问题，MPCPSO在寻优精度和迭代次数上表现出明显的优势，在算法执行速度方面略有缺陷，为使用粒子群算法求解高维复杂优化问题提供了新的思路。