基于遺傳算法的柔性車間作業(yè)調(diào)度 - 畢業(yè)設(shè)計正文

《基于遺傳算法的柔性車間作業(yè)調(diào)度 - 畢業(yè)設(shè)計正文》由會員分享，可在線閱讀，更多相關(guān)《基于遺傳算法的柔性車間作業(yè)調(diào)度 - 畢業(yè)設(shè)計正文（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 基于遺傳算法的柔性車間作業(yè)調(diào)度 摘要 車間生產(chǎn)調(diào)度問題是當(dāng)今工程領(lǐng)域研究的熱點。近十幾年來，面向用戶個性化需求的定制生產(chǎn)模式開始成為制造的主流，對市場需求的快速反應(yīng)能力開始成為企業(yè)能否在激烈的市場競爭中占得一席之地的重要標(biāo)志，因此，柔性快速的生產(chǎn)調(diào)度就顯得格外重要。 柔性作業(yè)車間調(diào)度是古典作業(yè)調(diào)度問題的擴展，柔性作業(yè)車間調(diào)度問題由于減少了機器的約束，所以比傳統(tǒng)作業(yè)車間調(diào)度問題的復(fù)雜性更高。因此，尋找有效的方法對柔性作業(yè)車間調(diào)度問題進行求解具有重要的理論價值和應(yīng)用意義。 本文首先介紹國內(nèi)外車間調(diào)度研究的方法和發(fā)展現(xiàn)狀，然后闡述遺傳算法的基本概念、原理和

2、方法。其次對所研究的作業(yè)車間調(diào)度進行了詳細的數(shù)學(xué)分析，并對數(shù)學(xué)描述進行了簡化，為下一步的算法設(shè)計建立數(shù)學(xué)模型。針對柔性作業(yè)車間調(diào)度問題的特點，提出了一種改進的遺傳算法，采用雙子串的方式來進行編碼，并且基于此給出了獨特的交叉和變異法則，從而取消了運用遺傳算法求解作業(yè)車間問題時為使基因合法化而進行的基因修復(fù)和重建過程。 最后給出了一個4×6 調(diào)度問題的測試?yán)樱⑶依L制出了作業(yè)調(diào)度的甘特圖。仿真實例證明了此算法的有效性。 關(guān)鍵詞：柔性車間作業(yè)調(diào)度；遺傳算法 ；雙子串編碼 Flexible Job-Shop Scheduli

3、ng Problem Based on Genetic Algorithm ABSTRACT Job-shop scheduling problem is the scientific research hotspot , in the past dozens of years, User-oriented personalized needs customization product mode starts to become the mainstream of manufacturing, the capability of rapid response in market dema

4、nds come to be an important symbol that whether the enterprise can occupy a room in the fierce market competition The flexible job shop scheduling problem is a generalization of the classical job shop scheduling problem. Due to machine constraint, flexible job shop scheduling is much more complex t

5、han traditional job shop scheduling. Thus, seeking the effective methods used to solve flexible job shop scheduling has important theoretical and applied significance. This paper firstly introduces the methods and developments about workshop scheduling inside and outside country; secondly expatiate

6、s the basic conception and principle about genetic algorithm; then analyses the job shop scheduling problem，and also predigests the mathematic depiction so as to convenience further program design. According to the characteristics of flexible job shop scheduling problem , an improved genetic algorit

7、hm has been adopted. It uses two multistage-based model to code. Based on that a special crossover operators and mutation operators are designed for genetic algorithm, By doing that, the repairing process to validate the schedule gene is successfully can—celled. In this paper, Finally , a example o

8、f 8 ×6 scheduling showed that the genetic algorithm was efficient .At the same time ,give the arithmetic examples of job shop，and show their schedule Gantt pictures． Key words: flexible job shop scheduling problem ；genetic algorithm; two multistage-based model to code. II 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 目錄

9、 摘要………………………………………………………………………………………………I ABSTRACT ……………………………………………………………………………………II 緒論………………………………………………………………………………………………1 1車間作業(yè)調(diào)度…………………………………………………………………………………2 1.1車間調(diào)度問題的研究意義 …………………………………………………………………2 1.2車間調(diào)度問題研究現(xiàn)狀 ……………………………………………………………………2 1.3車間調(diào)度問題的分類 ………………………………………………………………………3 1

10、.4實際車間調(diào)度問題的特點 …………………………………………………………………3 1.5車間調(diào)度問題的研究方法 …………………………………………………………………4 1.6實際車間生產(chǎn)調(diào)度研究中存在的主要問題 ………………………………………………5 1.7柔性車間作業(yè)調(diào)度問題 ……………………………………………………………………5 1.7.1問題描述 …………………………………………………………………………………5 1.7.2數(shù)學(xué)描述 …………………………………………………………………………………6 1.8 Gantt圖…………………………………………………………………………………

11、……7 2遺傳算法………………………………………………………………………………………8 2.1遺傳算法的基本思想 ………………………………………………………………………8 2.2遺傳算法的特點 ……………………………………………………………………………8 2.3遺傳算法的基本概念 ………………………………………………………………………9 2.4遺傳算法基本流程…………………………………………………………………………10 2.5遺傳算法的參數(shù)及基本操作 …………………………………………………………… 11 2.5.1算法參數(shù)……………………………………………………………………………

12、……11 2.5.2遺傳算法的編碼和解碼…………………………………………………………………12 2.5.3適應(yīng)度函數(shù) ………………………………………………………………………… 13 2.5.4遺傳操作…………………………………………………………………………………14 2.5.4.1初始種群的產(chǎn)生………………………………………………………………………14 2.5.4.2選擇算子……………………………………………………………………………… 15 2.5.4.3交叉算子……………………………………………………………………………… 15 2.5.4.4變異算子……………………………………

13、…………………………………………16 3遺傳算法求解柔性作業(yè)車間調(diào)度問題 ……………………………………………………17 3.1遺傳算法求解柔性作業(yè)車間調(diào)度問題的步驟 …………………………………………17 3.2遺傳操作設(shè)計………………………………………………………………………………17 3.2.1編碼………………………………………………………………………………………17 3.2.2適應(yīng)度函數(shù)………………………………………………………………………………18 II 3.2.3遺傳算法的主要操作步驟……………………………………………………18 4仿真實例及結(jié)論 ………………

14、……………………………………………………………21 5總結(jié)與展望 ………………………………………………………………………………23 5.1總結(jié)……………………………………………………………………………………… 23 5.2展望……………………………………………………………………………………… 23 參考文獻 ………………………………………………………………………………………24 致謝 ……………………………………………………………………………………………26 緒論 有效的調(diào)度方法與優(yōu)化技術(shù)的研究和應(yīng)用，對于制造企業(yè)提高生產(chǎn)效率、降低生產(chǎn)成本等方面起著重要作用，因而越來越受到學(xué)者

15、們的關(guān)注。如何進行組織管理，包括如何組織動態(tài)聯(lián)盟、如何重構(gòu)車間和單元、如何安排生產(chǎn)計劃、如何進行調(diào)度都是我們面臨的主要問題。其中車間作業(yè)調(diào)度與控制技術(shù)是實現(xiàn)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵，有關(guān)資料表明，制造過程中95％的消耗是在非切削過程中[2]。因此，有效的調(diào)度方法與優(yōu)化技術(shù)的研究和應(yīng)用，已成為先進制造技術(shù)實踐的基礎(chǔ)和關(guān)鍵。 車間作業(yè)調(diào)度(Job Shop Scheduling，簡稱JSS)的啟發(fā)式算法[3]，是用某一調(diào)度優(yōu)先級規(guī)則在當(dāng)前可調(diào)度工序中選擇一個工序進行加工，最終形成一個由所有被加工零件各工序組成的序列，即所謂調(diào)度結(jié)果．由于調(diào)度規(guī)則通常只針對特定問題和特定環(huán)境，它存在著難以

16、克服的缺點，如計算規(guī)模不可能較大，尋優(yōu)具有局部性等．而基于遺傳算法的車間作業(yè)調(diào)度的基本思想是，預(yù)先排列出若干個由工序組成的序列，然后對這些序列進行遺傳進化操作，從而達到優(yōu)化調(diào)度結(jié)果性能指標(biāo)的目的．由于遺傳算法只利用適應(yīng)性信息，它不要求目標(biāo)函數(shù)可微、連通和凸性，因而它是一種高效率的隨機搜索與優(yōu)化的方法，具有搜索面廣、算法速度快等優(yōu)點．然而遺傳算法中交叉概率和變異概率的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法收斂性，并且編碼與解碼的問題也對遺傳算法的應(yīng)用有較大的限制作用。同時遺傳算法易于早熟和陷入局部最優(yōu)解的缺點，也使人們不斷對遺傳算法進行改進。 研究車間生產(chǎn)調(diào)度問題，對促進企業(yè)生產(chǎn)管理

17、的現(xiàn)代化，建立現(xiàn)代企業(yè)制度，提高我國企業(yè)的競爭力，迅速打開走向世界的局面都具有重要的意義。 1車間作業(yè)調(diào)度 車間調(diào)度主要是針對一項可分解的工作(如產(chǎn)品制造)，探討在盡可能滿足約束條件(如交貨期、工藝路線、資源情況)的前提下，通過下達生產(chǎn)指令，安排其組成部分(操作)使用哪些資源、其加工時間及加工的先后順序，以獲得產(chǎn)品制造時間或成本的最優(yōu)化[4]。在理論研究中，車間作業(yè)調(diào)度問題常被稱為排序問題或資源分配問題或組合優(yōu)化問題。 1.1車間調(diào)度問題的研究意義 車間生產(chǎn)過程的調(diào)度問題，是制造系統(tǒng)運籌技術(shù)、管理技術(shù)與優(yōu)化技術(shù)發(fā)展的核心。有效的調(diào)度方法與優(yōu)化技

18、術(shù)的研究和應(yīng)用，已經(jīng)成為先進制造技術(shù)實踐的基礎(chǔ)和關(guān)鍵，優(yōu)良的調(diào)度策略對于提高生產(chǎn)系統(tǒng)的最優(yōu)性、提高經(jīng)濟效益，有著極大的作用。在理論研究中，車間作業(yè)調(diào)度問題常被稱為排序問題或資源分配問題或組合優(yōu)化問題。 隨著產(chǎn)品制造界的市場的競爭性在不斷提高，好的生產(chǎn)調(diào)度能提高資源的利用率和操作管理水平，生產(chǎn)出具有競爭力的產(chǎn)品。車間的調(diào)度優(yōu)化工作，因其在提高生產(chǎn)效率，降低生產(chǎn)成本等方面所起的重要作用，正越來越受到學(xué)者們的關(guān)注，也是本課題的研究意義所在。車間作業(yè)調(diào)度問題的研究不僅具有較大的實用價值，而且還有相當(dāng)大的理論意義。研究生產(chǎn)調(diào)度問題推動了遺傳算法、模擬退火算法、啟發(fā)式方法等優(yōu)化方法的發(fā)展與融合，也為其他

19、領(lǐng)域類似問題的解決提供了條件與手段。通過將優(yōu)化算法與調(diào)度方法相結(jié)合，使制造系統(tǒng)提高運行效率，滿足客戶的要求，增強企業(yè)在市場上的競爭力。 1.2車間調(diào)度問題研究現(xiàn)狀 由于調(diào)度問題是制造系統(tǒng)中最基本、最重要的問題之一，是生產(chǎn)管理的核心問題和關(guān)鍵技術(shù)，因此國內(nèi)外大量的學(xué)者對其進行了廣泛的探討和研究。調(diào)度問題的研究始于20世紀(jì)50年代，Johnson提出了解決n/2/F/Cmax和部分特殊的n/3/F/Cmax問題的優(yōu)化算法，代表調(diào)度理論研究的開始：60-70年代建立了調(diào)度理論的主體(經(jīng)典調(diào)度理論)并重視調(diào)度復(fù)雜性的研究。隨著70年代后期調(diào)度理論研究的深入及各種交叉學(xué)科的發(fā)展，又涌現(xiàn)出了許多新的車

20、間調(diào)度理論與方法，如神經(jīng)網(wǎng)絡(luò)、模擬退火法、遺傳算法等[5]。 由于各種車間作業(yè)調(diào)度的算法都存在著不同程度的優(yōu)缺點[6]，所以，近年來，人們開始將各種算法組合起來進行研究[7]，以揚長避短，達到優(yōu)化調(diào)度的目的。比如：使用將遺傳算法和禁忌搜索算法結(jié)合起來的混合策略，求解車間調(diào)度問題[8]。通過結(jié)合啟發(fā)式算法和遺傳算法的混合方法，求解多資源約束的車間調(diào)度問題[9]。 1.3 車間調(diào)度問題的分類 車間生產(chǎn)調(diào)度系統(tǒng)的分類方法很多，主要有以下幾種： (1) 根據(jù)加工系統(tǒng)的復(fù)雜度，生產(chǎn)調(diào)度可分為單機調(diào)度、作業(yè)車間調(diào)度(Job Shop)、流水車間(Flow Shop)調(diào)度、多機器并行加工調(diào)度。 (

21、2) 根據(jù)優(yōu)化準(zhǔn)則，可以分為基于代價和性能的調(diào)度兩大類。 (3) 根據(jù)生產(chǎn)環(huán)境的特點，可將調(diào)度問題分為確定性調(diào)度問題和隨機性調(diào)度問題。 (4) 根據(jù)作業(yè)的加工特點，可將調(diào)度問題分為靜態(tài)調(diào)度和動態(tài)調(diào)度。 1.4實際車間調(diào)度問題的特點： 車間生產(chǎn)調(diào)度問題有以下特點[10]： (1) 復(fù)雜性 由于裝卸作業(yè)、裝卸設(shè)備、庫場、搬運系統(tǒng)之間相互影響、相互作用、每個作業(yè)又要考慮它的到達時間、裝卸時間、準(zhǔn)備時問、操作順序、交貨期等，因而相當(dāng)復(fù)雜。而且調(diào)度問題是在等式或不等式約束下求性能指標(biāo)的優(yōu)化，在計算量上往往是NP難問題，即隨著問題規(guī)模的增大，對于求解最優(yōu)化的計算量呈指數(shù)增長，使得一些常規(guī)的最優(yōu)

22、化方法往往無能為力。 (2) 動態(tài)隨機性 在實際的生產(chǎn)調(diào)度系統(tǒng)中存在很多隨機的和不確定的因素，比如作業(yè)到達時間的不確定性、作業(yè)的加工時間也有一定的隨機性，而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些突發(fā)偶然事件，如設(shè)備的損壞或修復(fù)、作業(yè)交貨期的改變等。 (3) 多目標(biāo)性。 實際的計劃調(diào)度往往是多目標(biāo)的，并且這些目標(biāo)間可能發(fā)生沖突。Kiran等人將調(diào)度目標(biāo)分三類：基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)[11]。這種多目標(biāo)性導(dǎo)致調(diào)度的復(fù)雜性和計算量急劇增加。 1.5車間調(diào)度問題的研究方法 現(xiàn)有調(diào)度問題的研究方法大體上可以分為以下幾種類別： (1) 解析方法。只針對簡單小規(guī)模調(diào)度

23、問題的解析求解方法。 (2) 枚舉方法（enumerative methods）該類方法對小規(guī)模問題比較有效，但對于大規(guī)模問題計算量和存儲量難以承受。 ◆分支定界（bound and branch） ◆數(shù)學(xué)方法（mathematical method）。譬如整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、分解方法、代理對偶方法、Lagrangian松弛方法等。 (3) 構(gòu)造性方法（constructive method）。該類方法能夠快速建立問題的解，但通常解質(zhì)量較差，否則需要建立復(fù)雜的啟發(fā)式規(guī)則。 ◆ 優(yōu)先分配規(guī)則（priority dispatch rule）。譬如SPT，LRM，MWR等。 ◆

24、基于瓶頸的啟發(fā)式方法（bottleneck based heuristics）。如移動瓶頸過程，beam搜索等。 ◆ 插入方法（insertion algorithm）。如CDS，NEH法等。 (4) 領(lǐng)域搜索算法（local search method）。該類方法從若干解出發(fā)，對其領(lǐng)域的不斷搜索和當(dāng)前解的替換來實現(xiàn)優(yōu)化。 ◆ 迭代改進法（iterative improvement）。 ◆ 模擬退火法（simulated annealing，SA）。 ◆ 進化算法（evolutionary computation，EC）。它包括遺傳算法（genetic algorithm，GA）、進

25、化規(guī)劃、進化策略和遺傳編程。 ◆ 禁忌搜索（tabu search，TS）。 ◆ 巢分區(qū)（nested parition，NP）。 ◆ 變鄰域搜索（variable neighborhood search，VNS）。 ◆ 噪聲方法（noising method，NM）。 ◆ 閾值接受法（threshold accepting，TA）。 ◆ 可變深度搜索（variable deep search，VDS）。 (5) 人工智能方法（artificial intelligence）。該類方法利用人工智能的原理和技術(shù)進行搜索，譬如將優(yōu)化過程轉(zhuǎn)化成智能系統(tǒng)動態(tài)的演化過程，基于系統(tǒng)動態(tài)的演化

26、來實現(xiàn)優(yōu)化。 ◆ 神經(jīng)網(wǎng)絡(luò)（neural network，NN）。 ◆ 專家系統(tǒng)（expert system，ES）。 ◆ 蟻群系統(tǒng)（ant system，AS）。 ◆ 混沌搜索（chaotic search，CS）。 ◆ 免疫算法（immunity algorithm）。 另外，還有上述各算法的混合方法。 1.6實際車間生產(chǎn)調(diào)度研究中存在的主要問題 調(diào)度領(lǐng)域中的大部分問題都具有NP難問題，雖然對它的研究已經(jīng)有幾十年的歷史，但至今尚未形成一套系統(tǒng)的方法和理論。一些理論上的最優(yōu)化方法能提供最優(yōu)調(diào)度，但由于其計算的復(fù)雜性，并且忽略了很多實際因素，離實際運用還有很大距離。 由于大多

27、數(shù)調(diào)度問題屬于一類NP難組合問題，因此尋找具有多項式復(fù)雜性的最優(yōu)算法幾乎是不可能的。傳統(tǒng)的啟發(fā)式算法，智能模擬退火算法，禁忌算法，神經(jīng)網(wǎng)絡(luò)法等算法其共性是對生產(chǎn)線優(yōu)化問題尋求滿足實際需要的近似解或滿意解，而非精確最優(yōu)解。在調(diào)度問題的理論研究中，大多數(shù)還是集中在針對經(jīng)典的調(diào)度問題設(shè)計優(yōu)化算法，在實際車間調(diào)度中，車間計劃與車間調(diào)度往往是分層進行的，這可能造成計劃在實際調(diào)度中的不可行問題。另外，還有很多待進一步研究的問題，比如實際車間調(diào)度的多目標(biāo)性、動態(tài)隨機性等。 1.7柔性車間作業(yè)調(diào)度問題 1.7.1問題描述 一般的車間調(diào)度問題都是對于具體生產(chǎn)環(huán)境中復(fù)雜動態(tài)、多目標(biāo)、多約束調(diào)度的一種抽象和簡

28、化，其首要問題是對調(diào)度問題進行建模。Job Shop是一類最具一般性的生產(chǎn)加工環(huán)境，該類調(diào)度問題已得到廣泛的關(guān)注和研究。在傳統(tǒng)的Job Shop調(diào)度問題研究中，僅考慮各工序在唯一確定的機床上加工的情況，即先有確定的加工計劃，再進行作業(yè)調(diào)度，缺乏一定的柔性。隨著FMS的出現(xiàn)，這一傳統(tǒng)限制已被突破，各工序可以在多臺可選的機床上加工，即路徑柔性已成為生產(chǎn)的實際需求。研究具有路徑柔性的車間調(diào)度(Flexible Job Shop Scheduling，簡稱FJSS)問題具有重要的理論和應(yīng)用意義。從“系統(tǒng)工程方法論”的角度來看，建模是在選定目標(biāo)、約束條件及研究環(huán)境等工作基礎(chǔ)上進行的。因此在建立FJSS模

29、型之前，首先要對FJSS問題有個清楚的描述，明確問題的特點、目標(biāo)、約束及輸入輸出。FJSS問題的描述如下： 假定一個加工系統(tǒng)有m臺機器和n個工件，每個工件包含一道或多道工序，工件的工序順序是預(yù)先確定的，每道工序可以在多臺不同的機床上加工，工序的加工時間隨機床的性能不同而變化。調(diào)度目標(biāo)是為每道工序選擇最合適的機器，以及確定每臺機器上各工件工序的最佳加工順序及開工時間，使系統(tǒng)的某些性能指標(biāo)達到最優(yōu)。下面是針對該調(diào)度問題的假設(shè)： (1) 整個加工過程中，一個工件不能在同一臺機器上加工多次； (2) 任何一個工件的前一道工序加工完成后，方能進行后一道工序的加工， 在同一臺機器上一個加工任務(wù)完成

30、之后，方能開始另一個加工任務(wù)； (3) 各工件必須按工藝路線以指定的次序在機器上加工； (4) 不考慮工件加工的優(yōu)先權(quán)； (5) 每個工件的工序一旦進行就不能中斷； (6) 一個工件同一時間只能在一臺機器上加工，一臺機器同一時間只能加工一個工件，加工的開始時間為0。 1.7.2數(shù)學(xué)描述： 目標(biāo)函數(shù)： min (1-1) S．t． (1-2) (1-3)

31、(1-4) 其中： (1-5) (1-6) i,j = 1,2,…n；h,k = 1,2,…m； 其中，分別為工件i在機器k上的完成時間和加工時間；M是一個足夠大的正數(shù)；分別為指示系數(shù)和指示變量。式(1-1)表示目標(biāo)函數(shù)，即調(diào)度的目標(biāo)為最大完成時間最小化；式(1-2)表示順序約束條件，即各個工件各操作的先后加工順序，保證每個工件的加工順序滿足預(yù)先的要求；式(1-3)表示資源約束條件，即機器加工各個工件的先后順序，保證每臺機器一次只能加工一個工件。 1.8

32、Gantt圖 對于m臺機器(Machine)(M1，M2，…，Mm)，n個工件(Job)(J1，J2，…，Jn)的加工過程，調(diào)度通常用Gantt圖表示。Gantt圖是在1917年由Henry Laurence Gantt開發(fā)的。它基本上是一種線條圖，橫軸表示時間，縱軸表示要安排的活動，線條表示在整個期間計劃的和實際的活動完成情況。Gantt圖直觀地表明任務(wù)計劃在什么時候進行，以及實際進展與計劃要求的對比。Gantt圖使車間的計劃安排情況一目了然，成為管理人員了解全局，安排車間進度的有效工具。 表1.1 一個3×3的車間調(diào)度問題 Job (機器，時間) J1 （3,1） （1,2

33、） （2,2） J2 （3,1） （2,4） （1,1） J3 （2,2） （3,3） （1,1） 以一個3個工件3臺機器的JSP為例說明，表1.1中每個括弧中第一個數(shù)據(jù)表示工件在哪臺機器上加工，第二個數(shù)據(jù)表示加工時間。以Gantt圖表示的該實例的一個可行調(diào)度，如圖1.1所示。 圖1.1 表1.1中JSP的Gantt圖 2 遺傳算法 遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由美國密執(zhí)安大學(xué)的Holland教授提出，起源于60年代對自然和人工自適應(yīng)系統(tǒng)的研究[12]．70年代De Gong基于GA的思

34、想在計算機上進行大量的純數(shù)值函數(shù)優(yōu)化計算實驗[13]。在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進行歸納總結(jié)，形成了GA的基本框架[14]。近幾年來，GA主要在復(fù)雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應(yīng)用，取得了一些令人信服的結(jié)果。GA成功的應(yīng)用包括：作業(yè)調(diào)度與排序、可靠性設(shè)計、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、交通問題等等。 2.1遺傳算法的基本思想 遺傳算法(Genetic Algorithms)的基本思想來源于分子遺傳學(xué)和生物進化論，其基本原理是，產(chǎn)生若干代表問題候選解的成員，并組成一個群體，按照某一評價函數(shù)或算法對群體中的每個成員進行評估，評估結(jié)果代表解的良好性。按照適

35、者生存、優(yōu)勝劣汰的原則，群體中的某一成員愈適合，則愈有可能產(chǎn)生后代。利用遺傳操作對群體中的成員進行遺傳操作，產(chǎn)生新的后代，這種后代能繼承雙親的特征。對后代進行評估，并將其放入群體，代替上一代中較弱的成員(非良好解)。此過程反復(fù)執(zhí)行，這構(gòu)成一代代的群體。隨著遺傳過程的不斷進行，越來越良好的解就可以得到。 2.2遺傳算法的特點 遺傳算法是解決搜索問題的一種通用算法，對于大部分搜索問題都能夠使用，首先在此先闡述一下搜索算法的共同特征[14]： (1) 首先生成一組候選解，即構(gòu)造算法的初始解集； (2) 依據(jù)設(shè)定的適應(yīng)性條件計算這些解的適應(yīng)度； (3) 依據(jù)適應(yīng)度，選擇保留適應(yīng)度高的個體，去

36、除適應(yīng)度低的個體； (4) 對篩選出的新個體進行新的操作，生成新的適應(yīng)度個體。 這是大部分搜索算法所具有的特征，但是遺傳算法作為一種新型的算法，必然有它的特殊之處，它基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。 遺傳算法獨具的特點如下： (1) 遺傳算法是對問題參數(shù)的編碼(染色體)群進行進化，而不是參數(shù)本身。這是遺傳算法與傳統(tǒng)優(yōu)化算法的較大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)，克服了早熟的缺點。 (2) 遺傳算法的搜索是從問題解的串

37、集開始搜索，而不是從單個解開始。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實現(xiàn)并行化。 (3) 遺傳算法使用適應(yīng)度這一信息進行搜索，而不需導(dǎo)數(shù)等其它信息。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點使得遺傳算法的應(yīng)用范圍大大擴展。 (4) 遺傳算法使用的選擇、交叉、變異這三個算子都是隨機操作，而不是確定性規(guī)則。遺傳算法是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。 (5) 遺傳算法最善于搜索復(fù)雜地區(qū)，從中找出期望值高的區(qū)域和個體。 (6) 遺傳算法具有可擴展性，易于同別的算法技術(shù)混合。 綜上所述，

38、GA算法較之傳統(tǒng)優(yōu)化方法，具有良好的全局搜索能力，是一種全局優(yōu)化算法。但是，實際應(yīng)用遺傳算法時，往往出現(xiàn)早熟收斂、收斂性能差、局部最優(yōu)解等缺點。因為遺傳算法是一類基于“產(chǎn)生+測試”方式的迭代搜索算法，盡管算法在一定條件具有全局收斂性，但算法的交叉、變異、選擇等操作一般都是在概率意義下隨機進行的，雖然保證了種群的群體進化性，但一定程度上不可避免退化現(xiàn)象的出現(xiàn)。 2.3遺傳算法的基本概念 遺傳算法是由進化理論和遺傳學(xué)機理而產(chǎn)生的，基于概率的搜索優(yōu)化方法， 因而，在遺傳算法中要用到進化和遺傳學(xué)相關(guān)的概念。這些概念如下： (1) 串(String)：它是個體(Individual)的形式，在算

39、法中為表現(xiàn)為字符串， 并對應(yīng)于遺傳學(xué)中的染色體(Chromosome)。 (2) 群體(Population)：個體的集合，串是群體中的元素。 (3) 群體的大小(Population Size)：在群體中個體的數(shù)量為群體的大小。 (4) 基因(Gene)：基因是串中的元素，基因用于表示個體的特征。 (5) 適應(yīng)度(Fitness)：表示某個體對于環(huán)境的適應(yīng)程度。 2.4遺傳算法基本流程 遺傳算法是一類隨機優(yōu)化算法，但它不是簡單的隨機比較搜索，而是通過對染色體的評價和對染色體中基因的作用，有效地利用已有信息來指導(dǎo)搜索有希望改善優(yōu)化質(zhì)量的狀態(tài)。 標(biāo)準(zhǔn)遺傳算法的主要步驟如描述下：

40、 (1) 確定問題的編碼方案。編碼的目的主要是使優(yōu)化問題解的表現(xiàn)形式適合于遺傳算法中的遺傳運算，由于GA通常不直接作用于問題的解空間，而是利用解的某種編碼表示來進行進化，因此選擇合理的編碼機制對算法的質(zhì)量和效果有很大的影響。 (2) 適應(yīng)度函數(shù)的構(gòu)造和應(yīng)用。由于GA通常是基于適應(yīng)度函數(shù)進行遺傳操作的，因此合理的適應(yīng)度函數(shù)能夠?qū)€體的優(yōu)劣程度得以體現(xiàn)。適應(yīng)度函數(shù)基本上依據(jù)優(yōu)化問題的目標(biāo)函數(shù)而定，當(dāng)適應(yīng)度函數(shù)確定以后，自然選擇規(guī)律是以適應(yīng)度函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰，生存下來的染色體組成種群，形成一個可以繁殖下一代的群體。 (3) 算法參數(shù)的選取。通常包括；

41、種群大小、交叉概率、變異概率、進化代數(shù)等。 (4) 遺傳算子的設(shè)計。通常包括：初始化、選擇、交叉、變異和替換操作等。父代的遺傳基因結(jié)合是通過父代染色體之間的交叉并到達下一代個體的。新產(chǎn)生個體中可能發(fā)生基因變異，變異使解有更大的遍歷性。 (5) 確定算法的終止條件。終止準(zhǔn)則應(yīng)根據(jù)所求解問題的性質(zhì)，在優(yōu)化質(zhì)量和效率方面作合理均衡或側(cè)重。 圖2.1遺傳算法具體設(shè)計實施過程 2.5遺傳算法的參數(shù)及基本操作 2.5.1算法參數(shù) 標(biāo)準(zhǔn)的GA有6個關(guān)鍵參數(shù)，包括種群數(shù)目、交叉概率、變異概率、代溝、尺度窗口和選擇策略。因此如何確定GA的最優(yōu)參數(shù)仍然是一個熱點問題，也是研究GA的重點課題之一。

42、 (1)種群數(shù)目(Generation Size) 種群數(shù)目是影響算法最終優(yōu)化性能和效率的因素之一。當(dāng)種群數(shù)目設(shè)得過小時，不能提供足夠的采樣點來搜索整個解空間，以致算法性能很差；當(dāng)種群數(shù)目設(shè)得過大時，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增加計算量，從而使收斂時間太長，算法效率偏低。一般建議取值范圍是20-100。 (2)交叉概率(Crossover Rate) 交叉概率用于控制交叉操作發(fā)生的頻率。交叉概率過大時，種群中個體的更新很快，會使高適應(yīng)度的個體很快被破壞掉；概率過小時，交叉操作發(fā)生的頻率過低，使搜索停滯不前。一般建議的取值范圍是0.40-0.99。另外，也可使用自適應(yīng)

43、的思想來確定交叉概率，如Davis[15]提出，隨著GA在線性能的提高，可以增大交叉概率的取值。 (3)變異概率(Mutation Rate) 變異概率是保證種群多樣性的重要因素。通常，一個較低的變異率足以防止整個群體中任一位置的基因一直保持不變。但是，變異概率太小則不會產(chǎn)生新個體，概率太大則使GA成為隨機搜索。一般建議的取值范圍是0.0001-0.1000。另外，也可使用自適應(yīng)的思想來確定變異概率?？蓽p小變異概率的取值。 (4)代溝(G) 代溝用于控制每代中種群被替換的比例。當(dāng)G=100％時，種群中所有個體將被替換；G=50％時，一半種群將被替換。在標(biāo)準(zhǔn)GA中，G=100％，而有些替

44、換策略中G值與新舊個體的適應(yīng)度好壞有關(guān)而且是變化的。 (5)尺度窗口(W) 該參數(shù)用于由目標(biāo)值到適應(yīng)度的調(diào)整。對于最大化函數(shù)優(yōu)化問題，個體x的適應(yīng)度可以定義為： u(x)=f(X)一fmin (2-1) 其中f(x)為其目標(biāo)值，fmin為問題的最小目標(biāo)值。然而，fmin通常是未知的。許多方法用算法當(dāng)前進程發(fā)現(xiàn)的最小目標(biāo)值f’min作為替代。顯然，定義不同的f’min將影響優(yōu)良個體的選擇壓力。 (6)選擇策略(S) 通常有兩種選擇策略：其一為純選擇，即種群中每一個體根據(jù)其適應(yīng)度作比例選擇；其二為保優(yōu)策略，即先用純選擇作選擇，然后將

45、最優(yōu)個體加入下一代種群，該策略可防止最優(yōu)解的遺失。 2.5.2遺傳算法的編碼和解碼 在遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉(zhuǎn)化到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼。編碼是應(yīng)用GA時要解決的首要問題，也是設(shè)計GA時的一個關(guān)鍵步驟。 由于GA的優(yōu)化過程不是直接作用于問題參數(shù)本身，而是在一定編碼機制對應(yīng)的碼空間上進行的，因此編碼的選擇是影響其算法性能與效率的重要因數(shù)。GA的一個顯著特點是它交替地在編碼空間和解空間中工作，它在編碼空間對染色體進行遺傳操作，而在解空間對解進行評估和選擇。對于實數(shù)編碼，染色體和解之間的編碼與解碼(基因性與表現(xiàn)性之間的相互映射)有三

46、個主要問題： (1)染色體的可行性為染色體解碼成為解之后是否在給定問題的可行域內(nèi)的性質(zhì)。 (2)染色體的合法性是指編碼空間中的編碼是否可以映射到解空間中的一個解。凡是可以映射到解空間的編碼都是合法的，否則就是非法的。 (3)映射的唯一性從編碼空間到解空間的映射可以是1對1映射、X對1映射或1對X映射，顯然，1對1映射是最好的，而1對X映射是最不值得提倡的。 編碼(encoding)是問題的解空間到GA表達空間的一種映射。而解碼(decoding)是GA表達空間到問題的解空間的一種映射，如圖2.2所示。 圖2.2 GA表達空間和問題解空問 GA表達空間中的所有染色體并非全部對應(yīng)于

47、實際問題的。有效調(diào)度，如圖2.3所示。可能存在著對應(yīng)不合法調(diào)度和不可行調(diào)度的染色體。 圖2.3 調(diào)度的可行性和合法性 注：不可行指的是某個染色體解碼出來的解在給定問題的可行區(qū)域之外的現(xiàn)象；而非法性指的是某個染色體不能代表給定問題的解的現(xiàn)象 針對函數(shù)優(yōu)化的編碼技術(shù)主要有二進制編碼、十進制編碼、Gray編碼、實數(shù)編碼等。 (1) 二進制編碼是用若干二進制數(shù)表示一個個體，將原問題的解空間映射到位串空間B={0，l}上，然后在位串空間上進行遺傳操作。二進制編碼類似生物染色體的組成，從而使算法易于用生物遺傳理論來解釋。并使得遺傳操作如交叉、變異等很容易實現(xiàn)。另外，采用二進制編碼算法的處理模式

48、很多，但是可能使相鄰整數(shù)具有較大的Hamming[16]距離。例如15和16的二進制表示為01111和10000，因此算法要從15變?yōu)?6則必須改變所有的位。這種缺陷造成了Hamming懸崖將降低遺傳算子的搜索效率。在求解高維優(yōu)化問題時，二進制編碼串將非常長，從而使得算法的搜索效率很低。由于很多數(shù)值與非數(shù)值優(yōu)化問題都可以用二進制編碼來應(yīng)用遺傳算法，同時表達的模式最多，所以二進制編碼方法是遺傳算法中最常用的一種編碼方法，它具有以下優(yōu)點： 1) 編碼、解碼操作簡單易行。 2) 交叉、變異等遺傳操作便于實現(xiàn)。 3) 符合最小字符集編碼原則。 4) 便于用模式定理進行分析，因為模式定理就是以二

49、進制為基礎(chǔ)的。 (2) 格雷碼編碼方法 作為一種新的編碼方法具有自己獨特的優(yōu)勢，但本質(zhì)上還是和二進制編碼方法有相似之處。格雷碼能夠克服二進制編碼在結(jié)構(gòu)特征，以及一些連續(xù)函數(shù)的優(yōu)化問題中顯現(xiàn)出局部搜索能力差的缺陷，增強了算法的局部搜索能力。格雷碼是將二進制編碼通過一個轉(zhuǎn)換而得到的編碼。轉(zhuǎn)化公式[17]如下： 設(shè)有二進制編碼串為B =bmbm-1bm-2…b2b1 ,其中對應(yīng)的格雷碼為 G=gm gm-1gm-2…g2g1。則將二進制轉(zhuǎn)化為格雷碼的公式為： (2-2) 其中⊕為異或運算符，而格雷碼轉(zhuǎn)化為

50、二進制的運算公式為: (2-3) (3) 實數(shù)編碼 為了克服二進制編碼的缺點，對問題的變量是實向量的情形，可以直接采用實數(shù)編碼。采用實數(shù)表達法不必進行數(shù)制轉(zhuǎn)換，可直接在解的表現(xiàn)型上進行遺傳操作，從而可引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息來增加算法的搜索能力。遺傳算法在求高維、復(fù)雜優(yōu)化問題時通常采用實數(shù)編碼[18]。 2.5.3適應(yīng)度函數(shù) 遺傳算法遵循自然界優(yōu)勝劣汰的原則，在進行搜索中基本上不用外部信息，而用適應(yīng)度表示個體的優(yōu)劣，作為遺傳算法操作的依據(jù)。適應(yīng)度函數(shù)表明個體對環(huán)境適應(yīng)能力的強弱，

51、是區(qū)分群體中個體好壞的標(biāo)準(zhǔn)，也是進行自然選擇的唯一依據(jù)。 對于簡單的最小化問題，通?？梢灾苯訉⒛繕?biāo)函數(shù)變換成適應(yīng)度函數(shù)，例如將個體X的適應(yīng)度值f(X)定義為M-c(X)或e-ac(X),其中M為一足夠大的正數(shù)。c(X)為個體的目標(biāo)值，a>0。對于復(fù)雜優(yōu)化問題，往往需要構(gòu)造合適的評價函數(shù)，使其適應(yīng)GA進化優(yōu)化。對于適應(yīng)度和目標(biāo)函數(shù)值，有多種設(shè)計方法。它影響遺傳選擇的方向，最終影響遺傳運算結(jié)果。采用妥協(xié)方法[19]的基本思想是：通過最大完成時間來確定后悔值r，進而求得相應(yīng)染色體的適應(yīng)度。妥協(xié)方法根據(jù)某種距離度量方式來確定與理想解最近的解[20]。加權(quán)Lp范數(shù)[21]被用作距離度量方式來確定后悔值

52、r即 其中(z1*，z2*，…，zq*)是判據(jù)空間Z中的正理想點，權(quán)重(w1，w2，…，wq)被分配給目標(biāo)并用來強調(diào)其不同的重要程度。其中，z用每代種群中染色體的Tmax表示，z*即理想的最小化時間0+。理想解實際上無法達到，然而它可以成為評價可達到的非支配解的標(biāo)準(zhǔn)。后悔值r越小個體越好，因此將后悔值轉(zhuǎn)換為適應(yīng)值從而確保優(yōu)秀個體具有較大的適應(yīng)值。 設(shè)r(x)表示個體x的后悔值，rmax表示當(dāng)前代中的最大后悔值，rmin表示當(dāng)前代中的最小后悔值，求取染色體X的適應(yīng)度e(x) 其中是正實數(shù)，通常被限制在(0，1)中。該系數(shù)有兩個作用：避免式(2-5)產(chǎn)生被零除錯誤；可以將選擇方式從適應(yīng)值比例

53、選擇調(diào)整到純粹隨機選擇()。 值得一提的是，GA的優(yōu)化過程是一種搜索評價過程，如果評價過程占有的時間過多，則勢必影響算法的整體優(yōu)化性能。因此，對于評價過程復(fù)雜的問題，如仿真優(yōu)化問題，如何提出有效的評價機制來加速或簡化評價過程，將有利于提高GA的優(yōu)化效率。 2.5.4遺傳操作 2.5.4.1初始種群的產(chǎn)生 遺傳算法是群體型操作算法，在對解空間變量進行編碼后，緊接著就要隨機產(chǎn)生N個染色體，構(gòu)造遺傳算法的初始群體。但考慮到搜索效率和質(zhì)量，最好采用如下策略設(shè)定[21]： 1) 根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此范圍內(nèi)設(shè)定初始種群。 2) 先隨機產(chǎn)

54、生一定數(shù)目的個體，然后從中挑選最好的個體加到初始群體中，這種過程不斷迭代，直到初始種群中個體數(shù)目達到了預(yù)定規(guī)模。 2.5.4.2選擇算子 遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算。目的是為了避免有效基因的損失，從當(dāng)前群體中選出生命力強的染色體，使它有機會保留用以繁殖后代，從而提高全局收斂性和計算效率。 最常用的選擇方法是適應(yīng)度比例選擇、最優(yōu)個體保存選擇和錦標(biāo)賽選擇。 (1) 比例選擇(也稱輪盤賭)。比例選擇的基本思想是：根據(jù)染色體的適應(yīng)度值的大小，分配繁殖機會，適應(yīng)度相對低的個體則產(chǎn)生的后代數(shù)目將減少。該方法的染色體新個體是

55、概率性地從老群體中選擇的，其操作是隨機的。設(shè)群體大小為M，個體i的適應(yīng)度為Fi，則個體i被選中的概率Pi，為 Pi = (2 - 6) 由上式可見，適應(yīng)度越高的個體被選中的概率越大；反之，適應(yīng)度越低的個體被選中的概率越小。 (2) 基于排名的選擇。首先將種群中所有個體由好到壞進行排列，然后以一定方式分配給各個體一定的選擇概率，具體分配方式不限，如線性方式、非線性方式，但要要求越好的個體分配的概率越大，且所有個體所分配的概率之和為l。 (3) 錦標(biāo)賽選擇。首先在父代種群中隨機選取k個個體，然后令其中適配值或目標(biāo)值最好的個體為被選中

56、的個體。顯然k的大小影響選擇性能。 2.5.4.3交叉算子 遺傳算法中起核心作用的是交叉算子，也稱為基因重組(recombination)。采用的方法應(yīng)能夠使父代的特征遺傳給子代。子代應(yīng)能夠部分或者全部地繼承父代的結(jié)構(gòu)特征和有效的基因。在遺傳算法中，交叉運算之前還必須先對群體中的個體進行配對，它通常分為三步：第一步，對父代中的個體進行隨機配對；第二步，對所選擇的配對個體隨機產(chǎn)生一個交叉位置：第三步，將交叉位置后面的部分進行交換，產(chǎn)生兩個新的個體。下面我們來介紹在遺傳算法中主要應(yīng)用的兩種交叉方法： (1) 單點交叉 首先在相互配對的染色體中隨機確定一個交叉位置，然后對換交叉點后的子串。例

57、如父串為P1、P2，若單點交叉位置為4,則生成的子串為C1、C2。 P1→(1100∣100) C1→(1100∣011) P2→(0011∣011) C2→(0011∣100) (2) 多點交叉 首先在相互配對的染色體中隨機確定多個交叉位置，然后對換相應(yīng)的子串。若兩點交叉，位置選擇為2、5，父代個體同上，則經(jīng)過交叉后的子代個體為： C1→(11∣110∣00) C2→(00∣001∣11) 2.5.4.4變異算子 GA中的變異運算，是指以很小的概率隨機地改變?nèi)旧w串上的某些位，從而形成一個新的個體。如二進制編碼的個體，就是將個體在變異點上的

58、基因值取反，即0變1，1變0。從遺傳運算過程中產(chǎn)生新個體的能力方面來說，交叉運算是產(chǎn)生新個體的主要方法，它決定了GA的全局搜索能力；而變異運算是產(chǎn)生新個體的輔助方法，決定了GA的局部搜索能力。交叉算子與變異算子的相互配合，共同完成對搜索空間的全局搜索和局部搜索，從而使得GA能夠以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。 下面介紹幾種常用的變異操作方法。它們適用于二進制編碼和實數(shù)編碼的個體。 (1) 基本位變異 對群體中的個體的染色體串中，隨機的選擇一個或幾個基因位。，若需要進行變異操作則將基因座上的原有基因值（假設(shè)為）0，則變異操作將該基因值變?yōu)?；反之，若原有基因值為1，則變異操作將該

59、基因值變?yōu)?。 變異前：100111 選擇基因位3和5進行變異，變異后：101101 此操作僅限于二進制編碼的染色體串，對于實數(shù)編碼的串不適用。 (2) 逆轉(zhuǎn)基因位變異 在個體的染色體串中隨機的選擇兩個逆轉(zhuǎn)點，然后將兩個逆轉(zhuǎn)點之間的基因逆向排序，從而達到產(chǎn)生新個體的目的。 變異前：101011001 選擇兩個逆轉(zhuǎn)點為2和7，變異后：101101001 變異前：132456779 選擇兩個逆轉(zhuǎn)點為2和7，變異后：136542779 操作對于染色體串的編碼方式?jīng)]有過多的要求，因此是比較常用的變異方法，但通過觀察我們應(yīng)該發(fā)現(xiàn)此操作會產(chǎn)生與父代差異很大的染色體串，在應(yīng)用中予以

60、重視。 (3) 互換變異 在染色體串中隨機的選擇兩個基因位，然后互換基因位上的值，完成變異操作。 變異前：101101 選擇變異位置為3和5，變異后：100111 變異前：125673 選擇變異位置為3和5，變異后：127653 3遺傳算法求解柔性作業(yè)車間調(diào)度問題 3.1 遺傳算法求解柔性作業(yè)車間調(diào)度問題的步驟 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領(lǐng)域和種類。FJSS問題的優(yōu)化，可按圖3.1來構(gòu)造求解該問題的遺傳算法[22]。 在圖3.1中，對于求解FJSS模型的基于活動種群遺傳算法各操作的詳細設(shè)計，如圖中的編碼、解

61、碼方法、適應(yīng)度、遺傳算子(選擇、交叉、變異)等在上一章中已做具體介紹。 圖3.1 求解FJSS問題的遺傳算法主要構(gòu)造過程示意圖 運用基于活動種群的遺傳算法求解FJSS模型的總體流程則表示如下： 第一步 設(shè)計問題的染色體，隨機生成種群規(guī)模為P的初始可行解，即初始的可行調(diào)度。 第二步 根據(jù)FJSS模型的目標(biāo)函數(shù)定義調(diào)度問題的適應(yīng)度，評價個體的適應(yīng)度值。 第三步 按某種選擇策略選擇下一代種群。 第四步 按交叉概率Pc對種群中未匹配的個體進行交叉操作，生成新個體。 第五步 按變異概率Pm隨機選擇個體，進行變異操作生成新個體。 第六步 計算新個體的適應(yīng)度值，父代個體和子代個體共同參

62、與生存競爭。 第七步 判斷遺傳操作是否達到終止條件，是則停止遺傳操作，最優(yōu)個體為問題的局部最優(yōu)解，否則轉(zhuǎn)第三步。 第八步 判斷活動種群是否達到符合本問題的合適數(shù)目，是則停止遺傳操作，最優(yōu)個體為問題的局部最優(yōu)解，否則轉(zhuǎn)第一步。 第九步 比較各局部最優(yōu)解，得出全局最優(yōu)解，即最優(yōu)調(diào)度。 3.2遺傳操作設(shè)計 遺傳算法的重點和難點在于遺傳操作的設(shè)計，主要有編碼方法、解碼方法、適應(yīng)度評價、選擇、交叉和變異。對于不同的優(yōu)化問題，遺傳操作的設(shè)計也各有不同。車間調(diào)度問題的優(yōu)化不同于一般的數(shù)值優(yōu)化，它屬于NP難問題，遺傳操作比較復(fù)雜，在優(yōu)化過程中還要考慮解的合法性和可行性等問題。對于基于活動種群的FJS

63、S問題不僅要尋找最佳的排序方案，選擇最合適的機器，還要考慮各機器和工人加工的成本因素，所以更增添了求解的復(fù)雜性。 3.2.1 編碼 編碼方式：本文采用的是一種雙子串的基因編碼方式，第一子串編碼表示工序所選加工機器，第二子串編碼表示調(diào)度次序，用工序加工優(yōu)先權(quán)值標(biāo)示。結(jié)合實例具體的編碼方式如下： 1) 染色體的長度L為所加工工件的全部工序總和，這里L(fēng)=12。 2) Qij表示工件i的第j道工序可選用機器的集合如下： Q11={ M1、M2、M3}，Q12={ M2、M4、M5}。 Q13={ M1、M2、M3}，Q21={ M1、M3、M5}。 Q22={ M1、M2、M5}，Q23

64、={ M3、M5、M3}。 Q31={ M1、M2}， Q32={ M2、M4、M5}。 Q33={ M3、M5、M6}，Q41={ M1、M3、M4}。 Q42={ M2、M4、M6}，Q43={ M1、M3、M6}。 第一子串編碼表示工序所選的加工機器,在該工序的可選加工設(shè)備集中隨機選取。 第二子串編碼表示各工序加工的先后順序,數(shù)值越小說明越先加工(優(yōu)先權(quán)值) ,在 [1, L]中隨機產(chǎn)生。例如表3.1。 特別需要注意的是：由于第二子串編碼工序加工的先后順序是有講究的。在第一子串編碼確定的情況下得到的是未進行排序的第二子串編碼，這里可能會產(chǎn)生不符合工藝順序的調(diào)度，必須進

65、行調(diào)整。我們把同一工件各工序所隨機得到優(yōu)先值按從小到大排列，再次依次分配給本工件的各工序。 調(diào)整前：(3 4 2) (5 7 8) (9 6 12) (11 10 1) 調(diào)整后：(2 3 4) (5 7 8) (6 9 12) (1 10 11) 理論上驗證上述調(diào)整方案可行。 表3.1 第二字串編碼 工序 第一層編碼 第二層編碼 Q11 2 3 Q12 3 4 Q13 1 2 Q21 3 5 Q22 2 7 Q23 5 8 Q31 1 9 Q32 4 6 Q33 6 12 Q41 3 11

66、 Q42 4 10 Q43 6 1 注：M1表示機器編碼1，下同。 3.2.2 適應(yīng)度函數(shù) 適應(yīng)度函數(shù)：由于遺傳算法中要比較適應(yīng)度函數(shù)值,并在此基礎(chǔ)上計算選擇概率----適應(yīng)度函數(shù)值高的個體被選擇的概率也大。所以適應(yīng)度函數(shù)的值要取正值，并且能反映這一特性。本文研究的是最大流程時間Cmax的最小化問題,因此適應(yīng)度函數(shù)定義如下： (3-1) 3.2.3 遺傳算法的主要操作步驟 交叉操作是將種群中的兩個個體交換某些基因，產(chǎn)生新的基因組合。由于編碼的特殊性，交叉操作需對兩部分分別進行。如圖3.2所示。圖3.2中交叉操作方法主要是采用從一個父代（如父代1）中隨機產(chǎn)生兩個交叉點并將交叉點中間的子序列拷貝到子代的相應(yīng)位置的方法。對于第二層編碼為避免產(chǎn)生不合法染色體,可以從父代2中移走在子代中已有的子序列7、8、6 ，剩余的數(shù)依次放入子代中。而對于第一層編碼則可以將父代2的基因(除子代中已有的子序列外)直接拷貝到子代的相應(yīng)位置。