【文章內(nèi)容簡介】 變異很可能影響進(jìn)化過程?！按蠛漆槨钡膯栴}，所謂“大海撈針”問題就是沒有一個確切的適應(yīng)度函數(shù)表征個體好壞的問題，遺傳算法對這類問題無法找到收斂的路。，優(yōu)化問題要具體情況具體分析。所以在使用遺傳算法的同時，也可以嘗試其它算法，互相補(bǔ)充，甚至根本不用遺傳算法。 遺傳算法的進(jìn)展地球上自出現(xiàn)生命至今已有30多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進(jìn)化過程。1859年，達(dá)爾文根據(jù)長期對世界各地的考察以及人工選擇的實(shí)驗，發(fā)表了《物種起源》，系統(tǒng)地提出并建立了以“優(yōu)勝劣汰”、“適者生存”的自然選擇為基礎(chǔ)的進(jìn)化論學(xué)說，根據(jù)他的進(jìn)化論，生物發(fā)展進(jìn)化的原因主要有三個，就是遺傳、變異和選擇。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。經(jīng)過長時間的遺傳、變異和選擇，生物便逐漸從簡單到復(fù)雜，從低級到高級不斷地進(jìn)化和發(fā)展。 遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。每個個體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度（fitness）大小選擇（selection）個體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向［9］：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法［10］。這一新的學(xué)習(xí)機(jī)制對于解決人工智能［11］中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)［12］、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓21世紀(jì)中新的智能計算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（Evolution Programming,EP）以及進(jìn)化策略（Evolution Strategy,ES）等進(jìn)化計算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時獨(dú)立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。近年來，遺傳程序設(shè)計運(yùn)用遺傳算法的思想自動生成計算機(jī)程序解決了許多問題，如預(yù)測、分類、符號回歸和圖像處理等，作為一種新技術(shù)它己經(jīng)與遺傳算法并駕齊驅(qū)。 1996年，舉行了第1次遺傳程序設(shè)計國際會議，該領(lǐng)域己引起越來越多的相關(guān)學(xué)者們的興趣。1967年，“遺傳算法（Genetic Algorithms）”一詞。此后，Holland指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。1971年。1975年是遺傳算法研究歷史上十分重要的一年。這一年Holland出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》（Adaptation in Natural and Artificial Systems），這是第一本系統(tǒng)論述遺傳算法的專著，因此有人把1975年作為遺傳算法的誕生年。Holland在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論（schema theory）。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。同年， Jong完成了他的博士論文《一類遺傳自適應(yīng)系統(tǒng)的行為分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。該論文所做的研究工作，可看作是遺傳算法發(fā)展進(jìn)程中的一個里程碑，這是因為，他把Holland的模式理論與他的計算實(shí)驗結(jié)合起來。盡管De Jong和Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術(shù)?？梢哉J(rèn)為，De Jong的研究工作為遺傳算法及其應(yīng)用打下了堅實(shí)的基礎(chǔ)，他所得出的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。進(jìn)入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。1985年，在美國召開了第一屆遺傳算法國際會議（International Conference on Genetic Algorithms ，ICGA），并且成立國際遺傳算法學(xué)會（International Society of Genetic Algorithms ，ISGA），以后每兩年舉行一次。1989年，《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。該書總結(jié)了遺傳算法研究的主要成果，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。同年，美國斯坦福大學(xué)的Koza基于自然選擇原則創(chuàng)造性地提出了用層次化的計算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計( genetic programming, GP)方法，成功地解決了許多問題。 在歐洲，從1990年開始每隔一年舉辦一次Parallel Problem Solving from Nature 學(xué)術(shù)會議，其中遺傳算法是會議主要內(nèi)容之一。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會議還有Foundations of Genetic Algorithms，該會也是從1990年開始隔年召開一次。這些國際會議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動向。1991年，《遺傳算法手冊》（Handbook of Genetic Algorithms），其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應(yīng)用實(shí)例。 1992年，Koza發(fā)表了他的專著《遺傳程序設(shè)計:基于自然選擇法則的計算機(jī)程序設(shè)計》。1994年，他又出版了《遺傳程序設(shè)計，第二冊:可重用程序的自動發(fā)現(xiàn)》深化了遺傳程序設(shè)計的研究，使程序設(shè)計自動化展現(xiàn)了新局面。有關(guān)遺傳算法的學(xué)術(shù)論文也不斷在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》《IEEE Transactions on Neural Networks》,《IEEE Transactions on Signal Processing》等雜志上發(fā)表。1993年，MIT出版社創(chuàng)刊了新雜志《Evolutionary Computation》。1997年，IEEE又創(chuàng)刊了《Transactions on Evolutionary Computation》?！禔dvanced Computational Intelligence》雜志即將發(fā)刊。目前，關(guān)于遺傳算法研究的熱潮仍在持續(xù)，越來越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中現(xiàn)在隨著科學(xué)技術(shù)的日益發(fā)展，遺傳算法有了突飛猛進(jìn)的發(fā)展，不僅理論研究十分活躍，而在越來越多的領(lǐng)域得到發(fā)展。遺傳算法主要應(yīng)用在機(jī)器學(xué)習(xí)中。遺傳算法適合于維數(shù)很高、體積很大、環(huán)境復(fù)雜、問題結(jié)構(gòu)不十分清楚的場合，機(jī)器學(xué)習(xí)就屬于這類情況。一般的學(xué)習(xí)系統(tǒng)要求具有隨時間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)環(huán)境，更好達(dá)到目標(biāo)的能力。由于多樣性和復(fù)雜性，通常難以建立完善的理論以指導(dǎo)整個學(xué)習(xí)過程，從而使傳統(tǒng)尋優(yōu)技術(shù)的應(yīng)用受到限制，而這恰好是遺傳算法發(fā)揮的長處。除了機(jī)器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動控制、規(guī)劃設(shè)計、組合優(yōu)化、圖象處理、信號處理、人工生命、模式識別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會科學(xué)等。在人工智能研究中，現(xiàn)在還認(rèn)為人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動機(jī)、混沌理論與人工智能一樣，都是對今后十年的計算技術(shù)有重大影響的關(guān)鍵技術(shù)”。今后幾年，拓廣更加多樣的應(yīng)用領(lǐng)域，將是GA發(fā)展的主流。這也是本世紀(jì)高新技術(shù)迅速發(fā)展帶有規(guī)律性的特點(diǎn)，即面向應(yīng)用。與此同時，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行GA和分布式GA的研究。不論從理論還是應(yīng)用的角度看，最緊迫的應(yīng)是關(guān)于算法收斂性問題的研究，特別是過早收斂的防止。這對GA的實(shí)際應(yīng)用關(guān)系重大。 小結(jié)遺傳算法是一類隨機(jī)化算法，但是它不是簡單的隨機(jī)走動，它可以有效地利用已經(jīng)有的信息處理來搜索那些有希望改善解質(zhì)量的串，類似于自然進(jìn)化，遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進(jìn)行評價，并基于適應(yīng)度值來評價染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會。3 用遺傳算法對具體問題的解決與探討遺傳算法在解決作業(yè)車間調(diào)度問題上比經(jīng)典的啟發(fā)式算法好，同時遺傳算法比傳統(tǒng)的搜索技術(shù)有更強(qiáng)的優(yōu)越性，因為它不僅能解決某一特定問題，而且可以適應(yīng)不同的問題形式。 研究過程中的幾個關(guān)鍵問題 設(shè)備死鎖現(xiàn)象初始解群是問題的起點(diǎn)，解決設(shè)備死鎖問題必須從初始解群開始。本研究的設(shè)備死鎖不在同一臺機(jī)器上而是在不同的機(jī)器上產(chǎn)生死鎖現(xiàn)象，所謂的設(shè)備死鎖現(xiàn)象如圖所示，其中括號內(nèi)的兩個數(shù)據(jù)，意義為（工件號，工序號）。 設(shè)備死鎖示意圖，分屬工件1和工件2的總共四個工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設(shè)備1和設(shè)備2處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。 參數(shù)編碼遺傳編碼技術(shù)是實(shí)施遺傳算法的核心。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€體和問題的解(作為進(jìn)化的個體)。對于同一問題可以有不同的編碼表示方法。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。目前，調(diào)度問題中主要的遺傳算法編碼方式有以下幾種：（operationbased representation）其基本思想是將所有工件的操作進(jìn)行編碼，不同的工件用不同的編碼表示，而同一工件的所有操作在染色體中則用相同的編碼表示，其解碼原則是將染色體上的基因按照從左到右的順序解釋為相應(yīng)工件的操作順序，具有相同編碼的基因按照其在整個染色體中的位置解釋為工件相應(yīng)順序的操作。 加工時間和工藝約束項目工件操作序列123操作時間J1J2J3313352233機(jī)器J1J2J3M1M1M2M2M3M1M3M2M3，假設(shè)染色體為{2 1 2 3 1 1 3 2 3}，Oijk表示第i個工件的第j個工序在第k個機(jī)器上加工（以下同），則對機(jī)器加工順序的工藝約束，該染色體對應(yīng)的有序操作表為[O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務(wù)的第二個操作步驟，…以次類推。（我們用Gantte圖表示一個調(diào)度）。t1296J3J3J3J1J1J1J2J2J2tt1M110734M3M2 Gantte圖（jobbased representation）將每個染色體用n個代表工件的基因組成，是所有工件的一個排列。解碼過程是先加工第1號工件的所有操作，然后依次以最好允許加工時間加工后面所有操作。其基本思想是只對任務(wù)進(jìn)行編碼，然后按照編碼在染色體中的順序來以相應(yīng)的優(yōu)先級別安排任務(wù)。例如，對于上述3*3例子。對于有三項任務(wù)的調(diào)度問題，假設(shè)染色體為[2 3 1]，則可以解釋為首先安排第二項任務(wù)的所有操作，其次是第三項任務(wù)，最后才輪到第一項任務(wù)。（preferences listbeset representation）每個染色體用分別對應(yīng)于m臺不同機(jī)器的m個子串構(gòu)成，各子串是一個長度為n的符號串。用于表示機(jī)器上加工工件的一個排列順序。 ()對染色體的解釋為：在第一臺機(jī)器上首先應(yīng)該安排第二項工件的操作，其次是第一項工件的操作，第三項工件的操作；在第二臺機(jī)器上首先應(yīng)該安排第三項工件的操作，然后是第一、二項任務(wù)的操作，以此類推。前面兩種編碼方式比較復(fù)雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務(wù)相應(yīng)順序的操作。這是一種直接對調(diào)度方案進(jìn)行編碼的方式。顯然，這種解碼過程可產(chǎn)生活動調(diào)度。對于n個工件m機(jī)器問題，一個染色體包括個n*