【正文】 第一種交叉算子 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 22 頁(yè) 在用遺傳算法解決作業(yè)車間調(diào)度問題中 ,在對(duì)工序編碼的排序問題中 ,交叉算子不。 其中 ,∑fi 表示指所有個(gè)體適應(yīng)值之和。評(píng)價(jià)值 (目標(biāo)函數(shù) )較小的個(gè)體有較高的概率生存 ,即在下一代群體中再次出現(xiàn)。但是，變異概率太小則不會(huì)產(chǎn)生新個(gè)體 ，抑制早熟現(xiàn)象的能力較差，概率太大則會(huì)破壞掉很多較好的模式，使 GA 成為隨機(jī)搜索。 pm 變異概率是加大種群多樣性的重要因素。 pc 交叉概率用于控制交叉操作的頻率。通常，種群太小 時(shí)，不能提供足夠的采樣點(diǎn)，以致算法性能很差，甚至得不到問題得可行解；種 群太大時(shí)，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無(wú)疑會(huì)增加計(jì)算量，從而使收斂時(shí)間太長(zhǎng)。目前，如何確定 GA 的最優(yōu)參數(shù)仍舊是一個(gè)公開的問題，也是研究 GA 的重要課題之一。 STEP4:求出適應(yīng)度函數(shù) F=ti(chorm(n))。 STEP2:chrom（ i） 對(duì)應(yīng)相應(yīng)工序的加工機(jī)器為 machiner（ i）。從生物學(xué)角度講 ,適應(yīng)度相當(dāng)于“生存競(jìng)爭(zhēng) ,適者生存”的生物生存能力 ,在遺傳過程中具有重要意義。根據(jù)適應(yīng)度的大小 ,對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰。 初始種群的生成也可以用隨機(jī)方法產(chǎn)生，這是因?yàn)槿后w中的個(gè)體都是由工件的符號(hào)組成的，而且工件任意排列總能產(chǎn)生可行調(diào)度 .在下文的舉例驗(yàn)證過程中我們運(yùn)用了隨機(jī)的方法產(chǎn)生初始種群。重復(fù) STEP1， STEP2， STEP3， STEP4，直到種群滿。 STEP4：重復(fù) STIP2， STEP3，直到 GEN 的所有元素為零。 STEP2：產(chǎn)生一個(gè)整數(shù)隨機(jī)數(shù) 1=p=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é)束?？梢钥闯龉ぜ?j2 的所有工序都用相同的符號(hào) 2 來(lái)命名，并且根據(jù)它出 現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機(jī)器的對(duì)應(yīng)關(guān)系如下 所示。因?yàn)槊總€(gè)工件有三道工序，所以每個(gè)工件在一個(gè)染色體中剛好出現(xiàn)三次。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。顯然，這種解碼過程可產(chǎn)生活動(dòng)調(diào)度。 前面兩種編碼方式比較復(fù)雜，下面我們用基于操作的編碼方式來(lái)解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個(gè)基因代表一道工序，給所有同一工件的工序指定相同的符號(hào)，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務(wù)相應(yīng)順序的操作。用于表示機(jī)器上加工工件的一個(gè)排列順序。對(duì)于有三項(xiàng)任務(wù)的調(diào)度問題，假設(shè)染色體為 [2 3 1]，則可以解釋為首先安排第二項(xiàng)任務(wù)的所有操作，其次是第三項(xiàng)任務(wù)，最后才輪到第一項(xiàng)任務(wù)。 其基本思想是只對(duì)任務(wù)進(jìn)行編碼，然后按照編碼在染色體中的順序來(lái)以相應(yīng)的優(yōu)先級(jí)別安排任務(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 頁(yè) （ jobbased representation） 將每個(gè)染色體用 n個(gè)代表工件的基因組成，是所有工件的一個(gè)排列。 表 加工時(shí)間和工藝約束 項(xiàng)目 工件 操作序列 1 2 3 操作時(shí)間 J1 J2 J3 3 1 3 3 5 2 2 3 3 機(jī)器 J1 J2 J3 M1 M1 M2 M2 M3 M1 M3 M2 M3 對(duì)于上表 3個(gè)工件在 3個(gè)機(jī)器上加工的例子，假設(shè)染色體為 {2 1 2 3 1 1 3 2 3}， Oijk 表示第 i個(gè)工件的第 j 個(gè)工序在第 k 個(gè)機(jī)器上加工（以下同），則對(duì)機(jī)器加工順序的工藝約束，該染色體對(duì)應(yīng)的有序操作表為 [O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個(gè)工件的第一個(gè)操作步驟，然后安排第一個(gè)工件的第一個(gè)操作步驟，第二項(xiàng)任務(wù)的第二個(gè)操作步驟， ? 以次類推。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車 間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€(gè)體和問題的解 (作為進(jìn)化的個(gè)體 )。 圖 設(shè)備死鎖示意圖 在圖 中，分屬工件 1 和工件 2 的總共四個(gè)工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設(shè)備 1 和設(shè)備 2 處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。 研究過程中的幾個(gè)關(guān)鍵問題 設(shè)備死鎖現(xiàn)象 初始解群是問題的起點(diǎn)，解決設(shè)備死鎖問題必須從初始解群開始。與自然界相似，遺傳算法對(duì)待求解問題本身一無(wú)所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行 評(píng)價(jià)，并基于適應(yīng)度值來(lái)評(píng)價(jià)染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì)。這對(duì) GA 的實(shí)際應(yīng)用關(guān)系重大 。與此同時(shí)，理論方面同樣有大量工作 要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行 GA 和分布式 GA 的研究。 今后幾年，拓廣更加多樣的應(yīng)用領(lǐng)域，將是 GA 發(fā)展的主流。 除了機(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é)等。一般的學(xué)習(xí)系統(tǒng)要求具有隨時(shí)間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)環(huán)境，更好達(dá)到目標(biāo)的能力。 遺傳算法主要應(yīng)用在機(jī)器學(xué)習(xí) 中。《 Advanced Computational Intelligence》雜志即將發(fā)刊，由模糊集合創(chuàng)始人 教授為名譽(yù)主編。 1993 年，MIT 出版社創(chuàng)刊了新雜志《 Evolutionary Computation》。 1994 年，他又出版了《遺傳程序設(shè)計(jì)，第二冊(cè) :可重用程序的自動(dòng)發(fā)現(xiàn)》深化了遺傳程序設(shè)計(jì)的研究，使程序設(shè)計(jì)自動(dòng)化展現(xiàn)了新局面。 1991 年， 編輯出版了《遺傳算法手冊(cè)》 （ Handbook of Geic Algorithms） ，其中包括了遺傳算法在工程技術(shù)和社會(huì)生活中的大量應(yīng)用實(shí)例。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會(huì)議還有 Foundations of Geic Algorithms，該會(huì)也是從 1990 年開始隔年召開一次。同年，美國(guó)斯坦福大學(xué)的 Koza 基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來(lái)表達(dá)問題的遺傳程序設(shè)計(jì) ( geic programming, GP)方法，成功地解決了許多問題。 1989 年， Holland 的學(xué) 生 出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》 （ Geic Algorithms in Search , Optimization, and Machine Learning） 。 進(jìn)入八十年代，遺傳算法迎來(lái)了興盛發(fā)展時(shí)期，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門的課題。盡管 De Jong 和 Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 14 頁(yè) 選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時(shí)又提出了諸如代溝 （ generation gap）等新的遺傳操作技術(shù)。同年， Jong 完成了他的博士論文《一 類遺傳自適應(yīng)系統(tǒng)的行為分析》 （ An Analysis of the Behavior of a Class of Geic Adaptive System） 。 Holland 在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極其重要的模式理論 （ schema theory） 。 1975 年是遺傳算法研究 歷史上十分重要的一年。此后， Holland 指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。 1996 年，舉行了第 1 次遺傳程序設(shè)計(jì)國(guó)際會(huì)議，該領(lǐng)域己引起越來(lái)越多的相關(guān)學(xué)者們的興趣。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。所謂人工生命即是用計(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é)合。這一研究不僅對(duì)遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò) ［ 12］ 、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對(duì)開拓 21 世紀(jì)中新的智能計(jì)算技術(shù)將具有重要的意義。 隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人注目的新動(dòng)向 ［ 9］ ：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來(lái)離散的搜索空間 的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法 ［ 10］ 。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代 （ generation） 演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù) 問題域中個(gè)體的適應(yīng)度 （ fitness） 大小選擇 （ selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（ geic operators） 進(jìn)行組合交叉 （ crossover）和變異 （ mutation） ，產(chǎn)生出代表新的解集的種群。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn) （ 即基因型 ） 是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。 遺傳 算法 是從代表問題可能潛在的解集的一個(gè)種群 （ population） 開始的，而一個(gè)種群則由經(jīng)過基因 （ gene） 編碼的一定數(shù) 目的個(gè)體 (individual)組成。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來(lái)，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。 遺傳算法的 進(jìn)展 地球上自出現(xiàn)生命至今已有 30 多億年的歷史，從低級(jí)生物到高級(jí)生命再至擁有智慧的人類，這是一個(gè)漫長(zhǎng)的生物進(jìn)化過程。 ，優(yōu)化問題要具體情況具體分析。而另一種觀點(diǎn)則認(rèn)為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對(duì)于初期的種群來(lái)說(shuō)，交叉幾乎等效于 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 12 頁(yè) 一 個(gè)非常大的變異率，而這么大的變異很可能影響進(jìn)化過程。 ，但交叉和變異的重要性存在爭(zhēng)議。其中一種是所謂觸發(fā)式超級(jí)突變，就是當(dāng)染色體群體的質(zhì)量下降 (彼此的區(qū)別減少 )時(shí)增加突變概率 。 ，用遺傳算法求最優(yōu)解比較困難，因?yàn)槿旧w種群很可能過 早地 斂，而 對(duì)以后變化了的數(shù)據(jù)不再產(chǎn)生變化。 ，在存在噪聲的情況下，對(duì)同一問題利用遺傳算法求解所得的結(jié)果是相似的。 ，容易形成通用算法程序。 ，而不是對(duì)參數(shù)本身，因此遺傳算法具有靈活性高的特點(diǎn)。這種機(jī)制意味著搜索過程可以跳出局部最優(yōu)點(diǎn)，能很好地將局部搜索和全局搜索協(xié)調(diào)起來(lái)，達(dá)到全局最優(yōu)點(diǎn)。另一種為保優(yōu)策略，首先進(jìn)行純選擇，把目前最優(yōu)個(gè)體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失， 但在實(shí)際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃汀? 窗口 (scaling window) 該參數(shù)用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。如果變異概率太大的時(shí)，遺傳算法易變成隨機(jī)搜索，如果變異概率太小，則不能產(chǎn)生新個(gè)體，不利于種群的多樣性。增加種群多樣性具有重要意義。交換概率太小的時(shí)候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。 (population size) 種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時(shí)，不能提供足夠多的個(gè)體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。從總體上來(lái)說(shuō)，每代之間所處理的個(gè)體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨(dú)特的隱含并行性。由馬爾可夫鏈推導(dǎo)出來(lái)的一些結(jié)論 :基本遺傳算法收斂于最優(yōu)解的概率為 1,使用保留最優(yōu)個(gè)體策略的遺傳算法收斂于最優(yōu)解的概率為 1。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。概率太小時(shí)，交叉操作