帕累托部落進化算法及其在電力系統多目標優化發電調度中的應用

許悅，瞿凱平，張孝順，余濤

（華南理工大學電力學院，廣東 廣州，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.