【正文】 對(duì)群體中各個(gè)體的適應(yīng)值做比較 ,將適應(yīng)值小的個(gè)體復(fù)制 ,將 適應(yīng)值大的淘汰掉 ,這是因?yàn)樵谧鳂I(yè)調(diào)度算法中的適應(yīng)度函數(shù)為在 M 臺(tái)機(jī)器上加工完 N 個(gè)工件所需的時(shí)間 ,時(shí)間越短 ,更能達(dá)到優(yōu)化的目的。 遺傳算子的設(shè)計(jì) 選擇操作是對(duì)自然界“適者生存 ” 的模擬。 M 種群數(shù)目是影響算法最終優(yōu)化性能和效率的因素之一。適應(yīng)度是驅(qū)動(dòng)遺傳算法的動(dòng)力。 STEP3：令 chrom（ i） =p，并且將矩陣 GEN 的 p 行 GEN（ p，：）左移一個(gè)元素，此行移出的最后 一個(gè)元素 用 零代替。 如果染色體位為 [3 2 2 1 1 2 3 1 3 1]，其中 1 表示工件 j1， 2 表示工件 j2， 3 表示工件 j3。 （ preferences listbeset representation） 每個(gè)染色體用分別對(duì)應(yīng)于 m 臺(tái)不同機(jī)器的 m 個(gè)子串構(gòu)成，各子串是一個(gè)長(zhǎng)度為 n的符號(hào)串。 目前，調(diào)度問(wèn)題中主要的遺傳算法編碼方式有以下幾種： （ operationbased representation） 其基本思想是將所有工件的操作進(jìn)行編碼，不同的工件用不同的編碼表示，而同一 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 17 頁(yè) 工件的所有操作在染色體中則用相同的編碼表示，其解碼原則是將染色體上的基因按照從左到右的順序解釋為相應(yīng)工件的操作順序，具有相同編碼的基因按照其在整個(gè)染色體中的位置解釋為工件相應(yīng)順序的 操作。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 16 頁(yè) 3 用遺傳算法對(duì)具體問(wèn)題的解決與探討 遺傳算法 在解決作業(yè)車間調(diào)度問(wèn)題上 比經(jīng)典的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜 索技術(shù) 有 更強(qiáng)的 優(yōu)越 性，因?yàn)樗粌H能解決某一特定問(wèn) 題，而且可以適應(yīng)不同的問(wèn)題形式。在人工智能研究中，現(xiàn)在還認(rèn)為人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動(dòng)機(jī)、混沌理論與人工智能一樣，都是對(duì)今后十年的計(jì)算技術(shù)有重大影響的關(guān)鍵技術(shù)”。 1997 年， IEEE 又創(chuàng)刊了《 Transactions on Evolutionary Computation》。 在歐洲，從 1990 年開(kāi)始每隔一年舉辦一次 Parallel Problem Solving from Nature 學(xué)術(shù)會(huì)議，其中遺傳算法是會(huì)議主要內(nèi)容之一。該論文所做的研究工作，可看作是遺傳算法發(fā)展進(jìn)程中的一個(gè)里程碑，這是因?yàn)椋?Holland 的模式理論與他的計(jì)算實(shí)驗(yàn)結(jié)合起來(lái)。 1967 年， Holland 的學(xué)生 在博士論文中首次提出 “ 遺傳算法 （ Geic Algorithms） ” 一詞。三是并行處理的遺傳算法的研究十分活躍。每個(gè)個(gè)體實(shí)際上是染色體 (chromosome)帶有特征的實(shí)體。 “大海撈針”的問(wèn)題，所謂“大海撈針”問(wèn)題就是沒(méi)有一個(gè)確切的適應(yīng)度函數(shù)表征個(gè)體好壞的問(wèn)題，遺傳算法對(duì)這類問(wèn)題無(wú)法找到收斂的路。 遺傳算法的缺點(diǎn) ，而不能達(dá)到全局最優(yōu)。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 11 頁(yè) 遺傳算法的優(yōu)缺點(diǎn) 遺傳算法的優(yōu)點(diǎn) 遺傳算法在解決優(yōu)化問(wèn)題過(guò)程中有如 下優(yōu)點(diǎn) : ，而不是從單個(gè)解開(kāi)始。 (mutation rate) 變異概率 Pm。由隱含并行性定理可知，雖然表面上每代僅對(duì) N 個(gè)個(gè)體處理操作，而事實(shí)上處理了O(N3)個(gè)模式，且無(wú)需額外存儲(chǔ)。交叉概率太大時(shí)，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉 。目前已經(jīng)有大量的實(shí)踐證據(jù)支持這一假 設(shè)，盡管大量的證據(jù)并不等于理論證明，但是至少可以肯定的是對(duì)很多經(jīng)常碰到的問(wèn)題，遺傳算法都是適用的。 模式定理 :在遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級(jí)增長(zhǎng)。通過(guò)把各碼鏈適應(yīng)值轉(zhuǎn)換為一組具有線性序的區(qū)間，從而可利用二分查找法實(shí)現(xiàn)“輪盤(pán)賭”選擇操作的遞歸算法，使時(shí)間復(fù)雜度下降到 O（ nlog2n）。自然選擇的原則是適應(yīng)者生存，不適者淘汰。 雖然目前人們對(duì)進(jìn)化機(jī)制在一些方面還沒(méi)有弄清楚，但它們的一些特征已為人所知。 課題研究?jī)?nèi)容及結(jié)構(gòu)安排 本文共分為三 章。同上，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。 1 11 1 1 111121 2 ( 1 )110 0 000in n n n iiiP PPj j j Pj j j p j PPPPP P PPP P P P?????????????? （ ） MJ :機(jī)器順序陣， 此為 12m ax{ , , }nn P P P? 矩陣。 5. 工件的加工時(shí)間事先給定，且在整個(gè)加工過(guò)程中保持不變 。車間作業(yè)調(diào)度問(wèn)題中，每個(gè)工件都有獨(dú)特的加工路線 ［ 5］ 。本文從實(shí)際和理論兩方面進(jìn)行研究和深入，重點(diǎn)研究了現(xiàn)代進(jìn)化算法中有代表性發(fā)展優(yōu)勢(shì)的遺傳算法 。一些學(xué)者們經(jīng)過(guò)大量的實(shí)踐證明了 遺傳算法在解決作業(yè)車間調(diào)度問(wèn)題上 比經(jīng)典的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜索技術(shù) 有更強(qiáng)的 優(yōu)越 性，因?yàn)樗粌H能解決某一特定問(wèn)題，而且可以適應(yīng)不同的問(wèn) 題形式 ［ 2］ 。 當(dāng)前科學(xué)技術(shù)正進(jìn)入多學(xué)科互相交叉、互相滲透、互相影響的時(shí)代，生命科學(xué)與工程科學(xué)的交叉、滲透和相互促進(jìn)是其中一個(gè) 典型例子，也是近代科學(xué)技術(shù)發(fā)展的一個(gè)顯著特點(diǎn)。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)的成果作品。 關(guān)鍵詞 ： 作業(yè) 車間調(diào)度； 遺傳算法；改進(jìn)染色體編碼 ； 生產(chǎn)周期 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 II 頁(yè) Solving jopshop scheduling problem based on geic algorithm Abstract Simply speaking, the job shop scheduling problem(JSP) is the equipment resources optimization question. Job Shop Scheduling Problem as an important part of Computer IntegratedManufacturing System (CIMS) engineering is indispensable, and has vital effect onproduction management and control system. In the petion ecvironment nowadays, how touse the assignments quickly and to plan production with due consideration for all concernedhas bee a great subject for many recent years,the geic algorithms obtained great development it was used to solve the job shop scheduling problem paper discusses the chromosome code method in detail based on the geic algorithms and make the improvement on it. Through the research on mathematics model of JSP and optimized algorithm, theimproved adaptive geic algorithm (IAGA) obtained by applying the improved sigmoidfunction to adaptive geic algorithm is proposed. And in IAGA for JSP, the fitness ofalgorithm is represented by pletion time of jobs. Therefore, this algorithm making thecrossover and mutation probability adjusted adaptively and nonlinearly with the pletiontime, can avoid such disadvantages as premature convergence, low convergence speed andlow stability. Experimental results demonstrate that the proposed geic algorithm does notget stuck at a local optimum easily, and it is fast in convergence, simple to be implemented. the job shop scheduling system based on IAGA and GASH is designed andrealized, and the functions and operations of the system modules are introduced detailedly. In the end ,according to the code with improved carries on the geic algorithms desing, this paper offer one improved geic algorithms about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid. Keywords: jop shop scheduling。 作業(yè) 車間調(diào)度問(wèn)題是計(jì)算機(jī)集成制造系統(tǒng) (CIMS)工程中的一個(gè)重要組成部分，它對(duì)企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。該算法是將 sigmoid 函數(shù)的變形函數(shù)應(yīng)用到自適應(yīng)遺傳算法中，并將作業(yè)車間調(diào)度問(wèn)題中的完工時(shí)間大小作為算法的評(píng)價(jià)指標(biāo)，實(shí)現(xiàn)了交叉率和變異率隨著完工時(shí)間的非線性自適應(yīng)調(diào)整，較好地克服了標(biāo)準(zhǔn)遺傳算法在解決作業(yè)車間調(diào)度問(wèn)題時(shí)的“早熟”和穩(wěn)定性差的缺點(diǎn)，以及傳統(tǒng)的線性自適應(yīng)遺傳算法收斂速度慢的缺點(diǎn)。對(duì)本研究提供過(guò)幫助和做出過(guò)貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說(shuō)明并表示了謝意。 涉密論文按學(xué)校規(guī)定處理。 由于一般車間調(diào)度問(wèn)題的復(fù)雜性，各種不同的具體問(wèn)題往往有許多不同的算法來(lái)解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。它可分為精確求解方法和近視求解方法。一個(gè)工件在一臺(tái)機(jī)器上的加工程序稱為一道“工序”，相應(yīng)的加工時(shí)間稱為該工序的“加工時(shí)間”。 2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒(méi)有優(yōu)先約束關(guān)系限制的 。 P（ i， j） 表 示 i工件的第 j 道工序。同樣地，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿 。調(diào)度問(wèn)題從生產(chǎn)成本方面來(lái)考慮，其優(yōu)化目標(biāo)有 :庫(kù)存最少、在制品最少、設(shè)備利用率最高等 。它將問(wèn)題域中的可能解看作是群體的一個(gè)個(gè)體或染色體，并將每一個(gè)體編碼成符號(hào)串形式，對(duì)群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，依據(jù)適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時(shí)以全局并行搜索方式來(lái)搜索優(yōu)化群體中的最優(yōu)個(gè)體，求得滿足要求的最優(yōu)解。 。 遺傳算法的 模式定理 選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級(jí)增長(zhǎng)。 通過(guò)變異操作對(duì)個(gè)體串中單個(gè)位置進(jìn)行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而使遺傳算法找到全局最優(yōu)解的可能性存在 。 影響 選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。由馬爾可夫鏈推導(dǎo)出來(lái)的一些結(jié)論 :基本遺傳算法收斂于最優(yōu)解的概率為 1,使用保留最優(yōu)個(gè)體策略的遺傳算法收斂于最優(yōu)解的概率為 1。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。 窗口 (scaling window) 該參數(shù)用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。 ，容易形成通用算法程序。 ，但交叉和變異的重要性存在爭(zhēng)議。通過(guò)不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來(lái)，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。 隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人