基于聚類的差分進化算法的兩階段最優(yōu)潮流方法

田 瑋，江曉東

（天津大學(xué)電氣自動化與信息工程學(xué)院，天津 300072）

在科學(xué)、工程和經(jīng)濟學(xué)等研究領(lǐng)域中，最優(yōu)化問題比比皆是。最優(yōu)潮流則是電力系統(tǒng)中典型的優(yōu)化問題，半個世紀(jì)以來得到眾多學(xué)者的研究[1-3]。針對由實際優(yōu)化問題的復(fù)雜性導(dǎo)致傳統(tǒng)優(yōu)化算法難以求解到全局最優(yōu)解的問題，研究人員通過對數(shù)學(xué)優(yōu)化問題和生物進化之間潛在關(guān)系的觀察，將自然的進化過程作為模型，提出了智能算法。近年來，智能算法的研究主要由進化算法和群體智能算法等組成[4-5]。由Storn和Price提出的差分進化DE（differen?tial evolution）算法是一種極具競爭力的進化算法[6]。相比其他進化算法，DE算法具有容易實現(xiàn)、進化效率高和魯棒性強等優(yōu)點，在被初級定義之時便廣泛應(yīng)用于科學(xué)研究與工程實踐的領(lǐng)域[7-10]。同時，空間復(fù)雜度較低的DE算法具有一定的可擴展性以及處理大規(guī)模優(yōu)化問題的潛力。目前，DE算法已經(jīng)被拓展到多目標(biāo)和有約束優(yōu)化問題的研究領(lǐng)域[11-14]。然而，隨著DE算法的實際應(yīng)用，研究人員發(fā)現(xiàn)DE算法主要存在以下2個缺陷：第一，搜索停滯問題，即在種群進化后期，由個體間差異過小導(dǎo)致種群停止向全局最優(yōu)解的方向進化的現(xiàn)象；第二，過早收斂問題，即種群個體多樣性的缺失導(dǎo)致陷入局部最優(yōu)解的現(xiàn)象。為了提高DE算法的性能以適應(yīng)不同類型的優(yōu)化問題，研究人員對DE算法的改進研究逐漸增多[15]，主要有：為DE算法結(jié)構(gòu)增加組件，即以DE算法為進化框架，其他算法組件作為優(yōu)化輔助[16]；修改DE算法本身，即算法結(jié)構(gòu)的修改、搜索策略的改變、參數(shù)的選擇等[17，18]以提高DE算法的性能。

為平衡求解最優(yōu)化問題的速度和質(zhì)量，本文在DE算法的基礎(chǔ)之上，提出了一種基于聚類的DE算法的兩階段優(yōu)化方法，簡稱兩階段優(yōu)化方法，其中包含全局搜索階段和局部優(yōu)化階段。兩階段優(yōu)化方法的特點在于能實現(xiàn)確保求解最優(yōu)化問題質(zhì)量的同時提升求解速度，而這得益于第Ⅰ階段的全局搜索中DE算法與聚類相結(jié)合，實現(xiàn)快速確定可能存在局部最優(yōu)解的區(qū)域，以及第Ⅱ階段的局部勘探中局部優(yōu)化方法的采用實現(xiàn)高效收斂得到最優(yōu)解。

1 基于聚類的差分進化優(yōu)化算法

DE算法是一種并行直接搜索方法，其進化過程可概括為變異、交叉和選擇3個部分。DE算法是通過個體之間的差分量實現(xiàn)個體的變異以及種群的進化的，具體表示為

式中：i為索引；F為常數(shù)因子，F(xiàn)∈[0,2]，用于控制個體變異部分(xr2,G-xr3,G)；r1、r2、r3為隨機選擇且不同于索引i的整數(shù)，r1,r2,r3∈{1,2,…,NP}。因此個體的數(shù)目是必須大于或等于4以滿足此條件。

DE算法在種群進化初期，所有個體之間的差異較大，交叉步驟有助于擾動參數(shù)向量的多樣性的增加，而在種群進化后期，個體間的差分量逐漸減小，需要花費較多計算成本進行局部勘探。同時，控制參數(shù)以及進化策略的選擇對DE算法后期的全局搜索能力影響大[19]。為提高DE算法搜索最優(yōu)解的效率，本文提出了一種基于聚類的差分進化算法。

隨著種群的進化，個體間的差分量逐漸減小，種群在搜索空間中會出現(xiàn)“群聚”的情況，即相似的個體聚集在可能包含局部最優(yōu)解或全局最優(yōu)解的區(qū)域。在文獻[20]中提出對群聚的種群進行分組，并將種群分組數(shù)目不變和每個分組中的個體成員不變的狀態(tài)稱為“共識”。經(jīng)過多次測試發(fā)現(xiàn)，在DE算法中，當(dāng)種群達到共識狀態(tài)時，全局搜索能力也開始退化。

因此，種群的共識狀態(tài)可作為差分進化算法的停止條件，雖未求解到局部最優(yōu)解，但可快速確定可能包含局部最優(yōu)解或全局最優(yōu)解的子區(qū)域。為檢測種群的共識狀態(tài)，本文采用一種無監(jiān)督分類方法，即迭代自組織數(shù)據(jù)分析技術(shù)算法ISODATA（it?erative self-organizing data analysis technique algo?rithm）[21]，在種群進化過程中以固定的代數(shù)間隔對整個種群進行分組。ISODATA方法可在迭代過程中自動調(diào)整預(yù)先設(shè)定的聚類數(shù)量，以獲得合理的聚類結(jié)果。基于聚類的DE算法，令隨機種群進化達到共識狀態(tài)時停止迭代，其具體的停止條件為：種群進化50代內(nèi)分組的數(shù)目不變；限制目標(biāo)函數(shù)（適應(yīng)度）評估的最大次數(shù)為3.00×105。

2 局部優(yōu)化階段

局部優(yōu)化階段旨在第Ⅰ階段鎖定一個或多個存在局部最優(yōu)解的子區(qū)域的基礎(chǔ)上，用局部優(yōu)化算法加速找到各子區(qū)域?qū)?yīng)的局部最優(yōu)解。在第Ⅰ階段中，基于聚類的差分進化算法為非線性優(yōu)化問題的解決提供了分組式的子種群；第Ⅱ階段則從每個子群組中取最優(yōu)的個體和中心點作為初點，利用局部優(yōu)化方法收斂速度快的特性為每個子區(qū)域?qū)ふ蚁鄳?yīng)的局部最優(yōu)解，以提高解決優(yōu)化問題的效率。

本文在該階段選用的局部優(yōu)化方法是擬牛頓法。擬牛頓法是一種基于逼近牛頓法的方法，其特點在于無需海森矩陣信息而是利用目標(biāo)函數(shù)及其一階導(dǎo)數(shù)構(gòu)造出近似的目標(biāo)函數(shù)曲率。因此，擬牛頓法具有收斂速度快和數(shù)值穩(wěn)定的優(yōu)點，也是所有利用一階導(dǎo)數(shù)求解無約束優(yōu)化方法中最有效的方法[22]。

全局搜索階段和局部優(yōu)化階段共同組成兩階段優(yōu)化方法，其具體流程如圖1所示。本文將該兩階段優(yōu)化的思想應(yīng)用于電力系統(tǒng)的最優(yōu)潮流計算。

圖1 基于共識差分進化的兩階段優(yōu)化算法Fig.1 Two-stage optimization method based on DE

3 兩階段最優(yōu)潮流方法

電力系統(tǒng)最優(yōu)潮流是指在給定的系統(tǒng)結(jié)構(gòu)參數(shù)和負荷情況下，優(yōu)選滿足系統(tǒng)運行和安全約束的系統(tǒng)控制變量，使系統(tǒng)的某一目標(biāo)函數(shù)指標(biāo)達到最優(yōu)。從計算上，最優(yōu)潮流問題是一個非線性規(guī)劃問題，即一系列等式和不等式約束條件下的最小化問題，其數(shù)學(xué)模型可表示為

式中：u為控制變量，包括PV節(jié)點的有功功率輸出和電壓幅值、平衡節(jié)點的電壓幅值、變壓器分接頭和可調(diào)并聯(lián)電容器等；x為狀態(tài)變量，包括全部節(jié)點的電壓相角、PQ節(jié)點的電壓幅值和發(fā)電機的無功功率輸出等。其中，式（2）為系統(tǒng)的目標(biāo)函數(shù)，一般為發(fā)電機燃料總費用、網(wǎng)絡(luò)損耗或兩者的組合，本文選用發(fā)電機燃料總費用作為目標(biāo)函數(shù)；式（3）表示潮流方程等式約束；式（4）表示不等式約束，包括發(fā)電機有功和無功出力上下限、節(jié)點電壓幅值的上下限和線路潮流的熱極限約束。

兩階段最優(yōu)潮流方法的詳細流程介紹如下。

第Ⅰ階段（全局搜索階段）：基于聚類的DE算法中的種群個體變量是由控制變量和狀態(tài)變量組成的，其個體的優(yōu)劣評估指標(biāo)是由最優(yōu)潮流問題的轉(zhuǎn)化得到，具體表示為

式中：r為不等式約束的懲罰參數(shù)，本文中r設(shè)置為100；m為不等式約束的數(shù)目。目標(biāo)函數(shù)式（5）中不包含等式約束部分式（3），是由于在進化過程中，利用潮流計算獲得當(dāng)前控制變量下的狀態(tài)變量x，可保證直接滿足等式約束式（3）。

執(zhí)行基于聚類的DE算法的具體步驟如下。

步驟1在已知的范圍內(nèi)，初始化隨機種群。

步驟2計算種群中個體對應(yīng)的目標(biāo)函數(shù)式（5）。

步驟3利用式（1）對種群中的個體進行變異，其中參數(shù)F為0.7，并按照概率0.3進行交叉步驟；然后計算種群中個體對應(yīng)的目標(biāo)函數(shù)式（5），選擇目標(biāo)函數(shù)值小的個體進入下一步。

步驟4如果種群進化代數(shù)為50的倍數(shù)，執(zhí)行步驟5；否則，執(zhí)行步驟3。

步驟5ISODATA算法對種群進行聚類，如果執(zhí)行聚類次數(shù)大于等于2，則執(zhí)行步驟6，否則，執(zhí)行步驟3。

步驟6檢驗種群的分組情況未發(fā)生變化，即達到共識狀態(tài)，或計算目標(biāo)函數(shù)次數(shù)達到規(guī)定次數(shù)，則執(zhí)行第二階段的優(yōu)化；否則，執(zhí)行步驟3。

第Ⅱ階段（局部開發(fā)階段）：在已確定的區(qū)域基礎(chǔ)上，局部高效開發(fā)對應(yīng)的最優(yōu)解。在擬牛頓法中，需采用懲罰函數(shù)將最優(yōu)潮流問題轉(zhuǎn)化為無約束優(yōu)化的形式，即

式中：r1為等式約束的懲罰參數(shù)；r2為不等式約束的懲罰參數(shù)；n為等式約束的數(shù)目。本文中r1和r2分別設(shè)置為1 000和10 000。

執(zhí)行局部優(yōu)化算法的具體步驟如下。

步驟1選取第Ⅰ階段得到的每個分組中的中心位置和最優(yōu)潮流目標(biāo)函數(shù)式（2）最小的個體作為局部尋優(yōu)的初值。

步驟2對每個初值采用BFGS算法，沿著由一階導(dǎo)數(shù)信息構(gòu)造的方向搜索局部最優(yōu)解[23]。

步驟3從每個初值出發(fā)的搜索直至檢驗滿足收斂判據(jù)停止，將搜索到的最優(yōu)解組成最優(yōu)潮流解集合。

步驟4輸出最優(yōu)潮流解集合中最優(yōu)潮流目標(biāo)函數(shù)（發(fā)電總成本）最小的潮流解。

4 算例分析

在一組基準(zhǔn)非線性函數(shù)問題上對兩階段優(yōu)化方法進行測試，驗證其具備的有效性，并分析該方法在IEEE 118節(jié)點系統(tǒng)的最優(yōu)潮流計算的結(jié)果，說明該方法的實用潛力。

4.1 基準(zhǔn)函數(shù)測試

基準(zhǔn)測試函數(shù)如表1所示，用于測試兩階段優(yōu)化方法的性能，并與傳統(tǒng)差分進化算法相比較，表中包含常規(guī)問題(f1)、旋轉(zhuǎn)問題(f2-f3)、移位問題(f4-f6)和復(fù)合問題(f7-f9)[20]。在該算例中，變量維度為50以及隨機選擇的種群規(guī)模為30。DE算法的參數(shù)設(shè)置為：縮放因子F=0.7，交叉概率CR=0.3，差分策略DE/best/1。兩階段方法的第Ⅰ階段中DE算法與上述參數(shù)設(shè)置相同，聚類步驟的間隔代數(shù)為50。

表1 測試函數(shù)Tab.1 Test functions

圖2為測試函數(shù)f1（Rosenbrock）的等高線圖，隨機種群在第Ⅰ階段中經(jīng)過8 930次函數(shù)評估后，達到了共識的狀態(tài)，即該種群被分為4個組且在進化間隔代數(shù)內(nèi)保持不變；第Ⅱ階段取每個分組中最好的（目標(biāo)函數(shù)值最小）和中心位置的個體作為初點，利用擬牛頓法計算得到各子區(qū)域?qū)?yīng)的局部最優(yōu)解。圖2中，“*”代表各組的中心點和“×”代表各組的最優(yōu)個體，經(jīng)局部優(yōu)化算法計算后均收斂到全局最優(yōu)解（1，1），即五角星處。

圖2 測試函數(shù)Rosenbrock上的兩階段優(yōu)化算法過程Fig.2 Process of two-stage optimization method on the test function Rosenbrock

為評估并比較兩階段優(yōu)化方法和傳統(tǒng)DE算法的求解質(zhì)量和計算效率，表2統(tǒng)計了優(yōu)化方法找到的最優(yōu)解與已知的全局最優(yōu)解的差值。

表2 兩階段優(yōu)化方法與傳統(tǒng)差分進化算法的優(yōu)化結(jié)果比較Tab.2 Comparison of optimization result between twostage optimization method and traditional DE method

從表2可知，兩階段優(yōu)化方法成功地找到了函數(shù)f6的全局最優(yōu)解和函數(shù)f1、f3、f4和f7的接近全局最優(yōu)解的解。而對于函數(shù)f2、f5、f9，兩階段優(yōu)化方法雖然未找到對應(yīng)的全局最優(yōu)解，但大幅改善了找到的解的質(zhì)量。上述結(jié)果驗證了兩階段優(yōu)化算法在尋找測試函數(shù)的全局最優(yōu)解方面的有效性。

表3是優(yōu)化過程中計算目標(biāo)函數(shù)的統(tǒng)計總次數(shù)，其中Inf表示在規(guī)定的最大函數(shù)評估次數(shù)（3×105）內(nèi)優(yōu)化方法未找到全局最優(yōu)解的情況。

表3 兩階段法與傳統(tǒng)差分進化算法的計算效率比較Tab.3 Comparison of computational efficiency between two-stage method and traditional DE method

由表3中的結(jié)果對比可知，兩階段優(yōu)化方法尋找（近似）全局最優(yōu)解的效率高。尤其在函數(shù)f1的求解中，兩階段優(yōu)化方法函數(shù)計算僅花費8 934次便獲取了高質(zhì)量的最優(yōu)解，約占設(shè)定最大函數(shù)評估次數(shù)的2.98%。上述實驗結(jié)果表明，兩階段優(yōu)化方法具有求解質(zhì)量高和計算量小的優(yōu)點。

4.2 最優(yōu)潮流應(yīng)用測試

本算例在MATPOWER的IEEE 118節(jié)點系統(tǒng)的最優(yōu)潮流問題上對提出的兩階段優(yōu)化潮流方法進行測試。具體的求解過程闡述如下。

第Ⅰ階段中，基于聚類的差分進化算法中，種群規(guī)模設(shè)置為100，DE算法中參數(shù)設(shè)置與上述算例相同。狀態(tài)變量中電壓幅值的范圍為[0.94，1.06]p.u.。隨機初始化的總種群中最優(yōu)個體對應(yīng)的最優(yōu)潮流目標(biāo)函數(shù)（發(fā)電總成本）為135 856.50$/h（已知全局最優(yōu)解的目標(biāo)函數(shù)為129 660.69$/h）。經(jīng)3 400次評估目標(biāo)函數(shù)，種群達到共識狀態(tài)，此時聚類得到4個分組。表4中列出每個分組的中心位置和最優(yōu)個體對應(yīng)的最優(yōu)潮流目標(biāo)函數(shù)值。由表4中可知，種群達到共識狀態(tài)時，由聚類得到的4個分組的中心和最優(yōu)個體的最優(yōu)潮流目標(biāo)函數(shù)相近。雖然基于聚類DE算法全局探索得到的個體最優(yōu)潮流目標(biāo)函數(shù)均大于隨機初始種群中最優(yōu)個體的，但是初始的隨機種群中的最優(yōu)個體不滿足符合系統(tǒng)運行約束。

表4 基于聚類的差分進化算法計算結(jié)果Tab.4 Calculation result obtained by the group-based DE method

第Ⅱ階段對各組種群的優(yōu)質(zhì)個體進行一步優(yōu)化，即將各組挑選的優(yōu)質(zhì)個體作為初值，擬牛頓法從每個初值出發(fā)沿著梯度信息方向搜索得到對應(yīng)的最優(yōu)潮流解，如表5所示。

表5 局部優(yōu)化算法計算結(jié)果Tab.5 Calculation result obtained by the local optimization method

由表5的結(jié)果可知，經(jīng)擬牛頓法優(yōu)化4個組均得到了全局最優(yōu)解，這是由于第Ⅰ階段提供的初值接近全局最優(yōu)解，使得第Ⅱ階段更容易地找到全局最優(yōu)解。該測試結(jié)果驗證了兩階段優(yōu)化方法在電力系統(tǒng)最優(yōu)潮流問題中的實用性。

5 結(jié)語

本文提出的兩階段優(yōu)化方法結(jié)合了基于聚類的差分進化算法和局部優(yōu)化算法，達到高效求解最優(yōu)化問題的高質(zhì)量局部最優(yōu)解甚至全局最優(yōu)解的目的。在兩階段優(yōu)化方法中，基于聚類的差分進化算法提高了傳統(tǒng)差分進化算法的搜索效率，實現(xiàn)快速確定包含局部最優(yōu)解甚至全局最優(yōu)解的區(qū)域；局部優(yōu)化算法則用收斂速度快的優(yōu)點彌補啟發(fā)式算法進化后期效率低的缺陷。本文在一組基本測試函數(shù)以及不同規(guī)模電力系統(tǒng)的最優(yōu)潮流問題上對提出的兩階段優(yōu)化方法進行了測試，其結(jié)果表明，所提兩階段優(yōu)化方法具有高效性以及應(yīng)用于電力系統(tǒng)復(fù)雜非線性問題求解的潛力。隨著電力系統(tǒng)的發(fā)展，最優(yōu)潮流問題中離散變量的介入將使得智能混合優(yōu)化算法具有一定應(yīng)用的優(yōu)勢以及被進一步研究的意義。