一種適用于機(jī)組組合優(yōu)化的改進(jìn)整數(shù)編碼粒子群算法

吳和海++熊高峰+袁晉蓉+秦躍杰

摘 要： 針對(duì)機(jī)組組合這一高維、非線性混合整數(shù)規(guī)劃問題，提出一種結(jié)合修補(bǔ)策略的整數(shù)編碼粒子群（ICPSO） 算法。用正負(fù)整數(shù)分別表示機(jī)組開停機(jī)的時(shí)間長(zhǎng)度，有效減少待優(yōu)化變量個(gè)數(shù)。基于機(jī)組組合問題的特點(diǎn)，采用修補(bǔ)策略處理不滿足約束條件的個(gè)體，使算法只在可行解區(qū)域內(nèi)搜索，有效提高收斂速度，通過切除冗余機(jī)組，提高解的質(zhì)量。仿真算例表明，相比整型編碼遺傳（r?ICGA）算法、改進(jìn)粒子群（IPSO）算法、社會(huì)演化（SEP）算法，提出的ICPSO算法能夠更有效地處理大規(guī)模機(jī)組組合優(yōu)化問題，執(zhí)行時(shí)間較短、求解精度更高。

關(guān)鍵詞： 機(jī)組組合； 粒子群算法； 整數(shù)編碼； 修補(bǔ)策略

中圖分類號(hào)： TN919?34； TP18 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）11?0167?05

An modified integer?coded particle swarm optimization algorithm

for unit commitment optimization

WU Hehai， XIONG Gaofeng， YUAN Jinrong， QIN Yuejie

（College of Electrical and Information Engineering， Hunan University， Changsha 410082， China）

Abstract： Aiming at the high dimension and nonlinear mixed integer programming problems of unit commitment， an integer?coded particle swarm optimization （ICPSO） algorithm combined with repairing scheme is proposed. The positive and negative integers are used to represent the time length of unit startup and shutdown to reduce the quantity of variables under optimization effectively. On the basis of the characteristic of unit commitment， the repairing scheme is adopted to handle the individuals which can′t conform to the constraint conditions， so as to make it only search in the feasible solution region， and improve the convergence rate. The redundancy unit is cut out to improve the quality of solution. The simulation example results show that， in comparison with r?ICGA， IPSO algorithm and SEP algorithm， the ICPSO algorithm can handle the combinatorial optimization of large?scale units effectively， has shorter execution time and higher solving accuracy.

Keywords： unit commitment； particle swarm optimization； integer coding； repairing scheme

0 引 言

機(jī)組組合優(yōu)化是電力系統(tǒng)經(jīng)濟(jì)調(diào)度中一個(gè)非常重要的問題，它的高維數(shù)、非凸、離散、非線性，使得理論上很難求取其最優(yōu)解。但由于它能夠帶來顯著的經(jīng)濟(jì)效益，許多國(guó)內(nèi)外學(xué)者一直在積極研究，提出各種方法來解決這個(gè)問題，例如，動(dòng)態(tài)規(guī)劃法、拉格朗日松弛法、優(yōu)先順序法等確定方法以及遺傳算法、蟻群算法、模擬退火等智能優(yōu)化算法[1?2]。但到目前為止，以上方法均存在一定的缺陷，如面臨“維數(shù)災(zāi)”、求解時(shí)間較長(zhǎng)、精度不夠高等，不適合實(shí)際機(jī)組組合的優(yōu)化。

粒子群優(yōu)化算法（PSO）是一種隨機(jī)全局優(yōu)化算法，該算法自提出以來，因?yàn)槠渚哂泻?jiǎn)單、收斂速度快且效果顯著等優(yōu)點(diǎn)，在各個(gè)領(lǐng)域得到廣泛的應(yīng)用[3?6]。目前粒子群算法在求解機(jī)組組合問題時(shí)[7?8]，普遍采用二進(jìn)制編碼方式，用0?1表示發(fā)電機(jī)組的開停機(jī)狀態(tài)；處理約束條件在適應(yīng)度函數(shù)中加入懲罰項(xiàng)。對(duì)于大規(guī)模機(jī)組系統(tǒng)，這種編碼方式會(huì)導(dǎo)致種群個(gè)體長(zhǎng)度過長(zhǎng)，影響算法搜索效率，浪費(fèi)大量求解時(shí)間[9]；懲罰項(xiàng)的引入會(huì)使得計(jì)算時(shí)間的極大增加，同時(shí)懲罰乘子的調(diào)整也存在困難[10]。

針對(duì)上述問題，本文提出一種適用于大規(guī)模機(jī)組組合問題的整數(shù)編碼粒子群算法。采用整數(shù)編碼方式來表達(dá)機(jī)組組合問題，有效減少待優(yōu)化變量個(gè)數(shù)；同時(shí)采用粒子修補(bǔ)策略處理不滿足約束條件的粒子，以提高搜索速度和解的質(zhì)量。算例仿真驗(yàn)證了文中所提出的算法能夠有效求解電力系統(tǒng)大規(guī)模機(jī)組組合問題。

1 機(jī)組組合的數(shù)學(xué)模型

1.1 目標(biāo)函數(shù)

電力系統(tǒng)機(jī)組組合問題是指在規(guī)定的時(shí)期內(nèi)，在滿足功率平衡等約束條件下，合理的安排機(jī)組的開停機(jī)順序與出力，使得系統(tǒng)的總發(fā)電成本最小。機(jī)組組合問題的目標(biāo)函數(shù)可表示為[11]：

（1）

式中：為系統(tǒng)總發(fā)電成本；代表機(jī)組臺(tái)數(shù)；為時(shí)段總個(gè)數(shù)；為機(jī)組在時(shí)段內(nèi)的輸出功率；為機(jī)組在時(shí)段內(nèi)的開停機(jī)狀態(tài)，當(dāng)時(shí)表示機(jī)組開機(jī)，時(shí)表示機(jī)組停機(jī)；表示機(jī)組在時(shí)段內(nèi)的耗量成本，其中，為機(jī)組的運(yùn)行成本參數(shù)；表示機(jī)組在時(shí)段內(nèi)的啟動(dòng)成本，它與機(jī)組啟動(dòng)之前的連續(xù)停機(jī)時(shí)間長(zhǎng)短有關(guān)。

1.2 約束條件

（1） 功率平衡約束：

（2）

（2） 最小開/停機(jī)時(shí)間約束：

（3）

（4）

（3） 機(jī)組出力上下限約束：

（5）

（4） 旋轉(zhuǎn)備用約束：

（6）

（5） 機(jī)組爬坡約束：

（7）

（8）

（6） 最大開關(guān)機(jī)次數(shù)約束：

（9）

式中：表示調(diào)度時(shí)段內(nèi)的系統(tǒng)負(fù)荷需求；表示機(jī)組開機(jī)后的最小開機(jī)時(shí)間；表示機(jī)組的最小停運(yùn)時(shí)間；表示機(jī)組的最小出力；表示機(jī)組的最大出力；為時(shí)段內(nèi)的旋轉(zhuǎn)備用值；分別為機(jī)組的功率最大上調(diào)量、下調(diào)量；表示機(jī)組在調(diào)度周期內(nèi)的開停機(jī)次數(shù)；為機(jī)組在調(diào)度周期內(nèi)允許的最大開停機(jī)次數(shù)。

2 基于整數(shù)編碼粒子群算法的機(jī)組組合問題

求解

2.1 整數(shù)編碼

用正負(fù)整數(shù)分別表示機(jī)組開停機(jī)時(shí)間長(zhǎng)度，機(jī)組開停機(jī)狀態(tài)設(shè)計(jì)為矩陣： （10）

式中：為粒子種群中的第個(gè)個(gè)體；表示機(jī)組的狀態(tài)階段所持續(xù)的時(shí)間，正整數(shù)值代表機(jī)組連續(xù)開機(jī)的小時(shí)數(shù)，負(fù)整數(shù)值代表機(jī)組持續(xù)停機(jī)的小時(shí)數(shù)；表示機(jī)組開停機(jī)階段數(shù)的上限（每臺(tái)機(jī)組一般每天開停機(jī)次數(shù)不超過5次），一些重負(fù)荷機(jī)組的開停機(jī)階段數(shù)不足時(shí)用數(shù)字0填充，從而保持粒子矩陣列數(shù)恒定。每行表示某機(jī)組在調(diào)度周期內(nèi)的開停機(jī)安排，滿足。第臺(tái)機(jī)組所有時(shí)段的啟停安排由一組正負(fù)相間的整數(shù)串來表示，構(gòu)成矩陣的行向量。所有機(jī)組的整數(shù)串（行向量）組成整個(gè)調(diào)度周期全部機(jī)組的啟停安排，即機(jī)組組合問題的解。

圖1詳細(xì)演示了如何通過一個(gè)10×5的整數(shù)編碼矩陣表達(dá)10機(jī)組在24 h內(nèi)的一個(gè)調(diào)度安排。若使用二進(jìn)制編碼，同樣的調(diào)度所需的矩陣規(guī)模增大至10×24，計(jì)算量將大大增加。例如第六行向量 [-8，6，-5，4，-1]表示此機(jī)組在1～8時(shí)段內(nèi)停機(jī)，9～14時(shí)段內(nèi)開機(jī)，15～19時(shí)段內(nèi)停機(jī)，20～23時(shí)段內(nèi)開機(jī)，24時(shí)段內(nèi)停機(jī)。該編碼方式從特性上就限制了機(jī)組在一個(gè)調(diào)度周期內(nèi)的啟停狀態(tài)次數(shù)最多不超過滿足機(jī)組最大開停機(jī)次數(shù)的約束。

2.2 粒子種群的初始化

（1） 時(shí)，機(jī)組在第一個(gè)狀態(tài)階段持續(xù)的時(shí)間：

（11）

式中：表示機(jī)組在上一個(gè)調(diào)度周期最后一個(gè)狀態(tài)階段持續(xù)的時(shí)間，這樣生成的能夠保證機(jī)組延續(xù)前一個(gè)調(diào)度周期的狀態(tài)且滿足最小開停機(jī)時(shí)間約束。

（2） 時(shí)，考慮到機(jī)組需滿足最小開停機(jī)時(shí)間約束，可按式（12）初始化：

（12）

式中：表示第個(gè)狀態(tài)階段后剩余的調(diào)度時(shí)段數(shù)。

（13）

（3） 即最后一個(gè)狀態(tài)階段，它所持續(xù)的時(shí)間初始化如下：

（14）

由于隨機(jī)數(shù)的原因，若前個(gè)狀態(tài)階段的持續(xù)時(shí)間之和等于調(diào)度周期時(shí)段數(shù)則余下的狀態(tài)階段所持續(xù)的時(shí)間用0來補(bǔ)充，保證所有的粒子矩陣有相同的列數(shù)。根據(jù)式（11）～式（14）初始化得到的粒子種群，滿足機(jī)組最小開停機(jī)時(shí)間約束。

2.3 粒子進(jìn)化

粒子在尋優(yōu)過程中，依據(jù)迄今為止找到的最優(yōu)解和整個(gè)粒子群搜索到的最優(yōu)解來調(diào)整粒子的進(jìn)化速度和方向。

粒子的速度按照下式進(jìn)行變化：

（15）

粒子位置的更新公式如下：

（16）

式中：為種群粒子個(gè)數(shù)；為第次迭代后粒子的速度；為第次迭代后粒子的位置；為粒子個(gè)體的歷史最優(yōu)位置；為種群最好位置；rand1，rand2為[0，1]之間的隨機(jī)數(shù)；是加速度常數(shù)；為慣性權(quán)重；Int為取整符號(hào)。

2.4 修補(bǔ)粒子

在粒子群迭代優(yōu)化過程中不可避免地會(huì)產(chǎn)生一些無效的粒子，在這些無效粒子中會(huì)有各個(gè)狀態(tài)階段的持續(xù)時(shí)間之和不等于調(diào)度周期時(shí)段數(shù)整數(shù)串不是正負(fù)相間的情況，從而導(dǎo)致該粒子無效。需要對(duì)粒子個(gè)體進(jìn)行修補(bǔ)，按行向量的先后順序進(jìn)行。以個(gè)體中行為例，具體措施如下：

（1） 若保持前個(gè)狀態(tài)階段持續(xù)時(shí)間不變，其中滿足且令段的值變?yōu)?，正負(fù)保持不變；

（2） 若，考慮到此種情況修補(bǔ)繁瑣、耗時(shí)較多，則重新初始化該粒子；

（3） 若行不是正負(fù)相間的整數(shù)串，則保持的大小不變，依次調(diào)整它們的正負(fù)號(hào)以滿足條件；

（4） 若有的情況，則交換兩者的位置，否則不滿足編碼方式的特性。

2.5 約束條件處理

2.5.1 旋轉(zhuǎn)備用約束處理

每個(gè)時(shí)段都應(yīng)該對(duì)旋轉(zhuǎn)備用約束進(jìn)行檢驗(yàn)，若違反約束，則應(yīng)調(diào)整機(jī)組開停機(jī)狀態(tài)。本文采用機(jī)組最小耗量與機(jī)組的最大出力之比作為指標(biāo)，對(duì)機(jī)組進(jìn)行優(yōu)先排序[12]。當(dāng)時(shí)段所有開機(jī)機(jī)組的最大輸出功率之和小于系統(tǒng)負(fù)荷量和旋轉(zhuǎn)備用時(shí)，對(duì)按照指標(biāo)排列好的機(jī)組逐一檢查其開停機(jī)狀態(tài)，將狀態(tài)為0的機(jī)組開啟，直到滿足旋轉(zhuǎn)備用約束，轉(zhuǎn)至?xí)r段繼續(xù)檢驗(yàn)。

2.5.2 最小開停機(jī)時(shí)間約束處理

違背最小開機(jī)時(shí)間約束通常出現(xiàn)在高峰負(fù)荷時(shí)段，因?yàn)榉逯禃r(shí)間往往低于最小開機(jī)時(shí)間。類似地，因低負(fù)荷持續(xù)時(shí)間一般低于最短關(guān)機(jī)時(shí)間，最小關(guān)機(jī)約束的違背常出現(xiàn)于低負(fù)荷時(shí)段。在粒子群進(jìn)化過程中，采用最小開停機(jī)時(shí)間修補(bǔ)策略對(duì)粒子編碼矩陣進(jìn)行修復(fù)[13]。

如圖2所示，若檢查是否滿足最小開機(jī)時(shí)間約束，若不滿足，則將變?yōu)?，機(jī)組繼續(xù)開機(jī)；如圖3所示，若檢查～時(shí)刻機(jī)組是否都能滿足最小停機(jī)時(shí)間約束，若不滿足，則機(jī)組繼續(xù)開機(jī)，變?yōu)?。

2.6 切除冗余機(jī)組

在求解過程中，由于缺少對(duì)機(jī)組運(yùn)行實(shí)際特點(diǎn)的考慮，易出現(xiàn)小容量機(jī)組運(yùn)行過多、機(jī)組備用容量過剩的情況，使得發(fā)電成本增加。因此有必要關(guān)閉多余備用機(jī)組，即切除冗余機(jī)組。

在調(diào)度周期內(nèi)，依次檢查每個(gè)時(shí)段內(nèi)所有開機(jī)機(jī)組的最大出力之和是否超過系統(tǒng)負(fù)荷和旋轉(zhuǎn)備用。若超過，則按優(yōu)先表逆序關(guān)閉已開機(jī)組。再重新檢測(cè)，直至該時(shí)段機(jī)組輸出總功率不過量。

3 算例分析

本文采用經(jīng)典算例對(duì)算法的性能進(jìn)行檢驗(yàn)，為了便于對(duì)比分析，不考慮爬坡約束，可以直接采用等微增率準(zhǔn)則進(jìn)行負(fù)荷經(jīng)濟(jì)分配。計(jì)算中粒子種群大小取20；最大迭代進(jìn)化次數(shù)取100；均取2；權(quán)重系數(shù)從0.9～0.4線性遞減，粒子最大速度為10。計(jì)算周期為一天，全天分為24個(gè)時(shí)段。機(jī)組開停機(jī)階段數(shù)的上限考慮到粒子群算法的隨機(jī)性，應(yīng)用本文ICPSO算法進(jìn)行20次獨(dú)立迭代計(jì)算，取其中最好的解作為最終優(yōu)化結(jié)果。

采用文獻(xiàn)[8?9]中的10臺(tái)機(jī)組參數(shù)和24 h的負(fù)荷數(shù)據(jù)以及旋轉(zhuǎn)備用，并根據(jù)上述文獻(xiàn)中的復(fù)制方法將系統(tǒng)規(guī)模擴(kuò)大至20臺(tái)、40臺(tái)、60臺(tái)、80臺(tái)和100臺(tái)，系統(tǒng)負(fù)荷和備用同時(shí)按比例增加。

表1給出ICPSO算法求得的10機(jī)組系統(tǒng)最優(yōu)運(yùn)行成本，系統(tǒng)總的運(yùn)行成本為$563 937.7，其中啟動(dòng)總成本費(fèi)用為$4 090，機(jī)組發(fā)電總成本為$559 847.7，最優(yōu)調(diào)度表見表2。

表3為本文的ICPSO算法與其他優(yōu)化算法[8?9，11]對(duì)10～100臺(tái)機(jī)組系統(tǒng)求解結(jié)果的比較。可以看出，對(duì)于10機(jī)組系統(tǒng)，本文ICPSO算法和r?ICGA都能獲得相同的總費(fèi)用，優(yōu)于SEP，IPSO算法；隨著機(jī)組臺(tái)數(shù)的增加，ICPSO的求解結(jié)果均優(yōu)于其他三種方法，驗(yàn)證了本文算法求解大規(guī)模機(jī)組組合問題的有效性和高精度性。

圖4給出了本文算法在不同機(jī)組規(guī)模下的執(zhí)行時(shí)間曲線，隨著機(jī)組臺(tái)數(shù)的增加，執(zhí)行時(shí)間近似線性增長(zhǎng)，10機(jī)組時(shí)耗時(shí)約3.2 s，100機(jī)組時(shí)也只需要28.2 s左右。這是由于本文采用修復(fù)策略對(duì)不可行粒子進(jìn)行修復(fù)，使算法只在可行解區(qū)域內(nèi)搜索最優(yōu)解，有效提高收斂速度；同時(shí)相比二進(jìn)制編碼，本文的整數(shù)編碼方式能有效提高粒子群算法的搜索效率。因此本文提出的整數(shù)編碼粒子群算法更適用于求解大規(guī)模機(jī)組組合問題。

圖4 不同機(jī)組規(guī)模的執(zhí)行時(shí)間曲線

4 結(jié) 語(yǔ)

本文采用整數(shù)編碼粒子群算法來求解機(jī)組組合問題。通過整數(shù)編碼方式，用正負(fù)整數(shù)分別表示機(jī)組開停機(jī)時(shí)間長(zhǎng)度，相比于二進(jìn)制編碼它能有效減少待優(yōu)化變量個(gè)數(shù)。求解過程中針對(duì)機(jī)組組合問題的特點(diǎn)，采用修補(bǔ)策略處理不滿足約束條件的粒子，使算法只在可行解區(qū)域內(nèi)搜索，通過切除冗余機(jī)組提高解的精度。仿真算例表明，相比r?ICGA，IPSO，SEP，本文提出的ICPSO算法求解大規(guī)模機(jī)組組合優(yōu)化問題具有更高的精度，求解時(shí)間大幅度減少。

參考文獻(xiàn)

[1] KAZARLIS S A， BAKIRTZIS A G， PETRIDIS V. A genetic algorithm solution to the unit commitment problem [J]. IEEE transactions on power systems， 1996， 11（1）： 83?92.

[2] 黎靜華，蘭飛.機(jī)組組合問題的模型及算法綜述[J].現(xiàn)代電力，2011，28（6）：1?10.

[3] 李丹，高立群，王珂，等.電力系統(tǒng)機(jī)組組合問題的動(dòng)態(tài)雙種群粒子群算法[J].計(jì)算機(jī)應(yīng)用，2008，28（1）：104?107.

[4] 張濤，史蘇怡，徐雪琴.基于二進(jìn)制量子粒子群算法的含分布式電源配電網(wǎng)重構(gòu)[J].電力系統(tǒng)保護(hù)與控制，2016，44（4）：22?28.

[5] 方源，章桐，陳霏霏，等.電動(dòng)車動(dòng)力總成噪聲品質(zhì)粒子群?向量機(jī)預(yù)測(cè)模型[J].西安交通大學(xué)學(xué)報(bào)，2016，50（1）：41?46.

[6] 王春枝，張會(huì)麗，葉志偉，等.一種基于混沌粒子群算法和支持向量機(jī)的 P2P流量識(shí)別方法[J].計(jì)算機(jī)應(yīng)用與軟件，2015（8）：288?291.

[7] 耿曉軍，王剛.粒子群算法應(yīng)用于機(jī)組組合問題的優(yōu)化[J].現(xiàn)代電子技術(shù)，2007，30（16）：111?113.

[8] 趙波，曹一家.電力系統(tǒng)機(jī)組組合問題的改進(jìn)粒子群優(yōu)化算法[J].電網(wǎng)技術(shù)，2004，28（21）：6?10.

[9] 張偉，趙進(jìn)慧，王寧.帶修復(fù)操作整型編碼遺傳算法求解大規(guī)模機(jī)組組合問題[J].化工學(xué)報(bào)，2012，63（9）：2972?2979.

[10] AMJADY N， SHIRZADI A. Unit commitment using a new integer coded genetic algorithm [J]. European transactions on electrical power， 2009， 19（8）： 1161?1176.

[11] 王喆，余貽鑫，張弘鵬.社會(huì)演化算法在機(jī)組組合中的應(yīng)用[J].中國(guó)電機(jī)工程學(xué)報(bào)，2004，24（4）：12?17.

[12] 黎靜華，韋化.求解機(jī)組組合問題的領(lǐng)域搜索法[J].中國(guó)電機(jī)工程學(xué)報(bào)，2008，28（13）：33?40.

[13] 蔡振華.考慮電價(jià)的機(jī)組組合問題研究[D].長(zhǎng)沙：湖南大學(xué)，2013.