【正文】 該染色體對應(yīng)的有序操作表為 [O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務(wù)的第二個操作步驟， ? 以次類推。 其基本思想是只對任務(wù)進行編碼，然后按照編碼在染色體中的順序來以相應(yīng)的優(yōu)先級別安排任務(wù)。用于表示機器上加工工件的一個排列順序。顯然，這種解碼過程可產(chǎn)生活動調(diào)度。因為每個工件有三道工序，所以每個工件在一個染色體中剛好出現(xiàn)三次。 初始種群的生成 在 N 個工件 M臺機器的排序問題中，對每個機器的加工存在加工工藝順約束，這個工藝約束表示為工件的加工順序矩陣： M11 M12 ? M1M M（ J,M） = M21 M22 ? M2M ： ： ： ： () Mn1 Mn2 ? MnM 其中第 J行表示第 J個工件的機器順序 .機器號為零表示工件加工結(jié)束。 STEP4：重復(fù) STIP2， STEP3，直到 GEN 的所有元素為零。 初始種群的生成也可以用隨機方法產(chǎn)生，這是因為群體中的個體都是由工件的符號組成的，而且工件任意排列總能產(chǎn)生可行調(diào)度 .在下文的舉例驗證過程中我們運用了隨機的方法產(chǎn)生初始種群。從生物學(xué)角度講 ,適應(yīng)度相當(dāng)于“生存競爭 ,適者生存”的生物生存能力 ,在遺傳過程中具有重要意義。 STEP4:求出適應(yīng)度函數(shù) F=ti(chorm(n))。通常，種群太小 時，不能提供足夠的采樣點，以致算法性能很差，甚至得不到問題得可行解；種 群太大時，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增加計算量，從而使收斂時間太長。 pm 變異概率是加大種群多樣性的重要因素。評價值 (目標(biāo)函數(shù) )較小的個體有較高的概率生存 ,即在下一代群體中再次出現(xiàn)。 第一種交叉算子 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 22 頁 在用遺傳算法解決作業(yè)車間調(diào)度問題中 ,在對工序編碼的排序問題中 ,交叉算子不。 其中 ,∑fi 表示指所有個體適應(yīng)值之和。但是，變異概率太小則不會產(chǎn)生新個體 ，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使 GA 成為隨機搜索。 pc 交叉概率用于控制交叉操作的頻率。目前，如何確定 GA 的最優(yōu)參數(shù)仍舊是一個公開的問題，也是研究 GA 的重要課題之一。 STEP2:chrom（ i） 對應(yīng)相應(yīng)工序的加工機器為 machiner（ i）。根據(jù)適應(yīng)度的大小 ,對個體進行優(yōu)勝劣汰。重復(fù) STEP1， STEP2， STEP3， STEP4，直到種群滿。 STEP2：產(chǎn)生一個整數(shù)隨機數(shù) 1=p=N。可以看出工件 j2 的所有工序都用相同的符號 2 來命名，并且根據(jù)它出 現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機器的對應(yīng)關(guān)系如下 所示。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。 前面兩種編碼方式比較復(fù)雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務(wù)相應(yīng)順序的操作。對于有三項任務(wù)的調(diào)度問題，假設(shè)染色體為 [2 3 1]，則可以解釋為首先安排第二項任務(wù)的所有操作，其次是第三項任務(wù)，最后才輪到第一項任務(wù)。 圖 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è)計 第 18 頁 （ jobbased representation） 將每個染色體用 n個代表工件的基因組成，是所有工件的一個排列。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車 間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。 圖 設(shè)備死鎖示意圖 在圖 中，分屬工件 1 和工件 2 的總共四個工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設(shè)備 1 和設(shè)備 2 處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行 評價，并基于適應(yīng)度值來評價染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機會。與此同時，理論方面同樣有大量工作 要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行 GA 和分布式 GA 的研究。 除了機器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動控制、規(guī)劃設(shè)計、組合優(yōu)化、圖象處理、信號處理、人工生命、 模式識別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會科學(xué)等。 遺傳算法主要應(yīng)用在機器學(xué)習(xí) 中。 1993 年，MIT 出版社創(chuàng)刊了新雜志《 Evolutionary Computation》。 1991 年， 編輯出版了《遺傳算法手冊》 （ Handbook of Geic Algorithms） ，其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應(yīng)用實例。同年，美國斯坦福大學(xué)的 Koza 基于自然選擇原則創(chuàng)造性地提出了用層次化的計算機程序來表達問題的遺傳程序設(shè)計 ( geic programming, GP)方法，成功地解決了許多問題。 進入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。同年， Jong 完成了他的博士論文《一 類遺傳自適應(yīng)系統(tǒng)的行為分析》 （ An Analysis of the Behavior of a Class of Geic Adaptive System） 。 1975 年是遺傳算法研究 歷史上十分重要的一年。 1996 年，舉行了第 1 次遺傳程序設(shè)計國際會議，該領(lǐng)域己引起越來越多的相關(guān)學(xué)者們的興趣。所謂人工生命即是用計算機模 擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃 （ Evolution Programming,EP） 以及進化策略 （ Evolution Strategy,ES）等進化計算理論日益結(jié)合。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò) ［ 12］ 、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓 21 世紀(jì)中新的智能計算技術(shù)將具有重要的意義。由于仿照基因編碼的工作很復(fù)雜，我們往往進行簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代 （ generation） 演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù) 問題域中個體的適應(yīng)度 （ fitness） 大小選擇 （ selection）個體，并借助于自然遺傳學(xué)的遺傳算子（ geic operators） 進行組合交叉 （ crossover）和變異 （ mutation） ，產(chǎn)生出代表新的解集的種群。 遺傳 算法 是從代表問題可能潛在的解集的一個種群 （ population） 開始的，而一個種群則由經(jīng)過基因 （ gene） 編碼的一定數(shù) 目的個體 (individual)組成。 遺傳算法的 進展 地球上自出現(xiàn)生命至今已有 30 多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進化過程。而另一種觀點則認(rèn)為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 12 頁 一 個非常大的變異率，而這么大的變異很可能影響進化過程。其中一種是所謂觸發(fā)式超級突變，就是當(dāng)染色體群體的質(zhì)量下降 (彼此的區(qū)別減少 )時增加突變概率 。 ，在存在噪聲的情況下，對同一問題利用遺傳算法求解所得的結(jié)果是相似的。 ，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點。另一種為保優(yōu)策略，首先進行純選擇，把目前最優(yōu)個體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失， 但在實際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃?。如果變異概率太大的時，遺傳算法易變成隨機搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的多樣性。交換概率太小的時候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。 (population size) 種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。從總體上來說，每代之間所處理的個體要遠大于其表面的數(shù)目，這就是遺傳算法獨特的隱含并行性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。 交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進行有效搜索。 通常，種群太小則不能提供足夠的采樣點，以致算法性能很差 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 9 頁 上述結(jié)論并沒有得到證明，因而被稱為假設(shè)。這些模式在遺傳中很重要，稱為基因塊。 綜合上面所述，考慮到選擇操作、交換操作和 變異操作對模式的影響，則第 t 代種群 P(t)經(jīng)過遺傳操作后下一代種群 P(t+1)具有模式 H 的個體總數(shù)為 : _( ) ( )( , 1 ) ( , ) ( 1 ) ( 1 ( ) )1cmf H Hm H t m H t P P o Hlf?? ? ? ??? () 該式表示了下述的模式定理。但是如果其中一方個體不具有模式 H， 則有可能會引起另一個個體模式的改變。其傳統(tǒng)實現(xiàn)建立在逐項比較的基礎(chǔ)上，算法復(fù)雜度為 O（ n＾ 2） 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 7 頁 基本 遺傳算法 遺傳算法的基本思路 ； 將求解空間中的每一個點進行編碼，并從求解空間中任選 N個點組成初始群體； 。 大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進行演化的。 ，哪些適應(yīng)性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機會?；涗洷砻魑覀兯^察的復(fù)雜結(jié)構(gòu) 的生命是在相對短的時間進化而來的，對這一點包括生物學(xué)家在內(nèi)的許多人都感到驚奇。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 6 頁 2 遺傳算法相關(guān)理論與實現(xiàn)技術(shù) 遺傳算法 (Geic Algorithm, GA)是一種基于自然群體遺傳演化機制的高效探索算法，它是美國學(xué)者 Holland 于 1975 年首先提出來的 ［ 7］ 。兩個方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進，有的相互沖突，也有的毫無聯(lián)系。即 jM? 使得目標(biāo)函數(shù) ()jfM 取值最小 (或最大 )，且與 MJ 相容，則稱 jM? 為車間作業(yè)調(diào)度問題在此目標(biāo)函數(shù)下的最優(yōu)解。 (, )jMi j 表示在 i機器上排在第 j位 加工的工件號， (, )jMi? 表示 i機器上依次加工的各工件的排列。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 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:加工時間陣，此為 12m ax{ , , }nn P P P? 矩陣。不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。 假設(shè)有 n個工件，要在 m臺機器上加工，每個工件有 Pi 道工序，每臺機器上總共要加工 Lj 道工序。 4. 所有機器處理的加工類型均不同 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 3 頁 (機器 )獨占性約束 :任一臺機器每次只能加工一個工件，且一旦開工就不能中斷，反映了加工隊列中工件間的時序關(guān)系。用“加工順