【正文】 。 STEP2:chrom（ i） 對(duì)應(yīng)相應(yīng)工序的加工機(jī)器為 machiner（ i）。 pc 交叉概率用于控制交叉操作的頻率。 其中 ,∑fi 表示指所有個(gè)體適應(yīng)值之和。評(píng)價(jià)值 (目標(biāo)函數(shù) )較小的個(gè)體有較高的概率生存 ,即在下一代群體中再次出現(xiàn)。通常，種群太小 時(shí)，不能提供足夠的采樣點(diǎn)，以致算法性能很差，甚至得不到問(wèn)題得可行解；種 群太大時(shí)，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無(wú)疑會(huì)增加計(jì)算量，從而使收斂時(shí)間太長(zhǎng)。從生物學(xué)角度講 ,適應(yīng)度相當(dāng)于“生存競(jìng)爭(zhēng) ,適者生存”的生物生存能力 ,在遺傳過(guò)程中具有重要意義。 STEP4：重復(fù) STIP2， STEP3，直到 GEN 的所有元素為零。因?yàn)槊總€(gè)工件有三道工序，所以每個(gè)工件在一個(gè)染色體中剛好出現(xiàn)三次。用于表示機(jī)器上加工工件的一個(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è)操作步驟， ? 以次類推。 研究過(guò)程中的幾個(gè)關(guān)鍵問(wèn)題 設(shè)備死鎖現(xiàn)象 初始解群是問(wèn)題的起點(diǎn)，解決設(shè)備死鎖問(wèn)題必須從初始解群開始。 今后幾年，拓廣更加多樣的應(yīng)用領(lǐng)域，將是 GA 發(fā)展的主流?！?Advanced Computational Intelligence》雜志即將發(fā)刊，由模糊集合創(chuàng)始人 教授為名譽(yù)主編。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會(huì)議還有 Foundations of Geic Algorithms，該會(huì)也是從 1990 年開始隔年召開一次。盡管 De Jong 和 Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 14 頁(yè) 選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時(shí)又提出了諸如代溝 （ generation gap）等新的遺傳操作技術(shù)。此后， Holland 指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。這一研究不僅對(duì)遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn) （ 即基因型 ） 是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。 ，優(yōu)化問(wèn)題要具體情況具體分析。 ，用遺傳算法求最優(yōu)解比較困難，因?yàn)槿旧w種群很可能過(guò) 早地 斂，而 對(duì)以后變化了的數(shù)據(jù)不再產(chǎn)生變化。這種機(jī)制意味著搜索過(guò)程可以跳出局部最優(yōu)點(diǎn)，能很好地將局部搜索和全局搜索協(xié)調(diào)起來(lái)，達(dá)到全局最優(yōu)點(diǎn)。增加種群多樣性具有重要意義。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。 遺傳算法的收斂性分析 遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來(lái)防止最優(yōu)解的遺失。 模式定理保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。 交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過(guò)程所選擇的高適應(yīng)度的模式。自然選擇決定了群體中那些個(gè)個(gè)體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。進(jìn)化是發(fā)生在編碼染色體上，通過(guò)對(duì)染色體的譯碼部分生成生物體，但下面幾個(gè)關(guān)于進(jìn)化理論的一般特性已被廣大人們所接受。第一章簡(jiǎn)要介紹了車間調(diào)度問(wèn)題和求解調(diào)度問(wèn)題的基本方法 ；第 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 5 頁(yè) 二章介紹了遺傳算法的基本理論；第三章用遺傳算法來(lái)解決車間調(diào)度問(wèn)題 ,其中介紹了常用的幾種編碼方式 ,在比較的情況下提出本文主要用基于操作的編碼方式 .還有提出了幾種主要的遺傳算子。事實(shí)上，工件排列陣就是調(diào)度的一種表示形式。 MJ （ i， j）表示 i工件的第 j 道工序的機(jī)器號(hào)， (, )MJi? 表示 i工件的所有工序按優(yōu)先順序加工的各機(jī)器號(hào)的排列。 6. 緩沖區(qū)容量為無(wú)窮大。它所要解決的問(wèn)題就是確定每臺(tái)機(jī)器上不同工件的加工順序，以及每個(gè)工件的所有工序的起始加工時(shí)間，以最優(yōu)化某個(gè)性能指標(biāo)。 車間作業(yè)是指利用車間資源 (如機(jī)床、刀具、夾具等 )完成的某項(xiàng)任務(wù)。 作業(yè) 車間調(diào)度問(wèn)題表述 作業(yè)車間調(diào)度（ jobshop）問(wèn)題可以表述為：設(shè)有 N個(gè)工件在 M臺(tái)機(jī)器上加工，根據(jù)工件加工工藝的要求，每個(gè)工件使用 機(jī)器的順序及其每道工序所花時(shí)間已給定，調(diào)度問(wèn)題的目標(biāo)就是如何選擇加工順序使得總的加工時(shí)間最短最優(yōu)。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特點(diǎn)和趨勢(shì)。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。 geic algorithm。在當(dāng)今的競(jìng)爭(zhēng)環(huán)境下，如何利用計(jì)算機(jī)技術(shù)實(shí)現(xiàn)生產(chǎn)調(diào)度計(jì)劃優(yōu)化，快速調(diào)整資源配置，統(tǒng)籌安排生產(chǎn)進(jìn)度，提高設(shè)備利用率已成為許多加工企業(yè)面臨的重大課題。 在研究了作業(yè)車 間調(diào)度問(wèn)題數(shù)學(xué)模型和優(yōu)化算法的基礎(chǔ)上，將一種改進(jìn)的自適應(yīng)遺傳算法應(yīng)用在作業(yè)車間調(diào)度中。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過(guò)的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過(guò)的材料。本人授權(quán) 大學(xué)可以將 本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。目前的調(diào)度算法大多只關(guān)心工件的調(diào)度問(wèn)題，而對(duì)其它資源分配問(wèn)題則研究相對(duì)不多，將二者 結(jié)合起來(lái)研究應(yīng)該是值得注意的問(wèn)題，目前已有不少學(xué)者開始關(guān)注該問(wèn)題。 求解調(diào)度問(wèn)題的方法稱為調(diào)度優(yōu)化算法。在此基礎(chǔ)上，可對(duì)車間作業(yè)調(diào)度問(wèn)題進(jìn)行一般性的描述 :假定有多個(gè)工件，要經(jīng)過(guò)多臺(tái)機(jī)器加工。 此外，還有一些輔助假設(shè)條件，如下 : 1. 各工件經(jīng)過(guò)其準(zhǔn)備時(shí)間后可開始加工 。我們定義以下基本數(shù)學(xué)符號(hào) ［ 6］ ： J:所有工件的集合， 12{ , , }nJ J J J? ； M:所有機(jī)器的集合， 12{ , , }mM M M M? ； ijP： 工件 Ji 的工序集合， 12{ , , }i i i i ij j j j pP P P P?； P:所有工序的集合，此為 12m ax{ , , }nn P P P? 矩陣。 T(i, j)表示工件 i的第 j 道工序在 MJ（ i， j） 上的加工時(shí)間。 生產(chǎn) 調(diào)度問(wèn)題存在多種優(yōu)化目標(biāo)或者綜合優(yōu)化目標(biāo)，調(diào)度問(wèn)題的優(yōu)化目標(biāo)通常從兩個(gè)方面來(lái)考慮 :生產(chǎn)成本和生產(chǎn)時(shí)間。它摒棄了 傳統(tǒng)的搜索方式，模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程 ［ 8］ 。 ，變異可以使生物體子代 的染色體不同于它們父代的染色體，通過(guò)結(jié)合兩個(gè)父代染色體的物質(zhì)，重組過(guò)程可以在子代中產(chǎn)生有很大差異的染色體。運(yùn)用選擇、交叉、變異算子產(chǎn)生新一代群體； ，若找到滿足問(wèn)題的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)步驟 3。其中一方不具有模式 H 的概率為 1 p(H, t)，當(dāng)兩個(gè)個(gè)體發(fā)生交換時(shí)，如果引起模式 H 的改變，只可能將交換的起始位置選擇在第一個(gè)模式位到最后一個(gè)模式位之間的任何一個(gè)位置上，此時(shí)，使模式 H 生存的概率 Ps，為 : ()1 1scHPPl??? ? () 在交換過(guò)程中，可能使兩個(gè)都不具備模式 H 的個(gè)體經(jīng)交換后產(chǎn)生模式 H，故生存概率（ ()1 1c HP l?? ?）只是一個(gè)下界，則有： 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 8 頁(yè) ()11scHPPl??? ? () 綜合考慮選擇操作，模式 H 在下一代中的數(shù)量可以用下式來(lái)綜合估計(jì) : _( ) ( )( , 1 ) ( , ) ( 1 )1cf H Hm H t m H t p lf ?? ? ? ?? () 從上式可以看出，模式的平均適應(yīng)度高于群體平均適應(yīng)度，并且具有短 定義距的模式，將在下一代中成指數(shù)級(jí)的增長(zhǎng)。 基因塊假設(shè) :遺傳算法通過(guò)短定義距、低階以及高平均適應(yīng)度的模式 (基因塊 )，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無(wú)疑會(huì)增加計(jì)算量，造成收斂時(shí)間太長(zhǎng)，表現(xiàn)為收斂速度緩慢。 遺傳操作對(duì)收斂性的影響，可利用馬爾可夫鏈對(duì)遺傳算法進(jìn)行分析，從而論證了遺傳算法在收斂性方面的一些重要性質(zhì)，有力地支持了遺傳算法的理論基礎(chǔ)。種群選擇過(guò)大時(shí)，雖然能避免早熟收斂，但是增加了計(jì)算量。 (generation gap) 代溝 G 用于控制每一代群體被替換的比例，每代有 N (1G)個(gè)父代個(gè)體選中進(jìn)入下一代種群中，該參數(shù)和交換、變異概率以及選擇策略有很大關(guān)系，它并不是一個(gè)初始參數(shù)，而是評(píng)價(jià)遺傳算法的一個(gè)參數(shù)。 ，而非傳統(tǒng)方法的采用目標(biāo)函數(shù)的導(dǎo)數(shù)信息或者求解問(wèn)題域內(nèi)知識(shí)，因此具有普遍適應(yīng)性和可規(guī)?；奶攸c(diǎn)。另一種叫隨機(jī)外來(lái)染色體，是偶爾加入一些全新的隨機(jī)生成的染色體個(gè)體，從而增加染色體多樣性。 1859 年，達(dá)爾文根據(jù)長(zhǎng) 期對(duì)世界各地的考察以及人工選擇的實(shí)驗(yàn)，發(fā)表了 《 物種起源 》 ，系統(tǒng)地提出并建立了以“優(yōu)勝劣汰”、“適者生存”的自然選擇為基礎(chǔ)的進(jìn)化論學(xué)說(shuō)，根據(jù)他的進(jìn)化論，生物發(fā)展進(jìn)化的原因主要有三個(gè)，就是遺傳、變異和選擇。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼（ decoding） ，可以作為問(wèn)題近似最優(yōu)解 。 EP 和 ES 幾乎是和遺傳算法同時(shí)獨(dú)立發(fā)展起來(lái)的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計(jì)算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。這一年 Holland 出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》 （ Adaptation in Natural and Artificial Systems） ，這是第一本系統(tǒng)論述遺傳算法的專著，因此有人把 1975 年作為遺傳算法的誕生年。 1985 年，在美國(guó)召開了第一屆遺傳算法國(guó)際會(huì)議 （ International Conference on Geic Algorithms ， ICGA） ，并且成立國(guó)際遺傳算法學(xué)會(huì) （ International Society of Geic Algorithms ， ISGA） ，以后每?jī)赡昱e行一次。 1992 年， Koza 發(fā)表了他的專著《遺傳程序設(shè)計(jì) :基于自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)》。 遺傳算法適合于維數(shù)很高、體積很大、環(huán)境復(fù)雜、問(wèn)題結(jié)構(gòu)不十分清楚的場(chǎng)合，機(jī)器學(xué)習(xí)就屬于這類情況。不論從理論還是應(yīng)用的角度看，最緊迫的應(yīng)是關(guān)于算法收斂性問(wèn)題的研究，特別是過(guò)早收斂的防止。 參數(shù)編碼 遺傳編碼技術(shù)是實(shí)施遺傳算法的核心。解碼過(guò)程是先加工第 1 號(hào)工件的所有操作，然后依次以最好允許加工時(shí)間加工后面所有操作。這是一種直接對(duì)調(diào)度方案進(jìn)行編碼的方式。 染色體 1 1 2 2 3 3 1 1 2 3 ↓ ↓ ↓ 機(jī)器 1 2 3 一個(gè)好的調(diào)度方法（換句話說(shuō)就是染色體對(duì)應(yīng)的適應(yīng)度值高），可以有效提機(jī)器 的利用率，降低機(jī)器空閑的時(shí)間長(zhǎng)度，從而達(dá)到優(yōu)化的目的，遺傳算法就是來(lái)尋找這樣的更優(yōu)的調(diào)度策略。 這是用遺傳算法解決車間調(diào)度問(wèn)題的一種初始化群體方法 ［ 13］ ，但是它并不適用于基于操作的編碼方式。 ti(chrom(1))=ti(chrom(1),machine(1)) STEP3:for i=2 to n For k=1 to n ti(chrom(i))=ti(chrom(i1))+max(ti(chrom(ik),machine(ik)+k)) 其中若當(dāng) ik=0,則ti(chrom(ik),machine(ik))=0,還有要判斷 chorm(i)所對(duì)應(yīng)的工件在以前是否加工過(guò)，若加工過(guò)，則 ti(chrom(i))=ti(chorm(i1))。交叉概率太大時(shí)，種群中串的更新很快，進(jìn)而會(huì)使高適應(yīng)值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前。