1、2018屆工業(yè)工程專業(yè)畢業(yè)論文答辯考慮并行機(jī)的流水車間調(diào)度問(wèn)題研究答辯人：邱兵指導(dǎo)導(dǎo)師：巴黎老師2018年6月28日目錄CONTENTS遺傳算法基本理論仿真分析緒論柔性流水車間調(diào)度柔性流水車間遺傳算法設(shè)計(jì)總結(jié)與展望Part1緒論1-1 選題背景及意義1-2 研究現(xiàn)狀綜述選題背景及意義 選題背景1. 用戶對(duì)于產(chǎn)品的需要更加多元化和個(gè)性化，多品種、小批量生產(chǎn)方式成為占市場(chǎng)主 要份額的重要生產(chǎn)方式，使得企業(yè)生產(chǎn)過(guò)程更加的復(fù)雜，生產(chǎn)要素急劇增加，企業(yè) 生產(chǎn)管理變得越來(lái)越困難。2. 隨著經(jīng)濟(jì)全球化，市場(chǎng)競(jìng)爭(zhēng)日趨激烈，制造企業(yè)要想取得長(zhǎng)足的發(fā)展，獲得最大的 效益，必須提高企業(yè)響應(yīng)速度和生產(chǎn)效率、提高產(chǎn)品質(zhì)

2、量并且減少生產(chǎn)成本。 選題意義合理的調(diào)度方法可以合理地分配和使用企業(yè)生產(chǎn)資源，降低企業(yè)固定成本，提高資金周轉(zhuǎn)效率，提高設(shè)備利用效率，縮短生產(chǎn)周期，降低生產(chǎn)成本。第 4 頁(yè)選題背景及意義 考慮并行機(jī)的流水車間調(diào)度問(wèn)題流水車間調(diào)度問(wèn)題是生產(chǎn)調(diào)度中的一個(gè)重要的研究部分，制造業(yè)實(shí)際生產(chǎn)中，為提高機(jī)器的使用效率及生產(chǎn)效率，增加制造系統(tǒng)的柔性，同一工序往往設(shè)置多臺(tái)可選的機(jī)器， 為提高流水車間問(wèn)題的實(shí)際研究意義，本文提出一種考慮并行機(jī)的流水車間調(diào)度問(wèn)題，該問(wèn)題也稱為柔性流水車間調(diào)度問(wèn)題。與傳統(tǒng)車間調(diào)度相比，柔性流水車間調(diào)度更接近實(shí)際的車間調(diào)度情況，其在離散制造和流程工業(yè)中具有十分廣泛的應(yīng)用，如化工制藥，汽車

3、制造，鋼鐵冶金等行業(yè)。第 5 頁(yè)調(diào)度算法研究現(xiàn)狀調(diào)度問(wèn)題調(diào)度系統(tǒng)由于流水車間調(diào)度問(wèn)題是一個(gè)NP難問(wèn)題，因此很難用傳統(tǒng)的優(yōu)化算法求解。雖然在一個(gè)合理的時(shí)間內(nèi)，近似啟發(fā)式可以產(chǎn)生令人更滿意的調(diào)度方案，但它常常不能評(píng)估所得到的調(diào)度解決方案的次優(yōu)性。因此，有必要探索一種可以通過(guò)增加合理的計(jì)算時(shí)間來(lái)增加解次優(yōu)性的近似最優(yōu)調(diào)度算法。研究現(xiàn)狀綜述流水車間調(diào)度優(yōu)化問(wèn)題是一類具有柔性、動(dòng)態(tài)、模糊和多目標(biāo)優(yōu)化等問(wèn)題的NP難題，在實(shí)際車間調(diào)度中，生產(chǎn)計(jì)劃和調(diào)度往往是分層的，就將可能會(huì)導(dǎo)致不可行的調(diào)度。采用大數(shù)據(jù)處理技術(shù)將調(diào)度與計(jì)劃智能融合，實(shí)現(xiàn)真正的智能調(diào)度，需要進(jìn)一步的研究。根據(jù)目前調(diào)度理論的發(fā)展情況來(lái)看，經(jīng)典的

4、調(diào)度算法依然是研究調(diào)度問(wèn)題的基本方法，同時(shí)智能的調(diào)度算法發(fā)展的十分迅速，對(duì)于求解調(diào)度問(wèn)題具有很好的效果。將兩者相互融合將會(huì)成為一種趨勢(shì)。第 6 頁(yè)柔性流水1-1柔性流水車間調(diào)度建模Part2車間調(diào)度1-2常用調(diào)度算法分析比較第 8 頁(yè)柔性流水車間調(diào)度建模本文討論不相關(guān)并行機(jī)性流水車間調(diào)度，已知各個(gè)工件的每道工序在其不同并行機(jī)上的加工時(shí)間， 要求求出各個(gè)工件在每道工序上并行機(jī)的分配情況及在每個(gè)機(jī)器上的加工順序，使得最大完工時(shí)間最小化。圖2-2給出了柔性流水車間調(diào)度的示意圖。本文對(duì)不相關(guān)并行機(jī)柔性流水車間調(diào)度問(wèn)題進(jìn)行建模， 數(shù)學(xué)模型如下：式(2-1)為調(diào)度性能指標(biāo)。血 n Cmax(2-1)式(2

5、-2)確保每個(gè)優(yōu)先級(jí)位置只能對(duì)應(yīng)一個(gè)工件。式(2-3)確保每個(gè)工件只有一個(gè)優(yōu)先級(jí)位置。21mjYi,j,kLi=l芍， l = 1,l= l,2,.,n汀1 坊， i =l,i=I,2,.,n= 1,i =I,2,.,n; j= I, 2,., S( 2-2)( 2-3)( 2-4 )式(2-4)表示任一工序每個(gè)工件只能在一臺(tái)機(jī)器上加工。免j , k 飛， j , k + ti,j,k,i = I,2,.,n;j = I,2,., S;k= I,2,. .， 嘰式(2-5)表示同一工序上完成時(shí)間和開(kāi)始時(shí)間的關(guān)系。ei,j,ksi,j+l,ki= I, 2,.,n; j=I,2,.S-1;k=I

6、,2,.，嘰 ；k= I,2,式(2-6)表示同一工件不同工序間的先后制約關(guān)系。( 2-5 )，辦l( 2-6)罵1坊，應(yīng)1,K I f=1均， i+ i s i,1,k,i=l,2,.,n;l=l,2,.,n-l;k=l,2,.,m1( 2-7)式(2-7)表示在第一個(gè)工序調(diào)度排列中， 排位越前的工件開(kāi)始處理時(shí)間越早。罵兇l凇j ,k免j ,K 三 I f=1 坊，切i,j,k勻， j ,k+(1 罵1 芍， l2 勸， j ,k)L,Ipii= 1,2,.,n;/1 :; ;j=l,2,.S;k,k= 1,2,.,m(2-8)式 (2-8)表示同一階段分配在同一機(jī)器上的工件排位靠后的工件必

7、須等靠前的工牛加工完畢后才可進(jìn)行加工， 當(dāng)處于不同位置的工件不在同一階段的同一機(jī)器上加工時(shí)， 式(8)中L數(shù)值較大以保證不等式恒成立。第 9 頁(yè)常用調(diào)度算法分析比較AA精確算法雖然這些基于運(yùn)籌學(xué)的算法理論上在求解車間調(diào)度問(wèn)題能夠得到較好的解，但是往往其存在一定程度的枚舉，同時(shí)車間調(diào)度問(wèn)題的模型往往比較復(fù)雜，難以簡(jiǎn)化，導(dǎo)致計(jì)算量增大。BB近似算法啟發(fā)式算法具有計(jì)算簡(jiǎn)單且容易實(shí)現(xiàn)的優(yōu)點(diǎn)，但是往往將啟發(fā)式算法與其他算法相結(jié)合才能夠求出車間調(diào)度問(wèn)題的全局最優(yōu)解CC智能算法智能優(yōu)化算法對(duì)于大空間、全局尋優(yōu)、非線性、組合優(yōu)化等傳統(tǒng)優(yōu)化算法難以求解的問(wèn)題求解效率較高。目前主要的智能優(yōu)化方法有：模擬退火算法、

8、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法等。第 10 頁(yè)P(yáng)art3遺傳算法基本理論3-1 遺傳算法的概述3-2 遺傳算法的基本操作3-3 遺傳算法的參數(shù)設(shè)計(jì)遺傳算法概述基本思想遺傳算法是一種模擬自然進(jìn)化原理的多參數(shù)多群體并行優(yōu)化方法，它是給定一組初始解作為一個(gè)初始群體，通過(guò)選擇、交叉和變異等遺傳操作來(lái)搜索最優(yōu)解。 。缺點(diǎn)對(duì)于大規(guī)模組合優(yōu)化問(wèn)題，由于搜索空間大、搜索時(shí)間長(zhǎng)，往往會(huì)出現(xiàn)早熟收斂的情況，對(duì)初始種群很敏感，初始種群選擇不好會(huì)影響解的質(zhì)量和算法的效率。o ，應(yīng)用領(lǐng)域在函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、生產(chǎn)調(diào)度、模式識(shí)別、數(shù)據(jù)挖掘、圖像處理、神經(jīng)網(wǎng)絡(luò)、組合優(yōu)化及社會(huì)12科學(xué)等領(lǐng)域應(yīng)用的非常廣泛。遺傳43算法

9、優(yōu)點(diǎn)遺傳算法由于具有高效、簡(jiǎn)單、實(shí)用、魯棒性強(qiáng)等特點(diǎn)，良好的自適應(yīng)性、高效、并行和全局搜索的特點(diǎn)。第 12 頁(yè)遺傳算法的基本操作 選擇操作選擇操作是從父代種群中選擇出較優(yōu)的個(gè)體，并將其復(fù)制，從而產(chǎn)生子代種群。選擇操作能夠有效的避免較優(yōu)個(gè)體的淘汰，使較優(yōu)個(gè)體能夠以較大的概率生存下來(lái)，通過(guò)選擇操作能夠提高算法的計(jì)算效率和全局收斂性。(1) 賭選擇(2)排名選擇(3)錦標(biāo)賽選擇(4)父子競(jìng)爭(zhēng) 交叉操作交二叉操作是將種群中的個(gè)體隨機(jī)組合，以某一概率交換他們的部分基因，從而產(chǎn)生新的個(gè)體，從而使得種群朝著優(yōu)化的方向進(jìn)化。交叉操作能變異操作夠有效的提高遺傳算法在可行解集中的搜索能力，同時(shí)降低了對(duì)可行解的破壞

10、程度。常用的交叉方法有：?jiǎn)吸c(diǎn)交叉、多點(diǎn)交叉、POX交叉和LOX交叉等。變?nèi)愃阕蛹词菍⑷后w中個(gè)體的染色體上的某些基因值以一定的概率發(fā)生改變。通過(guò)變異操作能夠增加解的多樣性，避免由于選擇和交叉操作導(dǎo)第 13 頁(yè)致的某些基因的永久丟失，從而有效地避免遺傳算法過(guò)早收斂和陷入局部最優(yōu)解，保證其的科學(xué)性和有效性。常用的遺傳算法變異方式有實(shí)值變異和二進(jìn)制變異。對(duì)于實(shí)值變異常用的變異方法是將某些基因值用取值范圍內(nèi)的其他隨機(jī)值替代。對(duì)于二進(jìn)制變異常用的方法是隨機(jī)地將某些基因值遺傳算法的參數(shù)設(shè)計(jì)迭代次數(shù)終止迭代代數(shù)是遺傳算法終止運(yùn)行的一個(gè)具體種群規(guī)模01種群規(guī)模過(guò)小可能會(huì)使遺傳算法過(guò)早的收斂和陷入局部最優(yōu)解，種

11、群規(guī)模過(guò)大將會(huì)導(dǎo)致遺傳算法的計(jì)算量大大增加，從而影響算法的計(jì)算效率。一般而言，種群規(guī)模應(yīng)設(shè)置在10-200的范圍內(nèi)。02參數(shù)交叉概率的參數(shù)。一般而言， 終止迭代代數(shù)設(shè)置在100- 1000之間。04設(shè)計(jì)變異概率交叉概率決定了交叉算子被使用的頻率，較大的交叉頻率將會(huì)使得遺傳操作找到許多新的解，從而在一定程度上避免遺傳算法陷入局部最優(yōu)解，但是交叉概率過(guò)高將可能導(dǎo)致有效的遺傳信息的丟失；同時(shí)交叉概率過(guò)低將會(huì)影響到遺傳算法的計(jì)算效率。一般而言，交叉概率設(shè)置在0.25-1.00之間。03變異操作是遺傳算法的輔助性操作，但是其對(duì)于保持種群多樣性具有十分重要的意義。變異概率較低時(shí)可以防止遺傳操作中重要信息的

12、丟失，變異概率較高時(shí)將會(huì)使遺傳算法趨于一般的隨機(jī)搜索方法。一般而言，變異概率設(shè)置在0.001-0.1之間。第 14 頁(yè)P(yáng)art4柔性流水車間遺傳算法設(shè)計(jì)4-1 算法基本操作設(shè)計(jì)4-2 算法流程圖1編碼方式本文采用基于操作的編碼方式，這種編碼方式的最大好處是子代的染色體編碼全部為可行解， 這樣能在很大的程度上降低算法的復(fù)雜度并且減小算法的計(jì)算量。下面介紹基于操作的編碼方 式的實(shí)現(xiàn)方法：以五個(gè)工件、四道工序和六臺(tái)機(jī)器，其中第二道和第三道工序分別存在兩臺(tái)并行機(jī)的流水車間調(diào)度為例，并行機(jī)編號(hào)及分配情況如表4-1所示：工序1工序2工序3工序4M1M2M4M3M5M6表4-1 并行機(jī)-工序分配表其編碼過(guò)程

13、為：Step1：初始化一個(gè)39的矩陣，此時(shí)矩陣中的元素均為0；Step2：初始化5個(gè)基因計(jì)數(shù)器j1、j2、j3、j4、j5分別對(duì)應(yīng)基因1、2、3、4、5，用于記錄已經(jīng)填入染色體的同一個(gè)基因的個(gè)數(shù)；一個(gè)總計(jì)數(shù)器counter，用于記錄總插入次數(shù)。此時(shí)它們均為0；Step3：判斷counter是否為20，若是，則一個(gè)染色體生成完畢，程序結(jié)束，否則進(jìn)入Step4； Step4：生成一個(gè)在1，5之間的隨機(jī)數(shù)i，并將這個(gè)隨機(jī)數(shù)與1、2、3、4、5相比較，若i=1，則先讀取出j1的值，若j1=0，則Mj=1；若j1=1，則Mj= 2或4；若j1=2，則Mj= 3或5；若j1=3，則Mj=6；然后將Mj 插

14、入到同列的第二行， 然后將對(duì)應(yīng)的加工時(shí)間插入到同列的第三行， 并令j1= j1+1 ， counter=counter+1。若j1等于4，則返回Step3；2，3，4和5的情況與1同理。通過(guò)以上步驟可成功生成一個(gè)可行染色體，我們只需加一些循環(huán)條件即可生成任意個(gè)初始染色體，以組成初始種群。第 16 頁(yè)算法的基本操作設(shè)計(jì)第 17 頁(yè)解碼方式本文采用半主動(dòng)解碼方法，通過(guò)解碼，我們可以得到每個(gè)染色體對(duì)應(yīng)的完工時(shí)間、工件排列陣、以及數(shù)字化Gantt圖。交叉方法對(duì)于不同的編碼方式，應(yīng)采用與之相應(yīng)的交叉算子。本文采用基于操作的編碼方式，雖然基于操作編碼的交叉具有子代都是可行的這一優(yōu)點(diǎn)，但編碼相鄰基因沒(méi)有表現(xiàn)

15、出每臺(tái)機(jī)器上工序次序的特性，造成許多基于工序的編碼交叉不能繼承父代的優(yōu)良特性。本文采用POX交叉，它能夠很好地繼承父代優(yōu)良特征，并且子代總是可行的。具體程序段如下：設(shè)父代長(zhǎng)度為nm。染色體Parent 1與Parent 2，POX交叉產(chǎn)生后代Children 1和Children 2，交叉的具體步驟為： Step1:隨機(jī)劃分工件集1，2，n（n為工件序列號(hào)）為兩個(gè)非空的集合J1和J2。Step2:復(fù)制Parent1包含在J1的工件到Children 1，Parent 2包含在J1的工件到Children 2，保留它們的位置。Step3:復(fù)制Parent 2包含在J2的工件到Children 1

16、，Parent 1包含在J2的工件到Children 2，保留它們的順序第。18 頁(yè)下面以33問(wèn)題為例，來(lái)說(shuō)明兩父代的交叉過(guò)程。變異方法變異操作的作用是增加個(gè)體的多樣性，保證算法的全局搜索能力，有效地避免了遺傳算法過(guò)早收斂和陷入局部最優(yōu)解。本文擬采用兩種變異方法（工序變異和機(jī)器變異）相結(jié)合的遺傳算子，新的算子增大了變異的多樣性和隨機(jī)性。其具體的步驟如下：第 19 頁(yè)算法流程設(shè)計(jì)開(kāi)始初始化N個(gè)個(gè)體初始化n=0計(jì)算出N個(gè)染色體的完工時(shí)間找出這一代個(gè)體中的最優(yōu)解Y是否為第一代個(gè)體 將其設(shè)定為臨時(shí)最優(yōu)解N與得到的臨時(shí)最優(yōu)解比較，將完工時(shí)間最小的設(shè)定為臨時(shí)最優(yōu)解初始化m=0采用錦標(biāo)賽選擇法選出兩個(gè)個(gè)體產(chǎn)

17、生隨機(jī)數(shù)a0,1Na Pc 視之為兩臨時(shí)個(gè)體對(duì)選出的兩個(gè)體進(jìn)行POX交叉，將子代作為兩臨時(shí)個(gè)體Y產(chǎn)生隨機(jī)數(shù)b0,1Nb Pm m=m+1Y采用工序變異，變異一個(gè)臨時(shí)個(gè)體，令m=m+1產(chǎn)生隨機(jī)數(shù)c0,1NcPm m=m+1Y采用機(jī)器變異，變異另一個(gè)臨時(shí)個(gè)體，令m=m+1放入新種群Nm=NYn=n+1Nn=MY選出第M代中完工時(shí)間最小的，與臨時(shí)最優(yōu)解相比，完工時(shí)間最小的即為最終的最優(yōu)解第 20 頁(yè)設(shè)種群規(guī)模N，進(jìn)化代數(shù)M。算法的流程圖如圖4-2所示，具體的步驟如下：Step1：初始化N個(gè)個(gè)體，作為初始種群； Step2：初始化n=0（當(dāng)n=M時(shí)則算法結(jié)束）；Step3 ： 通過(guò)解碼， 算出這N個(gè)染

18、色體的完工時(shí)間（ 同時(shí)已得到對(duì)應(yīng)的工件排列陣和“ 數(shù)字化”Gantt圖）；Step4：通過(guò)比較完工時(shí)間，找出這一代中的最優(yōu)解，若為第一代，則視這一最優(yōu)解為臨時(shí)的最優(yōu)解，否則使本代中的最優(yōu)解與已得到的臨時(shí)最優(yōu)解相比較，取完工時(shí)間最小的為新的臨時(shí)最優(yōu)解；Step5：初始化m=0（當(dāng)m=N時(shí)相當(dāng)于生成了一個(gè)新種群）； Step6：用錦標(biāo)賽選擇法對(duì)這N個(gè)個(gè)體進(jìn)行選擇（選兩個(gè)）；Step7：對(duì)于選出的兩個(gè)體，先產(chǎn)生一個(gè)隨機(jī)數(shù)a0，1，若a Pc，則對(duì)其進(jìn)行POX交叉，產(chǎn)生的兩個(gè)子代作為臨時(shí)個(gè)體；反之則認(rèn)為此兩個(gè)個(gè)體為臨時(shí)個(gè)體；Step8：產(chǎn)生一個(gè)隨機(jī)數(shù)b0，1，若bPm，則對(duì)一個(gè)臨時(shí)個(gè)體進(jìn)行變異(工序變

19、異)，然后放入新種群，并令m=m+1，反之直接放入新種群，并令m=m+1；再產(chǎn)生一個(gè)隨機(jī)數(shù)c0，1，若c Pm，則對(duì)另一個(gè)的臨時(shí)個(gè)體進(jìn)行變異（機(jī)器變異），然后放入新種群，并令m=m+1，反之直接放入新種群，并令m=m+1；Step9：循環(huán)執(zhí)行Step6，7，8直到m=N（即產(chǎn)生了一個(gè)完整的新種群），令n=n+1；Step10：跳回Step3繼續(xù)，直到n=M，找出第M代種群中的最優(yōu)解，并將其對(duì)應(yīng)的完工時(shí)間與臨時(shí)最優(yōu)解對(duì)應(yīng)的完工時(shí)間相比較，最小的即成為最終的最優(yōu)解，此過(guò)程結(jié)束。第 21 頁(yè)P(yáng)art5仿真分析5-1 實(shí)例描述5-2 仿真分析如表5-1所示，為一個(gè)5個(gè)工件，6臺(tái)機(jī)器，4道工序的柔性流水

20、車間調(diào)度。其中工序2和工序3均含有兩臺(tái)并行機(jī)，且并行機(jī)的性能并不一樣，加工時(shí)間也不一樣，工件在含有并行機(jī)的工序上可以選擇任意一臺(tái)機(jī)器進(jìn)行加工；這個(gè)問(wèn)題為不相關(guān)并行機(jī)柔性流水車間調(diào)度問(wèn)題；以最大完工時(shí)間作為本調(diào)度問(wèn)題唯一的性能指標(biāo)工件工序1工序2工序3工序4M1M2M4M3M5M61759977296881163586698411121012810569131199表5-1 柔性流水車間調(diào)度實(shí)例第 23 頁(yè)下面利用所編程序，對(duì)本章第一節(jié)所提的問(wèn)題進(jìn)行求解。(1) 遺傳算法參數(shù)選擇：種群規(guī)模M=200，進(jìn)化代數(shù)G=100，采用錦標(biāo)賽選擇法，錦標(biāo)賽選手個(gè)數(shù)為兩個(gè)，采用POX交叉，交叉工件數(shù)為兩個(gè)，交

21、叉概率Pc= 0.9，采用機(jī)器變異和工序變異，變異概率Pm=0. 1，目標(biāo)函數(shù)為最小化最大完工時(shí)間。(2) 仿真結(jié)果及其分析：采用microsoft visual studio軟件進(jìn)行仿真，每代最佳完工時(shí)間和平均完工時(shí)間的曲線如圖5-1所示。10090完工時(shí)間（min）80706050403020100從圖中可以看出這個(gè)實(shí)例的最優(yōu)解為63min，即對(duì)于這個(gè)流水車間調(diào)度問(wèn)題，它的總完工時(shí)間最短為63min；在第21次迭代時(shí)就已迭代出最優(yōu)解。由程序計(jì)算結(jié)果得到的“數(shù)字化”Gantt圖，如表5-2所示。16111621263136414651566166717681869196迭代次數(shù)每代最短完工時(shí)

22、間每代平均完工時(shí)間圖5-1 柔性流水車間調(diào)度問(wèn)題實(shí)例迭代圖第 24 頁(yè)表5-2 柔性車間調(diào)度問(wèn)題實(shí)例的每臺(tái)機(jī)器開(kāi)工完工數(shù)字序列由程序計(jì)算結(jié)果得到最優(yōu)解對(duì)應(yīng)編碼（工件/機(jī)器/工時(shí)），如表5-3所示：表5-3 柔性車間調(diào)度問(wèn)題實(shí)例的最優(yōu)解借助表5-2和表5-3可以畫(huà)出該問(wèn)題最優(yōu)解的Gantt圖，如圖5-2所示：表5-2 柔性車間調(diào)度問(wèn)題實(shí)例的每臺(tái)機(jī)器開(kāi)工完工數(shù)字序列機(jī)器開(kāi)工完工開(kāi)工完工開(kāi)工完工開(kāi)工完工開(kāi)工完工M106611111818292938M261518233844M317234452M411172939M523313140404747575763由程序計(jì)算結(jié)果得到最優(yōu)解對(duì)應(yīng)編碼（工件/機(jī)器

23、/工時(shí)），如表5-3所示：表5-3 柔性車間調(diào)度問(wèn)題實(shí)例的最優(yōu)解借助表5-2和表5-3可以畫(huà)出該問(wèn)題最優(yōu)解的Gantt圖，如圖5-2所示：工件號(hào)55531341341352412422機(jī)器號(hào)12511412345661562636工時(shí)(min)69957611561078998761086第 25 頁(yè)通過(guò)上述典型算例的仿真研究，得到以下結(jié)論：對(duì)于典型柔性流水車間調(diào)度問(wèn)題，遺傳算法得到了調(diào)度的最優(yōu)解。本算法對(duì)交叉算子進(jìn)行了改進(jìn)，使得算法收斂速度較快，只需要幾秒時(shí)間，就可以得到問(wèn)題的最優(yōu)解?？梢钥闯?，對(duì)遺傳算法操作算子進(jìn)行改進(jìn)，各算子參數(shù)進(jìn)行多次調(diào)試，可以使遺傳算法更加高效地解決調(diào)度問(wèn)題。第 26

24、 頁(yè)(3) 相關(guān)參數(shù)對(duì)迭代結(jié)果的影響1迭代次數(shù)：當(dāng)其他參數(shù)不變時(shí)，迭代次數(shù)分別為10，100，150時(shí)，迭代圖分別如圖5-3，圖5-4，圖5-5所示。迭代次數(shù)73每代完工時(shí)間（min）7271706968676665641234567891074每代完工時(shí)間（min）727068666462601611162126313641465156616671768186919658迭代次數(shù)74每代完工時(shí)間（min）7270686664626019172533414957657381899710511312112913714558迭代次數(shù)圖5-3 最優(yōu)完工時(shí)間曲線（迭代次數(shù)為10）圖5-4 最優(yōu)完工時(shí)間

25、曲線（迭代次數(shù)為100）圖5-5 最優(yōu)完工時(shí)間曲線（迭代次數(shù)為150）分析：根據(jù)以上3幅圖，不難看出，當(dāng)?shù)螖?shù)過(guò)小時(shí)會(huì)導(dǎo)致染色體未進(jìn)化 完全，從而得到的染色體也非最優(yōu)的；增加迭代次數(shù)可以避免上述問(wèn)題的產(chǎn)生。不過(guò)，迭代次數(shù)過(guò)大會(huì)導(dǎo)致計(jì)算機(jī)負(fù)荷加重，降低求解效率，所以通常情況下， 迭代次數(shù)都是在經(jīng)過(guò)多次實(shí)驗(yàn)才最終確定的。第 27 頁(yè)2種群規(guī)模：當(dāng)其他參數(shù)不變時(shí)，種群規(guī)模分別為50，200，400時(shí)，迭代圖分別如圖5-6，圖5-7，圖5-8所示。7472每代完工時(shí)間（min）每代完工時(shí)間（min）717270706968686766666564646263626061161116212631364

26、14651566166717681869196161116212631364146515661667176818691965860迭代次數(shù)迭代次數(shù)圖5-6 最優(yōu)完工時(shí)間曲線（種群規(guī)模為50圖5-7 最優(yōu)完工時(shí)間曲線（種群規(guī)模為200）圖5-8 最優(yōu)完工時(shí)間曲線（種群規(guī)模為400）分析：根據(jù)以上3幅圖，可以看出，種群規(guī)模過(guò)小可能會(huì)使遺傳算法過(guò)早的收斂和陷入局部最優(yōu)解；種群規(guī)模的擴(kuò)大可以保證種群的多樣性，種群規(guī)模過(guò)大將會(huì)導(dǎo)致遺傳算法的計(jì)算量大大增加，從而影響算法的計(jì)算效率。對(duì)于實(shí)際的問(wèn)題，仍需要多次實(shí)驗(yàn)，方可最終確定種群規(guī)模。第 28 頁(yè)交叉概率：當(dāng)其他參數(shù)不變時(shí)，交叉概率分別為0.6，0.9，0

27、.95時(shí)，迭代圖分別如圖5-9，圖5-10，圖5-11所示每代完工時(shí)間（min）787674727068661611162126313641465156616671768186919664迭代次數(shù)圖5-9 最優(yōu)完工時(shí)間曲線（交叉概率為0.6）圖5-10 最優(yōu)完工時(shí)間曲線（交叉概率為0.9）圖5-11 最優(yōu)完工時(shí)間曲線（交叉概率為0.95）分析：根據(jù)以上3幅圖，可以看出，隨著交叉概率的增加， 種群的多樣性也會(huì)適當(dāng)增加，達(dá)到最優(yōu)解所需要的迭代次 數(shù)將會(huì)增加，從而在一定程度上避免遺傳算法陷入局部最 優(yōu)解，但是交叉概率過(guò)高將可能導(dǎo)致有效的遺傳信息的丟 失，如果這兩父代已經(jīng)是非常優(yōu)秀的個(gè)體，那么經(jīng)過(guò)交叉

28、 可能反而使得兩父代的優(yōu)越性降低。同時(shí)交叉概率過(guò)低將 會(huì)影響到遺傳算法的計(jì)算效率。第 29 頁(yè)變異概率：當(dāng)其他參數(shù)不變時(shí)，變異概率分別為0，0.1，1.0時(shí)，迭代圖分別如圖5-12，圖5-13，圖5-14所示。78每代完工時(shí)間（min）7476每代完工時(shí)間（min）72747072686670646862661611162126313641465156616671768186919660641611162126313641465156616671768186919658迭代次數(shù)迭代次數(shù)圖5-12 最優(yōu)完工時(shí)間曲線（變異概率為0）圖5-13 最優(yōu)完工時(shí)間曲線（變異概率為0.1）圖5-14 最優(yōu)完工時(shí)間曲線（變異概率為1.0）分析：根據(jù)以上3幅圖，可以看出，變異概率較低時(shí)可以防止遺傳操作中重要信息的丟失，但是種群的多樣性會(huì)降低，可能使遺傳算法過(guò)早的收斂