人工智能入門課件第5章 遺傳算法

第5章遺傳算法5.1遺傳算法的基本概念5.2遺傳編碼5.3適應(yīng)值函數(shù)5.4遺傳操作5.5初始化群體5.6控制參數(shù)的選取5.7算法的終止準(zhǔn)則5.8遺傳算法的基本理論5.9遺傳算法簡例5.10遺傳算法的應(yīng)用領(lǐng)域5.1遺傳算法的基本概念基本思想使用模擬生物和人類進(jìn)化的方法求解復(fù)雜的優(yōu)化問題，因而也稱為模擬進(jìn)化優(yōu)化算法。遺傳算法將擇優(yōu)與隨機(jī)信息交換結(jié)合在一起，在每一代中，使用用上代中最好的，即最適應(yīng)環(huán)境的位或片段，形成新的人工生物集。遺傳算法是一個(gè)迭代過程，在每次迭代中都保留一組候選解，并按某種優(yōu)劣指標(biāo)進(jìn)行排序，然后按某種指標(biāo)從中選出一些解，利用遺傳算子，即下面要講到的遺傳操作，對其進(jìn)行運(yùn)算以產(chǎn)生新一代的一組解。重復(fù)上述過程，直到滿足指定的收斂要求為止。5.1.1遺傳算法的基本概念定義5.1個(gè)體:

個(gè)體是一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來描述基本的遺傳結(jié)構(gòu)。定義5.2適應(yīng)性：每個(gè)個(gè)體有一對應(yīng)的適應(yīng)值。在優(yōu)化問題中，適應(yīng)值來自于一個(gè)估計(jì)函數(shù)。定義5.3群體:由個(gè)體組成的集合。定義5.4遺傳操作：遺傳操作作用于群體而產(chǎn)生新的群體。標(biāo)準(zhǔn)的代遺傳操作一般包括選擇(或復(fù)制)，交叉(或重組)和變異三種基本形式。例子

一個(gè)簡單的遺傳操作實(shí)例5.1.2遺傳算法的基本流程遺傳算法涉及五大要素：參數(shù)編碼初始群體設(shè)定適應(yīng)度函數(shù)設(shè)計(jì)遺傳操作設(shè)計(jì)控制參數(shù)設(shè)定

確定實(shí)際問題參數(shù)集對參數(shù)進(jìn)行編碼初始化群體Ｐ(t)評價(jià)群體滿足停止準(zhǔn)則?遺傳操作結(jié)束群體Ｐ(t＋１)?群體Ｐ(t)三個(gè)基本操作：1.選擇2.交叉3.變異其它高級操作標(biāo)準(zhǔn)遺傳算法基本流程框圖選擇種群新后代變異交叉1234110001110001110101010111010001101101101154.538.343.734.61324#位串適應(yīng)值排序110001110001110100011100010001011101110011000101010110011100交叉點(diǎn)變異位標(biāo)準(zhǔn)遺傳算法基本流程框圖實(shí)例交配池遺傳算法的執(zhí)行過程選擇編碼策略，把參數(shù)集合Ｘ和域轉(zhuǎn)換為相應(yīng)編碼空間Ｓ；定義適應(yīng)值函數(shù)f(X);定義遺傳策略，包括選擇群體大小、選擇、交叉、變異方法以及確定交叉概率Ｐｃ、變異概率Ｐｍ等遺傳參數(shù)；隨機(jī)初始化生成群體Ｐ(t);計(jì)算群體中個(gè)體的適應(yīng)值f(X);按照遺傳策略，運(yùn)用選擇、交叉和變異操作作用于群體，形成下一代群體；判斷群體性能是否滿足某一指標(biāo)，或已完成預(yù)定迭代次數(shù)，不滿足則返回步驟（6），或修改遺傳策略再返回步驟(6)。5.2遺傳編碼5.2.1二進(jìn)制編碼5.2.2Gray編碼5.2.3實(shí)數(shù)編碼5.2.4有序編碼5.2.5結(jié)構(gòu)式編碼5.2.1二進(jìn)制編碼在二進(jìn)制編碼過程中，首先要確定二進(jìn)制串的長度l，串長l取決于變量的定義域及計(jì)算所需的精度。例5.2

變量x的定義域?yàn)閇－2，5]，要求精度為10-6，則我們需將[－2，5]分成至少7000000個(gè)等長小區(qū)域，而每個(gè)小區(qū)域用一個(gè)二進(jìn)制串表示。于是串長至少等于23，這是因?yàn)椋?194304=222<7000000<223=8388608這樣，計(jì)算中的任何一個(gè)二進(jìn)制串（b22b21…b0）都對應(yīng)[-2，5]中的一個(gè)點(diǎn)。5.2.2Gray編碼Gray編碼即是將二進(jìn)制碼通過如下變換進(jìn)行轉(zhuǎn)換得到的碼。設(shè)有二進(jìn)制串（β1β2…βn），對應(yīng)的Gray串為（γ1γ2…γn），則從二進(jìn)制碼到Gray碼的變換為其中

表示模2加法。從一個(gè)Gray碼到二進(jìn)制串的變換為例5.3

二進(jìn)制串1101011對應(yīng)的Gray串為101110。5.2.3實(shí)數(shù)編碼為了克服二進(jìn)制編碼的缺點(diǎn)，對于問題的變量是實(shí)向量的情形，直接可以采用十進(jìn)制進(jìn)行編碼，這樣可以直接在解的表現(xiàn)形式上進(jìn)行遺傳操作，從而便于引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加系統(tǒng)的搜索能力例3

作業(yè)調(diào)度問題（JSP）的種群個(gè)體編碼常用m×n的矩陣Y=[yij]，i=1，2，…，m，j=1，2，…，n（n為從加工開始的天數(shù)，m為工件的優(yōu)先順序）。yij表示工件i在第j日的加工時(shí)間。下表是一個(gè)隨機(jī)生成的個(gè)體所示。010203040506070809工件10212212工件2012004工件3100131工件4023001工件50203000115.2.4有序編碼對很多組合優(yōu)化問題，目標(biāo)函數(shù)的值不僅與表示解的字符串中各字符的值有關(guān)，而且與其所在字符串中的位置有關(guān)。這樣的問題稱為有序問題。若目標(biāo)函數(shù)的值只與表示解的字符串中各字符的位置有關(guān)而與其具體的字符值無關(guān)，則稱為純有序問題，如采用頂點(diǎn)排列的旅行商問題。例5.4

有10個(gè)城市的TSP問題，城市序號為{1，2，…，10}，則編碼位串：

12345678910表示對城市采用按序號升序方法訪問行走路線示按特定“1→3→5→7→9→2→4→6→8→10→1”依次訪問各個(gè)城市。5.2.5結(jié)構(gòu)式編碼對很多問題其更自然的表示是樹或圖的形式，這時(shí)采用其它形式的變可能很困難。這種將問題的解表達(dá)成樹或圖的形式的編碼稱為結(jié)構(gòu)式編碼。5.3適應(yīng)值函數(shù)適應(yīng)值函數(shù)構(gòu)成了個(gè)體的生成環(huán)境。根據(jù)個(gè)體的適應(yīng)值可以決定它在此環(huán)境下的生存能力。若SL表示位串空間，SL上的適應(yīng)值函數(shù)可表示為f:SL→R+，f為實(shí)值函數(shù)，R+表示非負(fù)實(shí)數(shù)集合。針對進(jìn)化過程中關(guān)于遺傳操作的控制的需要，選擇函數(shù)變換T：g→f，使得對于最優(yōu)解x*，maxf(x*)=optg(x*)(x*

[u，v])。5.4遺傳操作5.4.1選擇(selection)5.4.2交叉操作(crossover)5.4.3變異操作(mutation)5.4.1選擇(selection)選擇即從當(dāng)前群體中選出個(gè)體以生成交配池（matingpool）的過程。所選出的這些個(gè)體具有良好的特征，以便產(chǎn)生優(yōu)良的后代。1.基于適應(yīng)值比例的選擇2.基于排名的選擇3.基于局部競爭機(jī)制的選擇1.基于適應(yīng)值比例的選擇（1）繁殖池選擇相對適應(yīng)值：

每個(gè)個(gè)體的繁殖量：Ni=round(reli?N)（2）轉(zhuǎn)盤賭選擇2πpi現(xiàn)生成一個(gè)[0，1]內(nèi)的隨機(jī)數(shù)r，若p1+p2+…+pi-1<r≤p1+p2+…+pi，則選擇個(gè)體i。1.基于適應(yīng)值比例的選擇（3）Boltzmann選擇利用函數(shù)δ(fi)=exp(fi/T)將適應(yīng)值進(jìn)行變換，以改變原始的選擇壓力。其中T是一個(gè)控制參數(shù)，T取得較大（?。┲禃r(shí)選擇具有較?。ù螅┑倪x擇壓力，即適應(yīng)值的相對比例變?。ù螅?，通過這個(gè)變換之后再按照前面的選擇方法進(jìn)行父體的選擇。2.基于排名的選擇（1）線性排名選擇首先假設(shè)群體成員按適應(yīng)值大小從好到壞依次排列為x1，x2，…，xN，然后根據(jù)一個(gè)線性函數(shù)分配選擇概率pi。設(shè)線性函數(shù)pi＝（a－b·i/（N+1））/N，i=1，2，…，N，其中a，b為常數(shù)。由于，易得，b=2(a－1)。又要求對任意i=1，2，…，N，有pi>0，且p1≥p2≥…≥pN，故限定1≤a≤2。通常使用的值為a=1.1。2.基于排名的選擇（2）非線性排名選擇將群體成員按適應(yīng)值從好到壞依次排列，并按下式進(jìn)行分配選擇概率：其中q是常數(shù)，表示最好的個(gè)體的選擇概率。3.基于局部競爭機(jī)制的選擇（1）錦標(biāo)賽選擇(tournamentselection)

選擇時(shí)，先隨機(jī)地選擇在群體中選擇k個(gè)個(gè)體（放回或不放回）進(jìn)行比較，適應(yīng)值最好的個(gè)體將被選擇作為生成下一代的父體。反復(fù)執(zhí)行該過程，直到下一代個(gè)體數(shù)量達(dá)到預(yù)定的群體規(guī)模。參數(shù)k稱為競賽規(guī)模，一般取k=2。（2）(μ，λ)和μ+λ選擇

(μ，λ)選擇是先從規(guī)模為μ種群中隨機(jī)選取個(gè)體通過交叉和變異生成λ（≥μ）個(gè)后代，然后再從這些后代中選取μ個(gè)最優(yōu)的后代作為新的一代種群。μ+λ選擇則是從這些后代與其父體共μ+λ個(gè)后代中選取μ個(gè)最優(yōu)的后代。5.4.2交叉操作(crossover)交叉的具體步驟為：從交配池中隨機(jī)取出要交配的一對個(gè)體；根據(jù)位串長度L，對要交配的一對個(gè)體，隨機(jī)選取[1，L－1]中一個(gè)或多個(gè)的整數(shù)k作為交叉點(diǎn)；根據(jù)交叉概率pc(0<pc≤1)實(shí)施交叉操作，配對個(gè)體在交叉點(diǎn)處，相互交換各自的部分內(nèi)容，從而形成新的一對個(gè)體。對二進(jìn)制編碼常用的交叉算子有單點(diǎn)交叉、多點(diǎn)交叉和均勻交叉。對于從交配池中隨機(jī)選擇的兩個(gè)串s1=a11a12…a1l1a1l2…a1L，s2=a21a22…a2l1a2l2…a2L隨機(jī)選擇一個(gè)交叉位x

[1，2，…，L－1]，不妨設(shè)

l1≤x≤l2，對兩個(gè)位串中該位置右側(cè)部分的染色體位串進(jìn)行交換，產(chǎn)生兩個(gè)子位串個(gè)體為：s’1=a11a12…a1l1a2l2…a2L，s’2=a21a22…a2l1a1l2…a1L例5.5

考慮如下兩個(gè)11位變量的父個(gè)體：父個(gè)體1：01110011010父個(gè)體2：10101100101交叉點(diǎn)在位置5，交叉后生成兩個(gè)子個(gè)體：子個(gè)體1：01110100101子個(gè)體2：101010110101.單點(diǎn)交叉2.多點(diǎn)交叉對于選定的兩個(gè)個(gè)體位串，隨機(jī)選擇多個(gè)交叉點(diǎn)，構(gòu)成交叉點(diǎn)集合：x

1，x

2，…x

K

[1，2，…，L－1]，x

k≤x

k＋1，k=1，2，…，K－1將L個(gè)基因?yàn)閯澐譃镵＋1個(gè)基因位集合：Qk={lk，lk+1，…，lk+1－1}，k=1，2，…，K＋1，l1=1，lK+2=L+1算子形式為例5.6

考慮如下兩個(gè)11位變量的父個(gè)體：父個(gè)體1：01110011010父個(gè)體2：10101100101交叉點(diǎn)在位置2，6，10，交叉后生成兩個(gè)子個(gè)體：子個(gè)體1：01101111011子個(gè)體2：10110000100生成的新個(gè)體為s’1=a’11a’12……a’1L，s’2=a’21a’22……a’2L

3.均勻交叉將位串上的每一位按相同概率隨機(jī)進(jìn)行均勻交叉。均勻交叉算子生成的新個(gè)體為：s’1=a’11a’12……a’1L，s’2=a’21a’22……a’2L，其操作描述如下：例5.7

父個(gè)體1：01110011010父個(gè)體2：10101100101模板：01100011010子個(gè)體1：00110000000子個(gè)體2：

11101111111例5.8

設(shè)城市數(shù)的旅行商問題，對如下的兩個(gè)個(gè)進(jìn)行交叉，中間得豎線表示交叉點(diǎn)。

得到下一代的個(gè)體為：

它們都不是合法的個(gè)體。怎樣保證所產(chǎn)生的個(gè)體仍然合法?一種方法是為參與交換的數(shù)增加一個(gè)映射如下:

將此映射應(yīng)用于未交換的等位基因得到:

則為合法的。5.4.3變異操作變異的具體操作為:對中任一個(gè)體，隨機(jī)產(chǎn)生一實(shí)數(shù)，如果大于事先定義的變異概率的閾值，就對該個(gè)體進(jìn)行變異。1.實(shí)值變異2.二進(jìn)制變異5.5初始化群體初始群體中的個(gè)體一般是隨機(jī)產(chǎn)生的。我們往往希望在問題解空間均勻采樣，隨機(jī)生成一定數(shù)目的個(gè)體（為群體規(guī)模的2倍，即2n），然后從中挑出較好的個(gè)體構(gòu)成初始群體。對于二進(jìn)制編碼，染色體位串上的每一位基因在{0，1}上隨機(jī)均勻選擇，所以群體初始化至少需要L×n次隨機(jī)取值?？梢宰C明初始群體的位串譯碼到問題實(shí)空間中也是均勻分布的。5.6控制參數(shù)的選取

主要的參數(shù)包括：位串長度L，群體規(guī)模n，交叉概率pc，變異概率pm。參數(shù)的最佳建議：

n=20～200

pc=0.6～1.0pm=0.005～0.015.7算法的終止準(zhǔn)則(1)預(yù)先規(guī)定最大演化代數(shù);(2)連續(xù)多代后解的適應(yīng)值沒有明顯改進(jìn)，則終止;(3)達(dá)到明確的解目標(biāo)，則終止。5.9遺傳算法簡例例5.9

用GA求解一元函數(shù)最大值的優(yōu)化問題：f(x)=xsin(10

·x)+2.0x

[-1，2]（1）編碼變量x作為實(shí)數(shù)，可以視為遺傳算法的表現(xiàn)型形式。現(xiàn)采用二進(jìn)制編碼形式。如果設(shè)定求解精度精確到6位小數(shù)，由于區(qū)間長度為2－（－1）=3，因此將閉區(qū)間[－1，2]分為3×106等份。因?yàn)?097152=221<3×106<222=4194304所以編碼的二進(jìn)制串長至少需要22位。現(xiàn)在采用22位二進(jìn)制編碼，將一個(gè)二進(jìn)制串（b21b20…b0）與區(qū)間[－1，2]內(nèi)對應(yīng)的實(shí)數(shù)值的建立對應(yīng)：例如:一個(gè)二進(jìn)制串s1=〈1000101110110101000111〉表示實(shí)數(shù)0.637197x’=（1000101110110101000111）2=2288967（2）產(chǎn)生初始種群一個(gè)個(gè)體由串長為22的隨機(jī)產(chǎn)生的二進(jìn)制串組成染色體的基因碼，我們可以產(chǎn)生一定數(shù)目的個(gè)體組成的種群。設(shè)產(chǎn)生的4個(gè)初始個(gè)體如下：s1=<1000101110110101000111>s2=<000000111000000010000>s3=<1110000000111111000101>s4=<001000100011011101000>（3）計(jì)算適應(yīng)度對于個(gè)體的適應(yīng)度的計(jì)算，考慮到本例目標(biāo)函數(shù)在定義域內(nèi)均大于0，而且是求函數(shù)的最大值，所以直接引用目標(biāo)函數(shù)作為適應(yīng)值函數(shù)：f(s)=f(x)這里二進(jìn)制串s對應(yīng)變量x的值。編號個(gè)體串x適應(yīng)值百分比%累計(jì)百分比%s110001011101101010001110.6371972.58634529.129.1s2000000111000000010000-0.9589731.07887812.141.2s311100000001111110001011.6278883.25065036.577.7s40010001000110111010010-0.5990321.98178522.3100（4）遺傳操作設(shè)按轉(zhuǎn)盤賭方式選擇子個(gè)體，生成的隨機(jī)數(shù)為0.35，0.72。則選中的個(gè)體為s2和s3。對s2和s3進(jìn)行交叉操作，隨機(jī)選擇一個(gè)交叉點(diǎn)，例如第5位與第6位之間的位置，交叉后產(chǎn)生新的子個(gè)體：s

2=<00000

00000111111000101>s

3=<11100

0111000000010000>這兩個(gè)子個(gè)體的適應(yīng)值分別為：f(s

2)=f(－0.998113)=1.940865f(s

3)=f(1.666028)=3.459245交叉后個(gè)體s

3的適應(yīng)值比其父個(gè)體的適應(yīng)值高。下面考察變異操作。假設(shè)已經(jīng)以一小概率選擇了s3的第5個(gè)遺傳因子（即第5位）變異，遺傳因子由原來的0變成1，產(chǎn)生新的個(gè)體為s

3=<1110100000111111000101>計(jì)算該個(gè)體的適應(yīng)值：f(s

3)=f(1.721638)=0.917743，發(fā)現(xiàn)個(gè)體的適應(yīng)值比其父個(gè)體的適應(yīng)值減少了，但是如果選擇第10個(gè)遺傳因子變異，產(chǎn)生的新個(gè)體為s"3=<1110000001111111000101>f(s"3)=f(1.630818)=3.343555顯然，這個(gè)個(gè)體的適應(yīng)值比其父個(gè)體的適應(yīng)值提高了。這說明變異操作有“擾動(dòng)”作用。（5）模擬結(jié)果設(shè)定種群大小為50