遺傳算法在作業(yè)車間調(diào)度問題中的應(yīng)用——先進制造管理作業(yè)

1、先進制造管理報告遺傳算法在作業(yè)車間調(diào)度問題中的應(yīng)用專業(yè)：管理科學(xué)與工程時間：2015年1月遺傳算法在作業(yè)車間調(diào)度問題中的應(yīng)用1 作業(yè)車間調(diào)度問題所謂生產(chǎn)調(diào)度，即對生產(chǎn)過程進行作業(yè)計劃，作為一個關(guān)鍵模塊，是整個先進生產(chǎn)制造系統(tǒng)實現(xiàn)管理技術(shù)、運籌方法、優(yōu)化技術(shù)、自動化與計算機技術(shù)發(fā)展的核心，有效的調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用，是實現(xiàn)先進制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。作業(yè)車間調(diào)度（job-shop）問題可以表述為：設(shè)有N個工件在M臺機器上加工，根據(jù)工件加工工藝的要求，每個工件使用機器的順序及其每道工序所花時間已給定，調(diào)度問題的目標(biāo)就是如何選擇加工順序使得總的加工時間最短最優(yōu)。前提假設(shè)：1. 每一

2、臺機器每次只能加工一個工件，每一個工件在機器上的加工被成為一道工序。2. 不同工件的加工工序可以不同；3. 所有工件的工序數(shù)不大于設(shè)備數(shù)；4. 每道工序必須在指定的某種設(shè)備上加工；5. 任何作業(yè)沒有搶先加工的優(yōu)先權(quán)；6. 在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件；車間作業(yè)是指利用車間資源(如機床、刀具、夾具等)完成的某項任務(wù)。在實際生產(chǎn)中，這項任務(wù)可能是裝配一種產(chǎn)品，也可能是完成一批工件的加工。而在本文中，為了研究方便，我們將這項任務(wù)限定為加工一批工件。在此基礎(chǔ)上，可對車間作業(yè)調(diào)度問題進行一般性的描述:假定有多個工件，要經(jīng)過多臺機器加工。一個工件在一臺機器上的加工程序稱為一道“工序”

3、，相應(yīng)的加工時間稱為該工序的“加工時間”。用事先給定的“加工路線”表示工件加工時技術(shù)上的約束，即工件的加工工藝過程。用“加工順序”表示各臺機器上各個工件加工的先后順序。車間作業(yè)調(diào)度問題中，每個工件都有獨特的加工路線。它所要解決的問題就是確定每臺機器上不同工件的加工順序，以及每個工件的所有工序的起始加工時間，以最優(yōu)化某個性能指標(biāo)。然而，車間調(diào)度是一個 NP-Hard 問題，運用窮舉法又會大大增加計算量，所以考慮利用遺傳算法求解。1.1 車間作業(yè)調(diào)度問題研究的假設(shè)條件在研究一般的車間作業(yè)調(diào)度問題中往往需要明確兩類重要假設(shè)條件:1.工藝路徑約束:工件的任一工序必須在其前道工序完成后才能開始，并保證同

4、一工件不會同時在兩臺機器上加工，反映了工件不同工序間的時序關(guān)系;2.資源(機器)獨占性約束:任一臺機器每次只能加工一個工件，且一旦開工就不能中斷，反映了加工隊列中工件間的時序關(guān)系。此外，還有一些輔助假設(shè)條件，如下:1. 各工件經(jīng)過其準(zhǔn)備時間后可開始加工;2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒有優(yōu)先約束關(guān)系限制的;3. 工序允許等待，即前一個工序未完成，則后面工序需要等待;4. 所有機器處理的加工類型均不同;5. 工件的加工時間事先給定，且在整個加工過程中保持不變;6. 緩沖區(qū)容量為無窮大。1.2 車間作業(yè)調(diào)度問題的數(shù)學(xué)模型設(shè)有n個工件，要在m臺機器上加工，每個工件有Pi道工序，每臺機器上總

5、共要加工Lj道工序。定義如下：J:所有工件的集合，； M:所有機器的集合，；：工件Ji的工序集合，；P:所有工序的集合，此為矩陣。P（i，j）表示i工件的第j道工序。，表示i工件的所有工序按優(yōu)先順序的排列。不足則置零。 （1.1）:機器順序陣，此為矩陣。（i，j）表示i工件的第j道工序的機器號，表示i工件的所有工序按優(yōu)先順序加工的各機器號的排列。若某工件的工序數(shù)不足則置零。 （1.2）T:加工時間陣，此為矩陣。T(i, j)表示工件i的第j道工序在（i，j）上的加工時間。同樣地，如果某工件的工序數(shù)不足則置零。 （1.3） ：工件排列陣，此為矩陣。表示在i機器上排在第j位加工的工件號，表示i機器

6、上依次加工的各工件的排列。同上，如果某工件的工序數(shù)不足則置零。事實上，工件排列陣就是調(diào)度的一種表示形式。由此，我們可以給出一般性的車間作業(yè)調(diào)度數(shù)學(xué)模型的定義:如果對應(yīng)于一個確定的，滿足或。即使得目標(biāo)函數(shù)取值最小(或最大)，且與相容，則稱為車間作業(yè)調(diào)度問題在此目標(biāo)函數(shù)下的最優(yōu)解。生產(chǎn)調(diào)度問題存在多種優(yōu)化目標(biāo)或者綜合優(yōu)化目標(biāo)，調(diào)度問題的優(yōu)化目標(biāo)通常從兩個方面來考慮:生產(chǎn)成本和生產(chǎn)時間。調(diào)度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標(biāo)有:庫存最少、在制品最少、設(shè)備利用率最高等;從生產(chǎn)時間方面來考慮，其優(yōu)化目標(biāo)有:最大程度滿足交貨期、最小完成時間、最小流動時間和最小等待時間等。2 遺傳算法遺傳算法(Genet

7、ic Algorithm, GA)是一種基于自然群體遺傳演化機制的高效探索算法，它是美國學(xué)者Holland于1975年首先提出來的。它摒棄了傳統(tǒng)的搜索方式，模擬達爾文的遺傳選擇和自然淘汰的生物進化過程。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復(fù)進行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進行評價，依據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。2.1 遺傳算法的基本思路1.首先確定問題的求解空間；2.其次將求解空間中的每一個點進行編碼，并

8、從求解空間中任選N個點組成初始群體；3.計算當(dāng)前群體中每個個體的適應(yīng)度函數(shù)值。運用選擇、交叉、變異算子產(chǎn)生新一代群體；4.對新一代群體中的個體進行評價，若找到滿足問題的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)步驟3。2.2 遺傳算法的模式定理1.選擇操作對模式的影響選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級增長。最常用的選擇方式是“輪盤賭”法。其傳統(tǒng)實現(xiàn)建立在逐項比較的基礎(chǔ)上，算法復(fù)雜度為O（n2）。通過把各碼鏈適應(yīng)值轉(zhuǎn)換為一組具有線性序的區(qū)間，從而可利用二分查找法實現(xiàn)“輪盤賭”選擇操作的遞歸算法，使時間復(fù)雜度下降到O（nlog2n）。2.交換操作對模式的影響交換操作是有規(guī)則

9、的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過程所選擇的高適應(yīng)度的模式。假設(shè)交換操作是采用的單點隨機雜交方式，隨機選取雜交的起始位置，交叉概率為Pc，兩個具有相同模式H的個體發(fā)生交換，即雜交操作，不會改變模式H。但是如果其中一方個體不具有模式H，則有可能會引起另一個個體模式的改變。其中一方不具有模式H的概率為1- p(H, t)，當(dāng)兩個個體發(fā)生交換時，如果引起模式H的改變，只可能將交換的起始位置選擇在第一個模式位到最后一個模式位之間的任何一個位置上，此時，使模式H生存的概率Ps，為:(2.1)在交換過程中，可能使兩個都不具備模式H的個體經(jīng)交換后產(chǎn)生模式H，故生存概率（）只是一個

10、下界，則有：(2.2)綜合考慮選擇操作，模式H在下一代中的數(shù)量可以用下式來綜合估計:(2.3)從上式可以看出，模式的平均適應(yīng)度高于群體平均適應(yīng)度，并且具有短定義距的模式，將在下一代中成指數(shù)級的增長。3.變異操作對模式的影響通過變異操作對個體串中單個位置進行代碼替換，替換的概率為變異概率Pm，則該位置不發(fā)生變異的概率為1-Pm。要使一個模式H在變異操作過程中不被破壞，就要保證模式H中確定位必須保證不變，因此，模式H保持不變的概率為:(2.4)上式中O(H)為該模式的階數(shù)。綜合上面所述，考慮到選擇操作、交換操作和變異操作對模式的影響，則第t代種群P(t)經(jīng)過遺傳操作后下一代種群P(t+1)具有模式

11、H的個體總數(shù)為:(2.5)該式表示了下述的模式定理。模式定理:在遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級增長。模式定理保證了較優(yōu)的模式(遺傳算法的較優(yōu)解)的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學(xué)基礎(chǔ)。由模式定理可知，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在后代中呈指數(shù)級增長。這些模式在遺傳中很重要，稱為基因塊?；驂K假設(shè):遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式(基因塊)，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性

12、存在;而基因塊假設(shè)則指出了在遺傳算子的作用下，算法具有生成全局最優(yōu)解的能力，即能生成高階、長定義距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。2.3 基本遺傳算法參數(shù)說明對遺傳算法性能有影響的參數(shù)主要有:種群數(shù)目N、交換概率Pc、變異概率Pm、代溝G、尺度窗口W、和選擇策略S等。1.種群數(shù)目(population size)種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。種群選擇過大時，雖然能避免早熟收斂，但是增加了計算量。2.交換概率(crossover rate)交換概率Pc用于控制交換操作的頻率。

13、交換概率太大的時，易產(chǎn)生更新過快，從而破壞掉高適應(yīng)度個體的現(xiàn)象。交換概率太小的時候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。3.變異概率(mutation rate)變異概率Pm。增加種群多樣性具有重要意義。通常選取一個較低的變異概率。如果變異概率太大的時，遺傳算法易變成隨機搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的多樣性。4.代溝(generation gap)代溝G用于控制每一代群體被替換的比例，每代有N(1-G)個父代個體選中進入下一代種群中，該參數(shù)和交換、變異概率以及選擇策略有很大關(guān)系，它并不是一個初始參數(shù)，而是評價遺傳算法的一個參數(shù)。5.尺度窗口(scaling window)該參數(shù)

14、用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。6.選擇策略(selection strategy)一般來說有兩種選擇策略，一種為純選擇，種群中每個個體根據(jù)其適應(yīng)度值進行比例選擇，即個體被選擇的概率與其適應(yīng)度值成正比。另一種為保優(yōu)策略，首先進行純選擇，把目前最優(yōu)個體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失，但在實際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃汀? 用遺傳算法對具體問題的解決與探討遺傳算法在解決作業(yè)車間調(diào)度問題上比經(jīng)典的啟發(fā)式算法好，同時遺傳算法比傳統(tǒng)的搜索技術(shù)有更強的優(yōu)越性，因為它不僅能解決某一特定問題，而且可以適應(yīng)不同的問題形式。3.1 研究過程中的幾個關(guān)鍵問題3.

15、1.1 參數(shù)編碼遺傳編碼技術(shù)是實施遺傳算法的核心。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€體和問題的解(作為進化的個體)。對于同一問題可以有不同的編碼表示方法。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)?；诓僮鞯木幋a（operation-based representation）的基本思想是將所有工件的操作進行編碼，不同的工件用不同的編碼表示，而同一工件的所有操作在染色體中則用相同的編碼表示，其解碼原則是將染色體上的基因按照從左到右的順序解釋為相應(yīng)工件的操作順序，具有

16、相同編碼的基因按照其在整個染色體中的位置解釋為工件相應(yīng)順序的操作。表3.1加工時間和工藝約束項目工件操作序列123操作時間J1J2J3313352233機器J1J2J3M1M1M2M2M3M1M3M2M3對于上表3.1所提出的3個工件在3個機器上加工的例子，假設(shè)染色體為2 1 2 3 1 1 3 2 3，Oijk表示第i個工件的第j個工序在第k個機器上加工（以下同），則對機器加工順序的工藝約束，該染色體對應(yīng)的有序操作表為O211 O111 O223 O312 O122 O133 O321 O232 O333，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務(wù)的

17、第二個操作步驟，以次類推。進而相應(yīng)的調(diào)度如圖3-1（我們用Gantte圖表示一個調(diào)度）。t1296J3J3J3J1J1J1J2J2J2tt1M110734M3M2圖3-1Gantte圖3.1.2 初始種群的生成在N個工件M臺機器的排序問題中，對每個機器的加工存在加工工藝順約束，這個工藝約束表示為工件的加工順序矩陣：M11 M12 M1MM（J,M）= M21 M22 M2M ： ： ： ： (3.1)Mn1Mn2 MnM其中第J行表示第J個工件的機器順序.機器號為零表示工件加工結(jié)束。相應(yīng)的每個加工操作有時間矩陣：T11 T12 T1MT21 T22 T2MT(J,M)= ： ： ： ：(3.2

18、)TN1 TN2 TNM 其中第J行表示第J個工件的機器加工時間,時間為零表示工件不在機器上加工.因為每個個體由N個工件號重復(fù)M次組成的.所以產(chǎn)生一個1,2. . .N(每個重復(fù)有N*M個操作)的全排列即是一個初始個體,算法如下：STEP1：用行號1代替機器順序矩陣M(j,m)的第j行的所有元素,零元素保持不變,若產(chǎn)生的矩陣為GEN。STEP2：產(chǎn)生一個整數(shù)隨機數(shù)1=p=N。STEP3：令chrom（i）=p，并且將矩陣GEN的p行GEN（p，：）左移一個元素，此行移出的最后一個元素用零代替。STEP4：重復(fù)STIP2，STEP3，直到GEN的所有元素為零。產(chǎn)生的chrom為一個個體。重復(fù)ST

19、EP1，STEP2，STEP3，STEP4，直到種群滿。初始種群的生成也可以用隨機方法產(chǎn)生，這是因為群體中的個體都是由工件的符號組成的，而且工件任意排列總能產(chǎn)生可行調(diào)度.在下文的舉例驗證過程中我們運用了隨機的方法產(chǎn)生初始種群。3.1.3 個體的適應(yīng)度函數(shù)在遺傳算法中,適應(yīng)度是描述個體性能的主要指標(biāo)。根據(jù)適應(yīng)度的大小,對個體進行優(yōu)勝劣汰。適應(yīng)度是驅(qū)動遺傳算法的動力。從生物學(xué)角度講,適應(yīng)度相當(dāng)于“生存競爭,適者生存”的生物生存能力,在遺傳過程中具有重要意義。適應(yīng)度函數(shù)就是目標(biāo)函數(shù)，在用遺傳算法解決車間調(diào)度問題里，定義個體的適應(yīng)度函數(shù)為在M臺機器上排序加工完N個工件所需的時間，根據(jù)染色體編碼的思想提

20、出的適應(yīng)度算法如下：STEP1:定義ti(n)為每個工件的可加工時間，初始化向量為零向量。STEP2:chrom（i）對應(yīng)相應(yīng)工序的加工機器為machiner（i）。ti(chrom(1)=ti(chrom(1),machine(1)STEP3:for i=2 to nFor k=1 to nti(chrom(i)=ti(chrom(i-1)+max(ti(chrom(i-k),machine(i-k)+k) 其中若當(dāng)i-k=0,則ti(chrom(i-k),machine(i-k)=0,還有要判斷chorm(i)所對應(yīng)的工件在以前是否加工過，若加工過，則ti(chrom(i)=ti(chor

21、m(i-1)。STEP4:求出適應(yīng)度函數(shù)F=ti(chorm(n)。3.1.4 算法參數(shù)標(biāo)準(zhǔn)GA有4個關(guān)鍵參數(shù)，包括種群數(shù)目（population size,記作M）、交叉概率（crossover rate,記作pc）、變異概率（mutation rate,記作pm）和代溝（generationgap,記作（G）。目前，如何確定GA的最優(yōu)參數(shù)仍舊是一個公開的問題，也是研究GA的重要課題之一。1.種群數(shù)目M種群數(shù)目是影響算法最終優(yōu)化性能和效率的因素之一。通常，種群太小時，不能提供足夠的采樣點，以致算法性能很差，甚至得不到問題得可行解；種群太大時，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增

22、加計算量，從而使收斂時間太長。當(dāng)然，在優(yōu)化過程中種群數(shù)目是允許變化的，也可以將較大規(guī)模的種群分解成若干子種群進行優(yōu)化。2.交叉概率pc交叉概率用于控制交叉操作的頻率。交叉概率太大時，種群中串的更新很快，進而會使高適應(yīng)值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前。3.變異概率pm變異概率是加大種群多樣性的重要因素。通常一個較低的變異概率足以防止整個群體中任一位置的基因一直保持不變。但是，變異概率太小則不會產(chǎn)生新個體，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使GA成為隨機搜索。3.1.5 遺傳算子的設(shè)計1.選擇算子選擇操作是對自然界“適者生存”的模擬。

23、評價值(目標(biāo)函數(shù))較小的個體有較高的概率生存,即在下一代群體中再次出現(xiàn)。一種常用的選擇方法是按比例選擇,即若個體i適應(yīng)值(目標(biāo)函數(shù))是fi,則個體在群體中復(fù)制(再生)的子代個數(shù)在群體中的比例將為:。其中,fi表示指所有個體適應(yīng)值之和。對群體中各個體的適應(yīng)值做比較,將適應(yīng)值小的個體復(fù)制,將適應(yīng)值大的淘汰掉,這是因為在作業(yè)調(diào)度算法中的適應(yīng)度函數(shù)為在M臺機器上加工完N個工件所需的時間,時間越短,更能達到優(yōu)化的目的。2.交叉算子在用遺傳算法解決作業(yè)車間調(diào)度問題中,在對工序編碼的排序問題中,交叉算子不能簡單交換兩個個體的相應(yīng)位置的基因段,因為這樣得到的后代個體可能不能滿足每個工件號重復(fù)M次的要求。例如:

24、染色體1 1 2 2 3 3 1 1 2 3 染色體2 2 1 3 1 2 3 1 3 2交換點隨機選擇4,則交換后得到的新串為: 染色體11 2 2 3 2 1 1 2 3染色體22 1 3 1 3 3 1 3 2很清楚的可以看到交換后新串中的每個工件出現(xiàn)的次數(shù)已經(jīng)不能等于機器數(shù)。所以為了滿足我們的工序編碼的要求,本文采用另一種交叉算子。算子描述如下:隨機將工件集合1,2,N分成兩個互補子集,相應(yīng)的將個體的基因分成兩個部分，然后把父母個體中的part2部分用h代替形成兩個新串，用第二個父母個體的part2部分按照原來的相對順序逐個替換第一個父母個體的part2 產(chǎn)生的新串中的h ,同樣用第一

25、個父母個體的part2 按照原來的相對順序逐個替換第二個父母個體的 prat1 產(chǎn)生的新串中的h,得到兩個后代個體。例如:對于一個4個工件4個機器問題,假如父母個體為:Parent1:1 3 4 2 4 2 3 3 1 4 3 2 1 4 2 1Parent2:3 2 4 1 1 2 3 4 4 2 3 1 2 4 1 3 假設(shè)隨機選擇工件1，2，則從parent1得到的新串為：New1:1 h h 2 h 2 h h 1 h h 2 1 h 2 1Part1:1 2 2 1 2 1 2 1Part2:3 4 4 3 3 4 3 4同樣從Parent2得到的新串為New2:h 2 h 1 1

26、2 h h h 2 h 1 2 h 1 hPart1: 2 1 1 2 2 1 2 1Part2: 3 4 3 4 4 3 4 3然后用Parent2個體的part2：3 4 3 4 4 3 4 3按照原來的相對順序逐個替換第一個父母個體Parent1產(chǎn)生的新串New1：1 h h 2 h 2 h h 1 h h 2 1 h 2 1中的h，得到的后代個體為：Parent1:1 3 4 2 3 2 4 4 1 3 4 2 1 3 2 1同理用Parent1個體的part2：3 4 4 3 3 4 3 4按照原來的相對順序逐個替換第二個父母個體Parent2產(chǎn)生的新串New2：h 2 h 1 1

27、2 h h h 2 h 1 2 h 1 h中的h，得到的后代個體為：Parent2:3 2 4 1 1 2 4 3 3 2 4 1 2 3 1 43.變異算子在做變異時，先對解群以一定的概率進行突變操作。在此作業(yè)調(diào)度算法中，不能簡單的將基因的值做改變。由于問題及其表示的特殊性，這樣簡單的改變可能是沒有意義的，例如，如果原來的基因鏈碼為：1 3 2 3 1 2 3 1 2把第一個基因1變異成3，則基因鏈碼變?yōu)椋? 3 2 3 1 2 3 1 2.這個鏈碼是沒有意義的，因為在基于操作的染色體編碼時，相同符號代表的是同一工件，且用同一符號在染色體出現(xiàn)的次數(shù)為機器的數(shù)目。所以采用上述變異算子是不可行的

28、。我們用如下變異方法：隨機產(chǎn)生一個整數(shù)，確定變異位置，然后，把該位置的基因與其前面的基因互換位置。同樣，以1 3 2 3 1 2 3 1 2為例，假設(shè)變異位置為2，則變異前后的基因鏈碼為：變異前：1 3 2 3 1 2 3 1 2變異后：3 1 2 3 1 2 3 1 23.2 遺傳算法終止條件GA的收斂理論說明了GA具有概率1收斂的極限性質(zhì)，然而實際算法通常難以實現(xiàn)理論上的收斂。本此實驗以迭代次數(shù)作為終止的條件。4仿真實驗首先以4個機器加工4個工件為例，來驗證一下在基于操作編碼時，上面的算法是否合理：假設(shè)交叉概率Pc=100%，變異概率Pm=25%，群體規(guī)模為4，下表為不同機器加工不同零件的

29、時間耗費：表4.1加工時間工件機器T1T2T3T4M1M2M3M424133542468164341.初始化群體，隨機產(chǎn)生染色體編碼因為對4個機器加工四個工件，在用基于操作編碼時，每個染色體包括16個基因。X1=chrom1（16）=1 2 4 3 3 1 2 4 2 1 2 3 4 1 3 4X2=chrom2（16）=2 3 1 4 1 2 3 4 3 4 1 2 2 1 4 3X3=chrom3（16）=3 1 4 2 2 1 4 3 4 3 2 2 1 3 4 1X4=chrom4（16）=4 1 3 2 1 2 3 3 4 2 1 3 4 1 2 4將這四個染色體作為種群的第一代?？?/p>

30、得F1=31， F2=33 ,F3=33, F4=34。染色體X4的適應(yīng)度值最大，表示加工時間最長。而染色體F1的適應(yīng)度值最小，表示加工完零件所需時間最短。2. 選擇操作 將染色體F4淘汰掉，將染色體F1進行復(fù)制作為F4，進行選擇后的群體為：X1 = 1 2 4 3 3 1 2 4 2 1 2 3 4 1 3 4 X2 = 2 3 1 4 1 2 3 4 3 4 1 2 2 1 4 3 X3 = 3 1 4 2 2 1 4 3 4 3 2 2 1 3 4 1 X4 = 1 2 4 3 3 1 2 4 2 1 2 3 4 1 3 4 3.交叉操作 我們隨機將染色體進行兩兩交叉，如果將染色體X1和

31、染色體X2，染色體X3和染色體X4進行交叉。這里我們用第一種交叉算子。交叉后的種群變?yōu)椋篨1 =1 2 3 4 3 1 2 4 2 1 2 3 4 1 4 3X2 =2 4 1 3 1 2 3 4 3 4 1 2 2 1 3 4X3 =4 1 3 2 2 1 3 4 3 4 2 2 1 3 4 1X4 =1 2 3 4 4 1 2 3 2 1 2 4 3 1 3 4交叉后的適應(yīng)度值為：F1=32, F2=32, F3=30, F4=32 ,將進行后的值和前面的進行比較，可以看到大部分個體經(jīng)過交叉后的個體性能大大提高。4.變異操作遺傳算法和生物的進化一樣，在進化的過程中，由于某些原因染色體的個別基因會發(fā)生變異，一般情況下變異后的個體比以前的優(yōu)，但有些變異不一定會產(chǎn)生優(yōu)秀的個體。為了說明變異這個問題，我們這里將變異概率設(shè)為0.25。對這個例子來說，就是這4條染色體中將有1條染