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

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

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

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

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

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

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

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

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

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

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

9.3遺傳算法的改進(jìn)算法9.4基于遺傳算法的生產(chǎn)調(diào)度方法第9頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2遺傳算法的基本算法遺傳算法的五個(gè)基本要素：參數(shù)編碼初始群體的設(shè)定適應(yīng)度函數(shù)的設(shè)計(jì)遺傳操作設(shè)計(jì)控制參數(shù)設(shè)定第10頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.1編碼

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

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

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

15：01111

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

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

Gray

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

2.實(shí)數(shù)編碼

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

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

第15頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.1編碼

3.有序串編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

過(guò)早收斂：縮小這些個(gè)體的適應(yīng)度，以降低這些超級(jí)個(gè)體的競(jìng)爭(zhēng)力。

停滯現(xiàn)象：改變?cè)歼m應(yīng)值的比例關(guān)系，以提高個(gè)體之間的競(jìng)爭(zhēng)力。

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

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

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

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

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

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

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

第24頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.4選擇

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

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

個(gè)體被選擇的概率為：

第25頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.4選擇

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

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

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

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

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

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

第28頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.4選擇

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

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

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

第29頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.4選擇

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

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

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

第30頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.4選擇

2.選擇個(gè)體方法（3）和選擇

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

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

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

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

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

1.基本的交叉算子（1）一點(diǎn)交叉（single-pointcrossover）

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

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

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

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

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

第35頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.5交叉

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

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

第36頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.5交叉

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

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

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

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

21ss與第37頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.5交叉

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

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

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

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

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

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

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

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

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

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

第43頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.6變異

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

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

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

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

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

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

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

返回（2）。

第50頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.2.8遺傳算法的特點(diǎn)

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

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

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

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

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

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

第56頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六9.3.2雙種群遺傳算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C

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

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

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

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

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

假設(shè)：

(1)

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

(2)

每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。

(3)

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

(4)

工序不能預(yù)定。

(5)

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

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

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

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

個(gè)工件、臺(tái)機(jī)器的流水車間調(diào)度問(wèn)題的完工時(shí)間：

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

（1）FSP的編碼方法

對(duì)于FSP，最自然的編碼方式是用染色體表示工件的順序。9.4.1基于遺傳算法的流水車間調(diào)度方法對(duì)于有四個(gè)工件的FSP，第個(gè)染色體，表示工件的加工順序?yàn)椋骸?/p>

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

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

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

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

例1Ho和Chang(1991)給出的5個(gè)工件、4臺(tái)機(jī)器問(wèn)題。

工件131412530219553343234227641322141353355719

加工時(shí)間表

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

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

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

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

最優(yōu)解收斂圖

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

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

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

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

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

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

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

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

HFSP的編碼矩陣

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

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

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

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

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ī)器編號(hào)第82頁(yè)，共89頁(yè)，2022年，5月20日，10點(diǎn)54分，星期六3.基于遺傳算法的求解方法9.4.2基于遺傳算法