【正文】 improved carries on the geic algorithms desing, this paper offer one improved geic algorithms about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid. Keywords: jop shop scheduling。 2. 不同工件的加工工序可以不同； 3. 所有工件的工序數(shù)不大于設(shè)備數(shù)； 4. 每道工序必須在指定的某種設(shè)備上加工； 5. 任何作業(yè)沒有搶先加工的優(yōu)先權(quán)； 6. 在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件； 調(diào)度問題具有相當(dāng)?shù)碾y度，目前調(diào)度問題的理論研究成果主要在 jobshop 問題為代表的基于最小完工時(shí)間的調(diào)度問題上。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 3 頁 (機(jī)器 )獨(dú)占性約束 :任一臺(tái)機(jī)器每次只能加工一個(gè)工件，且一旦開工就不能中斷，反映了加工隊(duì)列中工件間的時(shí)序關(guān)系。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 4 頁 1 11 2 1 1111 2 1 ( 1 )1 1100 000ijPjjjpj j n j Pn n n iiiP PPP P PMP P P PPPPM M MJM M M M?????????????? （ ） T:加工時(shí)間陣，此為 12m ax{ , , }nn P P P? 矩陣。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 6 頁 2 遺傳算法相關(guān)理論與實(shí)現(xiàn)技術(shù) 遺傳算法 (Geic Algorithm, GA)是一種基于自然群體遺傳演化機(jī)制的高效探索算法，它是美國學(xué)者 Holland 于 1975 年首先提出來的 ［ 7］ 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 7 頁 基本 遺傳算法 遺傳算法的基本思路 ； 將求解空間中的每一個(gè)點(diǎn)進(jìn)行編碼，并從求解空間中任選 N個(gè)點(diǎn)組成初始群體； 。這些模式在遺傳中很重要，稱為基因塊。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。如果變異概率太大的時(shí)，遺傳算法易變成隨機(jī)搜索，如果變異概率太小，則不能產(chǎn)生新個(gè)體，不利于種群的 多樣性。其中一種是所謂觸發(fā)式超級突變，就是當(dāng)染色體群體的質(zhì)量下降 (彼此的區(qū)別減少 )時(shí)增加突變概率 。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代 （ generation） 演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度 （ fitness） 大小選擇 （ selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（ geic operators） 進(jìn)行組合交叉 （ crossover）和變異 （ mutation） ，產(chǎn)生出代表新的解集的種群。 1975 年是遺傳算法研究歷史上十分重要的一年。 1991 年， 編輯出版了《遺傳算法手冊》 （ Handbook of Geic Algorithms） ，其中包括了遺傳算法在工程技術(shù)和社會(huì)生活中的大量應(yīng)用實(shí)例。與此同時(shí)，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行 GA 和分布式 GA 的研究。 圖 Gantte 圖 t 12 9 6 J3 J3 J3 J1 J1 J1 J2 J2 J2 t t 1 M1 10 7 3 4 M3 M2 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 18 頁 （ jobbased representation） 將每個(gè)染色體用 n個(gè)代表工件的基因組成，是所有工件的一個(gè)排列。可以看出工件 j2 的所有工序都用相同的符號 2 來命名，并且根據(jù)它出 現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機(jī)器的對應(yīng)關(guān)系如下 所示。 STEP2:chrom（ i） 對應(yīng)相應(yīng)工序的加工機(jī)器為 machiner（ i）。 其中 ,∑fi 表示指所有個(gè)體適應(yīng)值之和。但是，變異概率太小則不會(huì)產(chǎn)生新個(gè)體，抑制早熟現(xiàn)象的能力較差，概率太大則會(huì)破壞掉很多較好的模式，使 GA 成為隨機(jī)搜索。根據(jù)適應(yīng)度的大小 ,對個(gè)體進(jìn)行優(yōu)勝劣汰。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。 除了機(jī)器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動(dòng)控制、規(guī)劃設(shè)計(jì)、組合優(yōu)化、圖象處理、信號處理、人工生命、 模式識別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會(huì)科學(xué)等。同年，美國斯坦福大學(xué)的 Koza 基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計(jì) ( geic programming, GP)方法，成功地解決了許多問題。 1996 年，舉行了第 1 次遺傳程序設(shè)計(jì)國際會(huì)議，該領(lǐng)域己引起越來越多的相關(guān)學(xué)者們的興趣。 遺傳 算法 是從代表問題可能潛在的解集的一個(gè)種群 （ population） 開始的，而一個(gè)種群則由經(jīng)過基因 （ gene） 編碼的一定數(shù)目的個(gè)體 (individual)組成。 ，在存在噪聲的 情況下，對同一問題利用遺傳算法求解所得的結(jié)果是相似的。交換概率太小的時(shí)候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。 交叉操 作用于個(gè)體對，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。 綜合上面所述，考慮到選擇操作、交換操作和變異操作對模式的影響，則第 t 代種群 P(t)經(jīng)過遺傳操作后下一代種群 P(t+1)具有模式 H 的個(gè)體總數(shù)為 : _( ) ( )( , 1 ) ( , ) ( 1 ) ( 1 ( ) )1cmf H Hm H t m H t P P o Hlf?? ? ? ??? () 該式表示了下述的模式定理。 大多數(shù)生物體是通過自然選擇 和有性生殖這兩種基本過程進(jìn)行演化的。兩個(gè)方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進(jìn)，有的相互沖突，也有的毫無聯(lián)系。不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。用“加工順序”表示各臺(tái)機(jī)器上各個(gè)工件加工的先后順序。它特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線性問題。 在研究了作業(yè)車 間調(diào)度問題數(shù)學(xué)模型和優(yōu)化算法的基礎(chǔ)上，將一種改進(jìn)的自適應(yīng)遺傳算法應(yīng)用在作業(yè)車間調(diào)度中。 geic algorithm。 求解調(diào)度問題的方法稱為調(diào)度優(yōu)化算法。 此外，還有一些輔助假設(shè)條件，如下 : 1. 各工件經(jīng)過其準(zhǔn)備時(shí)間后可開始加工 。 T(i, j)表示工件 i的第 j 道工序在 MJ（ i， j） 上的加工時(shí)間。它摒棄了傳統(tǒng)的搜索方式，模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程 ［ 8］ 。運(yùn)用選擇、交叉、變異算子產(chǎn)生新一代群體； ，若找到滿足問題的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)步驟 3。 基因塊假設(shè) :遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式 (基因塊 )，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 遺傳操作對收斂性的影響，可利用馬爾可夫鏈對遺傳算法進(jìn)行分析，從而論證了遺傳算法在收斂性方面的一些重要性質(zhì)，有力地支持了遺傳算法的理論基礎(chǔ)。 (generation gap) 代溝 G 用于控制每一代群體被替換的比例，每代有 N (1G)個(gè)父代個(gè)體選中進(jìn)入下一代種群中，該參數(shù)和交換、變異概率以及選擇策略有很大關(guān)系，它并不是一個(gè)初始參數(shù)，而是評價(jià)遺傳算法的一個(gè)參數(shù)。另一種叫隨機(jī)外來染色體，是偶爾加入一些全新的隨機(jī)生成的染色體個(gè)體，從而 增加染色體多樣性。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后 生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼（ decoding） ，可以作為問題近似最優(yōu)解 。這一年 Holland 出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》 （ Adaptation in Natural and Artificial Systems） ，這是第一本系統(tǒng)論述遺傳算法的專著，因此有人把 1975 年作為遺傳算法的誕生年。 1992 年， Koza 發(fā)表了他的專著《遺傳程序設(shè)計(jì) :基于自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)》。不論從理論還是應(yīng)用的角度看，最緊迫的應(yīng)是關(guān)于算法收斂性問題的研究，特別是過早收斂的防止。解碼過程是先加工第 1 號工件的所有操作，然后依次以最好允許加工時(shí)間加工后面所有操作。 染色體 1 1 2 2 3 3 1 1 2 3 ↓ ↓ ↓ 機(jī)器 1 2 3 一個(gè)好的調(diào)度方法（換句話說就是染色體對應(yīng)的適應(yīng)度值高），可以有效提機(jī)器的利用率，降低機(jī)器空閑的時(shí)間長度，從而達(dá)到優(yōu)化的目的，遺傳算法就是來尋找這樣的更優(yōu)的調(diào)度策略。 ti(chrom(1))=ti(chrom(1),machine(1)) STEP3:for i=2 to n For k=1 to n ti(chrom(i))=ti(chrom(i1))+max(ti(chrom(ik),machine(ik)+k)) 其中若當(dāng) ik=0,則ti(chrom(ik),machine(ik))=0,還有要判斷 chorm(i)所對應(yīng)的工件在以前是否加工過，若加工過，則 ti(chrom(i))=ti(chorm(i1))。 對群體中各個(gè)體的適應(yīng)值做比較 ,將適應(yīng)值小的個(gè)體復(fù)制 ,將適應(yīng)值大的淘汰掉 ,這是因?yàn)樵谧鳂I(yè)調(diào)度算法中的適應(yīng)度函數(shù)為在 M 臺(tái)機(jī)器上加工完 N 個(gè)工件所需的時(shí)間 ,時(shí)間越短 ,更能達(dá)到優(yōu)化的目的。通常一個(gè)較低的變異概率足以防止整個(gè)群體中任一位置的基因一直保持不變。 個(gè)體的適應(yīng)度函數(shù) 在遺傳算法中 ,適應(yīng)度是描述個(gè)體性能的主要指標(biāo)。 對于 n 個(gè)工件 m 機(jī)器問題，一個(gè)染色體包括個(gè) n*m 個(gè)基因，每個(gè)個(gè)體出現(xiàn)在染色體中 m次，每個(gè)基因不表明具體的工序，而是指上下依賴關(guān)系的工序。對于同一問題可以有不同的編碼表示方法。由于多樣性和復(fù)雜性，通常難以建立完善的理論以指導(dǎo)整個(gè)學(xué)習(xí)過程，從而使傳統(tǒng)尋優(yōu)技術(shù)的應(yīng)用受到限制，而這恰好是遺傳算法發(fā)揮的長處。該書總結(jié)了遺傳算法研究的主要成果，對 遺傳算法及其應(yīng)用作了 全面而系統(tǒng)的論述 。 近年來，遺傳程序設(shè)計(jì)運(yùn)用遺傳算法的思想自動(dòng)生成計(jì)算機(jī)程序解決了許多問題，如預(yù)測、分類、符號回歸和圖像處理等，作為一種新技術(shù)它己經(jīng)與遺傳算法并駕齊驅(qū)。經(jīng)過長時(shí)間的遺傳、變異和選擇，生物便逐漸從簡單到復(fù)雜，從低級到高級不斷地進(jìn)化和發(fā)展。由于遺傳算法使用適應(yīng)度值這一信息進(jìn)行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。交換概率太大的時(shí)，易產(chǎn)生更新過快，從而破壞掉高適應(yīng)度個(gè)體的現(xiàn)象。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率 1 收斂于全局最優(yōu)解。要使一個(gè)模式 H 在變異操作過程中不被破壞，就要保證模式 H 中確定位必須保證不變，因此，模式 H 保持不變的概率為 : ()(1 ) 1 ( )OHs m mp p P o H? ? ? ? ? () 上式中 O(H)為該模式的階數(shù)。有關(guān)產(chǎn)生個(gè)體的信息包含在個(gè)體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個(gè)體會(huì)很好的適應(yīng)它們的環(huán)境。從生產(chǎn)時(shí)間方面來考慮，其優(yōu)化目標(biāo)有 :最大程度滿足交貨期、最小完成時(shí)間、最小流動(dòng) 時(shí)間和最小等待時(shí)間等。 ( , )ijPi P??，表示 i 工件的所有工序按優(yōu)先順序的排列。用事先給定的“加工路線”表示工件加工時(shí)技術(shù)上的約束，即工件的加工工藝過程。由于遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)搜 索算法 ［ 1］ 。本文在已有算法基礎(chǔ)上詳細(xì)討論了染色體編碼方法并對其進(jìn)行了改進(jìn)。 improvement chromosome code。它可分為精確求解方法和近視求解方法。 2.