基于遺傳算法的配電網(wǎng)優(yōu)化課件

1、學(xué)號：S100301001姓名：陳誠導(dǎo)師：朱偉基于遺傳算法的配電網(wǎng)優(yōu)化規(guī)劃1 遺傳算法簡介 遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局 優(yōu)化概率搜索方法。 它最早由美國密西根大學(xué)的H.Holland教授提出，起源于60年代對自然和人工 自適應(yīng)系統(tǒng)的研究； 1967年，Bagley發(fā)表了關(guān)于遺傳算法應(yīng)用的論文，在其論文中首次使用“遺傳算法（ Genetic Algorithm）”一詞。 70年代 De Jong基于遺傳算法的思想在計算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化 計算實驗。 在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。

2、1.11遺傳算法概要： 在遺傳算法中將n維決策向量Xx1,x2,xnT用n個記號Xi(i=1,2,n)所組成的符號串X來去示： Xxlx2xn Xx1，x2， ,xnT 把每一個xi看作一個遺傳基因，這樣，X就可看做是由n個遺傳基因所組成的一個 染色體。 這里的等位基因可以是一組整數(shù)。也可以是某一范圍內(nèi)的實數(shù)值，或者是純粹的 一個記號。最簡單的等位基因是由0和1這兩個整數(shù)組成的，相應(yīng)的染色體就可 表示為一個二進(jìn)制符號串。 這種編碼所形成的排列形式X是個體的基因型，與它對應(yīng)的X值是個體的表現(xiàn)型。 對于每一個個體X，要按照一定的規(guī)則確定出其適應(yīng)度，個體的適應(yīng)度與其對應(yīng) 的個體表現(xiàn)型X的目標(biāo)函數(shù)值相

3、關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)點，其適應(yīng)度越大；反之，其適應(yīng)度越小。 遺傳算法中，決策變量X組成了問題的解空間。對問題最優(yōu)解的搜索是通過對染色體X的搜索過程來進(jìn)行的。從而所有的染色體X就組成了問題的搜索空間。 生物的進(jìn)化是以集團(tuán)為主體的。與此相對應(yīng)，遺傳算法的運(yùn)算對象是由M個個 體所組成的集合，稱為群體（或稱種群）。與生物一代一代的自然進(jìn)化過程相類 似，遺傳算法的運(yùn)算過程也是一個反復(fù)迭代過程： 第t代群體記做 P(t)， 經(jīng)過一代遺傳和進(jìn)化后，得到 t+1 代群體，記做 P(t+1), 這個群體不斷地經(jīng)過遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng) 度較高的個體更多地遺傳到下一代，這樣最

4、終在群體中將會得到一個優(yōu)良的個體 X，它所對應(yīng)的表現(xiàn)型X將達(dá)到或接近于問題的最優(yōu)解X*。1.1.2 遺傳策法的運(yùn)算過程選擇(復(fù)制)： 根據(jù)各個個體的適應(yīng)度，按照一 定的規(guī)則或方法，從第t代群體P(t) 中選擇出一些優(yōu)良的個體遺傳到下 一代群體P(t+1)中；交叉： 將群體P(t)內(nèi)的各個個體隨機(jī)搭配 成對，對每一對個體，以某個概率 (稱為交叉概率）交換它們之間的 部分染色體；變異： 對群體P(t)中的每一個個體，以某一概率(稱為變異概率)改變某 一個或某一些基因座上的基因值為其他基因值。實際問題參數(shù)集編碼群體t計算適值運(yùn)算：復(fù)制 交叉 變異群體t+1滿足要求？解碼改善或解決實際問題群體t+1群

5、體tYN1.1.3 遺傳算法的手工模擬計算示例 為更好地理解遺傳算法的運(yùn)算過程，下面用手工計算來簡單地模擬遺傳算法的各 個主要執(zhí)行步驟。 例：求下述二元函數(shù)的最大值： max f(x1,x2)=x12+x22 s.t. x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 (1) 個體編碼 遺傳算法的運(yùn)算對象是表示個體的符號串，所以必須把變量 x1, x2 編碼為一種 符號串。本題中，用無符號二進(jìn)制整數(shù)來表示。 因 x1, x2 為 0 7之間的整數(shù)，所以分別用3位無符號二進(jìn)制整數(shù)來表示，將它 們連接在一起所組成的6位無符號二進(jìn)制數(shù)就形成了個體的基因型，表示一個可 行解。 例如，

6、基因型 X101110 所對應(yīng)的表現(xiàn)型是：x 5，6 。 個體的表現(xiàn)型x和基因型X之間可通過編碼和解碼程序相互轉(zhuǎn)換。 (2) 初始群體的產(chǎn)生 遺傳算法是對群體進(jìn)行的進(jìn)化操作，需要給其淮備一些表示起始搜索點的初始 群體數(shù)據(jù)。 本例中，群體規(guī)模的大小取為4，即群體由4個個體組成，每個個體可通過隨機(jī) 方法產(chǎn)生。 如：011101，101011，011100，111001 (3) 適應(yīng)度汁算 遺傳算法中以個體適應(yīng)度的大小來評定各個個體的優(yōu)劣程度，從而決定其遺傳 機(jī)會的大小。 本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值，并且是以求函數(shù)最大值為優(yōu)化目標(biāo)，故可直接 利用目標(biāo)函數(shù)值作為個體的適應(yīng)度。 (4) 選擇運(yùn)算 選擇運(yùn)

7、算(或稱為復(fù)制運(yùn)算)把當(dāng)前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個體將有更多的機(jī)會遺傳到下一代 群體中。 本例中，我們采用與適應(yīng)度成正比的概率來確定各個個體復(fù)制到下一代群體中 的數(shù)量。其具體操作過程是： 先計算出群體中所有個體的適應(yīng)度的總和 fi ( i=1.2,M ); 其次計算出每個個體的相對適應(yīng)度的大小 fi / fi ，它即為每個個體被遺傳 到下一代群體中的概率， 每個概率值組成一個區(qū)域，全部概率值之和為1； 最后再產(chǎn)生一個0到1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個概率區(qū) 域內(nèi)來確定各個個體被選中的次數(shù)。0124%24%17%35%1#2#

8、3#4#個體編號初始群體p(0)適值占總數(shù)的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數(shù)選擇結(jié)果1102011101111001101011111001 x1 x2 3 5 5 3 3 4 7 1(5) 交叉運(yùn)算 交叉運(yùn)算是遺傳算法中產(chǎn)生新個體的主要操作過程，它以某一概率相互交換某 兩個個體之間的部分染色體。 本例采用單點交叉的方法，其具體操作過程是： 先對群體進(jìn)行隨機(jī)配對； 其次隨機(jī)設(shè)置交叉點位置； 最后再相互交換配對染色體之間的部分基因。選擇結(jié)果01 110111 10011010 111110 01配對

9、情況交叉點位置個體編號12341-23-41-2：23-4：4交叉結(jié)果011001 111101101001111011 可以看出，其中新產(chǎn)生的個體“111101”、“111011”的適應(yīng)度較原來兩個個體 的適應(yīng)度都要高。(6) 變異運(yùn)算 變異運(yùn)算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進(jìn) 行改變，它也是產(chǎn)生新個體的一種操作方法。 本例中，我們采用基本位變異的方法來進(jìn)行變異運(yùn)算，其具體操作過程是： 首先確定出各個個體的基因變異位置，下表所示為隨機(jī)產(chǎn)生的變異點位置， 其中的數(shù)字表示變異點設(shè)置在該基因座處； 然后依照某一概率將變異點的原有基因值取反。對群體P(t)進(jìn)行一輪選擇、交叉

10、、變異運(yùn)算之后可得到新一代的群體p(t+1)。個體編號1234交叉結(jié)果011001 111101101001111011變異結(jié)果變異點4526011101 111111111001111010子代群體p(1)011101 111111111001111010 從上表中可以看出，群體經(jīng)過一代進(jìn)化之后，其適應(yīng)度的最大值、平均值都得 到了明顯的改進(jìn)。事實上，這里已經(jīng)找到了最佳個體“111111”。 注意 需要說明的是，表中有些欄的數(shù)據(jù)是隨機(jī)產(chǎn)生的。這里為了更好地說明問題， 我們特意選擇了一些較好的數(shù)值以便能夠得到較好的結(jié)果，而在實際運(yùn)算過程中 有可能需要一定的循環(huán)次數(shù)才能達(dá)到這個最優(yōu)結(jié)果。個體編號子

11、群體p(1)適值占總數(shù)的百分比總和1234011101 111111111001111010349850530.140.420.210.232351 x1 x2 3 5 7 7 7 1 7 2個體編號初始群體p(0) 適值fi(x1,x2)占總數(shù)的百分比fi / f1234011101101011011100111001343425500.240.240.170.35 x1 x2 3 5 5 3 3 4 7 1fi=143fmax=50f=35.75選擇結(jié)果011101111001101011111001配對情況交叉點位置1-23-41-2：23-4：4交叉結(jié)果011001 111101101

12、001111011選擇次數(shù)1102變異結(jié)果變異點4526011101 111111111001111010子代群體p(1) 適值fi(x1,x2)占總數(shù)的百分比fi / f011101 111111111001111010349850530.140.420.210.23 x1 x2 3 5 7 7 7 1 7 2fi=253fmax=98f=58.752.配電網(wǎng)網(wǎng)架優(yōu)化問題配電網(wǎng)網(wǎng)架優(yōu)化渉及到饋線段建設(shè)時間、建設(shè)地點和線徑等的最優(yōu)選擇，以滿足負(fù)荷增長的需求，同時服從饋線容量、電壓降落、網(wǎng)絡(luò)結(jié)構(gòu)、可靠性等約束。因此，網(wǎng)架優(yōu)化是一個大規(guī)模的組合優(yōu)化問題。常規(guī)的數(shù)學(xué)優(yōu)化方法很難在合理的時間內(nèi)得到問題

13、的最優(yōu)解，而遺傳算法不是對函數(shù)和它們的控制變量直接操作，所以不受函數(shù)約束條件的限制，能以較大的概率找到全局最優(yōu)解。2.1網(wǎng)架優(yōu)化模型2.11 目標(biāo)函數(shù)此模型中計及資金的時間價值，安等額分付資本回收計算，一年費用最小為目標(biāo)函數(shù)為： （1）式中 Z為方案的線路建設(shè)投資費用， 為方案第t年的運(yùn)行費用。當(dāng)以水平年為目標(biāo)時，設(shè)電氣設(shè)備的使用壽命n為25a，貼現(xiàn)率i為0.1，并假定使用年限內(nèi)運(yùn)行費用相等，則式（1）細(xì)化為 式（2）如下： 2.12約束條件a. 輻射網(wǎng)結(jié)構(gòu)。B. 電壓降落限制C. 負(fù)荷要求，AP=D式中 A為節(jié)點關(guān)聯(lián)弧矩陣，P為網(wǎng)絡(luò)潮流，D為負(fù)荷要求。d. 線路潮流限制，式中 為支路潮流，

14、為滿足某種條件的支路最大允許容量。2.2 編碼策略及初始解的產(chǎn)生采用常規(guī)二進(jìn)制編碼策略，將新建可行線路的投運(yùn)與否作為優(yōu)化變量（投運(yùn)為1，否則為0）。有隨機(jī)產(chǎn)生的備選網(wǎng)絡(luò)的生成樹替代常規(guī)遺傳算法隨機(jī)產(chǎn)生的初始解作為遺傳算法的初始解。生成樹的算法如下：屬于一個連通圖的頂點的集合稱為桶。初始狀態(tài)，所有各線條路都未標(biāo)記，定義的若干個桶也都是空的。第一步任意選擇一條線路。將它的兩個端點放入同一空桶內(nèi)，并標(biāo)記該線路。第二部任意選擇一條未標(biāo)記的線路（如果沒有這樣的線路，則算法停止），判斷兩端點是否都在同一桶內(nèi)。若是，返回第二步；否則，標(biāo)記該線路，轉(zhuǎn)向第三步。第三步若兩端點中的一個在桶內(nèi)，另一個不在，將不在桶

15、內(nèi)的端點放入另一個端點所在桶內(nèi)；若兩端點在不同的桶內(nèi)，將兩桶合并，使另一個成為空桶。如果圖的所有頂點都在一桶內(nèi)，則所有已標(biāo)記的線路構(gòu)成一個生成樹，算法停止。否則，返回第二步。2.3適應(yīng)值計算遺傳算法搜索的目標(biāo)是找到適應(yīng)值最大的解。右圖為適應(yīng)值的計算框圖。染色體解碼檢查網(wǎng)絡(luò)的連接結(jié)構(gòu)和輻射條件是否輻射網(wǎng)交流潮流功率是否越限壓降是否越限適應(yīng)值=f（功率損耗，電壓降，投資）適應(yīng)值=g(與電源相連的負(fù)荷節(jié)點數(shù))適應(yīng)值=h(功率越限數(shù)目)適應(yīng)值=v（壓降越限數(shù)目）NYYYNN2.4遺傳算子的設(shè)計2.4.1 選擇 應(yīng)用競爭法則，每次按一定概率從群體中選出m個個體，作為雙親用于繁殖后代，產(chǎn)生新的個體加入下一代群體中，體現(xiàn)自然界優(yōu)勝劣汰的思想。 2.4.2 雜交 采用單點雜交，即隨機(jī)地在兩個父染色體上選擇一個雜交點，僅交換該點對應(yīng)基因。因為原有父染色體均對應(yīng)輻射形網(wǎng)絡(luò)，經(jīng)上述隨機(jī)雜交后，輻射形結(jié)構(gòu)可能被破壞，因此，需區(qū)別不同的情況進(jìn)行處理：