帕累托部落进化算法及其在电力系统多目标优化发电调度中的应用

许悦，瞿凯平，张孝顺，余涛

（华南理工大学电力学院，广东 广州，510640）

0　引言

在实际工程应用中，往往需要解决多目标优化问题（multi-objective optimization problem, MOP）。随着帕累托（Pareto）概念的提出，各种多目标算法[1-4]也相继产生。传统的方法如约束法、加权法等将多目标问题转化为单目标问题求解，但这些传统方法存在计算速度慢、优化结果受约束值和权重值影响较大等缺点。近年来，新的用于解决MOP的智能算法迅速发展，以非支配排序遗传算法（non-dominated sorting genetic algorithm II, NSGA-II）[5]为代表的进化算法、以多目标粒子群（multiobjective particle swarm optimization, MOPSO）[6]为代表的群智能搜索算法、分布估计算法（estimation of distribution algorithm, EDA）[7]、基于分解的多目标算法（multi-objective evolutionary algorithm based on decomposition, MOEA/D）[8]等相继产生。很多学者受上述智能算法的启发，将之应用于电力系统多目标优化发电调度（multi objective generation dispatch, MOGD）[9-12]。但上述智能算法在用于MOGD过程中往往存在着各种问题：NSGA-II的交叉和变异操作随机性较大，对PF的趋近度不够；MOPSO自身的全局搜索能力较差，因而寻得的PF分布广度不够令人满意；分布估计算法聚类过程复杂，概率模型也不够精确，难以满足电力系统的动态需求；MOEA/D由于受初始权重值的影响较大，因此难以得到足够均匀的Pareto解集。此外，强度Pareto进化算法（strength Pareto evolutionary algorithm, SPEA）[13]、多目标差分进化算法（multi-objective differential evolution, MODE）[14]、非支配邻域免疫算法（non-dominated neighbor immune algorithm, NNIA）[15]等等也都应用于电力系统多目标优化中，但其往往只考虑了两个目标，对更多目标、更高维的搜索空间并不能得到令人满意的结果。

针对上述算法在求解多变量、多约束的电力系统多目标优化发电调度问题上的不足，本文提出一种新颖的帕累托部落进化算法（Pareto tribe evolution, PTE）。PTE的基础是原始部落为了自身的发展而采取的一系列行为。PTE共有三种基本策略：部落划分、部落繁衍、部落迁徙。PTE通过部落划分将PF分段，缩小了个体的移动步长，减少了移动的随机性。同时，动态的部落划分过程也是一种部落与部落、个体与个体之间的交流过程。引入非支配排序和共享度[16]得到每个个体的强度，通过混沌搜索[17]和趋近搜索相结合的部落繁衍策略使个体快速地向PF逼近。为了得到分布更广的PF，PTE让每个部落的最差个体进行随机迁徙。最后，本文引入灰色关联度用于选取Pareto解集中的折中解。

1　帕累托部落进化算法

基于Pareto理论的多目标优化问题一般定义如下[18]：

式中，F为目标函数集合，f为目标子函数，X为解向量；Mobj、Mineq和Meq分别表示目标函数、不等式约束和等式约束的个数。

本文所提的PTE算法是一种模拟原始人类社会性活动的新型启发式仿生算法。为提高适应自然环境的能力，地缘上联系密切的原始人类个体将自发形成一定规模的部落开始群体生活，依靠相互协作实现自身的生存和部落的发展，当栖息地环境恶化不适于人类生存时，全体部落成员将进行迁徙以寻找新的栖息地。与之类似，本文将满足所有约束的多个初始可行解定义为多个原始人类个体，在算法的每个周期部落都要经历形成、发展和迁徙三个阶段，不断向最佳栖息地（PF）逼近。其中，在发展阶段，各部落将依据个体适应度的大小选择首领与强者领导本部落。算法核心在于动态地将PF分段并赋予不同的个体以不同的地位，以实现精细化的局部搜索和个体间的协同搜索。

1.1　支路与节点重要性的评估

单目标优化多依据目标函数评价个体的适应度，但这一方法不适用于含多个目标的帕累托优化问题，因此，本文采用了一种基于非支配排序与共享函数的适应度评价策略。

（1）非支配排序

在评价个体适应度时，要根据个体之间的支配关系对其进行分层排序。首先选择出所有非支配的个体作为最优层序值个体，之后忽略该层个体继续按照支配与非支配关系的分层，以此方式直到完成全部个体的非支配排序。其中，最优层的非支配个体序值为1，而最劣层个体序值最大。非支配排序的序值反应了各个体对PF的真实趋近程度，是评价个体适应度的主属性，是个体优劣的直接体现。

（2）共享度

为区分非支配排序序值相等个体的适应度，本文采用共享度作为评价个体适应度的辅助属性。共享函数（记为表示了两个个体间的密切程度，共享度（记为Si）为个体与其他个体间的共享函数之和，其值越小表示解越稀疏，个体的适应度越强。假设某一非支配排序层下的个体数为Nnd，依照下式计算个体的共享度：

其中，i，j代表不同的个体，Dim为目标子函数个数；fkmax和fkmin为fk变化的上下界；称为共享度的峰半径，而ε为足够小的正数，dmax为个体间的最大距离。

共享度的引入有利于引导个体向更为稀疏的方向移动，从而获得空间分布更广的PF。传统算法多采用的拥挤距离表征个体的稀疏程度，由于PF分段点附近的拥挤距离很大，个体将趋向于向分段点聚集，引入共享度则避免了这一问题。

1.2　部落形成

传统的多目标优化算法未对PF进行分段，种群个体随机移动的步长过大，大空间内的搜索盲目性强，算法的寻优精度收受到影响。为此，PTE算法通过形成部落的方式对PF进行分段，限制了个体的移动步长和移动范围，减小了个体搜索过程中的盲目性。

每个迭代周期，PTE都要重新形成部落，这一过程即为部落与部落、个体与个体之间的交流过程。部落个数Ntr是一个随着时间t增加而线性增加的变量。算法迭代初期，部落个数较少，个体的移动范围较大，全局搜索能力强，利于发现移动范围内的Pareto解；随着算法的进行，个体已趋近于在PF附近搜索，增加的部落个数有利于增强算法的局部搜索能力。

部落形成的规则为：首先以随机选取的任一目标函数值为依据对全部个体进行排序，按照均匀的跨度选取要形成的Ntr个部落的初始成员，并计算全部个体到Ntr个初始成员的欧式距离：

式中，i=1,2,…,N0；j=1,2,…,Ntr。在此基础上，计算个体i被分配到部落j中的概率：

最后，按照ε-贪婪规则将个体i分配到相应的部落中：

式中，A为初始成员集合；rand为[0,1]之间的随机数；ε为一常数；s表示个体i根据概率pij执行随机轮盘选择。

1.3　部落发展

如图1所示，为使各部落成员趋近本部落的PF，PTE算法依据个体适应度给部落成员分配了不同的角色。每个部落中，非支配排序序值为1的个体为强者，代表了PTE中较为逼近PF的个体；在强者中共享度最小的个体为首领，综合非支配排序序值与共享度得到的强度最差的个体则成为迁徙者，其余个体为平民。

图1　PTE算法原理图Fig.1 Schematic of PTE

（1）强者

由于强者与首领的非支配排序层相同，两者没有严格的优劣之分，故采取带有追随行为的混沌搜索策略。混沌现象具有随机性、规律性和遍历性，因此，强者以基于Logistic映射的混沌搜索作为主要移动方式；此外，强者对首领具有一定的追随行为，追随度跟两者的共享度密切相关。强者的移动方式可描述如下：

式中，f1，f2分别为混沌搜索分量和追随首领分量；μ为混沌控制参数，本文取4，以加强混沌序列的随机性；t ir为第t周期用混沌序列产生的随机数；rsign为值为1或-1的随机数；h为趋近因子，表征个体对首领的追随程度，本文取0.1；S为共享度为步长向量，

式中，xrand为随机选取的不同于本个体的强者。

（2）首领

首领的移动方式与强者相同，也按照式(6) ～ (9)进行，不同的是，首领对自身的追随分量为零。

（3）平民

平民的移动方式由对首领的追随分量和对强者的追随分量构成，即：

式中，D为解分量某一维度，c1，c2分别是对首领和强者的追随因子，本文分别取1.5和1。1r、r2为[0,1]

之间的随机数，xlead，xstr分别为首领和最靠近i的强者。

1.4　部落迁徙

为提升种群多样性，优化算法对可行域的全局搜索性能，各部落中的迁徙者需进行随机迁徙操作：

PTE中迁徙者个数是动态调整的，其迁徙概率随运行周期t不断减小：

式中，pmax，pmin分别为迁徙概率最大值、最小值，分别取1和0.4；一起控制着曲线下降斜率，分别取70.584和0.05；为最大运行周期。当时，迁徙者的移动方式与平民相同，随着算法的进行，整个种群中非劣个体不断增多。

经过了部落发展和部落迁徙两个阶段后，全部个体都完成了一次动作，即产生一个子种群。此时将子种群加入到原种群，并根据个体适应度多筛选出N0个个体作为下次迭代的初始种群。

1.5　基于灰色关联度的折中解选择

Pareto解集提供了一组可供决策者选择的解，决策者需要从这组解中选取一个折中解作为最终的调度决策。常用的方法有模糊推理法和熵权理想点法[19]。但模糊推理往往依赖工程经验而缺乏理论依据；而熵权理想点法是根据各个指标携带信息量的大小确定权重，而在本文中，难以将三个目标携带信息的重要程度进行量化，因此无法准备定义其熵权。因此，本文采用灰色关联度来确定最终的折中解。

（1）决策矩阵初始化

成本型目标用下式进行归一化：

（2）方案的灰色关联度计算

式中：ρ为分辨率系数，通常取0.5。

（3）目标权重的确定

灰色关联度法用各方案到理想方案的关联度之和作为综合评价准则，为确定各目标权重，构造如下线性规划模型：

（4）计算加权灰色关联度

最后，得到方案i和理想方案的加权灰色关联度为：

W越大，则方案与理想方案越接近，方案越好。

1.6　算法流程

综上所述，利用PTE算法求解风险调度的流程如图2所示。当迭代次数达到预定值时，迭代完成。

图2　PTE算法流程图Fig.2 Flowchart of PTE

2　多目标优化发电调度(MOGD)

2.1　MOGD优化目标

（1）经济目标

MOGD经济目标是使总的发电燃料成本最小，每个发电机的耗量特性都可通过实验获得，实际分析中简化成用二次多项式表示，则总的发电燃料成本为：

（2）排放目标

燃料燃烧为发电机提供动力的过程中会向大气中排放大量的硫化物、碳化物等有害气体。排放目标代表了对环境的污染程度，本文仅考虑COx（碳氧化合物）的排放量：

（3）电压目标

电网运行中，每个节点都对应一个电压，且电压越处于约束的中间位置，电压质量越好，对设备及用户的影响越小。电压目标用下式表示：

2.2　MOGD约束条件

1）功率平衡约束：经潮流计算后，发电机总的有功出力应等于负荷Pload与有功网损Ploss之和。

2）有功出力约束：每个发电机的有功出力应在其允许的上下限之间。

3）无功出力约束：发电机的无功出力必须处于其允许的上下限之间。

4）线路传输功率约束：每条线路的视在功率应小于其限值以防止过载。

5）节点电压约束：节点电压幅值必须在其允许的上下限之间。

3　仿真分析

3.1　算法配置

以IEEE标准118节点54机组系统和300节点69机组系统作为研究对象，用于测试PTE，并与其他算法进行对比。系统拓扑、发电机参数以及约束数据参见文献[20]。对比算法采用MODE、MOPSO、NNIA、NSGA-II与SPEA2。每种算法运行10次，每次运行100周期，初始种群数都为100，Pareto解集中解的个数为100。PTE参数设置参见表1。PTE部落数随运行周期线性增加。初始为8，结束时为15。为方便观察各算法所得到的PF，算例一采用118节点两个目标的发电调度问题，为了测试PTE在解决多维目标、多变量问题中的表现，算例二采用300节点三个目标的发电调度问题。

算例一：118节点两个目标的发电调度问题（经济目标和排放目标）。

算例二：300节点三个目标的发电调度问题（经济目标、排放目标和电压目标）。

表1　参数设置Tab.1 Parameter settings

3.2　性能指标

为了深入比较各算法的性能，分别对各算法所得到的PF的趋近度、分布均匀度和分布广度进行比较。

1）趋近度指标用来评价算法得到的Pareto解集对真正PF的趋近情况。算例一采取的方式是计算Pareto解集至真实PF的欧式距离：

式中，Npf为各算法得到的Pareto解个数，Ntpf为真实PF中解个数。取各个算法运行20次求得的Pareto解，用所有Pareto解进行非支配排序得到最终的Pareto解集作为真实PF。三目标的真实PF是一个曲面，需要非常多的分布均匀的解来组成，实际问题中很难做到。因此，算例二取各算法每次得到的Pareto解，用所有Pareto解进行非支配排序得到最终的Pareto解集，各算法在此解集中所占比例即代表对真实PF的趋近程度。

2）分布均匀度用来评价算法所得Pareto解集的分布均匀性。本文用相对拥挤距离来表示：

式中，dc,i为个体i的拥挤距离，dc,avg为平均拥挤距离。

3）分布广度用来评价算法所得Pareto解集的最大散布范围。

式中，fk·MAX和fk·MIN分别是所有算法得到的第k个目标的最大值和最小值。

3.3　仿真结果分析

（1）两目标算例

根据PTE及各算法所得到的Pareto最优解集，相应经济目标和排放目标的极限值如表2所示。数据表明，PTE所找到的各目标的极限值在所有算法中都是最小的，此外，表7也显示PTE的分布广度最大，即说明了PTE算法全局搜索能力最强，更容易找到分布最广的Pareto解集。

为方便观察各算法所得到的PF，图3用两幅图显示了各算法的PF。将表现较好的NNIA、SPEA2、PTE三者置于下方，其余表现较差的置于上方。可以看到，PTE得到的PF两端延伸范围最长，说明PTE算法分布广度性能最为出色。表5数据显示，PTE所得到的Pareto趋近度指标为0.0871，NNIA稍差于PTE，为0.0875，其余算法趋近度指标明显大于PTE，说明PTE所得到的PF最接近于真实PF。对比表6中的分布均匀度指标，NNIA与SPEA2最好，分别为0.0207与0.0206，PTE稍差，为0.0248，说明PTE所得到的PF在分布均匀度这一指标上稍显不足。此外，PTE算法各指标的方差都最小，说明PTE最为稳定。

由于各算法的耗时主要与潮流计算时间有关，为了比较PTE与其他算法的效率，我们统计了各算法调用潮流运算函数的次数，NNIA为12620次，其余算法各为10000次，即每周期NNIA对每个个体的变动次数平均为1.262次，而其余算法为1次。各算法的运行时间如表3所示。从表中可知，NNIA耗时最长，NSGA-II耗时最短，其余算法耗时相近。可见，在相同的对个体变动次数条件下，PTE的耗时与其余算法相近，但得到的PF最让人满意。

表2　两目标算例各算法目标极值比较Tab.2 Minimums of cost and emission objective of Case 1

图3　算例一各算法PF对比图Fig. 3 Pareto fronts obtained of Case 1

（2）三目标算例

表3　算例一各算法消耗时间比较Tab.3 Comparisons of time consumption for Case 1

根据PTE及各算法所得到的Pareto最优解集，相应经济目标、排放目标和电压目标的极值如表4所示。数据表明，PTE所找到的三个目标的极值在所有算法中都是最小的，表7也显示PTE的分布广度最大，说明随着优化目标的增加，PTE依然能保持良好的全局搜索能力，找到分布最广的Pareto解集。

图4显示了各算法得到的PF，可见，PTE所得到的Pareto解集延伸范围最广，且最接近于真实PF，NSGA-II性能最差。表5显示，在最终形成的Pareto解集中，PTE的Pareto解所占比例为58.54%，其余算法明显低于PTE，同样说明了PTE得到的解集更接近于真实PF。对比表6中的分布均匀度指标，NNIA最好，为0.05148，PTE为0.14602，在分布均匀度这一指标上，PTE依然没有优势。

表4　算例二各算法目标极值比较Tab.4 Minimums of cost, emission and voltage objective of Case 2

图4　算例二各算法PF对比图Fig. 4 Pareto fronts obtained of Case 2

为了更加直观地说明PTE的搜索能力，图5显示了各算法各目标值的收敛曲线。可以看到，PTE经济目标和排放目标在每个周期都在持续下降，且下降程度非常均匀，特别是在算法后半段，其余算法收敛曲线明显下降不足，而PTE依然保持着良好的搜索能力。

图5　算例二各目标收敛曲线图Fig. 5 Convergence curves of all objectives for Case 2

（3）折中解选择

算例一用灰色关联度选取的折中解如图6所示。可以看到，折中解基本处于PF的中部位置，说明折中解同时兼顾了经济目标和排放目标，此外，折中解离理想解（5.5,5）的距离也很近，证明了灰色关联度用于折中解选取的可行性。

图6　算例一折中解选择Fig. 6 Compromise solution selected for Case 1

表5　各算法运行10次趋近度指标统计Tab.5 Resulting statistics of approaching metrics in 10 Runs

表6　各算法运行10次分布均匀度指标统计Tab.6 Resulting statistics of spacing metrics in 10 Runs

表7　各算法运行10次分布广度指标统计Tab.7 Resulting statistics of span metrics in 10 Runs

4　总结

为解决强约束、大规模的多目标优化问题，本文提出一种新颖的帕累托部落进化算法(PTE)，通过IEEE118节点和300节点系统的多目标优化发电调度仿真，并和其他常用的多目标算法进行对比，验证了PTE在解集多目标优化问题上的优越性。该算法主要有以下几点优势：① 通过划分部落，有效地缩小了个体的移动步长，增强了算法的局部搜索能力；通过赋予个体以不同的地位，各个不同的个体采取不同的移动方式，使算法更能快速地逼近Pareto前沿。② 通过动态地划分部落，使得部落与部落、个体与个体之间得到信息上的交流，算法的全局搜索能力得到加强。③ 基于非支配排序和共享度的个体强度，使得个体能够向稀疏的区域移动，改善了Pareto解集的分布均匀性。④ 当决策者没有明确权重的情况下，基于灰色关联度的折中解选择为决策者提供了一个可供参考的选择依据。⑤ 与NSGA-II、SPEA2、MOPSO和MODE一样，PTE对其它多目标优化问题求解也有很高的普适性。

[1] 吴雯美, 陆江, 谭敏, 等. 基于相关均衡强化学习协同算法的多区域无功优化研究[J]. 新型工业化, 2015(6):33-40.WU Wen-mei, LU Jiang, TAN Min, et al. Multi-regional Reactive Power Optimization Based on Correlated Equilibrium Q-learning Collaborative Algorithm [J]. The Journal of New Industrialization, 2015(6):33-40.

[2] 郑宇, 张睿, 李正佳. 智能电网中基于自适应一致性的自动发电控制与优化[J]. 新型工业化, 2016, 6(8):41-48.ZHENG Yu, ZHANG Rui, LI Zheng-jia. Optimizing Distributed Gain Scheduling Strategy for Load Frequency Control in Smart Grids Based on Adaptive Consensus Protocol [J]. The Journal of New Industrialization, 2016, 6(8):41-48.

[3] 任苹, 李楠. 基于差分和声搜索算法的短期电力系统优化调度[J]. 新型工业化, 2014(4):32-38.REN Ping, LI Nan. Optimal Short-term Hydrothermal Scheduling Based on Differential Harmony Search Algorithm [J]. The Journal of New Industrialization, 2014(4):32-38.

[4] 陈鑫, 余涛, 席磊, 等. 一种新颖的智能发电控制策略[J]. 新型工业化, 2015(5):40-48.CHEN Xin, YU Tao, XI Lei, et al. A Novel Policy for Smart Generation Control [J]. The Journal of New Industrialization, 2015(5):40-48.

[5] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[6] COELLO C A, LECHUGA M S. MOPSO: A proposal for multiple objective particle swarm optimization[C]//CEC02: Preceedings of the 2002 Congress on Evolutionary Computation. Piscataway: IEEE, 2002: 1051-1056.

[7] 周树德, 孙增圻. 分布估计算法综述[J]. 自动化学报, 2007, 33(2): 113-124.ZHOU Shu-de, SUN Zeng-qi. A Survey on Estimation of Distribution Algorithms[J]. Acta Automatica Sinica, 2007, 33(2): 113-124.

[8] ZHANG Q, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.

[9] 彭春华, 孙惠娟. 基于微分进化的多目标优化发电调度[J]. 中国电机工程学报, 2009, 29(34): 71-76.PENG Chun-hua, SUN Hui-juan. Multi-objective optimization power dispatch based on non-dominated sorting differential evolution[J].Proceedings of the CSEE, 2009, 29(34): 71-76.

[10] 庄怀东, 吴红斌, 刘海涛, 等. 含电动汽车的微网系统多目标经济调度[J]. 电工技术学报, 2014, 29(1): 365-373.ZHUANG Huai-dong, WU Hong-bin, LIU Hai-tao, et al. Multi-Objective Economic Dispatch of Microgrid System Considering Electric Vehicles[J]. Transactions of China Electrotechnical Society, 2014, 29(1): 365-373.

[11] 刘静, 罗先觉. 采用多目标随机黑洞粒子群优化算法的环境经济发电调度[J]. 中国电机工程学报, 2010, 30(34): 105-111.LIU Jing, LUO Xian-jue. Environmental Economic Dispatching Adopting Multiobjective Random Black-hole Particle Swarm Optimization Algorithm[J]. Proceedings of the CSEE, 2010, 30(34): 105-111.

[12] 姚瑶, 于继来．计及风电备用风险的电力系统多目标混合优化调度[J]. 电力系统自动化, 2011, 35(22): 118-124.YAO Yao, YU Ji-lai. Multi-objective hybrid optimal dispatch of power systems considering reserve risk due to wind power[J]. Automation of Electric Power Systems, 2011, 35(22): 118-124.

[13] ABIDO M A. Environmental/economic power dispatch using multi-objective evolutionary algorithms[J]. IEEE Transactions on Power Systems, 2003, 18(4): 1529-1537.

[14] MEZURA-MONTES E, REYES-SIERRA M, COELLO C A C. Multi-objective optimization using differential evolution: A survey of the state-of-the-art[C]//Advances in Differential Evolution. Berlin: Springer, 2008: 173-196.

[15] GONG M, JIAO L, DU H, et al. Multiobjective Immune Algorithm with Nondominated Neighbor-based Selection[J]. Evolutionary Computation, 2008, 16(2): 225-255.

[16] GOLDBERG D E, RICHARDSON J. Genetic algorithms with sharing for multimodal function optimization[C]//Proceedings of the 2nd International Conference on Genetic Algorithms. Hillsdale: L. Lawrence Erlbaum Associates, 1987: 41-49.

[17] CAPONETTO R, FORTUNA L, FAZZINO S, et al. Chaotic sequences to improve the performance of evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(3): 289-304.

[18] 毛森茂, 瞿凯平, 陈艺璇,等. 基于灰狼多目标算法的电网碳-能复合流优化调度[J]. 新型工业化, 2016, 6(9):11-17.MAO Sen-mao, QU Kai-ping, CHEN Yi-xuan, et al, Grey Wolf Multi-objective Optimizer for Optimal Carbon—energy Combined-flow[J].The Journal of New Industrialization, 2016, 6(9):11-17.

[19] ABIDO M A. Multiobjective evolutionary algorithms for electric power dispatch problem[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 315-329.

[20] Zimmerman R, Gan D. MATPOWER: A Matlab power system simulation package [EB/OL]. Available: http://www. pserc. cornell. edu/matpower.