一种基于簇类进化的电力经济负荷分配优化算法

陈　皓　潘晓英　张　洁

(西安邮电大学计算机学院　西安　710121)



一种基于簇类进化的电力经济负荷分配优化算法

陈皓潘晓英张洁

(西安邮电大学计算机学院西安710121)

(chenhao@xupt.edu.cn)

摘要电力经济负荷分配不仅能保证电力系统安全稳定地运行、延长机组使用寿命，还能节省能源，最大化电力企业的经济效益.此类问题可归为一种具有高维、不可微目标函数及多个非线性约束的数值优化问题.提出了一种新型的全局优化算法——簇类进化算法(cluster evolutionary algorithm, CEA)，并将其应用于求解ELD问题.CEA利用聚类过程在进化个体间构建一定结构的连接关系，并利用这种虚拟的簇类化组织来协调和控制系统的优化计算过程，提高群体的问题空间搜索效率以及抗早熟能力.在仿真实验中13个典型测试函数和3个IEEE系统被用于对CEA的性能进行检验.实验数据显示CEA对13个约束数值优化问题可用较小的计算代价获得较高质量的解，而对3个测试系统的计算结果则要好于目前已报道的最佳解.实验数据的统计分析显示CEA是一种高效的数值优化算法，可作为一种有效的ELD问题求解方法.

关键词进化算法；群体聚类机制；簇类进化搜索；约束数值优化；经济负荷分配

电力经济负荷分配(economic load dispatch, ELD)的目标是在一个发电系统内合理分配各发电机的运行功率，使得在满足总负荷和运行约束的条件下发电成本最小.通常发电机组的能耗特性使用二次函数来近似拟合，能耗函数为

(1)

其中,F为系统总发电费用(每小时美元数)，Ng为系统内发电机总数；Pi为第i台发电机的有功功率(MW)；Fi(Pi)为第i台发电机的耗量特性；αi，βi，γi为其耗量特性常数，εi为阀点效应引起的第i台发电机耗量特性变化，它可表示为

(2)

发电机组在工作时受3个约束条件限制：

1) 发电机运行约束

(3)

2) 禁止运转区域限制

(4)

3) 电力平衡约束

(5)

其中，PL为系统总负荷，PS为系统总网损.PS可由B系数法求得，网损与发电机有功率关系为

(6)

其中，P=(P1,P2,…,PNg)T为Ng维发电机有功功率列向量，PT为P的转置；B∈Ng×Ng，B0∈Ng，B00∈为网损系数.

ELD问题所具有的高维、不连续、不可微等特点使得其很难被动态规划法、拉格朗日乘数法等传统方法有效求解，而进化算法(evolutionary algorithm, EA)具有对目标函数的类型和搜索空间的结构没有任何限制，同时对计算中数据的不确定性也具有很强适应能力等特点，故可将传统方法计算ELD问题时忽略的网络损失、阀点效应等考虑在内，这显著提高了求解的实用性和有效性.目前，一些典型的进化优化算法，如遗传算法[1]、粒子群算法[2-3]、克隆算法[4]、差分进化算法[5]等被应用于对该问题的求解计算并获得了较好的效果.但是，高维且不连续的目标函数以及非线性的约束易使EA产生过早收敛或收敛缓慢等现象，在求解ELD问题的实践中该问题同样严重影响了EA实际的求解质量和计算效果.

进化搜索的动力源自对“优胜劣汰，适者生存”这一自然法则的模拟，这使得EA的基本计算框架既有良好的普适性又具有与生俱来的随机盲目性.在实际计算中，EA需要不断协调系统中从基因位到个体、群体等不同层面中多种全局性和局部性计算间的复杂协作关系才可有效降低其固有的随机盲目性所带来的负面影响.目前，自适应机制[6]是EA改进自身计算协调能力及稳定性的一种较为常用的方法.但制定合理有效的自适应策略本身就是一个难题，而且受计算模型复杂性的限制，自适应机制对系统性能的改进效果也是有限的.近期的一个研究动态是通过融合多种异构的搜索机制来混合建模[7-8].此类研究显示，搜索机制的多样化不但可有效改善系统的抗早熟能力，还可进一步提高群体的搜索速度.但如何平衡系统建模中多样性与复杂性以及不同搜索机制的特殊性及其相互间协调性的关系就成为了一个新问题.可见，EA对自身运算过程的协调和控制能力对其计算效果所产生的影响在随着算法模型的愈发复杂而变得越来越突出.

从生物学的角度看，许多重要进化事件的发生基础是基因聚类；而从社会学的角度看，部落、种族等具有簇类结构特征的社会单元则是人类进化和文明发展的基本组织.可见，具有簇类形态的组织结构在复杂群体进化的发生和发展过程中都起到了至关重要的调节和导向作用.受此启发，我们认为可在个体间构建一定结构的簇类组织，并利用簇类组织对模拟进化系统的运算过程进行控制和协调，以获得更为高效的进化搜索性能.基于此思想，我们提出了簇类进化算法(cluster evolutionary algorithm, CEA).在群体搜索过程中，CEA将基于聚类过程动态地构建个体间的虚拟连接关系即簇类组织，同时系统将基于这种簇类结构动态调节群体中全局性和局部性计算过程，并融合多种搜索机制形成有效的互补，以使CEA在计算的不同阶段形成更具针对性且协调性更佳的搜索机制组合，从而实现对复杂问题空间稳定、可靠的优化.

本文介绍了CEA的基本模型和主要计算机制，并使用13个测试函数和3个IEEE测试系统对CEA的计算性能进行了仿真实验，同时对实验数据进行了对比和统计分析，最后给出了结论.

1簇类搜索模型

1.1相关工作及问题

在进化搜索中，个体间的编码差异及其在问题空间的分布与它们所参与搜索运算的性能特点间有着一定的联系，而研究者一直在尝试利用此类关系来调节群体的搜索过程.如文献[9]通过基于编码相似性匹配的约束机制(mating restriction)来控制交叉运算中个体对的形成过程，以提高算法对多目标优化问题的求解性能.此类研究中系统对个体间亲疏关系的利用主要集中于特定的搜索运算内，而另一些算法则希望通过控制个体在问题空间的分布形态来构成结构化群体，并基于此调节系统的整体计算过程.如小生境机制[10]通过排挤或适应度共享策略来抑制群体的趋同过程并形成个体间一定程度地聚集，这种群体结构改善了系统对多峰问题的计算效果.但小生境的形成是一个间接且被动的过程，而且个体间的结构关系是一种隐式的存在，这使得算法不便于利用其对系统的计算过程进行更为主动地控制.近年的一些研究开始尝试对个体间的彼此关系进行特定地区分，并利用某种显式的类别结构来直接控制群体的搜索过程.如文献[11]从性别的角度将个体分为父和母2个组，其中母个体承担对编码空间的全局采样，而父个体则用于确定局部搜索的区域范围，系统通过对2组个体选择过程的控制来实现对全局和局部搜索过程的调节.另外，文献[12]利用混沌参数来量化个体间的差异，并根据个体所具有特征值的分布区间对群体进行分类，而参与差分计算的个体则挑选于不同子类，此方法提高了差分进化算法(differential evolution algorithm, DE)对作业调度问题的优化效果.

上述研究使研究者认识到对个体间亲疏关系的利用有助于改进算法的计算性能，但其计算效果依赖于系统对群体在问题空间中分布状态的有效分析.为了改进这一点，部分研究中引入了聚类计算.其中一些研究关注于通过聚类分析获得群体在问题空间中的分布特征并用于优化系统的控制参数.如文献[13]利用k均值聚类运算对群体分类，并以拥有当前最优个体和最差个体的子类中所包含个体的数量差异为依据，通过一个模糊系统对交叉和变异概率进行动态调节.而另一些研究则主要是针对差分进化算法的改进，聚类机制在DE中被用来计算群体所达到空间中的一些典型坐标，其作用类似于一个局部搜索算子.如文献[14]通过k均值聚类将群体中的个体分为k个子类，并通过计算簇类的重心向量来产生k个新个体；文献[15]则通过k个簇类重心个体进一步计算群体的重心向量，并围绕其随机产生p-k个新个体再与k个簇类重心个体一起组成规模为p的下代群体；文献[16]增加了2种交叉算子可分别围绕k个簇类重心向量以及群体的重心向量来进行搜索，文献[17]也采用类似的搜索机制.

上述研究显示，建立在个体间的簇类结构有助于提升模拟进化系统的自我调节能力，改进群体的搜索性能.但上述研究中簇类的规模k及其初始结构多是随机产生的，而事实上簇类组织的规模和结构与群体的搜索特性间有着紧密的联系，因此要使系统在整个搜索过程中能够持续保持合理、有效的计算状态，就需要动态地对簇类的规模和结构进行优化调整，这是现有研究所欠缺的.此外，上述研究中聚类的主要功能多是为了获得群体在问题空间的分布状态或得到局部区域的代表性向量，这未能充分利用簇类结构所形成的对局部空间进行求精搜索的有利条件；同时，簇类间较大的差异性也有助于提高群体对问题空间的勘探效率，这一点在相关研究中同样未被有效重视；另外，簇类结构也为算法协调系统中各种全局性和局部性计算机制间的关系提供了新的途径，而这一研究思路在现有工作中则未被提及.

1.2簇类搜索模型及定义

针对上述研究中的不足，本文提出了一种以簇类为计算的核心单元并基于类结构驱动的新型进化搜索模型——簇类进化算法CEA，其基本计算框架如图1所示：

Fig. 1　The model of cluster searching.图1　簇类搜索模型

不同于传统的EA，CEA不是以静态的群体为基础完成迭代搜索，而是通过动态结构的簇类组织来控制个体的生成和选择过程.在该模型中，簇类组织是一种依据群体在问题编码空间中的分布结构通过聚类计算形成的个体连接关系.在搜索运算中，系统将完全由簇类组织来控制和驱动.首先，簇类搜索运算过程被区分为类间搜索和类内搜索2个层面的计算.类间搜索通过不同子类间的协作来完成对问题空间的勘探，而类内搜索则通过同一子类内的信息交互实现多个局部区域内并行的求精.这种分工机制不仅有利于降低系统中全局性和局部性搜索运算间的耦合性，为更细致地协调二者间的关系提供基础，同时也为有效融合具有不同计算特性的搜索机制提供了环境.其次，系统将通过类迭代完成群体更替.我们注意到，真实的自然选择过程是局部且动态的，但在传统的选择模型中个体基于全局、静态的适应度评价易使个别性能突出的个体产生“占群”现象，促使群体早熟.类迭代中，系统将以子类为单位分别独立进行选择运算，这样既可全面地对群体进行采样，也可保证代表性个体的局部竞争优势.因而类选择迭代机制更符合自然选择的特点，并为实现群体多样性与逼近性间的平衡提供了一个新的方法.

上述模型中CEA具有3个独有的特点：1)簇类组织的规模和结构不是随机的，而是通过聚类计算进行有目地的调整和优化;2)聚类计算在CEA中的作用不是为了产生具有类内相似度最大或类间差异度最大的特定结构，而是通过对类组织的构造来优化系统的搜索状态、改进群体的计算效率，故将聚类计算机制融入群体搜索系统的过程有其特殊性;3)簇类结构改变了EA传统的搜索控制模式.在CEA中，簇类组织是一种介于群体和个体之间且粒度可变的单位，这不同于“个体-群体”静态的2级结构.簇类组织结构的这种可变性使算法在自我调节能力上具有了一种类似调焦的特性，系统可通过放大或缩小类的粒度以及类组织的规模来控制群体的搜索行为，并基于对类间和类内搜索过程间关系的协调来优化群体中全局性和局部性计算间的相互作用过程.

为了便于对算法进行描述，首先给出CEA在连续空间中的一些基本定义：

定义1. 个体I是一个属于D维问题空间S的实数向量，记为I∈S；群体Pop是规模为p的个体集合，即Pop={I1,I2,…,Ip}，其中个体Ii=(x1,x2,…,xD)的适应度值为fi>0，且Ii中每一维变量xj的搜索区间为xlow,j≤xj≤xup,j，j=1,2,…,D.

定义2. 个体Ii与Ij间的相似性可通过欧氏距离比Disi j来度量:

(7)

其中，xup和xlow为S的上下界向量，‖x-y‖表示x和y这2个实数向量的欧几里得范数.

显然，Disi j∈[0,1]，且Disi j愈趋近0说明Ii与Ij的相似性愈大，反之则相反.

定义3. 群体的平均欧氏距离比γ为

(8)

由上述定义可知γ∈[0,1]，且γ愈趋近0说明群体的平均差异性越小，反之则相反.故可用其作为群体多样性和收敛性的观察指标.

(9)

(10)

(11)

(12)

上述定义说明子类中的任意成员都是群体中某个体的唯一投影，而簇类组织则是依据成员所映射个体在问题空间中的分布特征形成的簇类化结构，故簇类组织的变化所改变的只是个体间虚拟的连接关系，个体在群体中的物理位置并未改变，这样有利于提高系统的聚类计算效率.另外，子类所属成员间无交集且簇类结构使得同一子类的成员间更具相似性而不同子类的成员间更具差异性，同时子类的中心成员成为了某个局部区域中最具竞争力和代表性的个体.

2簇类进化算法CEA

算法1为CEA的核心流程，包括了簇类组织初始化(Initializing)、簇类搜索(ClusterSearching)、群体聚类(Clustering)和类选择迭代(Cluster-Selecting)四个主要步骤. 其中,G为总迭代次数，第g代簇类搜索将基于簇类组织Cg控制完成新个体搜索并生成后代群体Popg′，而群体聚类则完成对第g代群体Popg及其后代群体Popg′的空间分布分析并产生新的簇类结构Cg′，最后通过类迭代过程挑选个体构建下代簇类组织Cg+1并产生相应的下代群体Popg+1.

算法1. CEA.

C0=Initializing(Pop0);

while(g

Popg′ =ClusterSearching(Cg);

Cg′=Clustering(Popg,Popg′);

Cg+1=ClusterSelecting(Cg′);

Popg+1=Cg+1;

}

2.1初始化

CEA的初始化包括群体初始化和簇类组织初始化2部分.在群体初始化中，系统将在问题空间S中对群体进行随机分布.在簇类组织初始化中，初始群体中的每个个体将被置为1个初始子类以及该子类的中心成员并形成规模为p的初始簇类组织，即

(13)

其中，i=1,2,…,p，C0中子类Ci的控制序号i取自个体Ii在Pop中的序号，而子类Ci的初始搜索规模参数τi被统一置为2.

2.2簇类搜索

算法2为簇类搜索的核心步骤,其中ch为本代类搜索产生的新个体数量，调节参数η∈(0,1)，UR(0,1)为一均匀分布的随机数.系统将利用子类序号i依次控制不同子类进行搜索，并通过参数τi限制子类Ci搜索的数量.首先进行的类间搜索将在Ci和其他子类间进行广域勘探，所产生的新个体将加入子类Ci;然后，竞争力相对较高的子类(即中心个体适应度值大于群体平均适应度值的子类)有机会通过类内搜索提高其所属成员的竞争力，而参数η被用来调节类内搜索的发生概率.

算法2. 簇类搜索(ClusterSearching).

i=1

ch=0

while (ch

t=0;

while (t<τi){*Ci的搜索过程*

Ci=SearchingAmongCluster(Ci,C);

t=t+2;

SearchingInsideCluster(Ci);

}

ch=ch+t;

i=i+1;

}

2.2.1类间搜索

(14)

(15)

其中，k=1,2,…,D′，变异概率βm为一个接近0的正小数，交叉概率βc∈(βm,1)，u=UR(0,1).

2.2.2类内搜索

类内搜索(SearchingInsideCluster)是只发生在子类所属成员内.我们利用类结构融合了差分搜索的计算方法来提高这一过程的求精效率.基于“DEbest1bin”策略，系统首先从Ci中随机挑选出成员=x1,x2,…,xD以及和(r≠s)，接着由中心成员以及和通过差分计算产生一个随机向量v=(v1,v2,…,vD)，

(16)

(17)

2.2.3簇类搜索的动态调节

簇类搜索中子类进行类内搜索的概率为1-η，故η的取值将直接影响系统每代进行的全局及局部搜索的比例.在CEA中，参数η将利用一个模拟退火过程来进行调节：

η=(exp(-γg

(18)

其中，γg为第g代群体的平均欧氏距离比，而第g代群体的退火温度Tg=T0ρg，T0=G，ρ是一个略小于1的数，ξ∈(0,1).图2为T0=200，ρ=0.95，ξ=0.95且γ分别为0.5，0.2，0.05时η所呈现出的变化曲线.图2说明参数η的变化使得类内搜索的发生概率exp[(-γgTg)-1]ξ保持了逐渐增大的趋势，并可随着群体多样性降低适当放缓趋于最大值ξ的速度.

Fig. 2　The parametric curve of η.图2　参数η的变化曲线

另外，类间搜索中变异运算的发生概率βm将通过一个线性函数来调节,第g代群体的变异概率为

βm=βmup(1-g

(19)

其中,G为总迭代数;βmup,βmlow∈(0,1).式(18)使得βm随着迭代数g的增大逐渐从βmup+βmlow递减到βmlow.

在式(18)(19)的调节下簇类搜索可在系统计算前期形成由“类间交叉+变异”主导的全局性搜索，目标是提高群体对问题空间S的勘探效率；随着1-η的升高，系统中将形成“类间交叉+类内差分+变异”的搜索组合，而随着βm和γ的不断降低且类内搜索频率逐步增加，系统将逐渐向邻域搜索过渡，最终促使群体加速收敛.

2.3群体聚类

显然，簇类搜索过程中类组织的规模和结构将直接影响系统的实际计算效果.下面我们来分析簇类结构的变化影响群体中全局和局部搜索过程的规律.

2.3.1簇类结构对群体搜索特性的调节

假设簇类搜索仅采用交叉运算且群体中的个体都不重复，那么由p(p>2)个个体构成的群体可搜索空间ΦPop将是由Cp2=p(p-1)2个交叉搜索子域所组成.其中由个体Ii和Ij构成的交叉子域的大

若设簇类组织C中所有子类内的个体对({(Ii,Ij)|i≠j,Ii,Ij∈Ck,k=1,2,…,|C|})之间的平均欧氏距离比为a，而所有子类间的个体对({(Ii,Ij)|Ii∈Cr,Ij∈Cs,r≠s,r,s=1,2,…,|C|})的平均欧氏距离比为b，且子类内和子类间个体对的数量分别为x和y，则可得等式γ=(x×a+y×b)(x+y).由于在一代搜索运算中群体的平均欧氏距离比γ以及x+y=Cp2都是定值，故可设Y=Cp2γ，则：

(20)

Fig. 3　The variation trend of x,y and a,b with different |C|.图3　x与y以及a与b随|C|的变化趋势

当每个个体构成一个子类，即|C|=p时，x与a将不存在，而b=γ且y=p；若整个群体构成了一个子类，即|C|=1时，y与b将不存在，而a=γ且x=p.可见，簇类结构在2种极端情况下实际都等效于无结构的单一群体.当1<|C|

由定义3可知，γ代表了当前群体的平均交叉搜索状态，当γ→1时系统将整体倾向于全局勘探，而当γ→0时系统将整体倾向于局部开采.式(19)中的参量a与b以及x与y则分别代表了当1<|C|

综上可见，通过调节簇类结构可以影响系统实际进行的局部和全局搜索的运算效果以及彼此间的相互作用关系，达到调节群体搜索状态的目的.同时，在迭代运算中系统需动态地寻找簇类结构的平衡点，以优化类间和类内搜索间的相互作用过程.

2.3.2簇类组织的构造机制

层次聚类可透过一种层次架构方式反复将数据进行聚合，以形成一个层次序列的聚类问题解.由于这个层次序列的形成过程有利于对簇类组织的规模进行调节，寻找簇类结构的平衡点，故我们借鉴层次聚类的基本思想来设计簇类组织的构造方法.为了提高计算效率，设置了矩阵MI与MC来分别存储个体间距idmi j和类间距cdmi j.设MI=(idmi j)，MC=(cdmi j)，

(21)

(22)

显然矩阵MI与MC都是下三角矩阵，且其对角线上的元素都为0.

在子类自底向上的聚合过程中需要设定一个停止条件.我们注意到:当最小子类间距超过γ时若继续进行子类合并会使参量a与x过度增高，而参量y明显下降，这既会影响类间搜索对问题空间的全局覆盖率也会影响类内求精的效率.故子类聚合的终止条件可设定为

(23)

下面是利用MI与MC对当前群体及其后代群体共2p个个体进行层次聚类的过程.

算法3. 构造簇类组织.

步骤1. 通过式(20)初始化MI，并计算当前群体的平均欧氏距离比γ，接着将每个个体Ii(i=1,2,…,2p)都置为一个子类Ci，并由MI初始化MC.

步骤2. 从MC中找到间距最小的2个子类Cr和Ck，即cdmrk=min(MC)，若满足cdmrk<γ则执行步骤3，否则结束聚类计算生成C′.

步骤3. 合并Cr与Ck组成为新子类Crk′，接着通过式(21)更新MC中Crk′与其余子类的间距值，并返回步骤2.

2.4类选择迭代

算法4. 类选择.

步骤2. 依据子类中心成员的适应度值对Cg′中的所有子类进行顺序排序，得到序列Cg′={C1,C2,…}，其中子类Ci在队列中的位置序号i(i=1,2,…,|Cg′|)将作为它的控制序号；

步骤3. 计算子类Ci的下代个体搜索规模限制参数τi:

τi=[2(|Cg′|-i+1)(|Cg′|2+|Cg′|)]p.

(24)

接着，截取其成员队列的前一半成员作为下代子类的成员，即:

(25)

步骤4. 将子类Ci加入下代类组织Cg+1，其所属成员加入下代群体Popg+1，i=i+1，返回步骤3.

3仿真实验

用VC++6.0实现CEA，并在PC (Pentium4 2.4 GHz,2 GB memory)上对13个典型的约束数值优化问题G01-G13[18]以及6机、15机和20机3个IEEE测试系统进行优化实验.

3.1对标准测试函数的优化实验

文献[18]提出了一种基于随机排序的约束函数处理机制，并将其应用于进化策略(evolutionary strategies， ES)；文献[19]借鉴经济学中“组织”的概念提出了一种改进的数值优化算法(organiza-tional evolutionary algorithm， OEA),ES与OEA对每个函数使用的最大评估次数都被设定为240 000次；文献[20]提出了一种基于定期重启机制的社会认知优化算法(stochastic social cognitive optimization，SSCO)，它对13个函数中的8个函数进行了计算，其函数评估总数为Np+Na×T(Np为知识库中的知识点数量，Na为学习代理的数量，T为学习周期)，实验中Np=98，Na=14，T=2 000.表1为CEA对G01～G13分别独立进行了50次运算后得到的统计结果与上述3种算法实验数据的比较.

Table 1　Summary Results of G01～G13

Continued (Table 1)

Notes:BFVis best function value;MFVis mean function value;Stdis standard deviations;WFVis worst function value.

G01的最小值为-15，4种算法的最优解都可达到此值，其中OEA解的整体质量最高，CEA解的均值仅次于OEA，而SSCO解的质量要好于ES.G02具有最大值0.803 619，CEA的最优解和解均值质量最佳，SSCO具有最好的最差解.G03的最大值为1，CEA，OEA，ES的求解结果非常接近.G04的最小值为-30 665.539，CEA对此函数的求解质量略差于其余3种算法.G05具有最小值5 126.497，CEA，OEA，ES的最优解基本一致，解的均值OEA略好，CEA的最差解质量相对较高.G06的最小值为-6 961.813 88，4种算法的最优解基本一致，CEA与OEA具有最好的解均值.G07的最小值为24.306 209 1，SSCO的最优解最佳，ES的解均值质量最高，CEA具有最好的最差解.G08具有最小值-0.095 825，CEA与OEA及ES的计算结果基本相同且略好于SSCO.G09的最小值为680.630 053 7，G13的最小值为0.053 949 8，对这2个函数OEA具有最佳的最优解和解均值，CEA的计算结果接近OEA.G10的最小值为7 049.330 7，对该函数CEA的计算结果好于ES但略差于其余2种算法.G11的最小值为0.75，G12的最小值为1，CEA与OEA及ES对这2个函数的计算结果都达到了最优值.

整体上来看，OEA所获得的结果最佳，而CEA则能以相对更少的搜索数量使其对13个测试函数的整体解质量接近于OEA并明显好于ES，这体现出CEA具有较高的计算效率.同时，在搜索规模接近的情况下，CEA对SSCO所优化的8个函数中的6个函数的优化均值要略好于SSCO，这说明CEA具有更好的搜索调节能力以及计算稳定性.因此可以说CEA是一种可行且高效的约束数值优化算法.

3.2对ELD问题的优化实验

ELD问题相对上述测试函数具有更高的维度和更复杂的约束，因此求解难度更大.通过对ELD问题的测试可检验CEA对复杂工程优化问题的实际计算能力.下述实验中适应度函数设计为

(26)

其中,Cmax为一足够大的常数，ηpz≥1为禁止运转区域限制系数，若Pi违反约束条件2(式(4))则该系数将为一个大于1的常数，反之则等于1，ηpb∈和π∈为电力平衡系数.

本节实验中的相关参数设置如下：在适应度函数的计算中，当违反禁止操作区域约束时，在6机系统实验中ηpz=1.2，在15机和20机系统实验中ηpz=1.4；在对6机和15机系统实验中电力平衡系数ηpb=100，对20机系统实验中ηpb=200，而π=1.另外，3次实验中CEA的群体规模都为80，而总迭代次数G分别为200，400，500.簇类搜索中交叉概率、变异概率的调节参数以及类内搜索的差分计算的相关参数与前述实验相同.以下是CEA对3个测试系统分别独立进行50次计算后得到的实验数据以及与文献中的其他算法实验结果的比较.

3.2.1对6机系统的实验

IEEE 6机测试系统的能耗特性以及B系数等相关参数见文献[2].当总负荷要求为1 263 MW时该系统目前已报道的最低发电成本是每小时US$ 15 438.49[21]，次优解为每小时US$15 443.10[22]，CEA搜索到的最低成本值为每小时US$1 5437.67，要略好于这2个结果.表2为5种代表性算法的最优解与CEA最优解的对比.

Table 2　Comparison of the Best Solution for IEEE 6 Generators System

Note:FVis cost function value.

表3为提供有统计数据7种算法实验结果的比较，其中BBO[22]采用的群体规模为50，终止条件是迭代1 000代.基于拍卖算法的AA[25]具有计算的确定性，其计算只进行一次.HIC-SQP[21]拥有相对较大的群体(帝国数量为10，殖民地数量为200)，迭代次数为200代.文献[26]中分别使用GA，PSO，DE这3种经典算法对6机和15机系统进行了100次运算，函数评估次数(FE)的上限分别设定为130 000.文献[27]提出了4种不同结构的萤火虫算法，其中融合交叉和变异算子的KHA-IV效果最佳，该算法的群体规模为50，迭代次数为100代.

Table 3　Comparison of the Statistical Results for IEEE 6 Generators System

从迭代代数和搜索数量的角度来看，上述算法在对6机系统的计算中GA，PSO，DE这3种典型算法的运算量最大，KHA-IV相对来说运算量最小，而CEA的运算量则要小于BBO和HIC-SQP.若从CPU时间开销的角度看，对6机系统CEA的每次迭代搜索时间要好于BBO和HIC-SQP.从成本值(FV)的角度来看CEA的解均值质量最好，HIC-SQP次之.

3.2.2对15机系统的实验

IEEE 15机测试系统的能耗特性以及B系数等相关参数见文献[2].当系统总负荷要求为2 630 MW时，该系统已报道的最低发电成本是每小时US$32 547.37[27]，次优解为每小时US$32 619.56[25]，CEA搜索到的最优解为每小时US$32 539.551 1，该成本值要明显优于目前相关文献中报道的最佳结果.表4是为4种算法最优解的对比.

Table 4　Comparison of the Best Solution for IEEE 15 Generators System

表5为7种算法实验统计结果的比较，其中AA，KHA-IV以及GA，PSO，DE这3种经典算法的群体规模及终止条件与6机系统相同.FA[28]采用了一个规模在100以内的可变群体规模，函数评估次数上限设置为50 000，该算法对15机系统的总计算时间平均为16.05 s.

从迭代代数和搜索数量的角度来看，上述算法在对15机系统的计算中GA，PSO，DE这3种典型算法的运算量依然是最大的，KHA-IV相对来说运算量仍是最小的，而CEA的运算量要小于FA.若从CPU时间开销的角度看，对15机系统AA的每代时间开销要小于CEA，但CEA进行一次运算的完整运算时间均值大约为10 s，要好于FA的16.05 s.从成本值(FV)的角度来看,CEA的成本均值质量仍然是最好的，KHA-IV次之.

Table 5　Comparison of the Statistical Results for IEEE 15 Generators System

3.2.3对20机系统的实验

IEEE 20机测试系统的能耗特性以及B系数等相关参数见文献[29].当系统总负荷要求为2 500 MW时，该系统已报道的最低发电成本是每小时US$ 62 456.63[29]，CEA搜索到的最优解为每小时US$ 62 455.58，要略好于这一结果.表6为3种算法最优解的对比.

采用20机系统为测试用例的文献相对较少，文献[29]中也没有提供实验的统计数据.文献[22]中BBO算法采用的群体规模为50，终止条件是迭代1 000代.在表7中我们仅将CEA的实验统计结果与BBO的实验数据进行比较.BBO得到的优化结果的最大值、最小值和均值非常接近，CEA计算得到的最小值要略好于BBO但均值则略差.

Table 6　Comparison of the Best Solution for IEEE 20 Generators System

Table 7　Comparison of the Statistical Results for IEEE 20 Generators System

上述实验数据显示，通过维持较大的搜索数量以及较长的迭代周期EA可以在一定程度上提高解的质量.例如，DE通过130 000次FE对15机系统所得到的成本均值要好于AA和FA.但由于有早熟风险的存在，较大的搜索数量并不一定能保证解的质量，如DE在运算量远大于HIC-SQP的情况下对6机系统的求解质量并不如后者.相对于上述算法，CEA的特点在于它具有更高效的搜索调节能力和突出的抗早熟能力，搜索稳定性更高.例如，对6机系统，在总运算量基本接近的情况下，CEA通过更有效率的搜索计算使得优化结果要整体优于HIC-SQP.而对15机系统，CEA则能以相对有限的运算量为代价明显提高解的质量，使得其最佳解和解的均值都好于KHA-IV.对20机系统，CEA在FE明显小于BBO的情况下使优化均值接近BBO而最优解则略好.可见，CEA具有更为可靠的计算效率及稳定性.

3.3算法分析

CEA的运算实质是利用簇类结构将交叉、变异运算与差分计算方法融合在一起，并利用前者全局搜索性能好的特点通过类间搜索过程保证CEA的全局勘探效率，同时利用后者局部收敛快的特点通过类内搜索过程提高系统的局部求精效果.在类间搜索和类内搜索的协同过程中，簇类结构以及类间和类内搜索的比例关系对CEA的计算过程有着重要影响.利用群体多样性参数γ以及式(22)和式(17)我们可实现在迭代过程中对簇类结构以及类内搜索发生概率1-η的动态调节.此外，交叉和变异算子中的相关参数对类间搜索过程的影响与GA中基本一致，差分计算中的相关参数对类内搜索过程的影响则与DE中基本相同，故在此不再做详细分析.本文将主要讨论增加了聚类过程后系统计算时间复杂度的变化，以及通过对CEA搜索过程中典型系统状态参数变化规律的分析来讨论簇类结构提高系统整体优化效率的原因.

3.3.1时间复杂度分析

进化搜索类算法一般都具有初始化、搜索、适应度评估以及选择迭代4个主要步骤.首先，CEA中初始化和个体适应度评估与传统算法模型是一致的.而类选择机制的计算过程主要包括对2p个个体的排序以及挑选并移动p个个体进入下代群体，相对传统选择模式此过程只是在不同子类内分散完成，故它的计算复杂度与传统排序选择一样都为O(p2).类间搜索与传统群体搜索过程都是通过交叉和变异运算产生p个新个体，其计算频度都是p2，而类内搜索只发生在部分子类中且发生概率在大部分时间内都较小，故其计算频度要小于p，因此簇类搜索与传统搜索模式的计算复杂度都为O(p).综上可见，CEA中额外的计算量主要集中于簇类组织的构造这一过程中.

在算法3中，步骤1的主要计算是构造MI并完成簇类组织初始化，这需要进行2p2-p次欧氏范数的计算；步骤2和步骤3是主要的聚类循环操作，在一次子类聚合中查找最小间距子类对以及更新MC的计算频度都为|C|(|C|-1)，而子类聚合的最多次数为|C|-1，故聚类循环的计算频度为2|C|×(|C|-1)2.因此，算法3的时间复杂度为O(max(p2,|C|3)).首先这个运算规模在可接受的范围内，其次由于簇类组织是一种虚拟的逻辑结构，簇类结构的变化只是改变了个体与子类间的映射关系，这一过程主要是由欧氏范数计算等算术运算所组成，故其计算开销相对于搜索产生新的向量个体并进行物理存储或计算复杂的适应度函数来说相对更小.例如，在表3中我们可发现由于HIC-SQP在每次迭代中进行了更大规模的搜索运算，所以其每代所需的CPU时间反而要大于额外增加了聚类计算的CEA.因此可以说，构造簇类组织所额外花费的计算对系统的总计算量影响是较有限的.

3.3.2算法运算状态分析

此节将主要讨论类间搜索以及类内搜索对CEA计算性能的影响，故对比了CEA以及去掉类内搜索过程的CEA(CEAwithoutDE)和标准遗传算法(GA)对3个系统优化过程中形成的状态参数均值变化曲线，包括平均成本值(FV)、簇类组织平均规模(|C|)以及群体平均多样性(γ)及其方差(δ).图4为3种算法对3个系统独立进行50次后得到的均值曲线.

Fig. 4　Status parameters variation curve of CEA.图4　CEA中系统状态参数的变化曲线

CEAwithoutDE中参数η=1，即它的簇类搜索中类内搜索不发生，系统此时主要依靠类间交叉来进行搜索，它和CEA的对比将体现类内搜索对CEA搜索效率的影响.GA代表了无结构的单一群体搜索机制，它和CEA及CEAwithoutDE的对比将体现簇类搜索使群体搜索产生的变化.GA采用算术交叉和非均匀变异算子以及线性排序选择算子.CEAwithoutDE的群体规模为100，GA的群体规模为200，这使得二者每代花费的FE都要大于CEA，此外二者的其余相关参数与CEA保持一致.

首先来对比CEA，CEAwithoutDE，GA相关参数曲线的差异.整体上看，前二者在对3个系统的计算中虽然|C|曲线都有一定的波动，但大体保持了一个稳定的规模.这种簇类结构使得群体在迭代过程中的群体多样性γ维持一个较为缓慢的递减趋势，这明显不同于GA中γ和其方差δ迅速降低的趋势,而且这一特征随着问题维度的增大就变得更为突出.我们已知参量γ表达了群体搜索的平均状态，而其方差δ则表达了搜索状态的差异性.GA中参量γ和δ的变化说明它的群体经过较短周期的“搜索+选择”计算就会迅速聚拢在一个局部范围内，若全局最优解不在这个区域内，则系统就无法避免产生早熟收敛.显然簇类结构使参量γ和δ具有了一种稳健收敛的过程，这使得群体在搜索的中前期维持了较有效的全局搜索幅度和丰富的差异性，故CEA对3个系统的成本值曲线在初期并不是像GA一般迅速下降而是维持一个相对平缓的下降过程，同时也不会像GA的成本曲线突然出现长时间的停滞，而是保持一个平滑且连续的递减趋势.可见，簇类搜索能够有效提高群体对复杂问题空间的搜索调节能力，在降低早熟的风险的同时维持稳定的搜索效率.

另外，在6机问题的计算中CEA与CEAwithoutDE的搜索过程差异并不明显，但随着问题维度的增大，计算中类内搜索及簇类搜索调节机制的作用就体现的较为突出.只进行类间搜索时系统会使群体在规模较大的问题空间中个体分布更广、更分散，故勘探到的可行解区域会更多，计算前期子类的规模可能会较大同时成本值下降会快些，如图4(b)所示.但缺少了类内搜索，子类将无法对所达区域进行有效的开采，这将影响子类的竞争力，使其在类选择的排序中排名靠后，降低了之后的搜索次数和后代数量.由于类选择只使一半的子类个体生存到下一代，故子类个体规模整体是萎缩的，若无法产生足够的后代个体，子类将逐渐消失，这是导致图4(c)中CEAwithoutDE的簇类规模在计算后期剧烈下降的原因.由此也会进一步影响群体的γ和δ的变化,我们可看到|C|曲线迅速下降时γ和δ的曲线也会产生明显的下降,|C|与γ和δ之间相互干扰的结果会不断影响系统的整体效率.

从CEA的各种曲线的整体走势来看，利用簇类结构来调节群体中全局性和局部性搜索的机制是可行且有效的，类间搜索和类内搜索的协调过程可在显著降低群体早熟风险的同时保证CEA对各种问题空间的优化性能.

4结论

本文提出了基于簇类搜索驱动的群体进化优化机制，形成了一种新型的进化搜索算法——CEA，并将其应用于对ELD问题的求解.在对13个标准约束数值优化问题的实验中，CEA可以相对较小的搜索规模获得较高质量的计算结果，而在对3个IEEE测试系统的仿真实验中CEA所获得的最优结果都要好于现有文献中记载的最佳解.实验的统计数据分析显示CEA对不同规模的ELD问题都具有较强的搜索调节能力以及稳定的计算性能.仿真实验说明，CEA可利用类组织有效融合多种搜索机制，并通过动态调节类间搜索和类内搜索间的协作关系使群体对各种复杂问题空间进行稳定且高效地搜索，这使得它可作为一种高效的约束数值优化算法并应用于求解各类ELD问题.

参考文献

[1]Ciornei I, Kyriakides E. A GA-API solution for the economic dispatch of generation in power system operation [J]. IEEE Trans on Power Systems, 2012, 27(1): 233-242

[2] Lee G Z. Particle swarm optimization to solving the economic dispatch considering the generator constraints [J]. IEEE Trans on Power Systems, 2003, 18(3): 1187-1195

[3] Coelho L S, Lee C S. Solving economic load dispatch problems in power systems using chaotic and Gaussian particle swarm optimization approaches [J]. Electrical Power and Energy Systems, 2008, 30: 297-307

[4]Panigrahi B K, Yadav S R, Agrawal S, et al. A clonal algorithm to solve economic load dispatch [J]. Electric Power Systems Research, 2007, 77: 1381-1389

[5]Coelho L S, Mariani V C. Improved differential evolution algorithms for handling economic dispatch optimization with generator constraints [J]. Energy Conversion and Management, 2007, 48: 1631-1639

[6]Bi Xiaojun, Liu Guo’an, Xiao Jin. Dynamic adaptive differential evolution based on novel mutation strategy[J]. Journal of Computer Research and Development, 2012, 49(6): 1288-1297 (in Chinese)(毕晓君, 刘国安, 肖婧. 基于新变异策略的动态自适应差分进化算法[J]. 计算机研究与发展, 2012, 49(6): 1288-1297)

[7]Wang L, Li L P. A coevolutionary differential evolution with harmony search for reliability-redundancy optimization [J]. Expert Systems with Applications, 2012, 39(5): 5271-5278

[8]Ciornei I, Kyriakides E. Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization [J]. IEEE Trans on Systems, Man, and Cybernetics—Part B, 2012, 42(1): 234-245

[9]Ishibuchi H, Narukawa K, Tsukamoto N, et al. An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization [J]. European Journal of Operational Research, 2008, 188(1): 57-75

[10]Ling Q, Wu G, Yang Z. Crowding clustering genetic algorithm for multimodal function optimization [J]. Applied Soft Computing, 2008, 8(1): 88-95

[11]Martíneza C G, Lozanob M, Herrerab F, et al. Global and local real-coded genetic algorithms based on parent-centric crossover operators [J]. European Journal of Operational Research, 2008, 185(3): 1088-1113

[12]Davendra D, Zelinka I, Davendra B M, et al. Clustered enhanced differential evolution for the blocking flow shop scheduling problem [J]. Central European Journal of Operations Research, 2012, 20(4): 679-717

[13]Zhang J, Chung H, Lo W. Clustering-based adaptive crossover and mutation probabilities for genetic algorithms [J]. IEEE Trans on Evolutionary Computation, 2007, 11 (3): 326-335

[14]Cai Z H, Gong W Y, Ling C X, et al. A clustering-based differential evolution for global optimization [J]. Applied Soft Computing, 2011, 11(1): 1363-1379

[15]Wang Y J, Zhang J S, Zhang G Y. A dynamic clustering-based differential evolution algorithm for global optimization [J]. European Journal of Operational Research, 2007, 183(1): 56-73

[16]Liu G, Li Y X, Niea X, et al. A novel clustering-based differential evolution with 2 multi-parent crossovers for global optimization [J]. Applied Soft Computing, 2012, 12(2): 663-681

[17]Cai Y Q, Wang J H, Yin J. Learning-enhanced differential evolution for numerical optimization [J]. Soft Computing, 2012, 16(2): 303-330

[18]Runarsson T P, Yao X. Stochastic ranking for constrained evolutionary optimization [J]. IEEE Trans Evolutionary Computation, 2000, 4(4): 284-294

[19]Liu J, Zhong W C, Jiao L C. An organizational evolutionary algorithm for numerical optimization [J]. IEEE Trans on Systems, Man, and Cybernetics—Part B, 2007, 37(4): 1052-1064

[20]Sun J, Wang S, Chen H. A guaranteed global convergence social cognitive optimizer [JOL]. Mathematical Problems in Engineering, 2014 [2015-05-01]. http:www.hindawi.comjournalsmpe2014534162

[21]Morshed M J, Asgharpour A. Hybrid imperialist competitive-sequential quadratic programming (HIC-SQP) algorithm for solving economic load dispatch with incorporating stochastic wind power: A comparative study on heuristic optimization techniques [J]. Energy Conversion and Management, 2014, 84: 30-40

[22]Bhattacharya A, Chattopadhyay P K. Biogeography-based optimization for different economic load dispatch problems[J]. IEEE Trans on Power Systems, 2010, 25(2): 1064-1077

[23]Selvakumar A I, Thanushkodi K. A new particle swarm optimization solution to nonconvex economic dispatch problems [J]. IEEE Trans on Power Systems, 2007, 22(1): 42-51

[24]Panigrahi B K, Pandi V R, Das S. Adaptive particle swarm optimization approach for static and dynamic economic load dispatch [J]. Energy Conversion and Management, 2008, 49: 1407-1415

[25]Binetti G, Davoudi A, Naso D, et al. A distributed auction-based algorithm for the nonconvex economic dispatch problem [J]. IEEE Trans on Industrial Informatics, 2014, 10(2):1124-1132

[26]Noman N, Iba H. Differential evolution for economic load dispatch problems [J]. Electric Power System Research, 2008, 78(8): 1322-1331

[27]Mandal B, Roy P K, Mandal S. Economic load dispatch using krill herd algorithm [J]. Electrical Power and Energy Systems, 2014, 57: 1-10

[28]Yang X S, Hosseini S S, Gandomi A H. Firely algorithm for solving non-convex economic dispatch problems with valve loading effect [J]. Applied Soft Computing, 2012, 12: 1180-1186

[29]Su C T, Tung C. New approach with a hopfield modeling framework to economic dispatch [J]. IEEE Trans on Power Systems, 2000, 15(2): 541-545

Chen Hao, born in 1978. PhD. Associate professor and master supervisor. Member of China Computer Federation. His main research interests include evolutionary computing and power system optimization.

Pan Xiaoying, born in 1981. PhD. Associate professor and master supervisor. Her main research interests include multi-agent system and numerical optimization.

Zhang Jie, born in 1992. Master candidate. Her main research interest is constrained numerical optimization algorithm.

收稿日期：2015-05-18；修回日期：2015-10-19

基金项目：国家自然科学基金项目(61203311,61105064)；陕西省教育厅科研计划项目(2013JK1183,2014JK1667)

中图法分类号TP18

A Cluster Evolutionary Algorithm for Power System Economic Load Dispatch Optimization

Chen Hao, Pan Xiaoying, and Zhang Jie

(SchoolofComputerScienceandTechnology,Xi’anUniversityofPosts&Telecommunications,Xi’an710121)

AbstractIn electric power system, economic load dispatch (ELD) is an important topic, which can not only help to build up safety and stable operation plans and prolong the service life of generating units but also can save energy and maximize the economic benefits of power enterprise. The practical ELD problem has non-smooth cost function with nonlinear constraints which make it difficult to be effectively solved. In this study, a novel global optimization algorithm, cluster evolutionary algorithm (CEA), is proposed to solve ELD problem. In CEA, a virtual cluster organization has been constructed among individuals in order to dynamically adjust the searching process of simulated evolutionary system and improve the optimization efficiency of population. In simulations, the CEA has been applied to 13 testing functions and 3 IEEE testing systems for verifying its feasibility. The experiments have shown the CEA can get high quality solutions with lesser computation cost for 13 testing functions. Compared with the other existing techniques, the proposed algorithm has shown better performance for 3 IEEE systems. Considering the quality of the solution obtained, this method seems to be a promising alternative approach for solving the ELD problem in practical power system.

Key wordsevolutionary algorithm (EA); population clustering mechanism; cluster evolutionary searching; constrained numerical optimization; economic load dispatch (ELD)

This work was supported by the National Natural Science Foundation of China (61203311,61105064) and the Scientific Research Program Funded by Shaanxi Provincial Education Department of China (2013JK1183,2014JK1667).