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

1、Artificial Intelligence Principles and Applications 第第 9 章章 遺傳算法及其應(yīng)用遺傳算法及其應(yīng)用 教材：教材： 王萬良王萬良人工智能及其應(yīng)用人工智能及其應(yīng)用（第（第2版）版） 高等教育出版社，高等教育出版社，2008. 6 2 第9章 遺傳算法及其應(yīng)用 o 9.1 遺傳算法的產(chǎn)生與發(fā)展遺傳算法的產(chǎn)生與發(fā)展 o 9.2 遺傳算法的基本算法遺傳算法的基本算法 o 9.3 遺傳算法的改進(jìn)算法遺傳算法的改進(jìn)算法 o 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法基于遺傳算法的生產(chǎn)調(diào)度方法 3 第9章 遺傳算法及其應(yīng)用 9.1 遺傳算法的產(chǎn)生與發(fā)展遺傳算法的產(chǎn)

2、生與發(fā)展 o 9.2 遺傳算法的基本算法遺傳算法的基本算法 o 9.3 遺傳算法的改進(jìn)算法遺傳算法的改進(jìn)算法 o 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法基于遺傳算法的生產(chǎn)調(diào)度方法 4 9.1 遺傳算法的產(chǎn)生與發(fā)展 遺傳算法遺傳算法（genetic algorithms，GA）：一類借鑒 生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法,非 常適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線 性優(yōu)化問題。 遺傳算法可廣泛應(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)算法的基本思想遺產(chǎn)算法的基

3、本思想 9.1.3 遺產(chǎn)算法的發(fā)展歷史遺產(chǎn)算法的發(fā)展歷史 9.1.4 設(shè)計(jì)遺產(chǎn)算法設(shè)計(jì)遺產(chǎn)算法的基本原則與內(nèi)容的基本原則與內(nèi)容 6 9.1.1 遺傳算法的生物學(xué)背景 o 適者生存適者生存：最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群 體。體。 o 生物進(jìn)化的基本過程：生物進(jìn)化的基本過程： 染色體染色體(chromosome)：生物生物 的遺傳物質(zhì)的主要載體。的遺傳物質(zhì)的主要載體。 基因基因(gene)：擴(kuò)展生物性狀擴(kuò)展生物性狀 的遺傳物質(zhì)的功能單元和結(jié)的遺傳物質(zhì)的功能單元和結(jié) 構(gòu)單位。構(gòu)單位。 基因座（基因座（locus）：染色體：染色體 中基因的位置。

4、中基因的位置。 等位基因（等位基因（alleles）：基因：基因 所取的值。所取的值。 7 9.1.2 遺傳算法的基本思想 生物遺傳概念生物遺傳概念遺產(chǎn)算法中的應(yīng)用遺產(chǎn)算法中的應(yīng)用 適者生存適者生存目標(biāo)值比較大的解被選擇的可能性大目標(biāo)值比較大的解被選擇的可能性大 個(gè)體（個(gè)體（Individual）解解 染色體（染色體（Chromosome） 解的編碼（字符串、向量等）解的編碼（字符串、向量等） 基因（基因（Gene）解中每一分量的特征解中每一分量的特征 適應(yīng)性（適應(yīng)性（Fitness）適應(yīng)函數(shù)值適應(yīng)函數(shù)值 群體（群體（Population） 根據(jù)適應(yīng)函數(shù)值選定的一組解（解的個(gè)根據(jù)適應(yīng)函數(shù)值選定

5、的一組解（解的個(gè) 數(shù)為群體的規(guī)模）數(shù)為群體的規(guī)模） 婚配（婚配（Marry） 交叉（交叉（Crossover）選擇兩個(gè)染色體進(jìn)行）選擇兩個(gè)染色體進(jìn)行 交叉產(chǎn)生一組新的染色體的過程交叉產(chǎn)生一組新的染色體的過程 變異（變異（Mutation）編碼的某一分量發(fā)生變化的過程編碼的某一分量發(fā)生變化的過程 8 9.1.2 遺傳算法的基本思想 遺傳算法的基本思想：遺傳算法的基本思想： 在求解問題時(shí)從多個(gè)解開始，然后通過一定的法在求解問題時(shí)從多個(gè)解開始，然后通過一定的法 則進(jìn)行逐步迭代以產(chǎn)生新的解。則進(jìn)行逐步迭代以產(chǎn)生新的解。 最優(yōu)化問題 遺傳算法 目標(biāo)函數(shù) 可 行 解 一組 解 適應(yīng)度函數(shù) 染 色 體 種

6、群 9 9.1.3 遺傳算法的發(fā)展歷史 o 1962年，F(xiàn)raser提出了自然遺傳算法。 o 1965年，Holland首次提出了人工遺傳操作的重要性。 o 1967年，Bagley首次提出了遺傳算法這一術(shù)語。 o 1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別中。 o 1971年，Hollstien在論文計(jì)算機(jī)控制系統(tǒng)中人工遺傳 自適應(yīng)方法中闡述了遺傳算法用于數(shù)字反饋控制的 方法。 o 1975年，美國J. Holland出版了自然系統(tǒng)和人工系統(tǒng) 的適配；DeJong完成了重要論文遺傳自適應(yīng)系統(tǒng) 的行為分析。 o 20世紀(jì)80年代以后，遺傳算法進(jìn)入興盛發(fā)展時(shí)期。 10 9.1.4 設(shè)

7、計(jì)遺傳算法的基本原則與內(nèi)容 設(shè)計(jì)的基本原則：設(shè)計(jì)的基本原則： 適用性 適用性：算法所能適用的問題種類。算法所能適用的問題種類。 可靠性可靠性：算法對(duì)于所設(shè)計(jì)的問題，以適當(dāng)?shù)木惹蠼馑惴▽?duì)于所設(shè)計(jì)的問題，以適當(dāng)?shù)木惹蠼?其中大多數(shù)問題的能力其中大多數(shù)問題的能力 。 收斂性收斂性：算法能否收斂到全局最優(yōu)。算法能否收斂到全局最優(yōu)。 穩(wěn)定性穩(wěn)定性：算法對(duì)其控制參數(shù)及問題數(shù)據(jù)的敏感度算法對(duì)其控制參數(shù)及問題數(shù)據(jù)的敏感度 。 生物類比生物類比：通過類比的方法引入在生物界被認(rèn)為是有通過類比的方法引入在生物界被認(rèn)為是有 效的方法及操作。效的方法及操作。 11 設(shè)計(jì)的基本內(nèi)容：設(shè)計(jì)的基本內(nèi)容： 9.1.4 設(shè)計(jì)

8、遺傳算法的基本原則與內(nèi)容 編碼方案編碼方案：編碼表示方式。編碼表示方式。 適應(yīng)度函數(shù)適應(yīng)度函數(shù)：目標(biāo)函數(shù)。目標(biāo)函數(shù)。 選擇策略選擇策略：優(yōu)勝劣汰。優(yōu)勝劣汰。 控制參數(shù)控制參數(shù)：種群的規(guī)模、算法執(zhí)行的最大代數(shù)、執(zhí)行種群的規(guī)模、算法執(zhí)行的最大代數(shù)、執(zhí)行 不同遺傳操作的概率等。不同遺傳操作的概率等。 遺傳算子遺傳算子：選擇選擇(selection)；交叉；交叉(crossover)；變異；變異 (mutation)。 算法的終止準(zhǔn)則算法的終止準(zhǔn)則：規(guī)定一個(gè)最大的演化代數(shù)，或算法規(guī)定一個(gè)最大的演化代數(shù)，或算法 在連續(xù)多少代以后解的適應(yīng)值沒有改進(jìn)。在連續(xù)多少代以后解的適應(yīng)值沒有改進(jìn)。 12 第9章 遺傳

9、算法及其應(yīng)用 o 9.1 遺傳算法的產(chǎn)生與發(fā)展遺傳算法的產(chǎn)生與發(fā)展 9.2 遺傳算法的基本算法遺傳算法的基本算法 o 9.3 遺傳算法的改進(jìn)算法遺傳算法的改進(jìn)算法 o 9.4 基于遺傳算法基于遺傳算法的生產(chǎn)調(diào)度方法的生產(chǎn)調(diào)度方法 13 9.2 遺傳算法的基本算法 o 遺傳算法的五個(gè)基本要素遺傳算法的五個(gè)基本要素： n 參數(shù)編碼 n 初始群體的設(shè)定 n 適應(yīng)度函數(shù)的設(shè)計(jì) n 遺傳操作設(shè)計(jì) n 控制參數(shù)設(shè)定 14 9.2 遺傳算法的基本算法 9.2.1 編碼編碼 9.2.2 群體設(shè)定群體設(shè)定 9.2.3 適應(yīng)度函數(shù)適應(yīng)度函數(shù) 9.2.4 選擇選擇 9.2.5 交叉交叉 9.2.6 變異變異 9.2

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

11、 了遺傳算子的搜索效率。 15：01111 16： 10000 要先給出求解的精度。 求解高維優(yōu)化問題的二進(jìn)制編碼串長，算法的搜索效率低。 17 9.2.1 編碼 1. 位串編碼位串編碼 （2） Gray 編碼編碼 Gray編碼:將二進(jìn)制編碼通過一個(gè)變換進(jìn)行轉(zhuǎn)換得到的編碼。 二進(jìn)制串 n . 21 Gray n . 21 二進(jìn)制編碼 Gray編碼 1 1 1 1 k k kk k Gray編碼 二進(jìn)制編碼 )2(mod 1 k i ik 18 9.2.1 編碼 2. 實(shí)數(shù)編碼實(shí)數(shù)編碼 采用實(shí)數(shù)表達(dá)法不必進(jìn)行數(shù)制轉(zhuǎn)換不必進(jìn)行數(shù)制轉(zhuǎn)換，可直接在解的表 現(xiàn)型上進(jìn)行遺傳操作。 多參數(shù)映射編碼的基本思想

12、多參數(shù)映射編碼的基本思想：把每個(gè)參數(shù)先進(jìn)行二進(jìn) 制編碼得到子串，再把這些子串連成一個(gè)完整的染色體。 多參數(shù)映射編碼中的每個(gè)子串對(duì)應(yīng)各自的編碼參數(shù)， 所以，可以有不同的串長度和參數(shù)的取值范圍有不同的串長度和參數(shù)的取值范圍。 19 9.2.1 編碼 3. 有序串編碼有序串編碼 有序問題有序問題：目標(biāo)函數(shù)的值不僅與表示解的字符串的值 有關(guān)，而且與其所在字符串的位置有關(guān)。 4結(jié)構(gòu)式編碼結(jié)構(gòu)式編碼 Goldberg等提出MessyGA(mGA)的遺傳算法編碼方法。 20 1. 初始種群的產(chǎn)生初始種群的產(chǎn)生 9.2.2 群體設(shè)定 （1）根據(jù)問題固有知識(shí)，把握最優(yōu)解所占空間在整個(gè)問 題空間中的分布范圍，然后

13、，在此分布范圍內(nèi)設(shè)定初始 群體。 （2）隨機(jī)產(chǎn)生一定數(shù)目的個(gè)體，從中挑選最好的個(gè)體加 到初始群體中。這種過程不斷迭代，直到初始群體中個(gè) 體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。 21 2. 種群規(guī)模的確定種群規(guī)模的確定 9.2.2 群體設(shè)定 模式定理模式定理表明：若群體規(guī)模為M，則遺傳操作可從這 M 個(gè)個(gè)體中生成和檢測 個(gè)模式，并在此基礎(chǔ)上能夠 不斷形成和優(yōu)化積木塊，直到找到最優(yōu)解。 3 M 群體規(guī)模太小，遺傳算法的優(yōu)化性能不太好，易陷入 局部最優(yōu)解。 群體規(guī)模太大，計(jì)算復(fù)雜。 22 1.1. 將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法 9.2.3 適應(yīng)度函數(shù) 若目標(biāo)函數(shù)為最大化最大

14、化問題，則 若目標(biāo)函數(shù)為最小化最小化問題，則 )()(xfxfFit )( 1 )( xf xfFit 將目標(biāo)函數(shù)轉(zhuǎn)換為求最大值的形式將目標(biāo)函數(shù)轉(zhuǎn)換為求最大值的形式, ,且保證函數(shù)值非負(fù)！且保證函數(shù)值非負(fù)！ 若目標(biāo)函數(shù)為最大化最大化問題，則 若目標(biāo)函數(shù)為最小化最小化問題，則 minmin ( )( ) ( ( ) 0 f xCf xC Fit f x 其他情況 maxmax ( )( ) ( ( ) 0 Cf xf xC Fit f x 其他情況 23 1.1. 將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法( (續(xù)）續(xù)） 9.2.3 適應(yīng)度函數(shù) 存在界限值預(yù)選估計(jì)困難或者不

15、能精確估計(jì)的問題！存在界限值預(yù)選估計(jì)困難或者不能精確估計(jì)的問題！ 若目標(biāo)函數(shù)為最大化最大化問題，則 若目標(biāo)函數(shù)為最小化最小化問題，則 ：目標(biāo)函數(shù)界限的保守估計(jì)值。 1 ( ( )0( )0 1( ) Fit f xccf x cf x ， 1 ( ( )0( )0 1( ) Fit f xccf x cf x ， c 24 2. 適應(yīng)度函數(shù)的尺度變換適應(yīng)度函數(shù)的尺度變換 在遺傳算法中，將所有妨礙適應(yīng)度值高的個(gè)體產(chǎn)生，從 而 影 響 遺 傳 算 法 正 常 工 作 的 問 題 統(tǒng) 稱 為 欺 騙 問 題欺 騙 問 題 （deceptive problem）。 9.2.3 適應(yīng)度函數(shù) 過早收斂過早

16、收斂：縮小這些個(gè)體的適應(yīng)度，以降低這些超級(jí)個(gè) 體的競爭力。 停滯現(xiàn)象停滯現(xiàn)象：改變?cè)歼m應(yīng)值的比例關(guān)系，以提高個(gè)體之 間的競爭力。 適應(yīng)度函數(shù)的尺度變換（尺度變換（fitness scaling）或者定標(biāo)定標(biāo)： 對(duì)適應(yīng)度函數(shù)值域的某種映射變換。 25 2. 適應(yīng)度函數(shù)適應(yīng)度函數(shù)的尺度變換的尺度變換( (續(xù)）續(xù)） （1）線性變換： baff 9.2.3 適應(yīng)度函數(shù) min ff f a avg avg min min ff ff b avg avg avg avgmult ff fC a max ) 1( avg avgavgmult ff ffCf b max max )( , avgavg

17、ff avgmult fCf max 滿足 滿足最小適應(yīng)度值非負(fù) 26 2. 適應(yīng)度函數(shù)適應(yīng)度函數(shù)的尺度變換的尺度變換( (續(xù)）續(xù)） （2）冪函數(shù)變換法： K ff af f e 9.2.3 適應(yīng)度函數(shù) （3）指數(shù)變換法： 27 9.2.4 選擇 1. 個(gè)體選擇概率分配方法個(gè)體選擇概率分配方法 選擇操作也稱為復(fù)制（reproduction）操作：從當(dāng)前群 體中按照一定概率選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為 父代繁殖下一代子孫。 判斷個(gè)體優(yōu)良與否的準(zhǔn)則是各個(gè)個(gè)體的適應(yīng)度值：個(gè)體 適應(yīng)度越高，其被選擇的機(jī)會(huì)就越多。 28 9.2.4 選擇 1. 個(gè)體選擇概率分配方法個(gè)體選擇概率分配方法 （1）適應(yīng)度

18、比例方法適應(yīng)度比例方法（fitness proportional model）或蒙特卡或蒙特卡 羅法羅法（Monte Carlo） M i i i si f f p 1 各個(gè)個(gè)體被選擇的概率和其適應(yīng)度值成比例。 個(gè)體 被選擇的概率為： i 29 9.2.4 選擇 1. 個(gè)體選擇概率分配方法個(gè)體選擇概率分配方法 （2） 排序方法排序方法 （rank-based model） 線性排序：J. E. Baker 群體成員按適應(yīng)值大小從好到壞依次排列： 個(gè)體 按轉(zhuǎn)盤式選擇的方式選擇父體 N xxx, 21 ii px 分配選擇概率 ) 1( MM bia pi 30 9.2.4 選擇 1. 個(gè)體選擇概

19、率分配方法個(gè)體選擇概率分配方法 （2） 排序方法排序方法 （rank-based model） 非線性排序： Z. Michalewicz 將群體成員按適應(yīng)值從好到壞依次排列，并按下式分 配選擇概率： Mi Mi q qq p M i i 1, 2 , 1 )1 ( )1 ( 1 1 31 9.2.4 選擇 1. 1.個(gè)體選擇概率分配方法個(gè)體選擇概率分配方法 （2） 排序方法排序方法 （rank-based model） 可用其他非線性函數(shù)來分配選擇概率，只要滿足以 下條件： M i i p 1 1 )2( 滿足則且若 iMM pxfxfxfxxxP ),(.)()( , ) 1 ( 212,

20、 1 M ppp 21 32 9.2.4 選擇 2. 選擇個(gè)體方法選擇個(gè)體方法 （1）轉(zhuǎn)盤賭選擇轉(zhuǎn)盤賭選擇（roulette wheel selection） 按個(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 33 9.2.4 選擇 2. 選擇個(gè)體方法選擇個(gè)體方法 （2）錦標(biāo)賽選擇方法錦標(biāo)賽選擇方法（tournament selection model） 錦標(biāo)賽選擇方法錦標(biāo)賽選擇方法：從群體中隨機(jī)選擇個(gè)個(gè)體，將其中適應(yīng) 度最高的個(gè)體保存到下一代。

21、這一過程反復(fù)執(zhí)行，直到保存 到下一代的個(gè)體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)量為止。 隨機(jī)競爭方法隨機(jī)競爭方法（stochastic tournament）：每次按賭輪選擇方 法選取一對(duì)個(gè)體，然后讓這兩個(gè)個(gè)體進(jìn)行競爭，適應(yīng)度高者 獲勝。如此反復(fù)，直到選滿為止。 34 9.2.4 選擇 2. 選擇個(gè)體方法選擇個(gè)體方法 （3） 和 選擇 ),( 選擇),( 從規(guī)模為 的群體中隨機(jī)選取個(gè)體通過重組和變異生成 個(gè)后代， 再選取 個(gè)最優(yōu)的后代作為新一代種群。 )( 選擇 從 個(gè)后代與其父體共 中選取 個(gè)最優(yōu)的后代。 )( 35 9.2.4 選擇 2. 選擇個(gè)體方法選擇個(gè)體方法 （4）Boltzmann錦標(biāo)賽選擇 最佳個(gè)

22、體（最佳個(gè)體（elitist model）保存方法）保存方法：把群體中適應(yīng)度最高 的個(gè)體不進(jìn)行交叉而直接復(fù)制到下一代中，保證遺傳算法終 止時(shí)得到的最后結(jié)果一定是歷代出現(xiàn)過的最高適應(yīng)度的個(gè)體。 （5）最佳個(gè)體保存方法 隨機(jī)選取兩個(gè)個(gè)體 ，若 則選擇適應(yīng)值 好的作為勝者，否則計(jì)算概率 ， 若 ，選擇差解，否則選擇好解。 21,x x | 21 xfxf Txfxfp|exp 21 ) 1 , 0randomp 36 9.2.5 交叉 1. 基本的交叉算子基本的交叉算子 （1）一點(diǎn)交叉一點(diǎn)交叉（single-point crossover） 一點(diǎn)交叉：在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)， 該點(diǎn)

23、前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新 的個(gè)體。 二點(diǎn)交叉：隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，將兩個(gè)交叉點(diǎn)之間的碼 串相互交換。 （2）二點(diǎn)交叉二點(diǎn)交叉 （two-point crossover） 37 9.2.5 交叉 1. 基本的交叉算子（續(xù)）基本的交叉算子（續(xù)） 均勻交叉：按照均勻概率抽取一些位，每一位是否被選取 都是隨機(jī)的，并且獨(dú)立于其他位。然后將兩個(gè)個(gè)體被抽取位 互換組成兩個(gè)新個(gè)體。 （3）均勻交叉均勻交叉（uniform crossover）或一致交叉 38 9.2.5 交叉 2. 修正的交叉方法修正的交叉方法 （1）部分匹配交叉）部分匹配交叉PMX：Goldberg D. E.和R.

24、 Lingle(1985) 231765489A 645932178B 231932489A 645765178B 39 9.2.5 交叉 2. 修正的交叉方法修正的交叉方法(續(xù)）續(xù)） （2）順序交叉順序交叉OX：Davis L. (1985) HHHA176548 HHHB493218 481765HHHA 184932HHHB 481932765 A 184765932 B （3） 循環(huán)交叉循環(huán)交叉CX：Smith D. (1985) 40 9.2.5 交叉 3. 實(shí)數(shù)編碼的交叉方法實(shí)數(shù)編碼的交叉方法 （1）離散交叉）離散交叉（discrete crossover） 部分離散交叉部分離散交

25、叉：在父解向量中選擇一部分分量，然后交換 這些分量。 二進(jìn)制的點(diǎn)式交叉二進(jìn)制的點(diǎn)式交叉 整體離散交叉整體離散交叉：以0.5的概率交換父體 的所有分 量。 二進(jìn)制編碼的均勻性交叉二進(jìn)制編碼的均勻性交叉 21 ss 與 41 9.2.5 交叉 3. 實(shí)數(shù)編碼的交叉方法（續(xù)）實(shí)數(shù)編碼的交叉方法（續(xù)） （2）算術(shù)交叉算術(shù)交叉（arithmetical crossover） 部分算術(shù)部分算術(shù)：先在父解向量中選擇一部分分量，如第 個(gè)分 量以后的所有分量，然后生成 個(gè)0，1區(qū)間的隨機(jī)數(shù)， 并將兩個(gè)后代定義為： k kn )1 (,.,1,.,( )2()1()2( 1 1 )1( 1 1 )1()1( 1v

26、vvvvvn n n n k k k k k z aaaas )1 (,.,1,.,( )1()2()1( 1 1 )2( 1 1 )2()2( 1vvvvvvn n n n k k k k k w aaaas nk aa . 1 42 9.2.5 交叉 3. 實(shí)數(shù)編碼的交叉方法（續(xù)）實(shí)數(shù)編碼的交叉方法（續(xù)） （2）算術(shù)交叉算術(shù)交叉（arithmetical crossover） 整體算術(shù)交叉整體算術(shù)交叉：先生成 n 個(gè)區(qū)間的隨機(jī)數(shù)，則后代分別定 義為： )()1 ( )2()1()2()2()1( iiiiiiiii vvavvavaz )()1 ( )1()2()1()1()2( iiii

27、iiiii vvavvavaw n aaa. 21 43 9.2.6 變異 1. 整數(shù)編碼的變異方法整數(shù)編碼的變異方法 （1）位點(diǎn)變異位點(diǎn)變異：群體中的個(gè)體碼串，隨機(jī)挑選一個(gè)或多 個(gè)基因座，并對(duì)這些基因座的基因值以變異概率作變動(dòng)。 （2）逆轉(zhuǎn)變異逆轉(zhuǎn)變異：在個(gè)體碼串中隨機(jī)選擇兩點(diǎn)（逆轉(zhuǎn)點(diǎn)）， 然后將兩點(diǎn)之間的基因值以逆向排序插入到原位置中。 （3）插入變異插入變異：在個(gè)體碼串中隨機(jī)選擇一個(gè)碼，然后將 此碼插入隨機(jī)選擇的插入點(diǎn)中間。 44 9.2.6 變異 1. 整數(shù)編碼的變異方法（續(xù)）整數(shù)編碼的變異方法（續(xù)） （4）互換變異互換變異：隨機(jī)選取染色體的兩個(gè)基因進(jìn)行簡單互 換。 （5）移動(dòng)變異移動(dòng)

28、變異：隨機(jī)選取一個(gè)基因，向左或者向右移動(dòng) 一個(gè)隨機(jī)位數(shù)。 （6）自適應(yīng)變異自適應(yīng)變異：類似于位點(diǎn)變異，但變異概率隨群體 中個(gè)體的多樣性程度而自適應(yīng)調(diào)整。 45 9.2.6 變異 2. 實(shí)數(shù)編碼的變異方法實(shí)數(shù)編碼的變異方法 （1）均勻性變異均勻性變異 ：父解),.,.,( 21nk vvvvs ：變異產(chǎn)生的后代),.,.,( 21nk vvvvs kiv kiv s k i , , 均勻性變異均勻性變異：在父解向量中隨機(jī)地選擇一個(gè)分量（第 個(gè)），然后在 中以均勻概率隨機(jī)選擇 代替 以得 到 ，即 k , kk ba k v k v s 46 9.2.6 變異 2. 實(shí)數(shù)編碼的變異方法（續(xù)）實(shí)數(shù)編

29、碼的變異方法（續(xù)） （2）正態(tài)性變異正態(tài)性變異（normal distributed mutation） n vvvs, 21 解向量 n , 21 攝動(dòng)向量 , s被選個(gè)體 , s新個(gè)體 ,0exp iii N iii Nvv, 0ni, 2 , 1 47 9.2.6 變異 2. 實(shí)數(shù)編碼的變異方法（續(xù)）實(shí)數(shù)編碼的變異方法（續(xù)） （3）非一致性變異非一致性變異 Z. Michalewicz首先提出將變異算子的結(jié)果與演化代數(shù)聯(lián)系 起來。 在演化初期，變異范圍相對(duì)較大，而隨著演化的推進(jìn)，變 異范圍越來越小，起著一種對(duì)演化系統(tǒng)的微調(diào)作用。 48 9.2.6 變異 2. 實(shí)數(shù)編碼的變異方法（續(xù)）實(shí)數(shù)

30、編碼的變異方法（續(xù)） （3）非一致性變異非一致性變異 ：區(qū)間 , kk ba 1)2( 0)2( , , rnd rnd abtv vbtv v kkk kkk k Tt ryyt 1 1, ：父解 ,., 21nk vvvvs ：變異后的解 , 121nkk vvvvvs 49 9.2.6 變異 2. 實(shí)數(shù)編碼的變異方法（續(xù)）實(shí)數(shù)編碼的變異方法（續(xù)） （4）自適應(yīng)變異自適應(yīng)變異 ：解空間的一個(gè)向量 , 21n vvvs max 1 f sf T變異溫度： 自適應(yīng)變異方式與非一致性變異算子相同，只是將其中的 演化代數(shù) 改為 ，函數(shù)表達(dá)式變?yōu)椋?t T T ryyT1, 50 9.2.7 遺傳算

31、法的一般步驟 問 題 初 始 化 染 色 體 種 群 計(jì) 算 每 個(gè) 個(gè) 體 的 適 應(yīng) 值 根 據(jù) 適 應(yīng) 值 選 擇 串 進(jìn) 行 復(fù) 制 交 叉 變 異 確 定 表 示 問 題 解 答 的 染 色 體 （ 編 碼 ） 輸 出 最 優(yōu) 解 是 否 滿 足 終 止 條 件 51 9.2.7 遺傳算法的一般步驟 （1）使用隨機(jī)方法或者其它方法，產(chǎn)生一個(gè)有N個(gè)染色 體 的初始群體 pop(1)， ； 1:t （2）對(duì)群體中的每一個(gè)染色體popi(t)，計(jì)算其適應(yīng)值 )(tpopfitnessf ii （3）若滿足停止條件，則算法停止；否則，以概率 從pop(t)中隨機(jī)選擇一些染色體構(gòu)成一個(gè)新種群

32、N j jii ffp 1 / ,.,2 , 1)() 1(Njtpoptnewpop j 52 9.2.7 遺傳算法的一般步驟 （4）以概率 進(jìn)行交叉產(chǎn)生一些新的染色體，得到一個(gè) 新的群體 c p ) 1( tcrosspop （5）以一個(gè)較小的概率 使染色體的一個(gè)基因發(fā)生變異， 形成 ； ，成為一個(gè)新的群體 返回 （2）。 m p ) 1( tmutpop 1 :tt ) 1()(tmutpoptpop 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ù)值來評(píng)估個(gè)體，并在此基

33、礎(chǔ)上進(jìn) 行遺傳操作，使種群中個(gè)體之間進(jìn)行信息交換。 54 第9章 遺傳算法及其應(yīng)用 o 9.1 遺傳算法的產(chǎn)生與發(fā)展遺傳算法的產(chǎn)生與發(fā)展 o 9.2 遺傳算法的基本算法遺傳算法的基本算法 9.3 遺傳算法的改進(jìn)算法遺傳算法的改進(jìn)算法 o 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法基于遺傳算法的生產(chǎn)調(diào)度方法 55 9.3 遺傳算法的改進(jìn)算法 9.3.1 雙倍體遺傳算法雙倍體遺傳算法 9.3.2 雙種群遺傳算法雙種群遺傳算法 9.3.3 自適應(yīng)遺傳算法自適應(yīng)遺傳算法 56 9.3.1 雙倍體遺傳算法 1. 基本思想基本思想 雙倍體遺傳算法采用顯性顯性和隱性隱性兩個(gè)染色體同時(shí)進(jìn)行 進(jìn)化，提供了一種記憶以前有

34、用的基因塊的功能。 雙倍體遺傳算法采用顯性遺傳顯性遺傳。 雙倍體遺傳延長了有用基因塊的壽命，提高了算法的收斂 能力，在變異概率低的情況下能保持一定水平的多樣性。 57 9.3.1 雙倍體遺傳算法 2. 雙倍體遺傳算法的設(shè)計(jì)雙倍體遺傳算法的設(shè)計(jì) （1）編碼）編碼/解碼解碼：兩個(gè)染色體（顯性、隱性） （2）復(fù)制算子）復(fù)制算子：計(jì)算顯性染色體的適應(yīng)度，按照顯性染色體 的復(fù)制概率將個(gè)體復(fù)制到下一代群體中。 （3）交叉算子）交叉算子：兩個(gè)個(gè)體的顯性染色體交叉、隱性染色體也 同時(shí)交叉。 （4）變異算子：）變異算子：個(gè)體的顯性染色體按正常的變異概率變異； 隱性染色體按較大的變異概率變異。 （5）雙倍體遺傳算

35、法顯隱性重排算子：）雙倍體遺傳算法顯隱性重排算子：個(gè)體中適應(yīng)值較大的 染色體設(shè)為顯性染色體，適應(yīng)值較小的染色體設(shè)為隱性染 色體。 58 n = 0 不 同 的 隨 機(jī) 方 法 產(chǎn) 生 兩 個(gè) 初 始 群 體 是 否 滿 足 停 止 準(zhǔn) 則 ？ 計(jì) 算 適 應(yīng) 度 兩 個(gè) 種 群 分 別 執(zhí) 行 選 擇 操 作 兩 個(gè) 種 群 分 別 執(zhí) 行 交 叉 操 作 兩 個(gè) 種 群 分 別 執(zhí) 行 變 異 操 作 隨 機(jī) 選 擇 兩 個(gè) 種 群 中 的 個(gè) 體 生 成 機(jī) 器 甘 特 圖 ， 計(jì) 算 目 標(biāo) 值 n = n + 1 輸出結(jié)果，結(jié)束 是 否 隨 機(jī) 個(gè) 體 及 最 優(yōu) 個(gè) 體 分 別 交

36、換 雙種群遺傳算法程序流程圖雙種群遺傳算法程序流程圖 59 9.3.2 雙種群遺傳算法 1.1. 基本思想基本思想 在遺傳算法中使用多種群同時(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è)體分別交換。 60 9.3.2 雙種群遺傳算法 2. 雙種群雙種群遺傳算法的設(shè)計(jì)遺傳算法的設(shè)計(jì) （1）編碼/解碼設(shè)計(jì) （2）交叉算子、變異算子 （3）雜交算子雜交算子 設(shè)種群A與種群B，當(dāng)A與B

37、種群都完成了選擇、交叉、 變異算子后，產(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 n = 0 不同的隨機(jī)方法產(chǎn) 生兩個(gè)初始群體 是否滿足停止 準(zhǔn)則？ 計(jì)算適應(yīng)度 兩個(gè)種群分別執(zhí)行 選擇操作 兩個(gè)種群分別執(zhí)行 交叉操作 兩個(gè)種群分別執(zhí)行 變異操作 隨機(jī)選擇兩個(gè)種群 中的個(gè)體 生成機(jī)器甘特圖 ，計(jì)算目標(biāo)值 n = n + 1 輸出結(jié)果，結(jié)束 是 否 隨機(jī)個(gè)體及最優(yōu)個(gè)體 分別交換 雙種群遺傳算法程序流程圖雙種群遺傳算法程序流程圖 62 9.3.3 自適應(yīng)遺傳算法 1. 基本思想基本思想 Srinvivas

38、M.，Patnaik L. M.等在1994年提出一種自適應(yīng) 遺傳算法(adaptive genetic algorithms，AGA)： 能隨適 應(yīng)度自動(dòng)改變。 cm PP和 AGA：當(dāng)種群各個(gè)體適應(yīng)度趨于一致或者趨于局部最 優(yōu)時(shí)，使 增加，以跳出局部最優(yōu)；而當(dāng)群體適應(yīng)度 比較分散時(shí)，使 減少，以利于優(yōu)良個(gè)體的生存。 cm PP和 cm PP和 同時(shí)，對(duì)于適應(yīng)度高于群體平均適應(yīng)值的個(gè)體，選擇 較低的 ，使得該解得以保護(hù)進(jìn)入下一代；對(duì)低于 平均適應(yīng)值的個(gè)體，選擇較高的 值，使該解被淘 汰。 cm PP和 cm PP和 63 9.3.3 自適應(yīng)遺傳算法 2. 自適應(yīng)自適應(yīng)遺傳算法的步驟遺傳算法的

39、步驟 （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)行交叉 操作。 1/fob i f maxavg ff和 c RP c p 64 2. 自適應(yīng)遺傳算法的步驟自適應(yīng)遺傳算法的步驟（續(xù)）（續(xù)） （6）對(duì)于群體中的所有個(gè)體，共N個(gè)，按照自適應(yīng)變異 公式計(jì)算自適應(yīng)變異概率 ，隨機(jī)產(chǎn)生 R(0,1)，如果 則對(duì)該染色

40、體進(jìn)行交叉操作。 （7）計(jì)算由交叉和變異生成新個(gè)體的適應(yīng)度，新個(gè)體與 父代一起構(gòu)成新群體。 （8）判斷是否達(dá)到預(yù)定的迭代次數(shù)，是則結(jié)束；否則轉(zhuǎn) （4）。 m RP 9.3.3 自適應(yīng)遺傳算法 m P 65 3. 適應(yīng)的適應(yīng)的交叉概率與變異概率交叉概率與變異概率 avg , 2 avg avgmax max1 c , )( ffk ff ff ffk P avg4 avg avgmax max3 m , , )( ffk ff ff ffk P 9.3.3 自適應(yīng)遺傳算法 普通自適應(yīng)算法中，當(dāng)個(gè)體適應(yīng)度值越接近最大適應(yīng)度值 時(shí)，交叉概率與變異概率就越??；當(dāng)?shù)扔谧畲筮m應(yīng)度值時(shí)， 交叉概率和變異概率

41、為零。 改進(jìn)的思想：當(dāng)前代的最優(yōu)個(gè)體不被破壞，仍然保留（最 優(yōu)保存策略）；但較優(yōu)個(gè)體要對(duì)應(yīng)于更高的交叉概率與變異 概率。 66 F自適應(yīng)方法自適應(yīng)方法： 9.3.3 自適應(yīng)遺傳算法 3. 自適應(yīng)的交叉概率與變異概率（續(xù)）自適應(yīng)的交叉概率與變異概率（續(xù)） max2 0 cc ffPP當(dāng)，； max2 0 mm ffPP當(dāng)，。 avg , 1 c avg avgmax avg 2c1c 1c c , )( ffP ff ff ffPP P P avgm1 avg avgmax max2m1m 1m m , , )( ffP ff ff ffPP P P 1212 0.9,0.6,0.1,0.001

42、 ccmm PPPP 67 avg ,2 avg avgmax max 1 c ), 2 sin( ffk ff ff ff k P avg,4 avg avgmax max 3 m ), 2 sin( ffk ff ff ff k P 9.3.3 自適應(yīng)遺傳算法 S自適應(yīng)方法自適應(yīng)方法： 3. 自適應(yīng)的交叉概率與變異概率（續(xù)）自適應(yīng)的交叉概率與變異概率（續(xù)） 1234 1.0,1.0,0.5,0.5,kkkk 68 avg ,2 avg avgmax max 1 c ), 2 cos(1 ffk ff ff ff k P avg,4 avg avgmax max 3 m ), 2 cos(1

43、 ffk ff ff ff k P 9.3.3 自適應(yīng)遺傳算法 3. 自適應(yīng)的交叉概率與變異概率（續(xù)）自適應(yīng)的交叉概率與變異概率（續(xù)） C 自適應(yīng)方法自適應(yīng)方法： 1234 1.0,1.0,0.5,0.5,kkkk 69 第9章 遺傳算法及其應(yīng)用 o 9.1 遺傳算法的產(chǎn)生與發(fā)展遺傳算法的產(chǎn)生與發(fā)展 o 9.2 遺傳算法的基本算法遺傳算法的基本算法 o 9.3 遺傳算法的改進(jìn)算法遺傳算法的改進(jìn)算法 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法基于遺傳算法的生產(chǎn)調(diào)度方法 70 9.4 基于遺傳算法的生產(chǎn)調(diào)度方法 9.4.1 基于遺傳算法的流水車間調(diào)度方法基于遺傳算法的流水車間調(diào)度方法 9.4.2 基于遺傳

44、算法的混合流水車間調(diào)度方法基于遺傳算法的混合流水車間調(diào)度方法 71 1. 流水車間調(diào)度問題流水車間調(diào)度問題 ), 1;, 1(mjnitij 問題描述：n 個(gè)工件要在 m 臺(tái)機(jī)器上加工，每個(gè) 工件需要經(jīng)過 m 道工序，每道工序要求不同的機(jī)器， n 個(gè)工件在 m 臺(tái)機(jī)器上的加工順序相同。工件在機(jī)器 上的加工時(shí)間是給定的，設(shè)為 問題的目標(biāo)：確定 n 個(gè)工件在每臺(tái)機(jī)器上的最優(yōu)加 工順序，使最大流程時(shí)間達(dá)到最小。 9.4.1 基于遺傳算法的流水車間調(diào)度方法 72 1. 流水車間流水車間調(diào)度問題調(diào)度問題 假設(shè)假設(shè)： (1) 每個(gè)工件在機(jī)器上的加工順序是給定的。 (2) 每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。 (

45、3) 一個(gè)工件不能同時(shí)在不同的機(jī)器上加工。 (4) 工序不能預(yù)定。 (5) 工序的準(zhǔn)備時(shí)間與順序無關(guān)，且包含在加工時(shí)間中。 (6) 工件在每臺(tái)機(jī)器上的加工順序相同，且是確定的。 9.4.1 基于遺傳算法的流水車間調(diào)度方法 73 1. 流水車間調(diào)度問題流水車間調(diào)度問題 9.4.1 基于遺傳算法的流水車間調(diào)度方法 問題的數(shù)學(xué)模型：問題的數(shù)學(xué)模型： 個(gè)工件、 臺(tái)機(jī)器的流水車間調(diào)度問題的完工時(shí)間： ，上的加工完工時(shí)間在機(jī)器：工序 ),(kjkjc ii ：工件的調(diào)度 , 21n jjj 11 1 )1 ,( j tjc mktkjckjc kj ,.,2,) 1,(),( 1 11 nitjcjc i

46、 jii ,.,2,) 1 ,() 1 ,( 11 mknitkjckjckjc kjiii i ,.,2;,.,2,)1,(),(max),( 1 ),( max mjcc n 最大流程時(shí)間： nm 最小使得調(diào)度目標(biāo)：確定 max21 ,cjjj n 74 2. 求解流水車間調(diào)度求解流水車間調(diào)度問題的遺傳算法設(shè)計(jì)問題的遺傳算法設(shè)計(jì) （1） FSP的編碼方法的編碼方法 對(duì)于FSP，最自然的編碼方式是用染色體表示工件的順 序。 9.4.1 基于遺傳算法的流水車間調(diào)度方法 對(duì)于有四個(gè)工件的FSP，第 個(gè)染色體 ，表示工 件的加工順序?yàn)椋?。 k4 , 3 , 2 , 1 k v 43, 21 ,j

47、jjj 75 2. 求解流水車間調(diào)度問題求解流水車間調(diào)度問題的遺傳算法設(shè)計(jì)的遺傳算法設(shè)計(jì) （2）FSP的適應(yīng)度函數(shù)的適應(yīng)度函數(shù) : 個(gè)染色體 的最大流程時(shí)間， FSP的適應(yīng)度函數(shù)： k cmax k k v k k c veval max 1 )( 9.4.1 基于遺傳算法的流水車間調(diào)度方法 76 3. 求解求解FSP的遺傳算法實(shí)例的遺傳算法實(shí)例 例例1 1 Ho 和 Chang(1991) 給出的5個(gè)工件、4臺(tái)機(jī)器問 題。 j 1 j t 2j t 3j t 4j t 工件 1 31 412530 2 19 55334 32342276 413221413 53355719 加工時(shí)間表加工時(shí)

48、間表 9.4.1 基于遺傳算法的流水車間調(diào)度方法 77 用遺傳算法求解。選擇交叉概率 ，變異概 ,種群 規(guī)模為20，迭代次數(shù) 。 6 . 0 c p 1 . 0 m p 50N 表9.3 遺傳算法運(yùn)行的結(jié)果 總運(yùn)行 次數(shù) 最好解 最壞解平均 最好解 的頻率 最好解的 平均代數(shù) 20213221 213.950.8512 9.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é)果遺傳算法運(yùn)行的結(jié)果 78 表9.3 遺傳算法運(yùn)行的結(jié)果 最優(yōu)解收斂圖最優(yōu)解收斂圖

49、9.4.1 基于遺傳算法的流水車間調(diào)度方法 79 平均值收斂圖平均值收斂圖 9.4.1 基于遺傳算法的流水車間調(diào)度方法 80 機(jī)器甘特圖機(jī)器甘特圖 9.4.1 基于遺傳算法的流水車間調(diào)度方法 81 9.4.2 基于遺傳算法的混合流水車間調(diào)度方法 1. 混合流水混合流水車間調(diào)度問題車間調(diào)度問題 問題的特征問題的特征：在某些工序上存在并行機(jī)器并行機(jī)器。 問題的描述問題的描述：需要加工多個(gè)工件，所有工件的加工 路線都相同，都需要依次通過幾道工序，在所有工序 中至少有一個(gè)工序存在著多臺(tái)并行機(jī)器。 需要解決的問題需要解決的問題：確定并行機(jī)器的分配情況確定并行機(jī)器的分配情況以及同同 一臺(tái)機(jī)器上工件的加工排

50、序一臺(tái)機(jī)器上工件的加工排序。 目標(biāo)目標(biāo)：最小化最大流程時(shí)間。 82 假設(shè)加工 個(gè)工件，每個(gè)工件都要依次經(jīng)過 個(gè)加工工序， 每個(gè)工序的并行機(jī)器數(shù)為 ， 。所有工序中至少有一 個(gè)工序存在并行機(jī)，即至少有一個(gè) 大于1。 NS i M ), 1(Si i M SNSS N N NS aaa aaa aaa A 21 22221 11211 9.4.2 基于遺傳算法的混合流水車間調(diào)度方法 2. 混合流混合流水車間調(diào)度問題的遺傳算法編碼方法水車間調(diào)度問題的遺傳算法編碼方法 HFSP的編碼矩陣的編碼矩陣 ： 上的一個(gè)實(shí)數(shù)，表 示 工件的第 個(gè)工序在第 臺(tái)并行機(jī)上加工。 ：多個(gè)工件 在同一臺(tái)機(jī)器上加工同一個(gè)工

51、序 ij a ) 1, 1 ( i M j i )( ij aInt kjaIntaInt ikij , )()( 83 ，按 的升序來加工工件。 ，根據(jù)每個(gè)工件的前一個(gè)工序的完成時(shí)間來確定其 加工順序，前一個(gè)工序先完成的先加工。 假如完成時(shí)間相同，也按 的升序來加工。 1i 1i j a1 ij a 9.4.2 基于遺傳算法的混合流水車間調(diào)度方法 染色體的長度： 。 1NNS , 0 , 0 , 0 , 2122111211SNSSNNk aaaaaaaaInd 染色體：染色體： 84 o 例如，對(duì)于有3個(gè)工件個(gè)工件、3道工序道工序、各工序的并行機(jī)器數(shù)并行機(jī)器數(shù) 分別為3，2，2的混合流水車間調(diào)度問題。 9.4.2 基于遺傳算法的混合流水車間調(diào)度方法 2 . 14 . 21 . 1 3 . 21 . 26 . 1 9 . 14 . 21 . 2 A 染色體染色體： 2.1，2.4，1.9，0，1.6，2.1，2.3，0，1.1，2.4，1.2 編碼矩陣編碼矩陣： 工序1工序2工序3