第9章-遺傳算法及其應(yīng)用.ppt

1、第 9 章 遺傳算法及其應(yīng)用,教材： 王萬(wàn)良人工智能及其應(yīng)用（第2版） 高等教育出版社，2008. 6,2,第9章 遺傳算法及其應(yīng)用,9.1 遺傳算法的產(chǎn)生與發(fā)展 9.2 遺傳算法的基本算法 9.3 遺傳算法的改進(jìn)算法 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法,3,第9章 遺傳算法及其應(yīng)用,9.1 遺傳算法的產(chǎn)生與發(fā)展 9.2 遺傳算法的基本算法 9.3 遺傳算法的改進(jìn)算法 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法,4,9.1 遺傳算法的產(chǎn)生與發(fā)展,遺傳算法（genetic algorithms，GA）：一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法,非常適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性優(yōu)

2、化問(wèn)題。 遺傳算法可廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。,5,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)容,6,9.1.1 遺傳算法的生物學(xué)背景,適者生存：最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群體。 生物進(jìn)化的基本過(guò)程：,染色體(chromosome)：生物的遺傳物質(zhì)的主要載體。 基因(gene)：擴(kuò)展生物性狀的遺傳物質(zhì)的功能單元和結(jié)構(gòu)單位。 基因座（locus）：染色體中基因的位置。 等位基因（alleles）：基因所取的值。,7,9.

3、1.2 遺傳算法的基本思想,8,9.1.2 遺傳算法的基本思想,遺傳算法的基本思想： 在求解問(wèn)題時(shí)從多個(gè)解開(kāi)始，然后通過(guò)一定的法則進(jìn)行逐步迭代以產(chǎn)生新的解。,9,9.1.3 遺傳算法的發(fā)展歷史,1962年，F(xiàn)raser提出了自然遺傳算法。 1965年，Holland首次提出了人工遺傳操作的重要性。 1967年，Bagley首次提出了遺傳算法這一術(shù)語(yǔ)。 1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別中。 1971年，Hollstien在論文計(jì)算機(jī)控制系統(tǒng)中人工遺傳自適應(yīng)方法中闡述了遺傳算法用于數(shù)字反饋控制的方法。 1975年，美國(guó)J. Holland出版了自然系統(tǒng)和人工系統(tǒng)的適配；DeJ

4、ong完成了重要論文遺傳自適應(yīng)系統(tǒng)的行為分析。 20世紀(jì)80年代以后，遺傳算法進(jìn)入興盛發(fā)展時(shí)期。,10,9.1.4 設(shè)計(jì)遺傳算法的基本原則與內(nèi)容,設(shè)計(jì)的基本原則：,11,設(shè)計(jì)的基本內(nèi)容：,9.1.4 設(shè)計(jì)遺傳算法的基本原則與內(nèi)容,12,第9章 遺傳算法及其應(yīng)用,9.1 遺傳算法的產(chǎn)生與發(fā)展 9.2 遺傳算法的基本算法 9.3 遺傳算法的改進(jìn)算法 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法,13,9.2 遺傳算法的基本算法,遺傳算法的五個(gè)基本要素： 參數(shù)編碼 初始群體的設(shè)定 適應(yīng)度函數(shù)的設(shè)計(jì) 遺傳操作設(shè)計(jì) 控制參數(shù)設(shè)定,14,9.2 遺傳算法的基本算法,9.2.1 編碼 9.2.2 群體設(shè)定 9.2.3

5、 適應(yīng)度函數(shù) 9.2.4 選擇 9.2.5 交叉 9.2.6 變異 9.2.7 遺傳算法的一般步驟,15,9.2.1 編碼,位串編碼,一維染色體編碼方法：將問(wèn)題空間的參數(shù)編碼為一維排列的染色體的方法。,二進(jìn)制編碼：用若干二進(jìn)制數(shù)表示一個(gè)個(gè)體，將原問(wèn)題的解空間映射到位串空間 B=0，1上，然后在位串空間上進(jìn)行遺傳操作。,（1） 二進(jìn)制編碼,16,9.2.1 編碼,(1) 二進(jìn)制編碼（續(xù)）,優(yōu)點(diǎn)： 類似于生物染色體的組成，算法易于用生物遺傳理論解釋，遺傳操作如交叉、變異等易實(shí)現(xiàn)；算法處理的模式數(shù)最多。,缺點(diǎn)： 相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離，降低了遺傳算子的搜索效率。 15：

6、01111 16： 10000 要先給出求解的精度。 求解高維優(yōu)化問(wèn)題的二進(jìn)制編碼串長(zhǎng)，算法的搜索效率低。,17,9.2.1 編碼,位串編碼 （2） Gray 編碼,Gray編碼:將二進(jìn)制編碼通過(guò)一個(gè)變換進(jìn)行轉(zhuǎn)換得到的編碼。,18,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ù)的取值范圍。,19,9.2.1 編碼,3. 有序串編碼,有序問(wèn)題：目標(biāo)函數(shù)的值不僅與表示解的

7、字符串的值有關(guān)，而且與其所在字符串的位置有關(guān)。,4結(jié)構(gòu)式編碼,Goldberg等提出MessyGA(mGA)的遺傳算法編碼方法。,20,初始種群的產(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ī)模。,21,2. 種群規(guī)模的確定,9.2.2 群體設(shè)定,模式定理表明：若群體規(guī)模為M，則遺傳操作可從這M 個(gè)個(gè)體中生成和檢測(cè) 個(gè)模式，并在此基礎(chǔ)上能夠不斷形成和優(yōu)化積木塊，直到找到最優(yōu)解。,群體規(guī)模

8、太小，遺傳算法的優(yōu)化性能不太好，易陷入局部最優(yōu)解。 群體規(guī)模太大，計(jì)算復(fù)雜。,22,將目標(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)題，則,23,將目標(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ì)值。,24,適應(yīng)度函數(shù)的尺度變換,在遺傳算法中，將所有妨礙適應(yīng)度值高的個(gè)體產(chǎn)生，從而影響遺傳算法

9、正常工作的問(wèn)題統(tǒng)稱為欺騙問(wèn)題（deceptive problem）。,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ù)的尺度變換（fitness scaling）或者定標(biāo)：對(duì)適應(yīng)度函數(shù)值域的某種映射變換。,25,適應(yīng)度函數(shù)的尺度變換(續(xù)）,（1）線性變換：,9.2.3 適應(yīng)度函數(shù),滿足,26,適應(yīng)度函數(shù)的尺度變換(續(xù)）,（2）冪函數(shù)變換法：,9.2.3 適應(yīng)度函數(shù),（3）指數(shù)變換法：,27,9.2.4 選擇,個(gè)體選擇概率分配方法 選擇操作也稱為復(fù)制（reproduction）操作：從當(dāng)

10、前群體中按照一定概率選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代繁殖下一代子孫。 判斷個(gè)體優(yōu)良與否的準(zhǔn)則是各個(gè)個(gè)體的適應(yīng)度值：個(gè)體適應(yīng)度越高，其被選擇的機(jī)會(huì)就越多。,28,9.2.4 選擇,個(gè)體選擇概率分配方法 （1）適應(yīng)度比例方法（fitness proportional model）或蒙特卡羅法（Monte Carlo）,各個(gè)個(gè)體被選擇的概率和其適應(yīng)度值成比例。,個(gè)體 被選擇的概率為：,29,9.2.4 選擇,1. 個(gè)體選擇概率分配方法 （2） 排序方法 （rank-based model）, 線性排序：J. E. Baker,群體成員按適應(yīng)值大小從好到壞依次排列： 個(gè)體 按轉(zhuǎn)盤(pán)式選擇的方式選擇父

11、體,30,9.2.4 選擇,1. 個(gè)體選擇概率分配方法 （2） 排序方法 （rank-based model）, 非線性排序： Z. Michalewicz,將群體成員按適應(yīng)值從好到壞依次排列，并按下式分配選擇概率：,31,9.2.4 選擇,1.個(gè)體選擇概率分配方法 （2） 排序方法 （rank-based model）,可用其他非線性函數(shù)來(lái)分配選擇概率，只要滿足以下條件：,32,9.2.4 選擇,2. 選擇個(gè)體方法 （1）轉(zhuǎn)盤(pán)賭選擇（roulette wheel selection）,按個(gè)體的選擇概率產(chǎn)生一個(gè)輪盤(pán)，輪盤(pán)每個(gè)區(qū)的角度與個(gè)體的選擇概率成比例。 產(chǎn)生一個(gè)隨機(jī)數(shù)，它落入轉(zhuǎn)盤(pán)的哪個(gè)區(qū)域

12、就選擇相應(yīng)的個(gè)體交叉。,第1輪產(chǎn)生一個(gè)隨機(jī)數(shù)：0.81,第2輪產(chǎn)生一個(gè)隨機(jī)數(shù)：0.32,33,9.2.4 選擇,2. 選擇個(gè)體方法 （2）錦標(biāo)賽選擇方法（tournament selection model）,錦標(biāo)賽選擇方法：從群體中隨機(jī)選擇個(gè)個(gè)體，將其中適應(yīng)度最高的個(gè)體保存到下一代。這一過(guò)程反復(fù)執(zhí)行，直到保存到下一代的個(gè)體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)量為止。,隨機(jī)競(jìng)爭(zhēng)方法（stochastic tournament）：每次按賭輪選擇方法選取一對(duì)個(gè)體，然后讓這兩個(gè)個(gè)體進(jìn)行競(jìng)爭(zhēng)，適應(yīng)度高者獲勝。如此反復(fù)，直到選滿為止。,34,9.2.4 選擇,2. 選擇個(gè)體方法 （3） 和 選擇,從規(guī)模為 的群體中隨機(jī)選

13、取個(gè)體通過(guò)重組和變異生成 個(gè)后代， 再選取 個(gè)最優(yōu)的后代作為新一代種群。,從 個(gè)后代與其父體共 中選取 個(gè)最優(yōu)的后代。,35,9.2.4 選擇,2. 選擇個(gè)體方法 （4）Boltzmann錦標(biāo)賽選擇,最佳個(gè)體（elitist model）保存方法：把群體中適應(yīng)度最高的個(gè)體不進(jìn)行交叉而直接復(fù)制到下一代中，保證遺傳算法終止時(shí)得到的最后結(jié)果一定是歷代出現(xiàn)過(guò)的最高適應(yīng)度的個(gè)體。,（5）最佳個(gè)體保存方法,隨機(jī)選取兩個(gè)個(gè)體 ，若 則選擇適應(yīng)值好的作為勝者，否則計(jì)算概率 ，若 ，選擇差解，否則選擇好解。,36,9.2.5 交叉,1. 基本的交叉算子 （1）一點(diǎn)交叉（single-point crossove

14、r）,一點(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-point crossover）,37,9.2.5 交叉,基本的交叉算子（續(xù)）,均勻交叉：按照均勻概率抽取一些位，每一位是否被選取都是隨機(jī)的，并且獨(dú)立于其他位。然后將兩個(gè)個(gè)體被抽取位互換組成兩個(gè)新個(gè)體。,（3）均勻交叉（uniform crossover）或一致交叉,38,9.2.5 交叉,2. 修正的交叉方法 （1）部分匹配交叉PMX：Goldberg D. E.和R. Lingle(

15、1985),39,9.2.5 交叉,2. 修正的交叉方法(續(xù)） （2）順序交叉OX：Davis L. (1985),（3） 循環(huán)交叉CX：Smith D. (1985),40,9.2.5 交叉,3. 實(shí)數(shù)編碼的交叉方法 （1）離散交叉（discrete crossover）,部分離散交叉：在父解向量中選擇一部分分量，然后交換這些分量。 二進(jìn)制的點(diǎn)式交叉,整體離散交叉：以0.5的概率交換父體 的所有分量。 二進(jìn)制編碼的均勻性交叉,41,9.2.5 交叉,3. 實(shí)數(shù)編碼的交叉方法（續(xù)） （2）算術(shù)交叉（arithmetical crossover）,部分算術(shù)：先在父解向量中選擇一部分分量，如第 個(gè)

16、分量以后的所有分量，然后生成 個(gè)0，1區(qū)間的隨機(jī)數(shù)，并將兩個(gè)后代定義為：,42,9.2.5 交叉,3. 實(shí)數(shù)編碼的交叉方法（續(xù)） （2）算術(shù)交叉（arithmetical crossover）,整體算術(shù)交叉：先生成 n 個(gè)區(qū)間的隨機(jī)數(shù)，則后代分別定義為：,43,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)中間。,44,9

17、.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)整。,45,9.2.6 變異,2. 實(shí)數(shù)編碼的變異方法 （1）均勻性變異,均勻性變異：在父解向量中隨機(jī)地選擇一個(gè)分量（第 個(gè)），然后在 中以均勻概率隨機(jī)選擇 代替 以得到 ，即,46,9.2.6 變異,2. 實(shí)數(shù)編碼的變異方法（續(xù)） （2）正態(tài)性變異（normal distributed mutation）,47,9.2.6 變異,2. 實(shí)數(shù)編碼的變

18、異方法（續(xù)） （3）非一致性變異,Z. Michalewicz首先提出將變異算子的結(jié)果與演化代數(shù)聯(lián)系起來(lái)。 在演化初期，變異范圍相對(duì)較大，而隨著演化的推進(jìn)，變異范圍越來(lái)越小，起著一種對(duì)演化系統(tǒng)的微調(diào)作用。,48,9.2.6 變異,2. 實(shí)數(shù)編碼的變異方法（續(xù)） （3）非一致性變異,49,9.2.6 變異,2. 實(shí)數(shù)編碼的變異方法（續(xù)） （4）自適應(yīng)變異,自適應(yīng)變異方式與非一致性變異算子相同，只是將其中的演化代數(shù) 改為 ，函數(shù)表達(dá)式變?yōu)椋?50,9.2.7 遺傳算法的一般步驟,51,9.2.7 遺傳算法的一般步驟,（1）使用隨機(jī)方法或者其它方法，產(chǎn)生一個(gè)有N個(gè)染色體的初始群體 pop(1)， ；

19、,（3）若滿足停止條件，則算法停止；否則，以概率 從pop(t)中隨機(jī)選擇一些染色體構(gòu)成一個(gè)新種群,52,9.2.7 遺傳算法的一般步驟,（4）以概率 進(jìn)行交叉產(chǎn)生一些新的染色體，得到一個(gè)新的群體,（5）以一個(gè)較小的概率 使染色體的一個(gè)基因發(fā)生變異，形成 ； ，成為一個(gè)新的群體 返回 （2）。,53,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)行信息交換。,54,第9章 遺傳算法及其應(yīng)用,9.1 遺傳算法的產(chǎn)生與發(fā)展 9.2

20、 遺傳算法的基本算法 9.3 遺傳算法的改進(jìn)算法 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法,55,9.3 遺傳算法的改進(jìn)算法,9.3.1 雙倍體遺傳算法 9.3.2 雙種群遺傳算法 9.3.3 自適應(yīng)遺傳算法,56,9.3.1 雙倍體遺傳算法,1. 基本思想 雙倍體遺傳算法采用顯性和隱性兩個(gè)染色體同時(shí)進(jìn)行進(jìn)化，提供了一種記憶以前有用的基因塊的功能。 雙倍體遺傳算法采用顯性遺傳。,雙倍體遺傳延長(zhǎng)了有用基因塊的壽命，提高了算法的收斂能力，在變異概率低的情況下能保持一定水平的多樣性。,57,9.3.1 雙倍體遺傳算法,2. 雙倍體遺傳算法的設(shè)計(jì),（1）編碼/解碼：兩個(gè)染色體（顯性、隱性） （2）復(fù)制算子：

21、計(jì)算顯性染色體的適應(yīng)度，按照顯性染色體 的復(fù)制概率將個(gè)體復(fù)制到下一代群體中。 （3）交叉算子：兩個(gè)個(gè)體的顯性染色體交叉、隱性染色體也同時(shí)交叉。 （4）變異算子：個(gè)體的顯性染色體按正常的變異概率變異；隱性染色體按較大的變異概率變異。 （5）雙倍體遺傳算法顯隱性重排算子：個(gè)體中適應(yīng)值較大的染色體設(shè)為顯性染色體，適應(yīng)值較小的染色體設(shè)為隱性染色體。,58,雙種群遺傳算法程序流程圖,59,9.3.2 雙種群遺傳算法,基本思想 在遺傳算法中使用多種群同時(shí)進(jìn)化，并交換種群之間優(yōu)秀個(gè)體所攜帶的遺傳信息，以打破種群內(nèi)的平衡態(tài)達(dá)到更高的平衡態(tài)，有利于算法跳出局部最優(yōu)。 多種群遺傳算法：建立兩個(gè)遺傳算法群體，分別獨(dú)

22、立地運(yùn)行復(fù)制、交叉、變異操作，同時(shí)當(dāng)每一代運(yùn)行結(jié)束以后，選擇兩個(gè)種群中的隨機(jī)個(gè)體及最優(yōu)個(gè)體分別交換。,60,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)。,61,雙種群遺傳算法程序流程圖,62,9.3.3 自適應(yīng)遺傳算法,1. 基本思想,Srinvivas M.，Patnaik L. M.等在1994年提出一種自適應(yīng)遺傳算法(adapt

23、ive genetic algorithms，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è)體，選擇較高的 值，使該解被淘汰。,63,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） 按輪盤(pán)賭規(guī)則選擇N 個(gè)個(gè)體，計(jì)算 。

24、 （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)行交叉操作。,64,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)遺傳算法,65,3. 適應(yīng)的交叉概率與變異概率,9.3.3 自適應(yīng)遺傳算法,普通自適應(yīng)算法中，當(dāng)個(gè)體適應(yīng)度值

25、越接近最大適應(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)于更高的交叉概率與變異概率。,66,F自適應(yīng)方法：,9.3.3 自適應(yīng)遺傳算法,3. 自適應(yīng)的交叉概率與變異概率（續(xù)）,67,9.3.3 自適應(yīng)遺傳算法,S自適應(yīng)方法：,自適應(yīng)的交叉概率與變異概率（續(xù)）,68,9.3.3 自適應(yīng)遺傳算法,自適應(yīng)的交叉概率與變異概率（續(xù)）,C 自適應(yīng)方法：,69,第9章 遺傳算法及其應(yīng)用,9.1 遺傳算法的產(chǎn)生與發(fā)展 9.2 遺傳算法的基本算法 9.3 遺傳算法的改進(jìn)算法 9.4 基于遺傳

26、算法的生產(chǎn)調(diào)度方法,70,9.4 基于遺傳算法的生產(chǎn)調(diào)度方法,9.4.1 基于遺傳算法的流水車間調(diào)度方法 9.4.2 基于遺傳算法的混合流水車間調(diào)度方法,71,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)度方法,72,1. 流水車間調(diào)度問(wèn)題,假設(shè)： (1)每個(gè)工件在機(jī)器上的加工順序是給定的。 (2)每臺(tái)機(jī)器同時(shí)只能加工一個(gè)

27、工件。 (3)一個(gè)工件不能同時(shí)在不同的機(jī)器上加工。 (4)工序不能預(yù)定。 (5)工序的準(zhǔn)備時(shí)間與順序無(wú)關(guān)，且包含在加工時(shí)間中。 (6) 工件在每臺(tái)機(jī)器上的加工順序相同，且是確定的。,9.4.1 基于遺傳算法的流水車間調(diào)度方法,73,1. 流水車間調(diào)度問(wèn)題,9.4.1 基于遺傳算法的流水車間調(diào)度方法,問(wèn)題的數(shù)學(xué)模型：,個(gè)工件、 臺(tái)機(jī)器的流水車間調(diào)度問(wèn)題的完工時(shí)間：,74,2. 求解流水車間調(diào)度問(wèn)題的遺傳算法設(shè)計(jì),（1） FSP的編碼方法 對(duì)于FSP，最自然的編碼方式是用染色體表示工件的順序。,9.4.1 基于遺傳算法的流水車間調(diào)度方法,對(duì)于有四個(gè)工件的FSP，第 個(gè)染色體 ，表示工件的加工順序?yàn)?/p>

28、： 。,75,2. 求解流水車間調(diào)度問(wèn)題的遺傳算法設(shè)計(jì),（2）FSP的適應(yīng)度函數(shù),: 個(gè)染色體 的最大流程時(shí)間， FSP的適應(yīng)度函數(shù)：,9.4.1 基于遺傳算法的流水車間調(diào)度方法,76,求解FSP的遺傳算法實(shí)例,例1 Ho 和 Chang(1991) 給出的5個(gè)工件、4臺(tái)機(jī)器問(wèn)題。,9.4.1 基于遺傳算法的流水車間調(diào)度方法,77,用遺傳算法求解。選擇交叉概率 ，變異概 ,種群規(guī)模為20，迭代次數(shù) 。,表9.3 遺傳算法運(yùn)行的結(jié)果,9.4.1 基于遺傳算法的流水車間調(diào)度方法,用窮舉法求得最優(yōu)解：4-2-5-1-3，加工時(shí)間：213； 最劣解：1-4-2-3-5，加工時(shí)間：294；平均解的加工時(shí)

29、間：265。,遺傳算法運(yùn)行的結(jié)果,78,表9.3 遺傳算法運(yùn)行的結(jié)果,最優(yōu)解收斂圖,9.4.1 基于遺傳算法的流水車間調(diào)度方法,79,平均值收斂圖,9.4.1 基于遺傳算法的流水車間調(diào)度方法,80,機(jī)器甘特圖,9.4.1 基于遺傳算法的流水車間調(diào)度方法,81,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í)間。,82,假設(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ù)，表示 工件