【正文】 序操作表為[O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務的第二個操作步驟，…以次類推。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調度問題上把它們轉換成遺傳空間的基因按一定結構組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結構數(shù)據(jù)。遺傳算法的工作基礎是選擇適當?shù)姆椒ū硎緜€體和問題的解(作為進化的個體)。 設備死鎖示意圖，分屬工件1和工件2的總共四個工序都處于循環(huán)等待其前面工序或前道工序結束加工的狀態(tài)之中，從而使設備1和設備2處于空轉狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。 研究過程中的幾個關鍵問題 設備死鎖現(xiàn)象初始解群是問題的起點，解決設備死鎖問題必須從初始解群開始。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并基于適應度值來評價染色體，使適用性好的染色體比適應性差的染色體有更多的繁殖機會。這對GA的實際應用關系重大。與此同時，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行GA和分布式GA的研究。今后幾年，拓廣更加多樣的應用領域，將是GA發(fā)展的主流。除了機器學習之外遺傳算法所涉及的主要領域還有自動控制、規(guī)劃設計、組合優(yōu)化、圖象處理、信號處理、人工生命、模式識別，神經(jīng)網(wǎng)絡、自適應控制、生物科學、系統(tǒng)工程、社會科學等。一般的學習系統(tǒng)要求具有隨時間推移逐步調整有關參數(shù)或者改變自身結構以更加適應環(huán)境，更好達到目標的能力。遺傳算法主要應用在機器學習中。《Advanced Computational Intelligence》雜志即將發(fā)刊。1993年，MIT出版社創(chuàng)刊了新雜志《Evolutionary Computation》。1994年，他又出版了《遺傳程序設計，第二冊:可重用程序的自動發(fā)現(xiàn)》深化了遺傳程序設計的研究，使程序設計自動化展現(xiàn)了新局面。1991年，《遺傳算法手冊》（Handbook of Genetic Algorithms），其中包括了遺傳算法在工程技術和社會生活中的大量應用實例。此外，以遺傳算法的理論基礎為中心的學術會議還有Foundations of Genetic Algorithms，該會也是從1990年開始隔年召開一次。同年，美國斯坦福大學的Koza基于自然選擇原則創(chuàng)造性地提出了用層次化的計算機程序來表達問題的遺傳程序設計( genetic programming, GP)方法，成功地解決了許多問題。1989年，《搜索、優(yōu)化和機器學習中的遺傳算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。進入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。盡管De Jong和Hollstien 一樣主要側重于函數(shù)優(yōu)化的應用研究，但他將選擇、交叉和變異操作進一步完善和系統(tǒng)化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術。同年， Jong完成了他的博士論文《一類遺傳自適應系統(tǒng)的行為分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。Holland在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論（schema theory）。1975年是遺傳算法研究歷史上十分重要的一年。此后，Holland指導學生完成了多篇有關遺傳算法研究的論文。 1996年，舉行了第1次遺傳程序設計國際會議，該領域己引起越來越多的相關學者們的興趣。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃（Evolution Programming,EP）以及進化策略（Evolution Strategy,ES）等進化計算理論日益結合。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結構的研究都是十分重要的。二是遺傳算法正日益和神經(jīng)網(wǎng)絡［12］、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。隨著應用領域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向［9］：一是基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學習算法［10］。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。染色體作為遺傳物質的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。 遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變異和遺傳向著適應環(huán)境的方向發(fā)展。 遺傳算法的進展地球上自出現(xiàn)生命至今已有30多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進化過程。，優(yōu)化問題要具體情況具體分析。而另一種觀點則認為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于一個非常大的變異率，而這么大的變異很可能影響進化過程。，但交叉和變異的重要性存在爭議。其中一種是所謂觸發(fā)式超級突變，就是當染色體群體的質量下降(彼此的區(qū)別減少)時增加突變概率。，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過早地斂，而對以后變化了的數(shù)據(jù)不再產(chǎn)生變化。，在存在噪聲的情況下，對同一問題利用遺傳算法求解所得的結果是相似的。，容易形成通用算法程序。，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點。這種機制意味著搜索過程可以跳出局部最優(yōu)點，能很好地將局部搜索和全局搜索協(xié)調起來，達到全局最優(yōu)點。另一種為保優(yōu)策略，首先進行純選擇，把目前最優(yōu)個體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失，但在實際應用中往往采取這兩種選擇策略結合的方法，并做適當?shù)淖冃汀?scaling window)該參數(shù)用于作出由目標值到適應度函數(shù)值的調整。如果變異概率太大的時，遺傳算法易變成隨機搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的多樣性。增加種群多樣性具有重要意義。交換概率太小的時候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。(crossover rate)交換概率Pc用于控制交換操作的頻率。(population size)種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。從總體上來說，每代之間所處理的個體要遠大于其表面的數(shù)目，這就是遺傳算法獨特的隱含并行性。由馬爾可夫鏈推導出來的一些結論:基本遺傳算法收斂于最優(yōu)解的概率為1,使用保留最優(yōu)個體策略的遺傳算法收斂于最優(yōu)解的概率為1。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。交叉操作用于個體對，產(chǎn)生新的個體，實質上是在解空間中進行有效搜索。選擇操作使高適應度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。通常，種群太小則不能提供足夠的采樣點，以致算法性能很差。 遺傳算法的收斂性分析遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。上述結論并沒有得到證明，因而被稱為假設。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在。這些模式在遺傳中很重要，稱為基因塊。模式定理保證了較優(yōu)的模式(遺傳算法的較優(yōu)解)的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學基礎。綜合上面所述，考慮到選擇操作、交換操作和變異操作對模式的影響，則第t代種群P(t)經(jīng)過遺傳操作后下一代種群P(t+1)具有模式H的個體總數(shù)為: ()該式表示了下述的模式定理。通過變異操作對個體串中單個位置進行代碼替換，替換的概率為變異概率Pm，則該位置不發(fā)生變異的概率為1Pm。但是如果其中一方個體不具有模式H，則有可能會引起另一個個體模式的改變。交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結構，但又最低限度地破壞選擇操作過程所選擇的高適應度的模式。其傳統(tǒng)實現(xiàn)建立在逐項比較的基礎上，算法復雜度為O（n＾2）。 遺傳算法的模式定理選擇操作是遺傳算法中體現(xiàn)“適者生存”的關鍵一環(huán)，它能控制高適應度的模式成指數(shù)級增長。 基本遺傳算法 遺傳算法的基本思路；，并從求解空間中任選N個點組成初始群體；。自然選擇決定了群體中那些個個體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進行演化的。，哪些適應性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機會。進化是發(fā)生在編碼染色體上，通過對染色體的譯碼部分生成生物體，但下面幾個關于進化理論的一般特性已被廣大人們所接受?；涗洷砻魑覀兯^察的復雜結構的生命是在相對短的時間進化而來的，對這一點包括生物學家在內(nèi)的許多人都感到驚奇。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復進行基于遺傳學的操作（遺傳，交叉和變異），根據(jù)預定的目標適應度函數(shù)對每個個體進行評價，依據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。2 遺傳算法相關理論與實現(xiàn)技術遺傳算法(Genetic Algorithm, GA)是一種基于自然群體遺傳演化機制的高效探索算法，它是美國學者Holland于1975年首先提出來的［7］。第一章簡要介紹了車間調度問題和求解調度問題的基本方法；第二章介紹了遺傳算法的基本理論；第三章用遺傳算法來解決車間調度問題,其中介紹了常用的幾種編碼方式,。兩個方向的優(yōu)化目標之間彼此不是相互孤立的，其中的許多具體目標之間的聯(lián)系很密切，有的相互促進，有的相互沖突，也有的毫無聯(lián)系。調度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標有:庫存最少、在制品最少、設備利用率最高等。即使得目標函數(shù)取值最小(或最大)，且與相容，則稱為車間作業(yè)調度問題在此目標函數(shù)下的最優(yōu)解。事實上，工件排列陣就是調度的一種表示形式。表示在i機器上排在第j位加工的工件號，表示i機器上依次加工的各工件的排列。同樣地，如果某工件的工序數(shù)不足，那么其空余的位置用0填滿。 （）T:加工時間陣，此為矩陣。（i，j）表示i工件的第j道工序的機器號，表示i工件的所有工序按優(yōu)先順序加工的各機器號的排列。不足，那么其空余的位置用0填滿。P（i，j）表示i工件的第j道工序。假設有n個工件，要在m臺機器上加工，每個工件有Pi道工序，每臺機器上總共要加工Lj道工序。6. 緩沖區(qū)容量為無窮大。4. 所有機器處理的加工類型均不同。2. 不考慮工件加工的優(yōu)先權，即工件之間沒有優(yōu)先約束關系限制的。(機器)獨占性約束:任一臺機器每次只能加工一個工件，且一旦開工就不能中斷，反映了加工隊列中工件間的時序關系。它所要解決的問題就是確定每臺機器上不同工件的加工順序，以及每個工件的所有工序的起始加工時間，以最優(yōu)化某個性能指標。用“加工順序”表示各臺機器上各個工件加工的先后順序。一個工件在一臺機器上的加工程序稱為一道“工序”，相應的加工時間稱為該工序的“加工時間”。而在本文中，為了研究方便，我們將這項任務限定為加工一批工件。車間作業(yè)是指利用車間資源(如機床、刀具、夾具等)完成的某項任務。而傳統(tǒng)的運籌學方法，即便在較大規(guī)模的基于單目標優(yōu)化的靜態(tài)調度問題中也難以有效應用。它可分為精確求解方法和近視求解方法。2. 不同工件的加工工序可以不同；3. 所有工件的工序數(shù)不大于設備數(shù)；4. 每道工序必須在指定的某種設備上加工；5. 任何作業(yè)沒有搶先加工的優(yōu)先權；6. 在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件；調度問題具有相當?shù)碾y度，目前調度問題的理論研究成果主要在jobshop問題為代表的基于最小完工時間的調度問題上。 作業(yè)車間調度問題表述作業(yè)車間調度（jobshop）問題可以表述為：設有N個工件在M臺機器上加工，根據(jù)工件加工工藝的要求，每個工件使用機器的順序及其每道工序所花時間已給定，調度問題的目標就是如何選擇加工順序使得總的加工時間最短最優(yōu)。它特別適合于處理傳統(tǒng)搜索算法解決不好的復雜和非線性問題。由于一般車間調度問題的復雜性，各種不同的具體問題往往有許多不同的算法來解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。雖然對其研究已有幾十年的歷史但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實際應用之間還存在著較大距離。遺傳