陳　皓　潘曉英　張　潔

(西安郵電大學(xué)計(jì)算機(jī)學(xué)院　西安　710121)

?

一種基于簇類進(jìn)化的電力經(jīng)濟(jì)負(fù)荷分配優(yōu)化算法

陳皓潘曉英張潔

(西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安710121)

(chenhao@xupt.edu.cn)

摘要電力經(jīng)濟(jì)負(fù)荷分配不僅能保證電力系統(tǒng)安全穩(wěn)定地運(yùn)行、延長機(jī)組使用壽命，還能節(jié)省能源，最大化電力企業(yè)的經(jīng)濟(jì)效益.此類問題可歸為一種具有高維、不可微目標(biāo)函數(shù)及多個(gè)非線性約束的數(shù)值優(yōu)化問題.提出了一種新型的全局優(yōu)化算法——簇類進(jìn)化算法(cluster evolutionary algorithm, CEA)，并將其應(yīng)用于求解ELD問題.CEA利用聚類過程在進(jìn)化個(gè)體間構(gòu)建一定結(jié)構(gòu)的連接關(guān)系，并利用這種虛擬的簇類化組織來協(xié)調(diào)和控制系統(tǒng)的優(yōu)化計(jì)算過程，提高群體的問題空間搜索效率以及抗早熟能力.在仿真實(shí)驗(yàn)中13個(gè)典型測(cè)試函數(shù)和3個(gè)IEEE系統(tǒng)被用于對(duì)CEA的性能進(jìn)行檢驗(yàn).實(shí)驗(yàn)數(shù)據(jù)顯示CEA對(duì)13個(gè)約束數(shù)值優(yōu)化問題可用較小的計(jì)算代價(jià)獲得較高質(zhì)量的解，而對(duì)3個(gè)測(cè)試系統(tǒng)的計(jì)算結(jié)果則要好于目前已報(bào)道的最佳解.實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)分析顯示CEA是一種高效的數(shù)值優(yōu)化算法，可作為一種有效的ELD問題求解方法.

關(guān)鍵詞進(jìn)化算法；群體聚類機(jī)制；簇類進(jìn)化搜索；約束數(shù)值優(yōu)化；經(jīng)濟(jì)負(fù)荷分配

電力經(jīng)濟(jì)負(fù)荷分配(economic load dispatch, ELD)的目標(biāo)是在一個(gè)發(fā)電系統(tǒng)內(nèi)合理分配各發(fā)電機(jī)的運(yùn)行功率，使得在滿足總負(fù)荷和運(yùn)行約束的條件下發(fā)電成本最小.通常發(fā)電機(jī)組的能耗特性使用二次函數(shù)來近似擬合，能耗函數(shù)為

(1)

其中,F為系統(tǒng)總發(fā)電費(fèi)用(每小時(shí)美元數(shù))，Ng為系統(tǒng)內(nèi)發(fā)電機(jī)總數(shù)；Pi為第i臺(tái)發(fā)電機(jī)的有功功率(MW)；Fi(Pi)為第i臺(tái)發(fā)電機(jī)的耗量特性；αi，βi，γi為其耗量特性常數(shù)，εi為閥點(diǎn)效應(yīng)引起的第i臺(tái)發(fā)電機(jī)耗量特性變化，它可表示為

(2)

發(fā)電機(jī)組在工作時(shí)受3個(gè)約束條件限制：

1) 發(fā)電機(jī)運(yùn)行約束

(3)

2) 禁止運(yùn)轉(zhuǎn)區(qū)域限制

(4)

3) 電力平衡約束

(5)

其中，PL為系統(tǒng)總負(fù)荷，PS為系統(tǒng)總網(wǎng)損.PS可由B系數(shù)法求得，網(wǎng)損與發(fā)電機(jī)有功率關(guān)系為

(6)

其中，P=(P1,P2,…,PNg)T為Ng維發(fā)電機(jī)有功功率列向量，PT為P的轉(zhuǎn)置；B∈Ng×Ng，B0∈Ng，B00∈為網(wǎng)損系數(shù).

ELD問題所具有的高維、不連續(xù)、不可微等特點(diǎn)使得其很難被動(dòng)態(tài)規(guī)劃法、拉格朗日乘數(shù)法等傳統(tǒng)方法有效求解，而進(jìn)化算法(evolutionary algorithm, EA)具有對(duì)目標(biāo)函數(shù)的類型和搜索空間的結(jié)構(gòu)沒有任何限制，同時(shí)對(duì)計(jì)算中數(shù)據(jù)的不確定性也具有很強(qiáng)適應(yīng)能力等特點(diǎn)，故可將傳統(tǒng)方法計(jì)算ELD問題時(shí)忽略的網(wǎng)絡(luò)損失、閥點(diǎn)效應(yīng)等考慮在內(nèi)，這顯著提高了求解的實(shí)用性和有效性.目前，一些典型的進(jìn)化優(yōu)化算法，如遺傳算法[1]、粒子群算法[2-3]、克隆算法[4]、差分進(jìn)化算法[5]等被應(yīng)用于對(duì)該問題的求解計(jì)算并獲得了較好的效果.但是，高維且不連續(xù)的目標(biāo)函數(shù)以及非線性的約束易使EA產(chǎn)生過早收斂或收斂緩慢等現(xiàn)象，在求解ELD問題的實(shí)踐中該問題同樣嚴(yán)重影響了EA實(shí)際的求解質(zhì)量和計(jì)算效果.

進(jìn)化搜索的動(dòng)力源自對(duì)“優(yōu)勝劣汰，適者生存”這一自然法則的模擬，這使得EA的基本計(jì)算框架既有良好的普適性又具有與生俱來的隨機(jī)盲目性.在實(shí)際計(jì)算中，EA需要不斷協(xié)調(diào)系統(tǒng)中從基因位到個(gè)體、群體等不同層面中多種全局性和局部性計(jì)算間的復(fù)雜協(xié)作關(guān)系才可有效降低其固有的隨機(jī)盲目性所帶來的負(fù)面影響.目前，自適應(yīng)機(jī)制[6]是EA改進(jìn)自身計(jì)算協(xié)調(diào)能力及穩(wěn)定性的一種較為常用的方法.但制定合理有效的自適應(yīng)策略本身就是一個(gè)難題，而且受計(jì)算模型復(fù)雜性的限制，自適應(yīng)機(jī)制對(duì)系統(tǒng)性能的改進(jìn)效果也是有限的.近期的一個(gè)研究動(dòng)態(tài)是通過融合多種異構(gòu)的搜索機(jī)制來混合建模[7-8].此類研究顯示，搜索機(jī)制的多樣化不但可有效改善系統(tǒng)的抗早熟能力，還可進(jìn)一步提高群體的搜索速度.但如何平衡系統(tǒng)建模中多樣性與復(fù)雜性以及不同搜索機(jī)制的特殊性及其相互間協(xié)調(diào)性的關(guān)系就成為了一個(gè)新問題.可見，EA對(duì)自身運(yùn)算過程的協(xié)調(diào)和控制能力對(duì)其計(jì)算效果所產(chǎn)生的影響在隨著算法模型的愈發(fā)復(fù)雜而變得越來越突出.

從生物學(xué)的角度看，許多重要進(jìn)化事件的發(fā)生基礎(chǔ)是基因聚類；而從社會(huì)學(xué)的角度看，部落、種族等具有簇類結(jié)構(gòu)特征的社會(huì)單元?jiǎng)t是人類進(jìn)化和文明發(fā)展的基本組織.可見，具有簇類形態(tài)的組織結(jié)構(gòu)在復(fù)雜群體進(jìn)化的發(fā)生和發(fā)展過程中都起到了至關(guān)重要的調(diào)節(jié)和導(dǎo)向作用.受此啟發(fā)，我們認(rèn)為可在個(gè)體間構(gòu)建一定結(jié)構(gòu)的簇類組織，并利用簇類組織對(duì)模擬進(jìn)化系統(tǒng)的運(yùn)算過程進(jìn)行控制和協(xié)調(diào)，以獲得更為高效的進(jìn)化搜索性能.基于此思想，我們提出了簇類進(jìn)化算法(cluster evolutionary algorithm, CEA).在群體搜索過程中，CEA將基于聚類過程動(dòng)態(tài)地構(gòu)建個(gè)體間的虛擬連接關(guān)系即簇類組織，同時(shí)系統(tǒng)將基于這種簇類結(jié)構(gòu)動(dòng)態(tài)調(diào)節(jié)群體中全局性和局部性計(jì)算過程，并融合多種搜索機(jī)制形成有效的互補(bǔ)，以使CEA在計(jì)算的不同階段形成更具針對(duì)性且協(xié)調(diào)性更佳的搜索機(jī)制組合，從而實(shí)現(xiàn)對(duì)復(fù)雜問題空間穩(wěn)定、可靠的優(yōu)化.

本文介紹了CEA的基本模型和主要計(jì)算機(jī)制，并使用13個(gè)測(cè)試函數(shù)和3個(gè)IEEE測(cè)試系統(tǒng)對(duì)CEA的計(jì)算性能進(jìn)行了仿真實(shí)驗(yàn)，同時(shí)對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了對(duì)比和統(tǒng)計(jì)分析，最后給出了結(jié)論.

1簇類搜索模型

1.1相關(guān)工作及問題

在進(jìn)化搜索中，個(gè)體間的編碼差異及其在問題空間的分布與它們所參與搜索運(yùn)算的性能特點(diǎn)間有著一定的聯(lián)系，而研究者一直在嘗試?yán)么祟愱P(guān)系來調(diào)節(jié)群體的搜索過程.如文獻(xiàn)[9]通過基于編碼相似性匹配的約束機(jī)制(mating restriction)來控制交叉運(yùn)算中個(gè)體對(duì)的形成過程，以提高算法對(duì)多目標(biāo)優(yōu)化問題的求解性能.此類研究中系統(tǒng)對(duì)個(gè)體間親疏關(guān)系的利用主要集中于特定的搜索運(yùn)算內(nèi)，而另一些算法則希望通過控制個(gè)體在問題空間的分布形態(tài)來構(gòu)成結(jié)構(gòu)化群體，并基于此調(diào)節(jié)系統(tǒng)的整體計(jì)算過程.如小生境機(jī)制[10]通過排擠或適應(yīng)度共享策略來抑制群體的趨同過程并形成個(gè)體間一定程度地聚集，這種群體結(jié)構(gòu)改善了系統(tǒng)對(duì)多峰問題的計(jì)算效果.但小生境的形成是一個(gè)間接且被動(dòng)的過程，而且個(gè)體間的結(jié)構(gòu)關(guān)系是一種隱式的存在，這使得算法不便于利用其對(duì)系統(tǒng)的計(jì)算過程進(jìn)行更為主動(dòng)地控制.近年的一些研究開始嘗試對(duì)個(gè)體間的彼此關(guān)系進(jìn)行特定地區(qū)分，并利用某種顯式的類別結(jié)構(gòu)來直接控制群體的搜索過程.如文獻(xiàn)[11]從性別的角度將個(gè)體分為父和母2個(gè)組，其中母個(gè)體承擔(dān)對(duì)編碼空間的全局采樣，而父個(gè)體則用于確定局部搜索的區(qū)域范圍，系統(tǒng)通過對(duì)2組個(gè)體選擇過程的控制來實(shí)現(xiàn)對(duì)全局和局部搜索過程的調(diào)節(jié).另外，文獻(xiàn)[12]利用混沌參數(shù)來量化個(gè)體間的差異，并根據(jù)個(gè)體所具有特征值的分布區(qū)間對(duì)群體進(jìn)行分類，而參與差分計(jì)算的個(gè)體則挑選于不同子類，此方法提高了差分進(jìn)化算法(differential evolution algorithm, DE)對(duì)作業(yè)調(diào)度問題的優(yōu)化效果.

上述研究使研究者認(rèn)識(shí)到對(duì)個(gè)體間親疏關(guān)系的利用有助于改進(jìn)算法的計(jì)算性能，但其計(jì)算效果依賴于系統(tǒng)對(duì)群體在問題空間中分布狀態(tài)的有效分析.為了改進(jìn)這一點(diǎn)，部分研究中引入了聚類計(jì)算.其中一些研究關(guān)注于通過聚類分析獲得群體在問題空間中的分布特征并用于優(yōu)化系統(tǒng)的控制參數(shù).如文獻(xiàn)[13]利用k均值聚類運(yùn)算對(duì)群體分類，并以擁有當(dāng)前最優(yōu)個(gè)體和最差個(gè)體的子類中所包含個(gè)體的數(shù)量差異為依據(jù)，通過一個(gè)模糊系統(tǒng)對(duì)交叉和變異概率進(jìn)行動(dòng)態(tài)調(diào)節(jié).而另一些研究則主要是針對(duì)差分進(jìn)化算法的改進(jìn)，聚類機(jī)制在DE中被用來計(jì)算群體所達(dá)到空間中的一些典型坐標(biāo)，其作用類似于一個(gè)局部搜索算子.如文獻(xiàn)[14]通過k均值聚類將群體中的個(gè)體分為k個(gè)子類，并通過計(jì)算簇類的重心向量來產(chǎn)生k個(gè)新個(gè)體；文獻(xiàn)[15]則通過k個(gè)簇類重心個(gè)體進(jìn)一步計(jì)算群體的重心向量，并圍繞其隨機(jī)產(chǎn)生p-k個(gè)新個(gè)體再與k個(gè)簇類重心個(gè)體一起組成規(guī)模為p的下代群體；文獻(xiàn)[16]增加了2種交叉算子可分別圍繞k個(gè)簇類重心向量以及群體的重心向量來進(jìn)行搜索，文獻(xiàn)[17]也采用類似的搜索機(jī)制.

上述研究顯示，建立在個(gè)體間的簇類結(jié)構(gòu)有助于提升模擬進(jìn)化系統(tǒng)的自我調(diào)節(jié)能力，改進(jìn)群體的搜索性能.但上述研究中簇類的規(guī)模k及其初始結(jié)構(gòu)多是隨機(jī)產(chǎn)生的，而事實(shí)上簇類組織的規(guī)模和結(jié)構(gòu)與群體的搜索特性間有著緊密的聯(lián)系，因此要使系統(tǒng)在整個(gè)搜索過程中能夠持續(xù)保持合理、有效的計(jì)算狀態(tài)，就需要?jiǎng)討B(tài)地對(duì)簇類的規(guī)模和結(jié)構(gòu)進(jìn)行優(yōu)化調(diào)整，這是現(xiàn)有研究所欠缺的.此外，上述研究中聚類的主要功能多是為了獲得群體在問題空間的分布狀態(tài)或得到局部區(qū)域的代表性向量，這未能充分利用簇類結(jié)構(gòu)所形成的對(duì)局部空間進(jìn)行求精搜索的有利條件；同時(shí)，簇類間較大的差異性也有助于提高群體對(duì)問題空間的勘探效率，這一點(diǎn)在相關(guān)研究中同樣未被有效重視；另外，簇類結(jié)構(gòu)也為算法協(xié)調(diào)系統(tǒng)中各種全局性和局部性計(jì)算機(jī)制間的關(guān)系提供了新的途徑，而這一研究思路在現(xiàn)有工作中則未被提及.

1.2簇類搜索模型及定義

針對(duì)上述研究中的不足，本文提出了一種以簇類為計(jì)算的核心單元并基于類結(jié)構(gòu)驅(qū)動(dòng)的新型進(jìn)化搜索模型——簇類進(jìn)化算法CEA，其基本計(jì)算框架如圖1所示：

Fig. 1　The model of cluster searching.圖1　簇類搜索模型

不同于傳統(tǒng)的EA，CEA不是以靜態(tài)的群體為基礎(chǔ)完成迭代搜索，而是通過動(dòng)態(tài)結(jié)構(gòu)的簇類組織來控制個(gè)體的生成和選擇過程.在該模型中，簇類組織是一種依據(jù)群體在問題編碼空間中的分布結(jié)構(gòu)通過聚類計(jì)算形成的個(gè)體連接關(guān)系.在搜索運(yùn)算中，系統(tǒng)將完全由簇類組織來控制和驅(qū)動(dòng).首先，簇類搜索運(yùn)算過程被區(qū)分為類間搜索和類內(nèi)搜索2個(gè)層面的計(jì)算.類間搜索通過不同子類間的協(xié)作來完成對(duì)問題空間的勘探，而類內(nèi)搜索則通過同一子類內(nèi)的信息交互實(shí)現(xiàn)多個(gè)局部區(qū)域內(nèi)并行的求精.這種分工機(jī)制不僅有利于降低系統(tǒng)中全局性和局部性搜索運(yùn)算間的耦合性，為更細(xì)致地協(xié)調(diào)二者間的關(guān)系提供基礎(chǔ)，同時(shí)也為有效融合具有不同計(jì)算特性的搜索機(jī)制提供了環(huán)境.其次，系統(tǒng)將通過類迭代完成群體更替.我們注意到，真實(shí)的自然選擇過程是局部且動(dòng)態(tài)的，但在傳統(tǒng)的選擇模型中個(gè)體基于全局、靜態(tài)的適應(yīng)度評(píng)價(jià)易使個(gè)別性能突出的個(gè)體產(chǎn)生“占群”現(xiàn)象，促使群體早熟.類迭代中，系統(tǒng)將以子類為單位分別獨(dú)立進(jìn)行選擇運(yùn)算，這樣既可全面地對(duì)群體進(jìn)行采樣，也可保證代表性個(gè)體的局部競爭優(yōu)勢(shì).因而類選擇迭代機(jī)制更符合自然選擇的特點(diǎn)，并為實(shí)現(xiàn)群體多樣性與逼近性間的平衡提供了一個(gè)新的方法.

上述模型中CEA具有3個(gè)獨(dú)有的特點(diǎn)：1)簇類組織的規(guī)模和結(jié)構(gòu)不是隨機(jī)的，而是通過聚類計(jì)算進(jìn)行有目地的調(diào)整和優(yōu)化;2)聚類計(jì)算在CEA中的作用不是為了產(chǎn)生具有類內(nèi)相似度最大或類間差異度最大的特定結(jié)構(gòu)，而是通過對(duì)類組織的構(gòu)造來優(yōu)化系統(tǒng)的搜索狀態(tài)、改進(jìn)群體的計(jì)算效率，故將聚類計(jì)算機(jī)制融入群體搜索系統(tǒng)的過程有其特殊性;3)簇類結(jié)構(gòu)改變了EA傳統(tǒng)的搜索控制模式.在CEA中，簇類組織是一種介于群體和個(gè)體之間且粒度可變的單位，這不同于“個(gè)體-群體”靜態(tài)的2級(jí)結(jié)構(gòu).簇類組織結(jié)構(gòu)的這種可變性使算法在自我調(diào)節(jié)能力上具有了一種類似調(diào)焦的特性，系統(tǒng)可通過放大或縮小類的粒度以及類組織的規(guī)模來控制群體的搜索行為，并基于對(duì)類間和類內(nèi)搜索過程間關(guān)系的協(xié)調(diào)來優(yōu)化群體中全局性和局部性計(jì)算間的相互作用過程.

為了便于對(duì)算法進(jìn)行描述，首先給出CEA在連續(xù)空間中的一些基本定義：

定義1. 個(gè)體I是一個(gè)屬于D維問題空間S的實(shí)數(shù)向量，記為I∈S；群體Pop是規(guī)模為p的個(gè)體集合，即Pop={I1,I2,…,Ip}，其中個(gè)體Ii=(x1,x2,…,xD)的適應(yīng)度值為fi>0，且Ii中每一維變量xj的搜索區(qū)間為xlow,j≤xj≤xup,j，j=1,2,…,D.

定義2. 個(gè)體Ii與Ij間的相似性可通過歐氏距離比Disi j來度量:

(7)

其中，xup和xlow為S的上下界向量，‖x-y‖表示x和y這2個(gè)實(shí)數(shù)向量的歐幾里得范數(shù).

顯然，Disi j∈[0,1]，且Disi j愈趨近0說明Ii與Ij的相似性愈大，反之則相反.

定義3. 群體的平均歐氏距離比γ為

(8)

由上述定義可知γ∈[0,1]，且γ愈趨近0說明群體的平均差異性越小，反之則相反.故可用其作為群體多樣性和收斂性的觀察指標(biāo).

(9)

(10)

(11)

(12)

上述定義說明子類中的任意成員都是群體中某個(gè)體的唯一投影，而簇類組織則是依據(jù)成員所映射個(gè)體在問題空間中的分布特征形成的簇類化結(jié)構(gòu)，故簇類組織的變化所改變的只是個(gè)體間虛擬的連接關(guān)系，個(gè)體在群體中的物理位置并未改變，這樣有利于提高系統(tǒng)的聚類計(jì)算效率.另外，子類所屬成員間無交集且簇類結(jié)構(gòu)使得同一子類的成員間更具相似性而不同子類的成員間更具差異性，同時(shí)子類的中心成員成為了某個(gè)局部區(qū)域中最具競爭力和代表性的個(gè)體.

2簇類進(jìn)化算法CEA

算法1為CEA的核心流程，包括了簇類組織初始化(Initializing)、簇類搜索(ClusterSearching)、群體聚類(Clustering)和類選擇迭代(Cluster-Selecting)四個(gè)主要步驟. 其中,G為總迭代次數(shù)，第g代簇類搜索將基于簇類組織Cg控制完成新個(gè)體搜索并生成后代群體Popg′，而群體聚類則完成對(duì)第g代群體Popg及其后代群體Popg′的空間分布分析并產(chǎn)生新的簇類結(jié)構(gòu)Cg′，最后通過類迭代過程挑選個(gè)體構(gòu)建下代簇類組織Cg+1并產(chǎn)生相應(yīng)的下代群體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部分.在群體初始化中，系統(tǒng)將在問題空間S中對(duì)群體進(jìn)行隨機(jī)分布.在簇類組織初始化中，初始群體中的每個(gè)個(gè)體將被置為1個(gè)初始子類以及該子類的中心成員并形成規(guī)模為p的初始簇類組織，即

(13)

其中，i=1,2,…,p，C0中子類Ci的控制序號(hào)i取自個(gè)體Ii在Pop中的序號(hào)，而子類Ci的初始搜索規(guī)模參數(shù)τi被統(tǒng)一置為2.

2.2簇類搜索

算法2為簇類搜索的核心步驟,其中ch為本代類搜索產(chǎn)生的新個(gè)體數(shù)量，調(diào)節(jié)參數(shù)η∈(0,1)，UR(0,1)為一均勻分布的隨機(jī)數(shù).系統(tǒng)將利用子類序號(hào)i依次控制不同子類進(jìn)行搜索，并通過參數(shù)τi限制子類Ci搜索的數(shù)量.首先進(jìn)行的類間搜索將在Ci和其他子類間進(jìn)行廣域勘探，所產(chǎn)生的新個(gè)體將加入子類Ci;然后，競爭力相對(duì)較高的子類(即中心個(gè)體適應(yīng)度值大于群體平均適應(yīng)度值的子類)有機(jī)會(huì)通過類內(nèi)搜索提高其所屬成員的競爭力，而參數(shù)η被用來調(diào)節(jié)類內(nèi)搜索的發(fā)生概率.

算法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為一個(gè)接近0的正小數(shù)，交叉概率βc∈(βm,1)，u=UR(0,1).

2.2.2類內(nèi)搜索

類內(nèi)搜索(SearchingInsideCluster)是只發(fā)生在子類所屬成員內(nèi).我們利用類結(jié)構(gòu)融合了差分搜索的計(jì)算方法來提高這一過程的求精效率.基于“DEbest1bin”策略，系統(tǒng)首先從Ci中隨機(jī)挑選出成員=x1,x2,…,xD以及和(r≠s)，接著由中心成員以及和通過差分計(jì)算產(chǎn)生一個(gè)隨機(jī)向量v=(v1,v2,…,vD)，

(16)

(17)

2.2.3簇類搜索的動(dòng)態(tài)調(diào)節(jié)

簇類搜索中子類進(jìn)行類內(nèi)搜索的概率為1-η，故η的取值將直接影響系統(tǒng)每代進(jìn)行的全局及局部搜索的比例.在CEA中，參數(shù)η將利用一個(gè)模擬退火過程來進(jìn)行調(diào)節(jié)：

η=(exp(-γg

(18)

其中，γg為第g代群體的平均歐氏距離比，而第g代群體的退火溫度Tg=T0ρg，T0=G，ρ是一個(gè)略小于1的數(shù)，ξ∈(0,1).圖2為T0=200，ρ=0.95，ξ=0.95且γ分別為0.5，0.2，0.05時(shí)η所呈現(xiàn)出的變化曲線.圖2說明參數(shù)η的變化使得類內(nèi)搜索的發(fā)生概率exp[(-γgTg)-1]ξ保持了逐漸增大的趨勢(shì)，并可隨著群體多樣性降低適當(dāng)放緩趨于最大值ξ的速度.

Fig. 2　The parametric curve of η.圖2　參數(shù)η的變化曲線

另外，類間搜索中變異運(yùn)算的發(fā)生概率βm將通過一個(gè)線性函數(shù)來調(diào)節(jié),第g代群體的變異概率為

βm=βmup(1-g

(19)

其中,G為總迭代數(shù);βmup,βmlow∈(0,1).式(18)使得βm隨著迭代數(shù)g的增大逐漸從βmup+βmlow遞減到βmlow.

在式(18)(19)的調(diào)節(jié)下簇類搜索可在系統(tǒng)計(jì)算前期形成由“類間交叉+變異”主導(dǎo)的全局性搜索，目標(biāo)是提高群體對(duì)問題空間S的勘探效率；隨著1-η的升高，系統(tǒng)中將形成“類間交叉+類內(nèi)差分+變異”的搜索組合，而隨著βm和γ的不斷降低且類內(nèi)搜索頻率逐步增加，系統(tǒng)將逐漸向鄰域搜索過渡，最終促使群體加速收斂.

2.3群體聚類

顯然，簇類搜索過程中類組織的規(guī)模和結(jié)構(gòu)將直接影響系統(tǒng)的實(shí)際計(jì)算效果.下面我們來分析簇類結(jié)構(gòu)的變化影響群體中全局和局部搜索過程的規(guī)律.

2.3.1簇類結(jié)構(gòu)對(duì)群體搜索特性的調(diào)節(jié)

假設(shè)簇類搜索僅采用交叉運(yùn)算且群體中的個(gè)體都不重復(fù)，那么由p(p>2)個(gè)個(gè)體構(gòu)成的群體可搜索空間ΦPop將是由Cp2=p(p-1)2個(gè)交叉搜索子域所組成.其中由個(gè)體Ii和Ij構(gòu)成的交叉子域的大

若設(shè)簇類組織C中所有子類內(nèi)的個(gè)體對(duì)({(Ii,Ij)|i≠j,Ii,Ij∈Ck,k=1,2,…,|C|})之間的平均歐氏距離比為a，而所有子類間的個(gè)體對(duì)({(Ii,Ij)|Ii∈Cr,Ij∈Cs,r≠s,r,s=1,2,…,|C|})的平均歐氏距離比為b，且子類內(nèi)和子類間個(gè)體對(duì)的數(shù)量分別為x和y，則可得等式γ=(x×a+y×b)(x+y).由于在一代搜索運(yùn)算中群體的平均歐氏距離比γ以及x+y=Cp2都是定值，故可設(shè)Y=Cp2γ，則：

(20)

Fig. 3　The variation trend of x,y and a,b with different |C|.圖3　x與y以及a與b隨|C|的變化趨勢(shì)

當(dāng)每個(gè)個(gè)體構(gòu)成一個(gè)子類，即|C|=p時(shí)，x與a將不存在，而b=γ且y=p；若整個(gè)群體構(gòu)成了一個(gè)子類，即|C|=1時(shí)，y與b將不存在，而a=γ且x=p.可見，簇類結(jié)構(gòu)在2種極端情況下實(shí)際都等效于無結(jié)構(gòu)的單一群體.當(dāng)1<|C|

由定義3可知，γ代表了當(dāng)前群體的平均交叉搜索狀態(tài)，當(dāng)γ→1時(shí)系統(tǒng)將整體傾向于全局勘探，而當(dāng)γ→0時(shí)系統(tǒng)將整體傾向于局部開采.式(19)中的參量a與b以及x與y則分別代表了當(dāng)1<|C|

綜上可見，通過調(diào)節(jié)簇類結(jié)構(gòu)可以影響系統(tǒng)實(shí)際進(jìn)行的局部和全局搜索的運(yùn)算效果以及彼此間的相互作用關(guān)系，達(dá)到調(diào)節(jié)群體搜索狀態(tài)的目的.同時(shí)，在迭代運(yùn)算中系統(tǒng)需動(dòng)態(tài)地尋找簇類結(jié)構(gòu)的平衡點(diǎn)，以優(yōu)化類間和類內(nèi)搜索間的相互作用過程.

2.3.2簇類組織的構(gòu)造機(jī)制

層次聚類可透過一種層次架構(gòu)方式反復(fù)將數(shù)據(jù)進(jìn)行聚合，以形成一個(gè)層次序列的聚類問題解.由于這個(gè)層次序列的形成過程有利于對(duì)簇類組織的規(guī)模進(jìn)行調(diào)節(jié)，尋找簇類結(jié)構(gòu)的平衡點(diǎn)，故我們借鑒層次聚類的基本思想來設(shè)計(jì)簇類組織的構(gòu)造方法.為了提高計(jì)算效率，設(shè)置了矩陣MI與MC來分別存儲(chǔ)個(gè)體間距idmi j和類間距cdmi j.設(shè)MI=(idmi j)，MC=(cdmi j)，

(21)

(22)

顯然矩陣MI與MC都是下三角矩陣，且其對(duì)角線上的元素都為0.

在子類自底向上的聚合過程中需要設(shè)定一個(gè)停止條件.我們注意到:當(dāng)最小子類間距超過γ時(shí)若繼續(xù)進(jìn)行子類合并會(huì)使參量a與x過度增高，而參量y明顯下降，這既會(huì)影響類間搜索對(duì)問題空間的全局覆蓋率也會(huì)影響類內(nèi)求精的效率.故子類聚合的終止條件可設(shè)定為

(23)

下面是利用MI與MC對(duì)當(dāng)前群體及其后代群體共2p個(gè)個(gè)體進(jìn)行層次聚類的過程.

算法3. 構(gòu)造簇類組織.

步驟1. 通過式(20)初始化MI，并計(jì)算當(dāng)前群體的平均歐氏距離比γ，接著將每個(gè)個(gè)體Ii(i=1,2,…,2p)都置為一個(gè)子類Ci，并由MI初始化MC.

步驟2. 從MC中找到間距最小的2個(gè)子類Cr和Ck，即cdmrk=min(MC)，若滿足cdmrk<γ則執(zhí)行步驟3，否則結(jié)束聚類計(jì)算生成C′.

步驟3. 合并Cr與Ck組成為新子類Crk′，接著通過式(21)更新MC中Crk′與其余子類的間距值，并返回步驟2.

2.4類選擇迭代

算法4. 類選擇.

步驟2. 依據(jù)子類中心成員的適應(yīng)度值對(duì)Cg′中的所有子類進(jìn)行順序排序，得到序列Cg′={C1,C2,…}，其中子類Ci在隊(duì)列中的位置序號(hào)i(i=1,2,…,|Cg′|)將作為它的控制序號(hào)；

步驟3. 計(jì)算子類Ci的下代個(gè)體搜索規(guī)模限制參數(shù)τi:

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

(24)

接著，截取其成員隊(duì)列的前一半成員作為下代子類的成員，即:

(25)

步驟4. 將子類Ci加入下代類組織Cg+1，其所屬成員加入下代群體Popg+1，i=i+1，返回步驟3.

3仿真實(shí)驗(yàn)

用VC++6.0實(shí)現(xiàn)CEA，并在PC (Pentium4 2.4 GHz,2 GB memory)上對(duì)13個(gè)典型的約束數(shù)值優(yōu)化問題G01-G13[18]以及6機(jī)、15機(jī)和20機(jī)3個(gè)IEEE測(cè)試系統(tǒng)進(jìn)行優(yōu)化實(shí)驗(yàn).

3.1對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)的優(yōu)化實(shí)驗(yàn)

文獻(xiàn)[18]提出了一種基于隨機(jī)排序的約束函數(shù)處理機(jī)制，并將其應(yīng)用于進(jìn)化策略(evolutionary strategies， ES)；文獻(xiàn)[19]借鑒經(jīng)濟(jì)學(xué)中“組織”的概念提出了一種改進(jìn)的數(shù)值優(yōu)化算法(organiza-tional evolutionary algorithm， OEA),ES與OEA對(duì)每個(gè)函數(shù)使用的最大評(píng)估次數(shù)都被設(shè)定為240 000次；文獻(xiàn)[20]提出了一種基于定期重啟機(jī)制的社會(huì)認(rèn)知優(yōu)化算法(stochastic social cognitive optimization，SSCO)，它對(duì)13個(gè)函數(shù)中的8個(gè)函數(shù)進(jìn)行了計(jì)算，其函數(shù)評(píng)估總數(shù)為Np+Na×T(Np為知識(shí)庫中的知識(shí)點(diǎn)數(shù)量，Na為學(xué)習(xí)代理的數(shù)量，T為學(xué)習(xí)周期)，實(shí)驗(yàn)中Np=98，Na=14，T=2 000.表1為CEA對(duì)G01～G13分別獨(dú)立進(jìn)行了50次運(yùn)算后得到的統(tǒng)計(jì)結(jié)果與上述3種算法實(shí)驗(yàn)數(shù)據(jù)的比較.

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種算法的最優(yōu)解都可達(dá)到此值，其中OEA解的整體質(zhì)量最高，CEA解的均值僅次于OEA，而SSCO解的質(zhì)量要好于ES.G02具有最大值0.803 619，CEA的最優(yōu)解和解均值質(zhì)量最佳，SSCO具有最好的最差解.G03的最大值為1，CEA，OEA，ES的求解結(jié)果非常接近.G04的最小值為-30 665.539，CEA對(duì)此函數(shù)的求解質(zhì)量略差于其余3種算法.G05具有最小值5 126.497，CEA，OEA，ES的最優(yōu)解基本一致，解的均值OEA略好，CEA的最差解質(zhì)量相對(duì)較高.G06的最小值為-6 961.813 88，4種算法的最優(yōu)解基本一致，CEA與OEA具有最好的解均值.G07的最小值為24.306 209 1，SSCO的最優(yōu)解最佳，ES的解均值質(zhì)量最高，CEA具有最好的最差解.G08具有最小值-0.095 825，CEA與OEA及ES的計(jì)算結(jié)果基本相同且略好于SSCO.G09的最小值為680.630 053 7，G13的最小值為0.053 949 8，對(duì)這2個(gè)函數(shù)OEA具有最佳的最優(yōu)解和解均值，CEA的計(jì)算結(jié)果接近OEA.G10的最小值為7 049.330 7，對(duì)該函數(shù)CEA的計(jì)算結(jié)果好于ES但略差于其余2種算法.G11的最小值為0.75，G12的最小值為1，CEA與OEA及ES對(duì)這2個(gè)函數(shù)的計(jì)算結(jié)果都達(dá)到了最優(yōu)值.

整體上來看，OEA所獲得的結(jié)果最佳，而CEA則能以相對(duì)更少的搜索數(shù)量使其對(duì)13個(gè)測(cè)試函數(shù)的整體解質(zhì)量接近于OEA并明顯好于ES，這體現(xiàn)出CEA具有較高的計(jì)算效率.同時(shí)，在搜索規(guī)模接近的情況下，CEA對(duì)SSCO所優(yōu)化的8個(gè)函數(shù)中的6個(gè)函數(shù)的優(yōu)化均值要略好于SSCO，這說明CEA具有更好的搜索調(diào)節(jié)能力以及計(jì)算穩(wěn)定性.因此可以說CEA是一種可行且高效的約束數(shù)值優(yōu)化算法.

3.2對(duì)ELD問題的優(yōu)化實(shí)驗(yàn)

ELD問題相對(duì)上述測(cè)試函數(shù)具有更高的維度和更復(fù)雜的約束，因此求解難度更大.通過對(duì)ELD問題的測(cè)試可檢驗(yàn)CEA對(duì)復(fù)雜工程優(yōu)化問題的實(shí)際計(jì)算能力.下述實(shí)驗(yàn)中適應(yīng)度函數(shù)設(shè)計(jì)為

(26)

其中,Cmax為一足夠大的常數(shù)，ηpz≥1為禁止運(yùn)轉(zhuǎn)區(qū)域限制系數(shù)，若Pi違反約束條件2(式(4))則該系數(shù)將為一個(gè)大于1的常數(shù)，反之則等于1，ηpb∈和π∈為電力平衡系數(shù).

本節(jié)實(shí)驗(yàn)中的相關(guān)參數(shù)設(shè)置如下：在適應(yīng)度函數(shù)的計(jì)算中，當(dāng)違反禁止操作區(qū)域約束時(shí)，在6機(jī)系統(tǒng)實(shí)驗(yàn)中ηpz=1.2，在15機(jī)和20機(jī)系統(tǒng)實(shí)驗(yàn)中ηpz=1.4；在對(duì)6機(jī)和15機(jī)系統(tǒng)實(shí)驗(yàn)中電力平衡系數(shù)ηpb=100，對(duì)20機(jī)系統(tǒng)實(shí)驗(yàn)中ηpb=200，而π=1.另外，3次實(shí)驗(yàn)中CEA的群體規(guī)模都為80，而總迭代次數(shù)G分別為200，400，500.簇類搜索中交叉概率、變異概率的調(diào)節(jié)參數(shù)以及類內(nèi)搜索的差分計(jì)算的相關(guān)參數(shù)與前述實(shí)驗(yàn)相同.以下是CEA對(duì)3個(gè)測(cè)試系統(tǒng)分別獨(dú)立進(jìn)行50次計(jì)算后得到的實(shí)驗(yàn)數(shù)據(jù)以及與文獻(xiàn)中的其他算法實(shí)驗(yàn)結(jié)果的比較.

3.2.1對(duì)6機(jī)系統(tǒng)的實(shí)驗(yàn)

IEEE 6機(jī)測(cè)試系統(tǒng)的能耗特性以及B系數(shù)等相關(guān)參數(shù)見文獻(xiàn)[2].當(dāng)總負(fù)荷要求為1 263 MW時(shí)該系統(tǒng)目前已報(bào)道的最低發(fā)電成本是每小時(shí)US$ 15 438.49[21]，次優(yōu)解為每小時(shí)US$15 443.10[22]，CEA搜索到的最低成本值為每小時(shí)US$1 5437.67，要略好于這2個(gè)結(jié)果.表2為5種代表性算法的最優(yōu)解與CEA最優(yōu)解的對(duì)比.

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

Note:FVis cost function value.

表3為提供有統(tǒng)計(jì)數(shù)據(jù)7種算法實(shí)驗(yàn)結(jié)果的比較，其中BBO[22]采用的群體規(guī)模為50，終止條件是迭代1 000代.基于拍賣算法的AA[25]具有計(jì)算的確定性，其計(jì)算只進(jìn)行一次.HIC-SQP[21]擁有相對(duì)較大的群體(帝國數(shù)量為10，殖民地?cái)?shù)量為200)，迭代次數(shù)為200代.文獻(xiàn)[26]中分別使用GA，PSO，DE這3種經(jīng)典算法對(duì)6機(jī)和15機(jī)系統(tǒng)進(jìn)行了100次運(yùn)算，函數(shù)評(píng)估次數(shù)(FE)的上限分別設(shè)定為130 000.文獻(xiàn)[27]提出了4種不同結(jié)構(gòu)的螢火蟲算法，其中融合交叉和變異算子的KHA-IV效果最佳，該算法的群體規(guī)模為50，迭代次數(shù)為100代.

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

從迭代代數(shù)和搜索數(shù)量的角度來看，上述算法在對(duì)6機(jī)系統(tǒng)的計(jì)算中GA，PSO，DE這3種典型算法的運(yùn)算量最大，KHA-IV相對(duì)來說運(yùn)算量最小，而CEA的運(yùn)算量則要小于BBO和HIC-SQP.若從CPU時(shí)間開銷的角度看，對(duì)6機(jī)系統(tǒng)CEA的每次迭代搜索時(shí)間要好于BBO和HIC-SQP.從成本值(FV)的角度來看CEA的解均值質(zhì)量最好，HIC-SQP次之.

3.2.2對(duì)15機(jī)系統(tǒng)的實(shí)驗(yàn)

IEEE 15機(jī)測(cè)試系統(tǒng)的能耗特性以及B系數(shù)等相關(guān)參數(shù)見文獻(xiàn)[2].當(dāng)系統(tǒng)總負(fù)荷要求為2 630 MW時(shí)，該系統(tǒng)已報(bào)道的最低發(fā)電成本是每小時(shí)US$32 547.37[27]，次優(yōu)解為每小時(shí)US$32 619.56[25]，CEA搜索到的最優(yōu)解為每小時(shí)US$32 539.551 1，該成本值要明顯優(yōu)于目前相關(guān)文獻(xiàn)中報(bào)道的最佳結(jié)果.表4是為4種算法最優(yōu)解的對(duì)比.

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

表5為7種算法實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果的比較，其中AA，KHA-IV以及GA，PSO，DE這3種經(jīng)典算法的群體規(guī)模及終止條件與6機(jī)系統(tǒng)相同.FA[28]采用了一個(gè)規(guī)模在100以內(nèi)的可變?nèi)后w規(guī)模，函數(shù)評(píng)估次數(shù)上限設(shè)置為50 000，該算法對(duì)15機(jī)系統(tǒng)的總計(jì)算時(shí)間平均為16.05 s.

從迭代代數(shù)和搜索數(shù)量的角度來看，上述算法在對(duì)15機(jī)系統(tǒng)的計(jì)算中GA，PSO，DE這3種典型算法的運(yùn)算量依然是最大的，KHA-IV相對(duì)來說運(yùn)算量仍是最小的，而CEA的運(yùn)算量要小于FA.若從CPU時(shí)間開銷的角度看，對(duì)15機(jī)系統(tǒng)AA的每代時(shí)間開銷要小于CEA，但CEA進(jìn)行一次運(yùn)算的完整運(yùn)算時(shí)間均值大約為10 s，要好于FA的16.05 s.從成本值(FV)的角度來看,CEA的成本均值質(zhì)量仍然是最好的，KHA-IV次之.

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

3.2.3對(duì)20機(jī)系統(tǒng)的實(shí)驗(yàn)

IEEE 20機(jī)測(cè)試系統(tǒng)的能耗特性以及B系數(shù)等相關(guān)參數(shù)見文獻(xiàn)[29].當(dāng)系統(tǒng)總負(fù)荷要求為2 500 MW時(shí)，該系統(tǒng)已報(bào)道的最低發(fā)電成本是每小時(shí)US$ 62 456.63[29]，CEA搜索到的最優(yōu)解為每小時(shí)US$ 62 455.58，要略好于這一結(jié)果.表6為3種算法最優(yōu)解的對(duì)比.

采用20機(jī)系統(tǒng)為測(cè)試用例的文獻(xiàn)相對(duì)較少，文獻(xiàn)[29]中也沒有提供實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù).文獻(xiàn)[22]中BBO算法采用的群體規(guī)模為50，終止條件是迭代1 000代.在表7中我們僅將CEA的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果與BBO的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行比較.BBO得到的優(yōu)化結(jié)果的最大值、最小值和均值非常接近，CEA計(jì)算得到的最小值要略好于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

上述實(shí)驗(yàn)數(shù)據(jù)顯示，通過維持較大的搜索數(shù)量以及較長的迭代周期EA可以在一定程度上提高解的質(zhì)量.例如，DE通過130 000次FE對(duì)15機(jī)系統(tǒng)所得到的成本均值要好于AA和FA.但由于有早熟風(fēng)險(xiǎn)的存在，較大的搜索數(shù)量并不一定能保證解的質(zhì)量，如DE在運(yùn)算量遠(yuǎn)大于HIC-SQP的情況下對(duì)6機(jī)系統(tǒng)的求解質(zhì)量并不如后者.相對(duì)于上述算法，CEA的特點(diǎn)在于它具有更高效的搜索調(diào)節(jié)能力和突出的抗早熟能力，搜索穩(wěn)定性更高.例如，對(duì)6機(jī)系統(tǒng)，在總運(yùn)算量基本接近的情況下，CEA通過更有效率的搜索計(jì)算使得優(yōu)化結(jié)果要整體優(yōu)于HIC-SQP.而對(duì)15機(jī)系統(tǒng)，CEA則能以相對(duì)有限的運(yùn)算量為代價(jià)明顯提高解的質(zhì)量，使得其最佳解和解的均值都好于KHA-IV.對(duì)20機(jī)系統(tǒng)，CEA在FE明顯小于BBO的情況下使優(yōu)化均值接近BBO而最優(yōu)解則略好.可見，CEA具有更為可靠的計(jì)算效率及穩(wěn)定性.

3.3算法分析

CEA的運(yùn)算實(shí)質(zhì)是利用簇類結(jié)構(gòu)將交叉、變異運(yùn)算與差分計(jì)算方法融合在一起，并利用前者全局搜索性能好的特點(diǎn)通過類間搜索過程保證CEA的全局勘探效率，同時(shí)利用后者局部收斂快的特點(diǎn)通過類內(nèi)搜索過程提高系統(tǒng)的局部求精效果.在類間搜索和類內(nèi)搜索的協(xié)同過程中，簇類結(jié)構(gòu)以及類間和類內(nèi)搜索的比例關(guān)系對(duì)CEA的計(jì)算過程有著重要影響.利用群體多樣性參數(shù)γ以及式(22)和式(17)我們可實(shí)現(xiàn)在迭代過程中對(duì)簇類結(jié)構(gòu)以及類內(nèi)搜索發(fā)生概率1-η的動(dòng)態(tài)調(diào)節(jié).此外，交叉和變異算子中的相關(guān)參數(shù)對(duì)類間搜索過程的影響與GA中基本一致，差分計(jì)算中的相關(guān)參數(shù)對(duì)類內(nèi)搜索過程的影響則與DE中基本相同，故在此不再做詳細(xì)分析.本文將主要討論增加了聚類過程后系統(tǒng)計(jì)算時(shí)間復(fù)雜度的變化，以及通過對(duì)CEA搜索過程中典型系統(tǒng)狀態(tài)參數(shù)變化規(guī)律的分析來討論簇類結(jié)構(gòu)提高系統(tǒng)整體優(yōu)化效率的原因.

3.3.1時(shí)間復(fù)雜度分析

進(jìn)化搜索類算法一般都具有初始化、搜索、適應(yīng)度評(píng)估以及選擇迭代4個(gè)主要步驟.首先，CEA中初始化和個(gè)體適應(yīng)度評(píng)估與傳統(tǒng)算法模型是一致的.而類選擇機(jī)制的計(jì)算過程主要包括對(duì)2p個(gè)個(gè)體的排序以及挑選并移動(dòng)p個(gè)個(gè)體進(jìn)入下代群體，相對(duì)傳統(tǒng)選擇模式此過程只是在不同子類內(nèi)分散完成，故它的計(jì)算復(fù)雜度與傳統(tǒng)排序選擇一樣都為O(p2).類間搜索與傳統(tǒng)群體搜索過程都是通過交叉和變異運(yùn)算產(chǎn)生p個(gè)新個(gè)體，其計(jì)算頻度都是p2，而類內(nèi)搜索只發(fā)生在部分子類中且發(fā)生概率在大部分時(shí)間內(nèi)都較小，故其計(jì)算頻度要小于p，因此簇類搜索與傳統(tǒng)搜索模式的計(jì)算復(fù)雜度都為O(p).綜上可見，CEA中額外的計(jì)算量主要集中于簇類組織的構(gòu)造這一過程中.

在算法3中，步驟1的主要計(jì)算是構(gòu)造MI并完成簇類組織初始化，這需要進(jìn)行2p2-p次歐氏范數(shù)的計(jì)算；步驟2和步驟3是主要的聚類循環(huán)操作，在一次子類聚合中查找最小間距子類對(duì)以及更新MC的計(jì)算頻度都為|C|(|C|-1)，而子類聚合的最多次數(shù)為|C|-1，故聚類循環(huán)的計(jì)算頻度為2|C|×(|C|-1)2.因此，算法3的時(shí)間復(fù)雜度為O(max(p2,|C|3)).首先這個(gè)運(yùn)算規(guī)模在可接受的范圍內(nèi)，其次由于簇類組織是一種虛擬的邏輯結(jié)構(gòu)，簇類結(jié)構(gòu)的變化只是改變了個(gè)體與子類間的映射關(guān)系，這一過程主要是由歐氏范數(shù)計(jì)算等算術(shù)運(yùn)算所組成，故其計(jì)算開銷相對(duì)于搜索產(chǎn)生新的向量個(gè)體并進(jìn)行物理存儲(chǔ)或計(jì)算復(fù)雜的適應(yīng)度函數(shù)來說相對(duì)更小.例如，在表3中我們可發(fā)現(xiàn)由于HIC-SQP在每次迭代中進(jìn)行了更大規(guī)模的搜索運(yùn)算，所以其每代所需的CPU時(shí)間反而要大于額外增加了聚類計(jì)算的CEA.因此可以說，構(gòu)造簇類組織所額外花費(fèi)的計(jì)算對(duì)系統(tǒng)的總計(jì)算量影響是較有限的.

3.3.2算法運(yùn)算狀態(tài)分析

此節(jié)將主要討論類間搜索以及類內(nèi)搜索對(duì)CEA計(jì)算性能的影響，故對(duì)比了CEA以及去掉類內(nèi)搜索過程的CEA(CEAwithoutDE)和標(biāo)準(zhǔn)遺傳算法(GA)對(duì)3個(gè)系統(tǒng)優(yōu)化過程中形成的狀態(tài)參數(shù)均值變化曲線，包括平均成本值(FV)、簇類組織平均規(guī)模(|C|)以及群體平均多樣性(γ)及其方差(δ).圖4為3種算法對(duì)3個(gè)系統(tǒng)獨(dú)立進(jìn)行50次后得到的均值曲線.

Fig. 4　Status parameters variation curve of CEA.圖4　CEA中系統(tǒng)狀態(tài)參數(shù)的變化曲線

CEAwithoutDE中參數(shù)η=1，即它的簇類搜索中類內(nèi)搜索不發(fā)生，系統(tǒng)此時(shí)主要依靠類間交叉來進(jìn)行搜索，它和CEA的對(duì)比將體現(xiàn)類內(nèi)搜索對(duì)CEA搜索效率的影響.GA代表了無結(jié)構(gòu)的單一群體搜索機(jī)制，它和CEA及CEAwithoutDE的對(duì)比將體現(xiàn)簇類搜索使群體搜索產(chǎn)生的變化.GA采用算術(shù)交叉和非均勻變異算子以及線性排序選擇算子.CEAwithoutDE的群體規(guī)模為100，GA的群體規(guī)模為200，這使得二者每代花費(fèi)的FE都要大于CEA，此外二者的其余相關(guān)參數(shù)與CEA保持一致.

首先來對(duì)比CEA，CEAwithoutDE，GA相關(guān)參數(shù)曲線的差異.整體上看，前二者在對(duì)3個(gè)系統(tǒng)的計(jì)算中雖然|C|曲線都有一定的波動(dòng)，但大體保持了一個(gè)穩(wěn)定的規(guī)模.這種簇類結(jié)構(gòu)使得群體在迭代過程中的群體多樣性γ維持一個(gè)較為緩慢的遞減趨勢(shì)，這明顯不同于GA中γ和其方差δ迅速降低的趨勢(shì),而且這一特征隨著問題維度的增大就變得更為突出.我們已知參量γ表達(dá)了群體搜索的平均狀態(tài)，而其方差δ則表達(dá)了搜索狀態(tài)的差異性.GA中參量γ和δ的變化說明它的群體經(jīng)過較短周期的“搜索+選擇”計(jì)算就會(huì)迅速聚攏在一個(gè)局部范圍內(nèi)，若全局最優(yōu)解不在這個(gè)區(qū)域內(nèi)，則系統(tǒng)就無法避免產(chǎn)生早熟收斂.顯然簇類結(jié)構(gòu)使參量γ和δ具有了一種穩(wěn)健收斂的過程，這使得群體在搜索的中前期維持了較有效的全局搜索幅度和豐富的差異性，故CEA對(duì)3個(gè)系統(tǒng)的成本值曲線在初期并不是像GA一般迅速下降而是維持一個(gè)相對(duì)平緩的下降過程，同時(shí)也不會(huì)像GA的成本曲線突然出現(xiàn)長時(shí)間的停滯，而是保持一個(gè)平滑且連續(xù)的遞減趨勢(shì).可見，簇類搜索能夠有效提高群體對(duì)復(fù)雜問題空間的搜索調(diào)節(jié)能力，在降低早熟的風(fēng)險(xiǎn)的同時(shí)維持穩(wěn)定的搜索效率.

另外，在6機(jī)問題的計(jì)算中CEA與CEAwithoutDE的搜索過程差異并不明顯，但隨著問題維度的增大，計(jì)算中類內(nèi)搜索及簇類搜索調(diào)節(jié)機(jī)制的作用就體現(xiàn)的較為突出.只進(jìn)行類間搜索時(shí)系統(tǒng)會(huì)使群體在規(guī)模較大的問題空間中個(gè)體分布更廣、更分散，故勘探到的可行解區(qū)域會(huì)更多，計(jì)算前期子類的規(guī)?？赡軙?huì)較大同時(shí)成本值下降會(huì)快些，如圖4(b)所示.但缺少了類內(nèi)搜索，子類將無法對(duì)所達(dá)區(qū)域進(jìn)行有效的開采，這將影響子類的競爭力，使其在類選擇的排序中排名靠后，降低了之后的搜索次數(shù)和后代數(shù)量.由于類選擇只使一半的子類個(gè)體生存到下一代，故子類個(gè)體規(guī)模整體是萎縮的，若無法產(chǎn)生足夠的后代個(gè)體，子類將逐漸消失，這是導(dǎo)致圖4(c)中CEAwithoutDE的簇類規(guī)模在計(jì)算后期劇烈下降的原因.由此也會(huì)進(jìn)一步影響群體的γ和δ的變化,我們可看到|C|曲線迅速下降時(shí)γ和δ的曲線也會(huì)產(chǎn)生明顯的下降,|C|與γ和δ之間相互干擾的結(jié)果會(huì)不斷影響系統(tǒng)的整體效率.

從CEA的各種曲線的整體走勢(shì)來看，利用簇類結(jié)構(gòu)來調(diào)節(jié)群體中全局性和局部性搜索的機(jī)制是可行且有效的，類間搜索和類內(nèi)搜索的協(xié)調(diào)過程可在顯著降低群體早熟風(fēng)險(xiǎn)的同時(shí)保證CEA對(duì)各種問題空間的優(yōu)化性能.

4結(jié)論

本文提出了基于簇類搜索驅(qū)動(dòng)的群體進(jìn)化優(yōu)化機(jī)制，形成了一種新型的進(jìn)化搜索算法——CEA，并將其應(yīng)用于對(duì)ELD問題的求解.在對(duì)13個(gè)標(biāo)準(zhǔn)約束數(shù)值優(yōu)化問題的實(shí)驗(yàn)中，CEA可以相對(duì)較小的搜索規(guī)模獲得較高質(zhì)量的計(jì)算結(jié)果，而在對(duì)3個(gè)IEEE測(cè)試系統(tǒng)的仿真實(shí)驗(yàn)中CEA所獲得的最優(yōu)結(jié)果都要好于現(xiàn)有文獻(xiàn)中記載的最佳解.實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)分析顯示CEA對(duì)不同規(guī)模的ELD問題都具有較強(qiáng)的搜索調(diào)節(jié)能力以及穩(wěn)定的計(jì)算性能.仿真實(shí)驗(yàn)說明，CEA可利用類組織有效融合多種搜索機(jī)制，并通過動(dòng)態(tài)調(diào)節(jié)類間搜索和類內(nèi)搜索間的協(xié)作關(guān)系使群體對(duì)各種復(fù)雜問題空間進(jìn)行穩(wěn)定且高效地搜索，這使得它可作為一種高效的約束數(shù)值優(yōu)化算法并應(yīng)用于求解各類ELD問題.

參考文獻(xiàn)

[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)(畢曉君, 劉國安, 肖婧. 基于新變異策略的動(dòng)態(tài)自適應(yīng)差分進(jìn)化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61203311,61105064)；陜西省教育廳科研計(jì)劃項(xiàng)目(2013JK1183,2014JK1667)

中圖法分類號(hào)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).