遺傳算法及其應(yīng)用

關(guān)于遺傳算法及其應(yīng)用第1頁，共89頁，2022年，5月20日，10點54分，星期六9.1遺傳算法的產(chǎn)生與發(fā)展

遺傳算法（geneticalgorithms，GA）：一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法,非常適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性優(yōu)化問題。遺傳算法可廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計和人工生命等領(lǐng)域。第2頁，共89頁，2022年，5月20日，10點54分，星期六9.1遺傳算法的產(chǎn)生與發(fā)展9.1.1遺傳算法的生物背景9.1.2遺產(chǎn)算法的基本思想9.1.3遺產(chǎn)算法的發(fā)展歷史9.1.4設(shè)計遺產(chǎn)算法的基本原則與內(nèi)容第3頁，共89頁，2022年，5月20日，10點54分，星期六

遺傳算法的生物學(xué)背景適者生存：最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群體。

生物進(jìn)化的基本過程：染色體(chromosome)：生物的遺傳物質(zhì)的主要載體?；?gene)：擴(kuò)展生物性狀的遺傳物質(zhì)的功能單元和結(jié)構(gòu)單位?；蜃╨ocus）：染色體中基因的位置。等位基因（alleles）：基因所取的值。第4頁，共89頁，2022年，5月20日，10點54分，星期六遺傳算法的基本思想生物遺傳概念遺產(chǎn)算法中的應(yīng)用適者生存目標(biāo)值比較大的解被選擇的可能性大個體（Individual）解染色體（Chromosome）解的編碼（字符串、向量等）基因（Gene）解中每一分量的特征適應(yīng)性（Fitness）適應(yīng)函數(shù)值群體（Population）根據(jù)適應(yīng)函數(shù)值選定的一組解（解的個數(shù)為群體的規(guī)模）婚配（Marry）交叉（Crossover）選擇兩個染色體進(jìn)行交叉產(chǎn)生一組新的染色體的過程變異（Mutation）編碼的某一分量發(fā)生變化的過程第5頁，共89頁，2022年，5月20日，10點54分，星期六9.1.2遺傳算法的基本思想

遺傳算法的基本思想：在求解問題時從多個解開始，然后通過一定的法則進(jìn)行逐步迭代以產(chǎn)生新的解。第6頁，共89頁，2022年，5月20日，10點54分，星期六9.1.4設(shè)計遺傳算法的基本原則與內(nèi)容

設(shè)計的基本原則：

適用性：算法所能適用的問題種類。可靠性：算法對于所設(shè)計的問題，以適當(dāng)?shù)木惹蠼馄渲写蠖鄶?shù)問題的能力。收斂性：算法能否收斂到全局最優(yōu)。穩(wěn)定性：算法對其控制參數(shù)及問題數(shù)據(jù)的敏感度。生物類比：通過類比的方法引入在生物界被認(rèn)為是有效的方法及操作。

第7頁，共89頁，2022年，5月20日，10點54分，星期六設(shè)計的基本內(nèi)容：

9.1.4設(shè)計遺傳算法的基本原則與內(nèi)容

編碼方案：編碼表示方式。適應(yīng)度函數(shù)：目標(biāo)函數(shù)。選擇策略：優(yōu)勝劣汰?？刂茀?shù)：種群的規(guī)模、算法執(zhí)行的最大代數(shù)、執(zhí)行不同遺傳操作的概率等。遺傳算子：選擇(selection)；交叉(crossover)；變異(mutation)。算法的終止準(zhǔn)則：規(guī)定一個最大的演化代數(shù)，或算法在連續(xù)多少代以后解的適應(yīng)值沒有改進(jìn)。第8頁，共89頁，2022年，5月20日，10點54分，星期六第9章遺傳算法及其應(yīng)用9.1遺傳算法的產(chǎn)生與發(fā)展9.2遺傳算法的基本算法

9.3遺傳算法的改進(jìn)算法9.4基于遺傳算法的生產(chǎn)調(diào)度方法第9頁，共89頁，2022年，5月20日，10點54分，星期六9.2遺傳算法的基本算法遺傳算法的五個基本要素：參數(shù)編碼初始群體的設(shè)定適應(yīng)度函數(shù)的設(shè)計遺傳操作設(shè)計控制參數(shù)設(shè)定第10頁，共89頁，2022年，5月20日，10點54分，星期六9.2遺傳算法的基本算法9.2.1編碼9.2.2群體設(shè)定9.2.3適應(yīng)度函數(shù)9.2.4選擇9.2.5交叉9.2.6變異9.2.7遺傳算法的一般步驟第11頁，共89頁，2022年，5月20日，10點54分，星期六9.2.1編碼

位串編碼一維染色體編碼方法：將問題空間的參數(shù)編碼為一維排列的染色體的方法。二進(jìn)制編碼：用若干二進(jìn)制數(shù)表示一個個體，將原問題的解空間映射到位串空間B={0，1}上，然后在位串空間上進(jìn)行遺傳操作。

（1）二進(jìn)制編碼第12頁，共89頁，2022年，5月20日，10點54分，星期六9.2.1編碼

(1)二進(jìn)制編碼（續(xù)）優(yōu)點：類似于生物染色體的組成，算法易于用生物遺傳理論解釋，遺傳操作如交叉、變異等易實現(xiàn)；算法處理的模式數(shù)最多。缺點：①相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離，降低了遺傳算子的搜索效率。

15：01111

16：10000②要先給出求解的精度。③求解高維優(yōu)化問題的二進(jìn)制編碼串長，算法的搜索效率低。第13頁，共89頁，2022年，5月20日，10點54分，星期六9.2.1編碼

位串編碼（2）Gray編碼Gray編碼:將二進(jìn)制編碼通過一個變換進(jìn)行轉(zhuǎn)換得到的編碼。二進(jìn)制串

Gray

二進(jìn)制編碼Gray編碼Gray編碼二進(jìn)制編碼第14頁，共89頁，2022年，5月20日，10點54分，星期六9.2.1編碼

2.實數(shù)編碼

采用實數(shù)表達(dá)法不必進(jìn)行數(shù)制轉(zhuǎn)換，可直接在解的表現(xiàn)型上進(jìn)行遺傳操作。

多參數(shù)映射編碼的基本思想：把每個參數(shù)先進(jìn)行二進(jìn)制編碼得到子串，再把這些子串連成一個完整的染色體。多參數(shù)映射編碼中的每個子串對應(yīng)各自的編碼參數(shù)，所以，可以有不同的串長度和參數(shù)的取值范圍。

第15頁，共89頁，2022年，5月20日，10點54分，星期六9.2.1編碼

3.有序串編碼

有序問題：目標(biāo)函數(shù)的值不僅與表示解的字符串的值有關(guān)，而且與其所在字符串的位置有關(guān)。4．結(jié)構(gòu)式編碼

Goldberg等提出MessyGA(mGA)的遺傳算法編碼方法。第16頁，共89頁，2022年，5月20日，10點54分，星期六初始種群的產(chǎn)生9.2.2群體設(shè)定

（1）根據(jù)問題固有知識，把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。（2）隨機(jī)產(chǎn)生一定數(shù)目的個體，從中挑選最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。

第17頁，共89頁，2022年，5月20日，10點54分，星期六2.種群規(guī)模的確定9.2.2群體設(shè)定

模式定理表明：若群體規(guī)模為M，則遺傳操作可從這M個個體中生成和檢測個模式，并在此基礎(chǔ)上能夠不斷形成和優(yōu)化積木塊，直到找到最優(yōu)解。

群體規(guī)模太小，遺傳算法的優(yōu)化性能不太好，易陷入局部最優(yōu)解。群體規(guī)模太大，計算復(fù)雜。第18頁，共89頁，2022年，5月20日，10點54分，星期六將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法

9.2.3適應(yīng)度函數(shù)

若目標(biāo)函數(shù)為最大化問題，則若目標(biāo)函數(shù)為最小化問題，則將目標(biāo)函數(shù)轉(zhuǎn)換為求最大值的形式,且保證函數(shù)值非負(fù)！

若目標(biāo)函數(shù)為最大化問題，則若目標(biāo)函數(shù)為最小化問題，則第19頁，共89頁，2022年，5月20日，10點54分，星期六將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法(續(xù)）

9.2.3適應(yīng)度函數(shù)

存在界限值預(yù)選估計困難或者不能精確估計的問題！

若目標(biāo)函數(shù)為最大化問題，則若目標(biāo)函數(shù)為最小化問題，則：目標(biāo)函數(shù)界限的保守估計值。第20頁，共89頁，2022年，5月20日，10點54分，星期六適應(yīng)度函數(shù)的尺度變換

在遺傳算法中，將所有妨礙適應(yīng)度值高的個體產(chǎn)生，從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題（deceptiveproblem）。

9.2.3適應(yīng)度函數(shù)

過早收斂：縮小這些個體的適應(yīng)度，以降低這些超級個體的競爭力。

停滯現(xiàn)象：改變原始適應(yīng)值的比例關(guān)系，以提高個體之間的競爭力。

適應(yīng)度函數(shù)的尺度變換（fitnessscaling）或者定標(biāo)：對適應(yīng)度函數(shù)值域的某種映射變換。第21頁，共89頁，2022年，5月20日，10點54分，星期六適應(yīng)度函數(shù)的尺度變換(續(xù)）

（1）線性變換：9.2.3適應(yīng)度函數(shù)

滿足滿足最小適應(yīng)度值非負(fù)第22頁，共89頁，2022年，5月20日，10點54分，星期六適應(yīng)度函數(shù)的尺度變換(續(xù)）

（2）冪函數(shù)變換法：

9.2.3適應(yīng)度函數(shù)

（3）指數(shù)變換法：第23頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

個體選擇概率分配方法選擇操作也稱為復(fù)制（reproduction）操作：從當(dāng)前群體中按照一定概率選出優(yōu)良的個體，使它們有機(jī)會作為父代繁殖下一代子孫。判斷個體優(yōu)良與否的準(zhǔn)則是各個個體的適應(yīng)度值：個體適應(yīng)度越高，其被選擇的機(jī)會就越多。

第24頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

個體選擇概率分配方法（1）適應(yīng)度比例方法（fitnessproportionalmodel）或蒙特卡羅法（MonteCarlo）

各個個體被選擇的概率和其適應(yīng)度值成比例。

個體被選擇的概率為：

第25頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

1.個體選擇概率分配方法（2）排序方法（rank-basedmodel）①線性排序：J.E.Baker

群體成員按適應(yīng)值大小從好到壞依次排列：個體按轉(zhuǎn)盤式選擇的方式選擇父體第26頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

1.個體選擇概率分配方法（2）排序方法（rank-basedmodel）②非線性排序：Z.Michalewicz

將群體成員按適應(yīng)值從好到壞依次排列，并按下式分配選擇概率：第27頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

1.個體選擇概率分配方法（2）排序方法（rank-basedmodel）

可用其他非線性函數(shù)來分配選擇概率，只要滿足以下條件：

第28頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

2.選擇個體方法（1）轉(zhuǎn)盤賭選擇（roulettewheelselection）

按個體的選擇概率產(chǎn)生一個輪盤，輪盤每個區(qū)的角度與個體的選擇概率成比例。產(chǎn)生一個隨機(jī)數(shù)，它落入轉(zhuǎn)盤的哪個區(qū)域就選擇相應(yīng)的個體交叉。第1輪產(chǎn)生一個隨機(jī)數(shù)：0.81

第2輪產(chǎn)生一個隨機(jī)數(shù)：0.32

第29頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

2.選擇個體方法（2）錦標(biāo)賽選擇方法（tournamentselectionmodel）

錦標(biāo)賽選擇方法：從群體中隨機(jī)選擇個個體，將其中適應(yīng)度最高的個體保存到下一代。這一過程反復(fù)執(zhí)行，直到保存到下一代的個體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)量為止。

隨機(jī)競爭方法（stochastictournament）：每次按賭輪選擇方法選取一對個體，然后讓這兩個個體進(jìn)行競爭，適應(yīng)度高者獲勝。如此反復(fù)，直到選滿為止。

第30頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

2.選擇個體方法（3）和選擇

從規(guī)模為的群體中隨機(jī)選取個體通過重組和變異生成個后代，再選取個最優(yōu)的后代作為新一代種群。

從個后代與其父體共中選取個最優(yōu)的后代。第31頁，共89頁，2022年，5月20日，10點54分，星期六9.2.4選擇

2.選擇個體方法（4）Boltzmann錦標(biāo)賽選擇

最佳個體（elitistmodel）保存方法：把群體中適應(yīng)度最高的個體不進(jìn)行交叉而直接復(fù)制到下一代中，保證遺傳算法終止時得到的最后結(jié)果一定是歷代出現(xiàn)過的最高適應(yīng)度的個體。（5）最佳個體保存方法

隨機(jī)選取兩個個體，若則選擇適應(yīng)值好的作為勝者，否則計算概率，若，選擇差解，否則選擇好解。第32頁，共89頁，2022年，5月20日，10點54分，星期六9.2.5交叉

1.基本的交叉算子（1）一點交叉（single-pointcrossover）

一點交叉：在個體串中隨機(jī)設(shè)定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個新的個體。

二點交叉：隨機(jī)設(shè)置兩個交叉點，將兩個交叉點之間的碼串相互交換。（2）二點交叉（two-pointcrossover）第33頁，共89頁，2022年，5月20日，10點54分，星期六9.2.5交叉

基本的交叉算子（續(xù)）

均勻交叉：按照均勻概率抽取一些位，每一位是否被選取都是隨機(jī)的，并且獨立于其他位。然后將兩個個體被抽取位互換組成兩個新個體。（3）均勻交叉（uniformcrossover）或一致交叉第34頁，共89頁，2022年，5月20日，10點54分，星期六9.2.5交叉

2.修正的交叉方法（1）部分匹配交叉PMX：GoldbergD.E.和R.Lingle(1985)

第35頁，共89頁，2022年，5月20日，10點54分，星期六9.2.5交叉

2.修正的交叉方法(續(xù)）（2）順序交叉OX：DavisL.(1985)

（3）循環(huán)交叉CX：SmithD.(1985)

第36頁，共89頁，2022年，5月20日，10點54分，星期六9.2.5交叉

3.實數(shù)編碼的交叉方法（1）離散交叉（discretecrossover）

部分離散交叉：在父解向量中選擇一部分分量，然后交換這些分量?！?/p>

二進(jìn)制的點式交叉

整體離散交叉：以0.5的概率交換父體的所有分量?！M(jìn)制編碼的均勻性交叉

21ss與第37頁，共89頁，2022年，5月20日，10點54分，星期六9.2.5交叉

3.實數(shù)編碼的交叉方法（續(xù)）（2）算術(shù)交叉（arithmeticalcrossover）

部分算術(shù)：先在父解向量中選擇一部分分量，如第個分量以后的所有分量，然后生成個[0，1]區(qū)間的隨機(jī)數(shù)，并將兩個后代定義為：第38頁，共89頁，2022年，5月20日，10點54分，星期六9.2.5交叉

3.實數(shù)編碼的交叉方法（續(xù)）（2）算術(shù)交叉（arithmeticalcrossover）

整體算術(shù)交叉：先生成n個區(qū)間的隨機(jī)數(shù)，則后代分別定義為：第39頁，共89頁，2022年，5月20日，10點54分，星期六9.2.6變異

1.整數(shù)編碼的變異方法（1）位點變異：群體中的個體碼串，隨機(jī)挑選一個或多個基因座，并對這些基因座的基因值以變異概率作變動。（2）逆轉(zhuǎn)變異：在個體碼串中隨機(jī)選擇兩點（逆轉(zhuǎn)點），然后將兩點之間的基因值以逆向排序插入到原位置中。

（3）插入變異：在個體碼串中隨機(jī)選擇一個碼，然后將此碼插入隨機(jī)選擇的插入點中間。第40頁，共89頁，2022年，5月20日，10點54分，星期六9.2.6變異

1.整數(shù)編碼的變異方法（續(xù)）（4）互換變異：隨機(jī)選取染色體的兩個基因進(jìn)行簡單互換。（5）移動變異：隨機(jī)選取一個基因，向左或者向右移動一個隨機(jī)位數(shù)。（6）自適應(yīng)變異：類似于位點變異，但變異概率隨群體中個體的多樣性程度而自適應(yīng)調(diào)整。第41頁，共89頁，2022年，5月20日，10點54分，星期六9.2.6變異

2.實數(shù)編碼的變異方法（1）均勻性變異

均勻性變異：在父解向量中隨機(jī)地選擇一個分量（第個），然后在中以均勻概率隨機(jī)選擇代替以得到，即第42頁，共89頁，2022年，5月20日，10點54分，星期六9.2.6變異

2.實數(shù)編碼的變異方法（續(xù)）（2）正態(tài)性變異（normaldistributedmutation）

第43頁，共89頁，2022年，5月20日，10點54分，星期六9.2.6變異

2.實數(shù)編碼的變異方法（續(xù)）（3）非一致性變異Z.Michalewicz首先提出將變異算子的結(jié)果與演化代數(shù)聯(lián)系起來。在演化初期，變異范圍相對較大，而隨著演化的推進(jìn)，變異范圍越來越小，起著一種對演化系統(tǒng)的微調(diào)作用。第44頁，共89頁，2022年，5月20日，10點54分，星期六9.2.6變異

2.實數(shù)編碼的變異方法（續(xù)）（3）非一致性變異第45頁，共89頁，2022年，5月20日，10點54分，星期六9.2.6變異

2.實數(shù)編碼的變異方法（續(xù)）（4）自適應(yīng)變異

自適應(yīng)變異方式與非一致性變異算子相同，只是將其中的演化代數(shù)改為，函數(shù)表達(dá)式變?yōu)椋?/p>

第46頁，共89頁，2022年，5月20日，10點54分，星期六9.2.7遺傳算法的一般步驟第47頁，共89頁，2022年，5月20日，10點54分，星期六48第48頁，共89頁，2022年，5月20日，10點54分，星期六9.2.7遺傳算法的一般步驟（1）使用隨機(jī)方法或者其它方法，產(chǎn)生一個有N個染色體的初始群體pop(1)，；

（2）對群體中的每一個染色體popi(t)，計算其適應(yīng)值（3）若滿足停止條件，則算法停止；否則，以概率從pop(t)中隨機(jī)選擇一些染色體構(gòu)成一個新種群第49頁，共89頁，2022年，5月20日，10點54分，星期六9.2.7遺傳算法的一般步驟（4）以概率進(jìn)行交叉產(chǎn)生一些新的染色體，得到一個新的群體

（5）以一個較小的概率使染色體的一個基因發(fā)生變異，形成；，成為一個新的群體

返回（2）。

第50頁，共89頁，2022年，5月20日，10點54分，星期六9.2.8遺傳算法的特點

可直接對結(jié)構(gòu)對象進(jìn)行操作。利用隨機(jī)技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進(jìn)行高效率搜索。采用群體搜索策略，易于并行化。僅用適應(yīng)度函數(shù)值來評估個體，并在此基礎(chǔ)上進(jìn)行遺傳操作，使種群中個體之間進(jìn)行信息交換。第51頁，共89頁，2022年，5月20日，10點54分，星期六第9章遺傳算法及其應(yīng)用9.1遺傳算法的產(chǎn)生與發(fā)展9.2遺傳算法的基本算法9.3遺傳算法的改進(jìn)算法

9.4基于遺傳算法的生產(chǎn)調(diào)度方法第52頁，共89頁，2022年，5月20日，10點54分，星期六9.3遺傳算法的改進(jìn)算法

9.3.1雙倍體遺傳算法9.3.2雙種群遺傳算法9.3.3自適應(yīng)遺傳算法第53頁，共89頁，2022年，5月20日，10點54分，星期六9.3.1雙倍體遺傳算法1.基本思想雙倍體遺傳算法采用顯性和隱性兩個染色體同時進(jìn)行進(jìn)化，提供了一種記憶以前有用的基因塊的功能。雙倍體遺傳算法采用顯性遺傳。

雙倍體遺傳延長了有用基因塊的壽命，提高了算法的收斂能力，在變異概率低的情況下能保持一定水平的多樣性。第54頁，共89頁，2022年，5月20日，10點54分，星期六

9.3.1雙倍體遺傳算法2.雙倍體遺傳算法的設(shè)計（1）編碼/解碼：兩個染色體（顯性、隱性）（2）復(fù)制算子：計算顯性染色體的適應(yīng)度，按照顯性染色體的復(fù)制概率將個體復(fù)制到下一代群體中。（3）交叉算子：兩個個體的顯性染色體交叉、隱性染色體也同時交叉。（4）變異算子：個體的顯性染色體按正常的變異概率變異；隱性染色體按較大的變異概率變異。（5）雙倍體遺傳算法顯隱性重排算子：個體中適應(yīng)值較大的染色體設(shè)為顯性染色體，適應(yīng)值較小的染色體設(shè)為隱性染色體。第55頁，共89頁，2022年，5月20日，10點54分，星期六

雙種群遺傳算法程序流程圖

第56頁，共89頁，2022年，5月20日，10點54分，星期六9.3.2雙種群遺傳算法

基本思想在遺傳算法中使用多種群同時進(jìn)化，并交換種群之間優(yōu)秀個體所攜帶的遺傳信息，以打破種群內(nèi)的平衡態(tài)達(dá)到更高的平衡態(tài)，有利于算法跳出局部最優(yōu)。

多種群遺傳算法：建立兩個遺傳算法群體，分別獨立地運行復(fù)制、交叉、變異操作，同時當(dāng)每一代運行結(jié)束以后，選擇兩個種群中的隨機(jī)個體及最優(yōu)個體分別交換。第57頁，共89頁，2022年，5月20日，10點54分，星期六9.3.2雙種群遺傳算法2.雙種群遺傳算法的設(shè)計（1）編碼/解碼設(shè)計（2）交叉算子、變異算子（3）雜交算子設(shè)種群A與種群B，當(dāng)A與B種群都完成了選擇、交叉、變異算子后，產(chǎn)生一個隨機(jī)數(shù)num，隨機(jī)選擇A中num個個體與A中最優(yōu)個體，隨機(jī)選擇B中num個個體與B中最優(yōu)個體，交換兩者，以打破平衡態(tài)。第58頁，共89頁，2022年，5月20日，10點54分，星期六

雙種群遺傳算法程序流程圖第59頁，共89頁，2022年，5月20日，10點54分，星期六9.3.3自適應(yīng)遺傳算法

1.基本思想SrinvivasM.，PatnaikL.M.等在1994年提出一種自適應(yīng)遺傳算法(adaptivegeneticalgorithms，AGA)：能隨適應(yīng)度自動改變。AGA：當(dāng)種群各個體適應(yīng)度趨于一致或者趨于局部最優(yōu)時，使增加，以跳出局部最優(yōu)；而當(dāng)群體適應(yīng)度比較分散時，使減少，以利于優(yōu)良個體的生存。

同時，對于適應(yīng)度高于群體平均適應(yīng)值的個體，選擇較低的，使得該解得以保護(hù)進(jìn)入下一代；對低于平均適應(yīng)值的個體，選擇較高的值，使該解被淘汰。第60頁，共89頁，2022年，5月20日，10點54分，星期六9.3.3自適應(yīng)遺傳算法

2.自適應(yīng)遺傳算法的步驟（1）編碼/解碼設(shè)計。（2）初始種群產(chǎn)生：N（N是偶數(shù)）個候選解，組成初始解集。（3）定義適應(yīng)度函數(shù)為，計算適應(yīng)度。（4）按輪盤賭規(guī)則選擇N個個體，計算。（5）將群體中的各個個體隨機(jī)搭配成對，共組成N/2對，對每一對個體，按照自適應(yīng)公式計算自適應(yīng)交叉概率，隨機(jī)產(chǎn)生R(0,1)，如果則對該對染色體進(jìn)行交叉操作。第61頁，共89頁，2022年，5月20日，10點54分，星期六2.自適應(yīng)遺傳算法的步驟（續(xù)）（6）對于群體中的所有個體，共N個，按照自適應(yīng)變異公式計算自適應(yīng)變異概率，隨機(jī)產(chǎn)生R(0,1)，如果則對該染色體進(jìn)行交叉操作。（7）計算由交叉和變異生成新個體的適應(yīng)度，新個體與父代一起構(gòu)成新群體。（8）判斷是否達(dá)到預(yù)定的迭代次數(shù)，是則結(jié)束；否則轉(zhuǎn)（4）。

9.3.3自適應(yīng)遺傳算法

第62頁，共89頁，2022年，5月20日，10點54分，星期六3.適應(yīng)的交叉概率與變異概率9.3.3自適應(yīng)遺傳算法

普通自適應(yīng)算法中，當(dāng)個體適應(yīng)度值越接近最大適應(yīng)度值時，交叉概率與變異概率就越?。划?dāng)?shù)扔谧畲筮m應(yīng)度值時，交叉概率和變異概率為零。

改進(jìn)的思想：當(dāng)前代的最優(yōu)個體不被破壞，仍然保留（最優(yōu)保存策略）；但較優(yōu)個體要對應(yīng)于更高的交叉概率與變異概率。第63頁，共89頁，2022年，5月20日，10點54分，星期六

F－自適應(yīng)方法：9.3.3自適應(yīng)遺傳算法

3.自適應(yīng)的交叉概率與變異概率（續(xù)）第64頁，共89頁，2022年，5月20日，10點54分，星期六9.3.3自適應(yīng)遺傳算法

S－自適應(yīng)方法：自適應(yīng)的交叉概率與變異概率（續(xù)）第65頁，共89頁，2022年，5月20日，10點54分，星期六9.3.3自適應(yīng)遺傳算法

自適應(yīng)的交叉概率與變異概率（續(xù)）

C

－自適應(yīng)方法：

第66頁，共89頁，2022年，5月20日，10點54分，星期六第9章遺傳算法及其應(yīng)用9.1遺傳算法的產(chǎn)生與發(fā)展9.2遺傳算法的基本算法9.3遺傳算法的改進(jìn)算法9.4基于遺傳算法的生產(chǎn)調(diào)度方法第67頁，共89頁，2022年，5月20日，10點54分，星期六9.4基于遺傳算法的生產(chǎn)調(diào)度方法

9.4.1基于遺傳算法的流水車間調(diào)度方法9.4.2基于遺傳算法的混合流水車間調(diào)度方法第68頁，共89頁，2022年，5月20日，10點54分，星期六1.流水車間調(diào)度問題

問題描述：n個工件要在m臺機(jī)器上加工，每個工件需要經(jīng)過m道工序，每道工序要求不同的機(jī)器，n個工件在m臺機(jī)器上的加工順序相同。工件在機(jī)器上的加工時間是給定的，設(shè)為

問題的目標(biāo)：確定n個工件在每臺機(jī)器上的最優(yōu)加工順序，使最大流程時間達(dá)到最小。9.4.1基于遺傳算法的流水車間調(diào)度方法第69頁，共89頁，2022年，5月20日，10點54分，星期六1.流水車間調(diào)度問題

假設(shè)：

(1)

每個工件在機(jī)器上的加工順序是給定的。

(2)

每臺機(jī)器同時只能加工一個工件。

(3)

一個工件不能同時在不同的機(jī)器上加工。

(4)

工序不能預(yù)定。

(5)

工序的準(zhǔn)備時間與順序無關(guān)，且包含在加工時間中。

(6)工件在每臺機(jī)器上的加工順序相同，且是確定的。

9.4.1基于遺傳算法的流水車間調(diào)度方法第70頁，共89頁，2022年，5月20日，10點54分，星期六1.流水車間調(diào)度問題9.4.1基于遺傳算法的流水車間調(diào)度方法

問題的數(shù)學(xué)模型：

個工件、臺機(jī)器的流水車間調(diào)度問題的完工時間：

第71頁，共89頁，2022年，5月20日，10點54分，星期六2.求解流水車間調(diào)度問題的遺傳算法設(shè)計

（1）FSP的編碼方法

對于FSP，最自然的編碼方式是用染色體表示工件的順序。9.4.1基于遺傳算法的流水車間調(diào)度方法對于有四個工件的FSP，第個染色體，表示工件的加工順序為：。

第72頁，共89頁，2022年，5月20日，10點54分，星期六2.求解流水車間調(diào)度問題的遺傳算法設(shè)計

（2）FSP的適應(yīng)度函數(shù)

:個染色體的最大流程時間，F(xiàn)SP的適應(yīng)度函數(shù)：

9.4.1基于遺傳算法的流水車間調(diào)度方法第73頁，共89頁，2022年，5月20日，10點54分，星期六求解FSP的遺傳算法實例

例1Ho和Chang(1991)給出的5個工件、4臺機(jī)器問題。

工件131412530219553343234227641322141353355719

加工時間表

9.4.1基于遺傳算法的流水車間調(diào)度方法第74頁，共89頁，2022年，5月20日，10點54分，星期六用遺傳算法求解。選擇交叉概率，變異概,種群規(guī)模為20，迭代次數(shù)。

表9.3遺傳算法運行的結(jié)果

總運行次數(shù)最好解最壞解平均最好解的頻率最好解的平均代數(shù)20213221213.950.85129.4.1基于遺傳算法的流水車間調(diào)度方法用窮舉法求得最優(yōu)解：4-2-5-1-3，加工時間：213；最劣解：1-4-2-3-5，加工時間：294；平均解的加工時間：265。

遺傳算法運行的結(jié)果第75頁，共89頁，2022年，5月20日，10點54分，星期六表9.3遺傳算法運行的結(jié)果

最優(yōu)解收斂圖

9.4.1基于遺傳算法的流水車間調(diào)度方法第76頁，共89頁，2022年，5月20日，10點54分，星期六平均值收斂圖

9.4.1基于遺傳算法的流水車間調(diào)度方法第77頁，共89頁，2022年，5月20日，10點54分，星期六機(jī)器甘特圖

9.4.1基于遺傳算法的流水車間調(diào)度方法第78頁，共89頁，2022年，5月20日，10點54分，星期六9.4.2基于遺傳算法的混合流水車間調(diào)度方法1.混合流水車間調(diào)度問題

問題的特征：在某些工序上存在并行機(jī)器。

問題的描述：需要加工多個工件，所有工件的加工路線都相同，都需要依次通過幾道工序，在所有工序中至少有一個工序存在著多臺并行機(jī)器。

需要解決的問題：確定并行機(jī)器的分配情況以及同一臺機(jī)器上工件的加工排序。

目標(biāo)：最小化最大流程時間。第79頁，共89頁，2022年，5月20日，10點54分，星期六

假設(shè)加工個工件，每個工件都要依次經(jīng)過個加工工序，每個工序的并行機(jī)器數(shù)為，。所有工序中至少有一個工序存在并行機(jī)，即至少有一個大于1。9.4.2基于遺傳算法的混合流水車間調(diào)度方法2.混合流水車間調(diào)度問題的遺傳算法編碼方法

HFSP的編碼矩陣

：上的一個實數(shù)，表示工件的第個工序在第臺并行機(jī)上加工。：多個工件在同一臺機(jī)器上加工同一個工序第80頁，共89頁，2022年，5月20日，10點54分，星期六

，按的升序來加工工件。，根據(jù)每個工件的前一個工序的完成時間來確定其加工順序，前一個工序先完成的先加工。假如完成時間相同，也按的升序來加工。

9.4.2基于遺傳算法的混合流水車間調(diào)度方法染色體的長度：。

染色體：第81頁，共89頁，2022年，5月20日，10點54分，星期六例如，對于有3個工件、3道工序、各工序的并行機(jī)器數(shù)分別為3，2，2的混合流水車間調(diào)度問題。

9.4.2基于遺傳算法的混合流水車間調(diào)度方法

染色體：[2.1，2.4，1.9，0，1.6，2.1，2.3，0，1.1，2.4，1.2]

編碼矩陣：

混合流水車間調(diào)度的機(jī)器編號第82頁，共89頁，2022年，5月20日，10點54分，星期六3.基于遺傳算法的求解方法9.4.2基于遺傳算法