【正文】 對群體中各個體的適應(yīng)值做比較 ,將適應(yīng)值小的個體復(fù)制 ,將 適應(yīng)值大的淘汰掉 ,這是因為在作業(yè)調(diào)度算法中的適應(yīng)度函數(shù)為在 M 臺機器上加工完 N 個工件所需的時間 ,時間越短 ,更能達(dá)到優(yōu)化的目的。 遺傳算子的設(shè)計 選擇操作是對自然界“適者生存 ” 的模擬。 M 種群數(shù)目是影響算法最終優(yōu)化性能和效率的因素之一。適應(yīng)度是驅(qū)動遺傳算法的動力。 STEP3：令 chrom（ i） =p，并且將矩陣 GEN 的 p 行 GEN（ p，：）左移一個元素，此行移出的最后 一個元素 用 零代替。 如果染色體位為 [3 2 2 1 1 2 3 1 3 1]，其中 1 表示工件 j1， 2 表示工件 j2， 3 表示工件 j3。 （ preferences listbeset representation） 每個染色體用分別對應(yīng)于 m 臺不同機器的 m 個子串構(gòu)成，各子串是一個長度為 n的符號串。 目前，調(diào)度問題中主要的遺傳算法編碼方式有以下幾種： （ operationbased representation） 其基本思想是將所有工件的操作進行編碼，不同的工件用不同的編碼表示，而同一 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 17 頁 工件的所有操作在染色體中則用相同的編碼表示，其解碼原則是將染色體上的基因按照從左到右的順序解釋為相應(yīng)工件的操作順序，具有相同編碼的基因按照其在整個染色體中的位置解釋為工件相應(yīng)順序的 操作。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 16 頁 3 用遺傳算法對具體問題的解決與探討 遺傳算法 在解決作業(yè)車間調(diào)度問題上 比經(jīng)典的啟發(fā)式算法好，同時遺傳算法比傳統(tǒng)的搜 索技術(shù) 有 更強的 優(yōu)越 性，因為它不僅能解決某一特定問 題，而且可以適應(yīng)不同的問題形式。在人工智能研究中，現(xiàn)在還認(rèn)為人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動機、混沌理論與人工智能一樣，都是對今后十年的計算技術(shù)有重大影響的關(guān)鍵技術(shù)”。 1997 年， IEEE 又創(chuàng)刊了《 Transactions on Evolutionary Computation》。 在歐洲，從 1990 年開始每隔一年舉辦一次 Parallel Problem Solving from Nature 學(xué)術(shù)會議，其中遺傳算法是會議主要內(nèi)容之一。該論文所做的研究工作，可看作是遺傳算法發(fā)展進程中的一個里程碑，這是因為，他把 Holland 的模式理論與他的計算實驗結(jié)合起來。 1967 年， Holland 的學(xué)生 在博士論文中首次提出 “ 遺傳算法 （ Geic Algorithms） ” 一詞。三是并行處理的遺傳算法的研究十分活躍。每個個體實際上是染色體 (chromosome)帶有特征的實體。 “大海撈針”的問題，所謂“大海撈針”問題就是沒有一個確切的適應(yīng)度函數(shù)表征個體好壞的問題，遺傳算法對這類問題無法找到收斂的路。 遺傳算法的缺點 ，而不能達(dá)到全局最優(yōu)。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 11 頁 遺傳算法的優(yōu)缺點 遺傳算法的優(yōu)點 遺傳算法在解決優(yōu)化問題過程中有如 下優(yōu)點 : ，而不是從單個解開始。 (mutation rate) 變異概率 Pm。由隱含并行性定理可知，雖然表面上每代僅對 N 個個體處理操作，而事實上處理了O(N3)個模式，且無需額外存儲。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉 。目前已經(jīng)有大量的實踐證據(jù)支持這一假 設(shè)，盡管大量的證據(jù)并不等于理論證明，但是至少可以肯定的是對很多經(jīng)常碰到的問題，遺傳算法都是適用的。 模式定理 :在遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級增長。通過把各碼鏈適應(yīng)值轉(zhuǎn)換為一組具有線性序的區(qū)間，從而可利用二分查找法實現(xiàn)“輪盤賭”選擇操作的遞歸算法，使時間復(fù)雜度下降到 O（ nlog2n）。自然選擇的原則是適應(yīng)者生存，不適者淘汰。 雖然目前人們對進化機制在一些方面還沒有弄清楚，但它們的一些特征已為人所知。 課題研究內(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 :機器順序陣， 此為 12m ax{ , , }nn P P P? 矩陣。 5. 工件的加工時間事先給定，且在整個加工過程中保持不變 。車間作業(yè)調(diào)度問題中，每個工件都有獨特的加工路線 ［ 5］ 。本文從實際和理論兩方面進行研究和深入，重點研究了現(xiàn)代進化算法中有代表性發(fā)展優(yōu)勢的遺傳算法 。一些學(xué)者們經(jīng)過大量的實踐證明了 遺傳算法在解決作業(yè)車間調(diào)度問題上 比經(jīng)典的啟發(fā)式算法好，同時遺傳算法比傳統(tǒng)的搜索技術(shù) 有更強的 優(yōu)越 性，因為它不僅能解決某一特定問題，而且可以適應(yīng)不同的問 題形式 ［ 2］ 。 當(dāng)前科學(xué)技術(shù)正進入多學(xué)科互相交叉、互相滲透、互相影響的時代，生命科學(xué)與工程科學(xué)的交叉、滲透和相互促進是其中一個 典型例子，也是近代科學(xué)技術(shù)發(fā)展的一個顯著特點。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。 關(guān)鍵詞 ： 作業(yè) 車間調(diào)度； 遺傳算法；改進染色體編碼 ； 生產(chǎn)周期 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 II 頁 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)度問題是計算機集成制造系統(tǒng) (CIMS)工程中的一個重要組成部分，它對企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。該算法是將 sigmoid 函數(shù)的變形函數(shù)應(yīng)用到自適應(yīng)遺傳算法中，并將作業(yè)車間調(diào)度問題中的完工時間大小作為算法的評價指標(biāo)，實現(xiàn)了交叉率和變異率隨著完工時間的非線性自適應(yīng)調(diào)整，較好地克服了標(biāo)準(zhǔn)遺傳算法在解決作業(yè)車間調(diào)度問題時的“早熟”和穩(wěn)定性差的缺點，以及傳統(tǒng)的線性自適應(yīng)遺傳算法收斂速度慢的缺點。對本研究提供過幫助和做出過貢獻(xiàn)的個人或集體，均已在文中作了明確的說明并表示了謝意。 涉密論文按學(xué)校規(guī)定處理。 由于一般車間調(diào)度問題的復(fù)雜性，各種不同的具體問題往往有許多不同的算法來解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。它可分為精確求解方法和近視求解方法。一個工件在一臺機器上的加工程序稱為一道“工序”，相應(yīng)的加工時間稱為該工序的“加工時間”。 2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒有優(yōu)先約束關(guān)系限制的 。 P（ i， j） 表 示 i工件的第 j 道工序。同樣地，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿 。調(diào)度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標(biāo)有 :庫存最少、在制品最少、設(shè)備利用率最高等 。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復(fù)進行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進行評價，依據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。 。 遺傳算法的 模式定理 選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級增長。 通過變異操作對個體串中單個位置進行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在 。 影響 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。由馬爾可夫鏈推導(dǎo)出來的一些結(jié)論 :基本遺傳算法收斂于最優(yōu)解的概率為 1,使用保留最優(yōu)個體策略的遺傳算法收斂于最優(yōu)解的概率為 1。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。 窗口 (scaling window) 該參數(shù)用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。 ，容易形成通用算法程序。 ，但交叉和變異的重要性存在爭議。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。 隨著應(yīng)用領(lǐng)域的擴展，遺傳算法的研究出現(xiàn)了幾個引人