遺傳-模擬算法的機組檢修計劃

以遺傳—模擬退火混合算法為基礎(chǔ)的火力發(fā)電機組檢修計劃安排的研究2008年內(nèi)容提要火力發(fā)電機組計劃檢修簡介火力發(fā)電機組計劃檢修數(shù)學模型遺傳/模擬退火算法在發(fā)電機組計劃檢修中的運用算例結(jié)論與展望火力發(fā)電機組計劃檢修簡介

－－發(fā)電機組停電事故停電事故

發(fā)電機組是電力系統(tǒng)的重要組成部分。當發(fā)電機組特別是大容量機組意外事故停運時，電力系統(tǒng)的發(fā)電容量減少，備用容量隨之減少，直接影響到電力系統(tǒng)運行的可靠性。如果不能保持發(fā)電容量與負荷之間的平衡，將導致電網(wǎng)頻率的變化，甚至導致電力系統(tǒng)崩潰，造成大面積停電。同時，意外事故如短路，往往會嚴重損壞發(fā)電設備。這些都會造成重大的經(jīng)濟損失和社會影響。計劃檢修 計劃檢修是減少發(fā)電機組停運事故，同時保證電力系統(tǒng)運行安全性和可靠性的一種有效方法。由于機組停機檢修直接影響電網(wǎng)的發(fā)電出力和負荷儲備，所以它對電網(wǎng)運行的可靠性和經(jīng)濟性都有很大的影響。此外，許多短期或長期的運行、調(diào)度問題，例如機組出力的調(diào)配與組合、抽水蓄能和常規(guī)水火電優(yōu)化、燃料計劃、可靠性計算、以及發(fā)電費用預算等都要以檢修計劃數(shù)據(jù)為基礎(chǔ)，所以制訂一個最優(yōu)的檢修計劃有十分重要意義。隨著電網(wǎng)裝機容量和機組臺數(shù)的增加以及社會對電力生產(chǎn)可靠性與經(jīng)濟性要求的提高，檢修計劃問題的重要性亦日益突出?；鹆Πl(fā)電機組計劃檢修簡介

－－發(fā)電機組計劃檢修火力發(fā)電機組計劃檢修簡介

－－發(fā)電機檢修的基本要求一個合理檢修計劃應滿足下列的基本要求：1、在機組檢修期間，保證電力系統(tǒng)運行的安 全性和供電的可靠性。2、保證電力系統(tǒng)運行的經(jīng)濟性。3、檢修次數(shù)的約束。4、檢修時間間隔約束。5、檢修人力物力的約束。6、檢修連續(xù)性等其它要求?；鹆Πl(fā)電機組計劃檢修簡介

－－發(fā)電機檢修的現(xiàn)狀與分類（1）火力發(fā)電機組計劃檢修問題實際上是一個帶約束條件的組合優(yōu)化問題。從優(yōu)化目標來看，可分為：1、等備用容量法2、等風險度法3、總費用最小法火力發(fā)電機組計劃檢修簡介

－－發(fā)電機檢修的現(xiàn)狀與分類（2）總費用最小法：總費用最小法是從經(jīng)濟性出發(fā)來安排檢修計劃的一種算法。在檢修期間，除了正常的運行費用外，還要支出龐大的檢修費用，同時還會帶來許多“潛在”費用，如發(fā)電機組停運期間少發(fā)電能的損失，備用容量降低而可能造成的停電損失等。本文將這些費用之和稱為總費用。一個合理的檢修計劃應既考慮到系統(tǒng)的經(jīng)濟性，同時又能滿足系統(tǒng)的可靠性和安全性。本文以總費用最小為優(yōu)化目標，將系統(tǒng)的備用容量和（或）風險度等作為約束條件來考慮?；鹆Πl(fā)電機組計劃檢修簡介

－－發(fā)電機檢修的現(xiàn)狀與分類（3）從求解優(yōu)化問題的方法來看，有1、整數(shù)規(guī)劃法2、動態(tài)規(guī)劃法3、分枝定界法4、模糊控制算法5、遺傳算法6、模擬退火算法等等發(fā)電機組計劃檢修計劃數(shù)學模型

－－檢修計劃與可靠性的關(guān)系電力系統(tǒng)中發(fā)電機組的檢修計劃與系統(tǒng)的可靠性密切相關(guān)： 一方面，周期性地安排各機組的預防性檢修，使設備經(jīng)常保持良好的技術(shù)狀態(tài)，可以減少故障，延長壽命，從而提高電力系統(tǒng)運行的可靠性；另一方面，發(fā)電機組的檢修除了需要直接的用于檢修的龐大費用外，還會帶來許多潛在的費用，如發(fā)電機組停運期間少發(fā)電能的費用，備用容量降低而可能造成的停電損失費用等。因此，合理地安排檢修計劃，可以顯著提高系統(tǒng)運行的可靠性和經(jīng)濟性。發(fā)電機組計劃檢修計劃數(shù)學模型

－－發(fā)電系統(tǒng)的可靠性評估方法發(fā)電系統(tǒng)可靠性評估方法：１、建立發(fā)電機組的停運容量概率模型２、建立負荷的概率模型３、將兩個模型組合成風險度模型來求出發(fā)電系統(tǒng)的可靠性指標，如電力不足概率(LOLP)、期望缺電量(EENS)等。發(fā)電機組計劃檢修計劃數(shù)學模型

－－停運容量概率模型遞推算法（1）發(fā)電容量概率模型的遞推算法 容量模型實際上就是一張容量停運概率表。它表示出容量停運狀態(tài)的概率、頻率、持續(xù)時間等參數(shù)。容量狀態(tài)可以是確定，也可以是累計的。前者由各發(fā)電機停運容量組合得到，后者由大于或等于某一停運容量的單獨停運容量組合得到。

發(fā)電機組計劃檢修計劃數(shù)學模型

－－停運容量概率模型遞推算法（２）1、追加一臺機組的單獨概率和累積概率的遞推算法追加一臺強迫停運率為u，容量為c的兩狀態(tài)機組后，強迫停運率恰好為x的狀態(tài)的遞推公式為：其中分別是追加機組前、后停運容量為x的概率。發(fā)電機組計劃檢修計劃數(shù)學模型

－－停運容量概率模型遞推算法（3）2、單獨頻率和累積頻率的遞推算法 追加一臺兩狀態(tài)機組后停運容量為x的單獨狀態(tài)頻率：

累積狀態(tài)的頻率：y為大于x的第一個容量；為向具有更大的有效容量和更小容量的轉(zhuǎn)移率發(fā)電機組計劃檢修計劃數(shù)學模型

－－停運容量概率模型遞推算法（4）3、從容量中減去機組的遞推算法式中為減去待檢修機組i的停運概率和機組i的容量。發(fā)電機組計劃檢修計劃數(shù)學模型

－－兩級負荷模型（1）兩級負荷模型按下述假定形成：在D天內(nèi)有N級負荷水平，這N級負荷水平為一隨機數(shù)列，且每隔D天循環(huán)一次；日峰荷持續(xù)e天，低谷負荷持續(xù)1-e天且保持恒定不變。負荷的轉(zhuǎn)移率與容量的轉(zhuǎn)移率彼此獨立。兩級負荷模型的參數(shù)如下：負荷水平N；負峰荷值谷荷值;出現(xiàn)次數(shù);循環(huán)長度；平均持續(xù)時間峰荷(e天)；谷峰(1-e天)發(fā)電機組計劃檢修計劃數(shù)學模型

－－風險度模型（1）將容量模型和負荷模型結(jié)合，形成風險度模型。使用風險度模型計算可靠性指標。1、LOLE和HLOLE：電力不足期望天數(shù)或小時數(shù)

其中分別為第i天（或第i小時）的可用容量、預測峰荷和電力不足概率。發(fā)電機組計劃檢修計劃數(shù)學模型

－－風險度模型（2）2、EENS：電量不足期望值。

式中，為計算步長，為第i小時電力不足累積概率，m為小時數(shù)?；鹆Πl(fā)電機組計劃檢修優(yōu)化模型

——目標函數(shù)（1）發(fā)電機組計劃檢修可看作一個帶約束條件的組合優(yōu)化問題。在滿足合理可靠性（如最小備用容量）和檢修條件（如檢修力量）等約束下，安排機組的檢修時間，使所需的費用最小。這里的費用包括生產(chǎn)費用、檢修費用和期望停電損失費用等。火力發(fā)電機組計劃檢修優(yōu)化模型

——目標函數(shù)（2）目標函數(shù)可用下式表示

式中，i：參加檢修機組的序號；I：參加檢修機組數(shù)目j：檢修時段序號（如星期）；J：檢修時段數(shù)。：機組i燃料費用系數(shù)；機組i在時段j的出力。：機組i檢修起始時間，機組i預定起始檢修時間，火力發(fā)電機組計劃檢修優(yōu)化模型

——目標函數(shù)（3）當機組i在開始檢修時的檢修費用；停電損失費用系數(shù)。在時段j的期望停電損失電能。式中的三項分別表示生產(chǎn)費用、檢修費用和停電損失期望值?；鹆Πl(fā)電機組計劃檢修優(yōu)化模型

——約束條件1、開始檢修時間約束；機組i的起始檢修時間應在預定期內(nèi)：2、檢修連續(xù)性約束；機組i一旦開始檢修，在檢修時段數(shù)，機組i都處于檢修狀態(tài);3、檢修力量約束一些機組（如同一電廠內(nèi)）由于檢修人力、物力或場地問題不能同時安排檢修。4、電力系統(tǒng)功率平衡約束；5、最小備用容量約束?；鹆Πl(fā)電機組計劃檢修優(yōu)化模型

——考慮約束條件的目標函數(shù)開始檢修時間和檢修連續(xù)性約束條件在尋求最優(yōu)解時很容易判斷是否被滿足。約束條件（3）、（4）、（5）須用懲罰函數(shù)來表示。引入懲罰函數(shù)和懲罰法系數(shù)表示約束條件（3）、（4）和（5），考慮了約束條件目標函數(shù)便可寫為：

遺傳/模擬退火算法

——遺傳算法（1）遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。其主要特點是群體搜索策略和群體中個體的信息交換，搜索不依賴于梯度信息。它尤其適用于處理傳統(tǒng)搜索方法難于解決的復雜和非線性問題。現(xiàn)在廣泛應用于組合優(yōu)化、機器學習、自適應控制、規(guī)劃設計等領(lǐng)域。遺傳/模擬退火算法

——遺傳算法（2）簡單遺傳算法 遺傳算法是具有“生成＋檢測”(generate-andtest)的迭代過程的搜索方法。遺傳算法是一種群體操作，該操作以群體中的所有個體為對象。選擇、交叉和變異是遺傳算法的3個主要操作算子，它們構(gòu)成了所謂的遺傳操作（geneticoperation），使遺傳算法具有了其它算法所沒有的特性。遺傳/模擬退火算法

——遺傳算法（3）遺傳算法包括了如下5個基本要素：（1）參數(shù)編碼；（2）初始群體設定；（3）適應值函數(shù)的設計；（4）遺傳操作設計（選擇和交叉操作）；（5）控制參數(shù)設定。這5個要素構(gòu)成遺傳算法的核心內(nèi)容。遺傳算法在搜索進化的過程中，需評估個體的優(yōu)劣，并作為以后遺傳的依據(jù)，評估函數(shù)稱作適值函數(shù)。實際問題參數(shù)值編碼成位串形式群體1計算適值選擇與遺傳統(tǒng)計結(jié)果群體2經(jīng)過優(yōu)化的一個或多個參數(shù)值改善或解決實際問題位串解碼得參數(shù)計算目標函數(shù)值函數(shù)值向適值影射適值調(diào)整繁殖交叉變異群體2隨機算子遺傳算法流程圖遺傳/模擬退火算法

——遺傳算法（4）控制遺傳算法的主要參數(shù)有群體規(guī)模和算法執(zhí)行的最大代數(shù)目，次要參數(shù)有復制概率、交叉概率和變異概率等參數(shù)。它們對遺傳算法的影響集中在兩大方面：優(yōu)化結(jié)果和計算時間。遺傳算法理論主要基于模式定理和積木塊假設。遺傳算法的優(yōu)越性主要表現(xiàn)在：1）、它在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，它也能以很大的概率找到整體最優(yōu)解；2）由于它固有的并行性，遺傳算法非常適用于大規(guī)模并行計算機。遺傳/模擬退火算法

——遺傳算法（5）組合優(yōu)化（combinatorialoptimization）是遺傳算法最基本的也是最重要的研究和應用領(lǐng)域之一。一般來說，組合優(yōu)化問題通常帶有大量的局部極值點，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線性的NP完全問題，因此，精確地求解組合優(yōu)化問題的全局最優(yōu)解一般是不可能的。遺傳算法近十幾年來在組合優(yōu)化領(lǐng)域得到了相當廣泛的研究和應用，并已在解決諸多典型組合優(yōu)化問題中顯示了良好的性能和效果。機組檢修實際上就是一個帶約束條件的組合優(yōu)化問題。遺傳/模擬退火算法

——遺傳算法（6）采用遺傳算法的組合優(yōu)化方法可以描述如下：（1）確定群體規(guī)模n（整數(shù)），使用隨機的方法或其它方法產(chǎn)生n個可能解組成初始解群。（2）對每一個個體(變量k稱作“代”數(shù)，初始值為k=1），計算其適應值。（3）對于每一個體，計算其生存的概率:

然后設計一個隨機選擇器，依據(jù)以一定的隨機方法產(chǎn)生配種個體遺傳/模擬退火算法

——遺傳算法（7）（4）產(chǎn)生下一代解群。選擇兩個配種個體,并依據(jù)一定的組合規(guī)則（如交叉、變異、逆轉(zhuǎn)等）將結(jié)合成兩個新一代的個體，直至新一代n個個體形成完畢。（5）重復步驟（2）—（4），直至滿足程序的終止條件（如解的質(zhì)量達到滿意的范圍或代數(shù)達到預定值。遺傳/模擬退火算法

——模擬退火算法（1）模擬退火（SimulatedAnnealing）算法是基于MonteCarlo迭代求解法的一種啟發(fā)式隨機搜索算法。它通過模擬退火過程，尋找到全局（或近似）最優(yōu)解。該算法把目標函數(shù)看成退火物體的能量函數(shù)，某一控制參數(shù)視為溫度T，解空間當作退火物體的形態(tài)空間，因此其尋找基態(tài)的過程也就是求目標函數(shù)極小值的優(yōu)化過程。遺傳/模擬退火算法

——模擬退火算法（2）設為所有可能的組合狀態(tài)集合，C：S→R為非負目標函數(shù)，即反映取狀態(tài)為解的代價，則組合優(yōu)化問題可表述為尋找使得SA法的基本思想是把每種組合狀態(tài)看作某一物質(zhì)體系的微觀狀態(tài)，而看成該物質(zhì)體系的狀態(tài)下的能量，并用控制參數(shù)T表示偽溫度。讓T從一個足夠高的值緩慢下降。對每個T，用Metropolis抽樣法模擬該體系在此T下的熱平衡態(tài)。遺傳/模擬退火算法

——模擬退火算法（3）即對當前狀態(tài)S做隨機擾動產(chǎn)生一個新狀態(tài)，計算增量,并根據(jù)概率exp()接受作為新的當前狀態(tài)。當這樣的隨機擾動重復足夠多次數(shù)后，系統(tǒng)將達到該溫度下的熱平衡態(tài)，并且系統(tǒng)的狀態(tài)將導致Boltzmann分布，b是Boltzmann常數(shù)。遺傳/模擬退火算法

——模擬退火算法（4）SA算法應遵循的如下的準則以便使其具有良好的退火策略。1．初始溫度的選取。退火算法要求足夠大。在算法SA中，不可能選為無窮大。選擇的準則為使所選擇的初始溫度與溫度時具有基本相同的效果即可。2．降溫過程。退火算法要求的選取應遵循兩個規(guī)則：的選取應使溫度從初溫下降到最低溫度所需的降溫次數(shù)不能為n的指數(shù)（否則SA算法的迭代次數(shù)將按N的指數(shù)規(guī)律增加）；的選取應保證最后求得最優(yōu)解的概率。遺傳/模擬退火算法

——模擬退火算法（5）若選得太大，溫度T下降快，算法計算時間短，但求解的準確性下降，還有可能陷入局部最小值。在具體實現(xiàn)算法時，降溫可用如下迭代實現(xiàn)。為一自適應調(diào)度參數(shù)，其選取原則為：在某個溫度下的迭代結(jié)束后，以能量函數(shù)E的方差為依據(jù)，當方差較小時，調(diào)節(jié)值，使值較大；否則，使較小。3．最低溫度的選取。實現(xiàn)退火過程要求最低溫度趨于零，然而在SA算法中，不可能等于零（否則會出現(xiàn)被零除之現(xiàn)象）。只要保證在最低溫度下，使系統(tǒng)趨于最優(yōu)解的概率為1即可。遺傳/模擬退火算法在機組計劃檢修中的應用——位串（1）1、位串以一年為一個檢修周期，一個星期為一個時段。假設機組i需要個時段才能完成檢修。由于機組檢修必須連續(xù)進行，機組i一旦在時段開始檢修，則在期間上，機組i都處于檢修狀態(tài)。由于一年有52個時段（星期），每一臺機組的起始檢修時段可用6個二進制位表示。表示I臺機組起始檢修時段的組合狀態(tài)的位串長度為6*I。如下圖所示。遺傳/模擬退火算法在機組計劃檢修中的應用——位串（2）B5B4B3B2B1B0機組1：010011機組2：100100. .機組n：000111

機組１機組２.........機組n位串：010011100100.........000111

位串的結(jié)構(gòu)（例）上圖中一行表示一臺機組的起始檢修時間，一個位串可表示一個完整的機組檢修計劃。遺傳/模擬退火算法在機組計劃檢修中的應用——位串（3）因為機組i的起始檢修時間

于是機組i的檢修時間便可求出。應當特別說明，對于每一臺機組，大于110100（對應于十進制的52）的位串為無效位串。遺傳/模擬退火算法在機組計劃檢修中的應用——適值函數(shù)（1）機組檢修計劃優(yōu)化目標是使總費用函數(shù)F(x)最小。使用遺傳算法時，須將目標函數(shù)映射成求適應值求極大值形式。本文使用下面的映射方法獲得適應值函數(shù)f(x)。

是一個足夠大的輸入值，與群體無關(guān).。用適應值函數(shù)來衡量位串（個體）的優(yōu)劣。適應值大的個體有較強的生存能力來繁殖下一代。在求解的過程中，往往要對適應值進行縮放，即適應值定標。適應值定標方式有線性定標、σ截斷和乘冪定標。本文采用線性定標。遺傳/模擬退火算法在機組計劃檢修中的應用——適值函數(shù)（2）對于原適應值函數(shù)f，線性定標后的適應值函數(shù)f'為：f'=af+b式中，a、b滿足下列的兩個條件：1）原適應值平均值f等于定標后的適應值平均值。2）定標后適應值函數(shù)的最大值等于原適應值函數(shù)平均值所指定的倍數(shù)，即

一般，可在（1.2~2.0）范圍取值。如果定標后出現(xiàn)負的適應值，可以把原適應值最小值映射到定標后的最小值。但此時仍需保持遺傳/模擬退火算法在機組計劃檢修中的應用——遺傳/模擬退火算法（1）本文采用多層次交叉操作。交叉操作在同一位串的機組間和不同位串間進行。由于單臺機組沒有適值函數(shù)，隨機選擇同一位串內(nèi)的兩臺機組進行交叉操作，如圖所示。B5B4B3B2B1B0B5B4B3B2B1B0----機組i100|110機組i100101機組j110|101機組j110110--- (a)交叉前（b)交叉后 同一位串內(nèi)的機組間交叉操作遺傳/模擬退火算法在機組計劃檢修中的應用——遺傳/模擬退火算法（2）不同位串間的交叉操作應按它們的適應值比例進行，如圖4所示。機組１機組２......機組n機組１機組２....機組n----位串i010011100|100......001101位串i010011100100....000111位串j010011100|100......000111位串j010011100100....001101----

(a)交叉前（b)交叉后 不同位串間交叉操作遺傳/模擬退火算法在機組計劃檢修中的應用——