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