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

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

1.個體與種群

●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。

●

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

2.適應度與適應度函數

●

適應度(fitness)就是借鑒生物個體對環境的適應程度，而對問題中的個體對象所設計的表征其優劣的一種測度。

●適應度函數(fitnessfunction)就是問題中的全體個體與其適應度之間的一個對應關系。它一般是一個實值函數。該函數就是遺傳算法中指導搜索的評價函數。

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

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

9----

1001

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

●

選擇-復制(selection-reproduction)

●

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

●

變異(mutation，亦稱突變)

2023/2/111

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

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

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

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

染色體s1=01001011,s2=10010101,

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

變異就是改變染色體某個(些)位上的基因。染色體s=11001101，將其第三位上的0變為1,即

s=11001101→11101101=s′。

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

遺傳算法基本流程框圖生成初始種群計算適應度選擇-復制交叉變異生成新一代種群終止?結束2023/2/115

算法中的一些控制參數：

■

種群規模：初始種群中染色體的數量

■

最大換代數

■

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

■

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

基本遺傳算法Step1

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

隨機產生U中的N個個體s1,s2,…,sN，組成初始種群S0={s1,s2,…,sN}，置代數計數器t=1；Step3

計算S中每個個體的適應度f(si)；Step4

若終止條件滿足，則取S中適應度最大的個體作為所求結果，算法結束。否則step52023/2/117

Step5

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

Step6

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

；2023/2/118

Step7

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

；

Step8

將群體S3作為新一代種群，即用S3代替S，t=t+1，轉Step3，計算適應度；

2023/2/1191.3遺傳算法應用舉例

例1.1

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

y=x2

31

XY2023/2/120

分析

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

解

(1)

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

(2)定義適應度函數,

取適應度函數：f(x)=x2

終止條件：x=31(11111)

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

s3=8(01000),s4=19(10011)計算適應度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)計算各代種群中的各個體的適應度,并對其染色體進行選擇、遺傳、變異操作2023/2/123再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

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］區間內產生一個均勻分布的隨機數r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為2023/2/126選擇-復制

設從區間［0,1］中產生4個隨機數如下:

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

染色體

適應度選擇概率積累概率選中次數s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0012023/2/127于是，經復制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

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

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

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變異設變異率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中各染色體的情況

染色體

適應度選擇概率積累概率

估計的選中次數s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.0012023/2/131

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

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

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

做交叉運算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

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

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

這一輪仍然不會發生變異。

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

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

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

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

染色體

適應度選擇概率積累概率

估計的選中次數s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0012023/2/133

設這一輪的選擇-復制結果為：

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

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

做交叉運算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得

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

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

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

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

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

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

YYy=x2

8131924

X第一代種群及其適應度y=x2

12162527

XY第二代種群及其適應度y=x2

9192428

XY第三代種群及其適應度y=x2

16242831

X第四代種群及其適應度2023/2/136例1.2水電站廠內經濟運行

水電站廠內經濟運行準則是在滿足電力系統負荷（日負荷圖）要求的前提下，使各機組耗用的總流量最小，它是電力系統經濟運行的重要組成部分。開停機計劃問題在數學上表現為一個大規模的非線性整數規劃問題。

目標：總流量最小2023/2/137用遺傳算法尋求最優運行方式時，每個染色體表示某一時段各機組的組合狀態，染色體中基因表示其對應機組的運行方式，1表示開機，0表示停機，如系統共有5臺機組，染色體10011，表示在該時段第1，4，5臺機組開機。適應度函數為：開開關關關…N個2023/2/138式中，Q0為一常數，Hit

為第i臺機組在t時段的平均水頭，Nit為第i臺機組在t時段的平均出力，Qi

為第i臺機組在水頭Hit

、出力Nit下的發電流量，uit為t時段第i個基因的值，Pikt

為第i臺機組的開停機罰因子，Qikt為第i臺機組的開停機損耗流量。初始種群由滿足約束條件的個體組成，然后對染色體利用適應度函數評價，根據給定的選擇概率、交叉概率、變異概率進行選擇、交叉、變異（1變0，0變1）操作，直到滿足某種收斂準則。2023/2/139例1.3含沙量預報XX水庫上游的A水文站至入庫的B站區間，是該水庫泥沙的主要來源，入庫含沙量隨著區間產流量的變化而變化，而A站以上地區的入庫水沙則相對穩定。現有QB、QA資料，預測入庫含沙量。水文站A水文站B水庫Q區=QB-QAQB資料分析表明含沙量與兩組數據相關性較高2023/2/140預報函數：式中

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

-1得Lc則字符串長度為5參數之和2023/2/1411.4遺傳算法的優缺點

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

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