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

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

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

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

4、ong完成了重要論文遺傳自適應(yīng)系統(tǒng)的行為分析。 20世紀(jì)80年代以后，遺傳算法進入興盛發(fā)展時期。,10,9.1.4 設(shè)計遺傳算法的基本原則與內(nèi)容,設(shè)計的基本原則：,11,設(shè)計的基本內(nèi)容：,9.1.4 設(shè)計遺傳算法的基本原則與內(nèi)容,12,第9章 遺傳算法及其應(yīng)用,9.1 遺傳算法的產(chǎn)生與發(fā)展 9.2 遺傳算法的基本算法 9.3 遺傳算法的改進算法 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法,13,9.2 遺傳算法的基本算法,遺傳算法的五個基本要素： 參數(shù)編碼 初始群體的設(shè)定 適應(yīng)度函數(shù)的設(shè)計 遺傳操作設(shè)計 控制參數(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 編碼,位串編碼,一維染色體編碼方法：將問題空間的參數(shù)編碼為一維排列的染色體的方法。,二進制編碼：用若干二進制數(shù)表示一個個體，將原問題的解空間映射到位串空間 B=0，1上，然后在位串空間上進行遺傳操作。,（1） 二進制編碼,16,9.2.1 編碼,(1) 二進制編碼（續(xù)）,優(yōu)點： 類似于生物染色體的組成，算法易于用生物遺傳理論解釋，遺傳操作如交叉、變異等易實現(xiàn)；算法處理的模式數(shù)最多。,缺點： 相鄰整數(shù)的二進制編碼可能具有較大的Hamming距離，降低了遺傳算子的搜索效率。 15：

6、01111 16： 10000 要先給出求解的精度。 求解高維優(yōu)化問題的二進制編碼串長，算法的搜索效率低。,17,9.2.1 編碼,位串編碼 （2） Gray 編碼,Gray編碼:將二進制編碼通過一個變換進行轉(zhuǎn)換得到的編碼。,18,9.2.1 編碼,2. 實數(shù)編碼,采用實數(shù)表達法不必進行數(shù)制轉(zhuǎn)換，可直接在解的表現(xiàn)型上進行遺傳操作。 多參數(shù)映射編碼的基本思想：把每個參數(shù)先進行二進制編碼得到子串，再把這些子串連成一個完整的染色體。 多參數(shù)映射編碼中的每個子串對應(yīng)各自的編碼參數(shù)，所以，可以有不同的串長度和參數(shù)的取值范圍。,19,9.2.1 編碼,3. 有序串編碼,有序問題：目標(biāo)函數(shù)的值不僅與表示解的

7、字符串的值有關(guān)，而且與其所在字符串的位置有關(guān)。,4結(jié)構(gòu)式編碼,Goldberg等提出MessyGA(mGA)的遺傳算法編碼方法。,20,初始種群的產(chǎn)生,9.2.2 群體設(shè)定,（1）根據(jù)問題固有知識，把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。 （2）隨機產(chǎn)生一定數(shù)目的個體，從中挑選最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)目達到了預(yù)先確定的規(guī)模。,21,2. 種群規(guī)模的確定,9.2.2 群體設(shè)定,模式定理表明：若群體規(guī)模為M，則遺傳操作可從這M 個個體中生成和檢測 個模式，并在此基礎(chǔ)上能夠不斷形成和優(yōu)化積木塊，直到找到最優(yōu)解。,群體規(guī)模

8、太小，遺傳算法的優(yōu)化性能不太好，易陷入局部最優(yōu)解。 群體規(guī)模太大，計算復(fù)雜。,22,將目標(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ù)為最小化問題，則,23,將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法(續(xù)）,9.2.3 適應(yīng)度函數(shù),存在界限值預(yù)選估計困難或者不能精確估計的問題！,若目標(biāo)函數(shù)為最大化問題，則 若目標(biāo)函數(shù)為最小化問題，則 ：目標(biāo)函數(shù)界限的保守估計值。,24,適應(yīng)度函數(shù)的尺度變換,在遺傳算法中，將所有妨礙適應(yīng)度值高的個體產(chǎn)生，從而影響遺傳算法

9、正常工作的問題統(tǒng)稱為欺騙問題（deceptive problem）。,9.2.3 適應(yīng)度函數(shù),過早收斂：縮小這些個體的適應(yīng)度，以降低這些超級個體的競爭力。,停滯現(xiàn)象：改變原始適應(yīng)值的比例關(guān)系，以提高個體之間的競爭力。,適應(yīng)度函數(shù)的尺度變換（fitness scaling）或者定標(biāo)：對適應(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 選擇,個體選擇概率分配方法 選擇操作也稱為復(fù)制（reproduction）操作：從當(dāng)

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

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

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

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

14、r）,一點交叉：在個體串中隨機設(shè)定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結(jié)構(gòu)進行互換，并生成兩個新的個體。,二點交叉：隨機設(shè)置兩個交叉點，將兩個交叉點之間的碼串相互交換。,（2）二點交叉 （two-point crossover）,37,9.2.5 交叉,基本的交叉算子（續(xù)）,均勻交叉：按照均勻概率抽取一些位，每一位是否被選取都是隨機的，并且獨立于其他位。然后將兩個個體被抽取位互換組成兩個新個體。,（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ù)編碼的交叉方法 （1）離散交叉（discrete crossover）,部分離散交叉：在父解向量中選擇一部分分量，然后交換這些分量。 二進制的點式交叉,整體離散交叉：以0.5的概率交換父體 的所有分量。 二進制編碼的均勻性交叉,41,9.2.5 交叉,3. 實數(shù)編碼的交叉方法（續(xù)） （2）算術(shù)交叉（arithmetical crossover）,部分算術(shù)：先在父解向量中選擇一部分分量，如第 個

16、分量以后的所有分量，然后生成 個0，1區(qū)間的隨機數(shù)，并將兩個后代定義為：,42,9.2.5 交叉,3. 實數(shù)編碼的交叉方法（續(xù)） （2）算術(shù)交叉（arithmetical crossover）,整體算術(shù)交叉：先生成 n 個區(qū)間的隨機數(shù)，則后代分別定義為：,43,9.2.6 變異,1. 整數(shù)編碼的變異方法 （1）位點變異：群體中的個體碼串，隨機挑選一個或多個基因座，并對這些基因座的基因值以變異概率作變動。,（2）逆轉(zhuǎn)變異：在個體碼串中隨機選擇兩點（逆轉(zhuǎn)點），然后將兩點之間的基因值以逆向排序插入到原位置中。,（3）插入變異：在個體碼串中隨機選擇一個碼，然后將此碼插入隨機選擇的插入點中間。,44,9

17、.2.6 變異,1. 整數(shù)編碼的變異方法（續(xù)） （4）互換變異：隨機選取染色體的兩個基因進行簡單互換。 （5）移動變異：隨機選取一個基因，向左或者向右移動一個隨機位數(shù)。 （6）自適應(yīng)變異：類似于位點變異，但變異概率隨群體中個體的多樣性程度而自適應(yīng)調(diào)整。,45,9.2.6 變異,2. 實數(shù)編碼的變異方法 （1）均勻性變異,均勻性變異：在父解向量中隨機地選擇一個分量（第 個），然后在 中以均勻概率隨機選擇 代替 以得到 ，即,46,9.2.6 變異,2. 實數(shù)編碼的變異方法（續(xù)） （2）正態(tài)性變異（normal distributed mutation）,47,9.2.6 變異,2. 實數(shù)編碼的變

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

19、,（3）若滿足停止條件，則算法停止；否則，以概率 從pop(t)中隨機選擇一些染色體構(gòu)成一個新種群,52,9.2.7 遺傳算法的一般步驟,（4）以概率 進行交叉產(chǎn)生一些新的染色體，得到一個新的群體,（5）以一個較小的概率 使染色體的一個基因發(fā)生變異，形成 ； ，成為一個新的群體 返回 （2）。,53,9.2.8 遺傳算法的特點,可直接對結(jié)構(gòu)對象進行操作。 利用隨機技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進行高效率搜索。 采用群體搜索策略，易于并行化。 僅用適應(yīng)度函數(shù)值來評估個體，并在此基礎(chǔ)上進行遺傳操作，使種群中個體之間進行信息交換。,54,第9章 遺傳算法及其應(yīng)用,9.1 遺傳算法的產(chǎn)生與發(fā)展 9.2

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

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

22、立地運行復(fù)制、交叉、變異操作，同時當(dāng)每一代運行結(jié)束以后，選擇兩個種群中的隨機個體及最優(yōu)個體分別交換。,60,9.3.2 雙種群遺傳算法,2. 雙種群遺傳算法的設(shè)計 （1）編碼/解碼設(shè)計 （2）交叉算子、變異算子 （3）雜交算子,設(shè)種群A與種群B，當(dāng)A與B種群都完成了選擇、交叉、變異算子后，產(chǎn)生一個隨機數(shù)num，隨機選擇A中num個個體與A中最優(yōu)個體，隨機選擇B中num個個體與B中最優(yōu)個體，交換兩者，以打破平衡態(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)度自動改變。,AGA：當(dāng)種群各個體適應(yīng)度趨于一致或者趨于局部最優(yōu)時，使 增加，以跳出局部最優(yōu)；而當(dāng)群體適應(yīng)度比較分散時，使 減少，以利于優(yōu)良個體的生存。,同時，對于適應(yīng)度高于群體平均適應(yīng)值的個體，選擇較低的 ，使得該解得以保護進入下一代；對低于平均適應(yīng)值的個體，選擇較高的 值，使該解被淘汰。,63,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 個個體，計算 。

24、 （5）將群體中的各個個體隨機搭配成對，共組成N/2對， 對每一對個體，按照自適應(yīng)公式計算自適應(yīng)交叉概率 ，隨機產(chǎn)生R(0,1)，如果 則對該對染色體進行交叉操作。,64,2. 自適應(yīng)遺傳算法的步驟（續(xù)） （6）對于群體中的所有個體，共N個，按照自適應(yīng)變異公式計算自適應(yīng)變異概率 ，隨機產(chǎn)生 R(0,1)，如果 則對該染色體進行交叉操作。 （7）計算由交叉和變異生成新個體的適應(yīng)度，新個體與父代一起構(gòu)成新群體。 （8）判斷是否達到預(yù)定的迭代次數(shù)，是則結(jié)束；否則轉(zhuǎn) （4）。,9.3.3 自適應(yīng)遺傳算法,65,3. 適應(yīng)的交叉概率與變異概率,9.3.3 自適應(yīng)遺傳算法,普通自適應(yīng)算法中，當(dāng)個體適應(yīng)度值

25、越接近最大適應(yīng)度值時，交叉概率與變異概率就越?。划?dāng)?shù)扔谧畲筮m應(yīng)度值時，交叉概率和變異概率為零。,改進的思想：當(dāng)前代的最優(yōu)個體不被破壞，仍然保留（最優(yōu)保存策略）；但較優(yōu)個體要對應(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 遺傳算法的改進算法 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)度問題,問題描述：n 個工件要在 m 臺機器上加工，每個工件需要經(jīng)過 m 道工序，每道工序要求不同的機器，n 個工件在 m 臺機器上的加工順序相同。工件在機器上的加工時間是給定的，設(shè)為,問題的目標(biāo)：確定 n 個工件在每臺機器上的最優(yōu)加工順序，使最大流程時間達到最小。,9.4.1 基于遺傳算法的流水車間調(diào)度方法,72,1. 流水車間調(diào)度問題,假設(shè)： (1)每個工件在機器上的加工順序是給定的。 (2)每臺機器同時只能加工一個

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

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

29、間：265。,遺傳算法運行的結(jié)果,78,表9.3 遺傳算法運行的結(jié)果,最優(yōu)解收斂圖,9.4.1 基于遺傳算法的流水車間調(diào)度方法,79,平均值收斂圖,9.4.1 基于遺傳算法的流水車間調(diào)度方法,80,機器甘特圖,9.4.1 基于遺傳算法的流水車間調(diào)度方法,81,9.4.2 基于遺傳算法的混合流水車間調(diào)度方法,1. 混合流水車間調(diào)度問題,問題的特征：在某些工序上存在并行機器。 問題的描述：需要加工多個工件，所有工件的加工路線都相同，都需要依次通過幾道工序，在所有工序中至少有一個工序存在著多臺并行機器。 需要解決的問題：確定并行機器的分配情況以及同一臺機器上工件的加工排序。 目標(biāo)：最小化最大流程時間。,82,假設(shè)加工 個工件，每個工件都要依次經(jīng)過 個加工工序，每個工序的并行機器數(shù)為 ， 。所有工序中至少有一個工序存在并行機，即至少有一個 大于1。,9.4.2 基于遺傳算法的混合流水車間調(diào)度方法,2. 混合流水車間調(diào)度問題的遺傳算法編碼方法,HFSP的編碼矩陣,： 上的一個實數(shù)，表示 工件