第3章優(yōu)化算法1-遺傳算法2014

12023/2/1系統(tǒng)工程第三章系統(tǒng)的優(yōu)化算法第一節(jié)基于遺傳算法的隨機(jī)優(yōu)化搜索1.1基本概念1.2基本遺傳算法1.3遺傳算法應(yīng)用舉例1.4遺傳算法的特點(diǎn)與優(yōu)勢(shì)1.5基于實(shí)數(shù)編碼的加速遺傳算法2023/2/13遺傳算法概述遺傳算法（geneticalgorithm，簡(jiǎn)稱GA）是由美國J.H.Holland于1975年提出的一種全新的優(yōu)化搜索算法。GA發(fā)展初期，并沒有引起學(xué)術(shù)界的關(guān)注，因而發(fā)展比較緩慢，直到八十年代，GA的研究才引起重視并逐步成熟起來，目前，已在組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、經(jīng)濟(jì)預(yù)測(cè)等領(lǐng)域取得了令人矚目的應(yīng)用成果。2023/2/14算法的學(xué)說：（１）遺傳:“種瓜得瓜，種豆得豆”，親代把生物信息交給子代，子代按照所得信息而發(fā)育、分化，子代總是和親代具有相同或相似的性狀。（２）變異:

親代和子代之間以及子代的不同個(gè)體之間總有差異。變異是隨機(jī)發(fā)生的，變異的選擇和積累是生命多樣性的根源。（３）生存斗爭(zhēng)和適者生存:由于弱肉強(qiáng)食和生存斗爭(zhēng)不斷進(jìn)行，其結(jié)果是適者生存，不適者被淘汰，通過一代代的選擇作用，物種變異朝著一個(gè)方向積累，演變?yōu)樾碌奈锓N。2023/2/15基本思想——遺傳進(jìn)化，根據(jù)自然選擇和適者生存原理，用簡(jiǎn)單的編碼技術(shù)和繁殖機(jī)制，模擬自然界生物群體優(yōu)勝劣汰的進(jìn)化過程，實(shí)現(xiàn)對(duì)復(fù)雜問題的求解。把搜索空間（欲求解問題的解空間）映射為遺傳空間，把每一個(gè)可能的解編碼為一個(gè)向量（二進(jìn)制或十進(jìn)制數(shù)字串），稱為一個(gè)染色體（或個(gè)體），向量中每一個(gè)元素稱為基因。所有染色體組成群體（群體中染色體個(gè)數(shù)用POP表示），并按預(yù)定的目標(biāo)函數(shù)（或某種評(píng)價(jià)指標(biāo)）對(duì)每個(gè)染色體進(jìn)行評(píng)價(jià)，根據(jù)其結(jié)果給出一個(gè)適應(yīng)度值。遺傳算法的實(shí)現(xiàn)2023/2/16算法開始時(shí)，先隨機(jī)地產(chǎn)生一些染色體（欲求解問題的候選解），計(jì)算其適應(yīng)度，根據(jù)適應(yīng)度對(duì)諸染色體進(jìn)行選擇、交叉、變異操作，剔除適應(yīng)度差的染色體，留下適應(yīng)度較好（性能優(yōu)良）的染色體，從而得到新的群體。新群體的染色體是上一代群體的優(yōu)秀者，繼承了上一代的優(yōu)良性態(tài)，因而明顯優(yōu)于上一代，這樣就能向著更優(yōu)解的方向進(jìn)化，直至滿足某種預(yù)定的優(yōu)化收斂指標(biāo)。2023/2/171.1基本概念

1.個(gè)體與種群

●個(gè)體就是模擬生物個(gè)體而對(duì)問題中的對(duì)象（一般就是問題的解）的一種稱呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。

●

種群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集。2023/2/18

2.適應(yīng)度與適應(yīng)度函數(shù)

●

適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度，而對(duì)問題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。

●適應(yīng)度函數(shù)(fitnessfunction)就是問題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。

2023/2/193.染色體與基因

染色體（chromosome）就是問題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個(gè)體染色體

9----

1001

（2，5，6）----0101011102023/2/1104.遺傳操作亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作:

●

選擇-復(fù)制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

2023/2/111

選擇-復(fù)制通常做法是：對(duì)于一個(gè)規(guī)模為N的種群S，每個(gè)染色體xi∈S具有一定的選擇概率P(xi)所決定的選中機(jī)會(huì),分N次從S中隨機(jī)選定N個(gè)染色體,并進(jìn)行復(fù)制。

選擇概率P(xi)的計(jì)算公式為父代個(gè)體的數(shù)量2023/2/112

交叉就是互換兩個(gè)染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

染色體s1=01001011,s2=10010101,

交換其后4位基因,即2023/2/113

變異就是改變?nèi)旧w某個(gè)(些)位上的基因。染色體s=11001101，將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。2023/2/1141.2基本遺傳算法

遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束2023/2/115

算法中的一些控制參數(shù)：

■

種群規(guī)模：初始種群中染色體的數(shù)量

■

最大換代數(shù)

■

交叉率(crossoverrate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4～0.99。

■

變異率(mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.1。2023/2/116

基本遺傳算法Step1

在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；Step2

隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1,s2,…,sN，組成初始種群S0={s1,s2,…,sN}，置代數(shù)計(jì)數(shù)器t=1；Step3

計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f(si)；Step4

若終止條件滿足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。否則step52023/2/117

Step5

按選擇概率P(xi)所決定的選中機(jī)會(huì)，每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制（賭輪選擇法），共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1(子代)；

Step6

按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對(duì)進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2(子代)

；2023/2/118

Step7

按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3(子代)

；

Step8

將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)Step3，計(jì)算適應(yīng)度；

2023/2/1191.3遺傳算法應(yīng)用舉例

例1.1

利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。

y=x2

31

XY2023/2/120

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。那么，［0,31］中的點(diǎn)x就是解的個(gè)體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(gè)(解)空間。這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。2023/2/121

解

(1)

設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S0:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應(yīng)度函數(shù),

取適應(yīng)度函數(shù)：f(x)=x2

終止條件：x=31(11111)

若精度ε=1則區(qū)間長(zhǎng)度Smax-Smin=31(Smax-Smin)/ε=31≤2L-1L=52023/2/122s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)計(jì)算適應(yīng)度f(si)

。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361∑f=1170(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對(duì)其染色體進(jìn)行選擇、遺傳、變異操作2023/2/123再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.312023/2/124

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法2023/2/125

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計(jì)算公式為2023/2/126選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0012023/2/127于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）S0的子代S12023/2/128交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。分別交換后兩位基因，得新染色體：

s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）

s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）

S1的子代S22023/2/129變異設(shè)變異率pm=0.001。這樣，群體S2中共有5×4×0.001=0.02位基因可以變異。顯然不足1位，所以本輪遺傳操作不做變異。

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）2023/2/130

第二代種群S2中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.0012023/2/131

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍然不會(huì)發(fā)生變異。

2023/2/132得第三代種群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代種群S3中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0012023/2/133

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會(huì)發(fā)生變異。2023/2/134得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。操作終止，將染色體“11111”作為最終結(jié)果輸出。將染色體“11111”解碼，即得最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。

YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x2

16242831

X第四代種群及其適應(yīng)度2023/2/136例1.2水電站廠內(nèi)經(jīng)濟(jì)運(yùn)行

水電站廠內(nèi)經(jīng)濟(jì)運(yùn)行準(zhǔn)則是在滿足電力系統(tǒng)負(fù)荷（日負(fù)荷圖）要求的前提下，使各機(jī)組耗用的總流量最小，它是電力系統(tǒng)經(jīng)濟(jì)運(yùn)行的重要組成部分。開停機(jī)計(jì)劃問題在數(shù)學(xué)上表現(xiàn)為一個(gè)大規(guī)模的非線性整數(shù)規(guī)劃問題。

目標(biāo)：總流量最小2023/2/137用遺傳算法尋求最優(yōu)運(yùn)行方式時(shí)，每個(gè)染色體表示某一時(shí)段各機(jī)組的組合狀態(tài)，染色體中基因表示其對(duì)應(yīng)機(jī)組的運(yùn)行方式，1表示開機(jī)，0表示停機(jī)，如系統(tǒng)共有5臺(tái)機(jī)組，染色體10011，表示在該時(shí)段第1，4，5臺(tái)機(jī)組開機(jī)。適應(yīng)度函數(shù)為：開開關(guān)關(guān)關(guān)…N個(gè)2023/2/138式中，Q0為一常數(shù)，Hit

為第i臺(tái)機(jī)組在t時(shí)段的平均水頭，Nit為第i臺(tái)機(jī)組在t時(shí)段的平均出力，Qi

為第i臺(tái)機(jī)組在水頭Hit

、出力Nit下的發(fā)電流量，uit為t時(shí)段第i個(gè)基因的值，Pikt

為第i臺(tái)機(jī)組的開停機(jī)罰因子，Qikt為第i臺(tái)機(jī)組的開停機(jī)損耗流量。初始種群由滿足約束條件的個(gè)體組成，然后對(duì)染色體利用適應(yīng)度函數(shù)評(píng)價(jià)，根據(jù)給定的選擇概率、交叉概率、變異概率進(jìn)行選擇、交叉、變異（1變0，0變1）操作，直到滿足某種收斂準(zhǔn)則。2023/2/139例1.3含沙量預(yù)報(bào)XX水庫上游的A水文站至入庫的B站區(qū)間，是該水庫泥沙的主要來源，入庫含沙量隨著區(qū)間產(chǎn)流量的變化而變化，而A站以上地區(qū)的入庫水沙則相對(duì)穩(wěn)定?，F(xiàn)有QB、QA資料，預(yù)測(cè)入庫含沙量。水文站A水文站B水庫Q區(qū)=QB-QAQB資料分析表明含沙量與兩組數(shù)據(jù)相關(guān)性較高2023/2/140預(yù)報(bào)函數(shù)：式中

—入庫含沙量的預(yù)報(bào)值，kg/m3;μ—含沙量的真值，kg/m3;Q1—B站流量，m3/s;Q2—區(qū)間流量，m3/s;a1,a2,b1,b2,c—模型參數(shù)。目標(biāo)函數(shù)：若精度ε=0.01(cmax-cmin)/ε≤2L

-1得Lc則字符串長(zhǎng)度為5參數(shù)之和2023/2/1411.4遺傳算法的優(yōu)缺點(diǎn)

◆優(yōu)點(diǎn):標(biāo)準(zhǔn)遺傳算法（SGA）至今仍是國內(nèi)外GA應(yīng)用中常用的實(shí)施方案，它提供了遺傳算法的基本框架，也解決了簡(jiǎn)單的函數(shù)優(yōu)化問題：（1）解空間搜索遺傳算法一般是直接在解空間搜索,而不像其它搜索那樣一般是在問題空間搜索,最后才找到解。（2）不受導(dǎo)數(shù)的影響傳統(tǒng)優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，往往需要函數(shù)的導(dǎo)數(shù)值等其他輔助信息才能確定搜索方向。無法或很難求導(dǎo)數(shù)的目標(biāo)函數(shù)，或?qū)?shù)不存在，以及組合優(yōu)化問題等，應(yīng)用遺傳算法時(shí)就顯得比較方便。2023/2/142（3）并行搜索遺傳算法的搜索過程是從空間的一個(gè)點(diǎn)集(種群)到另一個(gè)點(diǎn)集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。因而它實(shí)際是一種并行搜索,適合大規(guī)模并行計(jì)算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。（4）較強(qiáng)的適應(yīng)性遺傳算法的適應(yīng)性強(qiáng),除需知適應(yīng)度函數(shù)外,幾乎不需要其他的先驗(yàn)知識(shí)。2023/2/143（5）全局搜索遺傳算法長(zhǎng)于全局搜索,它不受搜索空間的限制性假設(shè)的約束,不要求連續(xù)性,能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解。

（6）決策變量的編碼作為運(yùn)算對(duì)象對(duì)決策變量的編碼處理方式，借鑒了生物學(xué)中染色體和基因等概念，模仿自然界中生物的遺傳和進(jìn)化機(jī)理，對(duì)一些無數(shù)值概念或很難有數(shù)值概念，而只有代碼概念的優(yōu)化問題，編碼處理方式更顯示出了其獨(dú)持的優(yōu)越性。2023/2/144（7）使用概率搜索技術(shù)傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法，一個(gè)搜索點(diǎn)到另一個(gè)搜索點(diǎn)的轉(zhuǎn)移有確定的轉(zhuǎn)移方法和轉(zhuǎn)移關(guān)系，這種確定性有可能使得搜索永遠(yuǎn)達(dá)不到最優(yōu)點(diǎn)。遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，選擇、交叉、變異以一種概率的方式來進(jìn)行的．雖然這種概率特性也會(huì)使群體中產(chǎn)生—些適應(yīng)度不高的個(gè)體，但隨著進(jìn)化過程的進(jìn)行，新的群體中總會(huì)更多地產(chǎn)生出許多優(yōu)良的個(gè)體。（交叉和變異概率等參數(shù)會(huì)影響算法的搜索效率，如何選擇是一個(gè)比較重要的問題。）2023/2/145但對(duì)于復(fù)雜的系統(tǒng)優(yōu)化問題，SGA在使用時(shí)出現(xiàn)了一些困難和問題，（１）SGA收斂于最優(yōu)解的概率小于1。（２）SGA在使用選擇算子進(jìn)行優(yōu)勝劣汰時(shí)，要求個(gè)體的適應(yīng)度均大于零，因此需考慮