一種基于簇類進化的電力經濟負荷分配優化算法

陳　皓　潘曉英　張　潔

(西安郵電大學計算機學院　西安　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).