2023學(xué)年完整公開課版遺傳算法

——遺傳算法快遞分撥中心運(yùn)營實(shí)務(wù)工作單位：淄博職業(yè)學(xué)院主講：孫海雷

內(nèi)容講解一、

歸納總結(jié)二、目錄一、基本概念

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

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

內(nèi)容講解

1.個體與種群

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

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

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

內(nèi)容講解3.染色體與基因

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

9----

1001

（2，5，6）----010101110內(nèi)容講解二、基本遺傳算法流程內(nèi)容講解

遺傳算法基本流程框圖生成初始種群計算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束內(nèi)容講解算法中的一些控制參數(shù)：

■

種群規(guī)模

■

最大換代數(shù)

■

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

■

變異率(mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.1。三、基本遺傳算法步驟

步1在搜索空間U上定義一個適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；步2隨機(jī)產(chǎn)生U中的N個個體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計數(shù)器t=1；步3計算S中每個個體的適應(yīng)度f()；步4若終止條件滿足，則取S中適應(yīng)度最大的個體作為所求結(jié)果，算法結(jié)束。內(nèi)容講解內(nèi)容講解步5按選擇概率P(xi)所決定的選中機(jī)會，每次從S中隨機(jī)選定1個個體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個染色體組成群體S1；步6按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個染色體，配對進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；步7按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；步8將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；四、遺傳算法的特點(diǎn)與優(yōu)勢

內(nèi)容講解◆遺傳算法的主要特點(diǎn)

——遺傳算法一般是直接在解空間搜索,而不像圖搜索那樣一般是在問題空間搜索,最后才找到解。

——遺傳算法的搜索隨機(jī)地始于搜索空間的一個點(diǎn)集,而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點(diǎn)或終止節(jié)點(diǎn),所以遺傳算法是一種隨機(jī)搜索算法。

——遺傳算法總是在尋找優(yōu)解,而不像圖搜索那樣并非總是要求優(yōu)解,而一般是設(shè)法盡快找到解,所以遺傳算法又是一種優(yōu)化搜索算法。

——遺傳算法的搜索過程是從空間的一個點(diǎn)集(種群)到另一個點(diǎn)集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個點(diǎn)到另一個點(diǎn)地搜索。因而它實(shí)際是一種并行搜索,適合大規(guī)模并行計算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。（四）遺傳算法的特點(diǎn)與優(yōu)勢

內(nèi)容講解（四）遺傳算法的特點(diǎn)與優(yōu)勢

內(nèi)容講解——遺傳算法的適應(yīng)性強(qiáng),除需知適應(yīng)度函數(shù)外,幾乎不需要其他的先驗(yàn)知識?！z傳算法長于全局搜索,它不受搜索空間的限制性假設(shè)的約束,不要求連續(xù)性