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

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

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

2、方法。其次對所研究的作業(yè)車間調(diào)度進(jìn)行了詳細(xì)的數(shù)學(xué)分析，并對數(shù)學(xué)描述進(jìn)行了簡化，為下一步的算法設(shè)計(jì)建立數(shù)學(xué)模型。針對柔性作業(yè)車間調(diào)度問題的特點(diǎn)，提出了一種改進(jìn)的遺傳算法，采用雙子串的方式來進(jìn)行編碼，并且基于此給出了獨(dú)特的交叉和變異法則，從而取消了運(yùn)用遺傳算法求解作業(yè)車間問題時(shí)為使基因合法化而進(jìn)行的基因修復(fù)和重建過程。 最后給出了一個(gè)4×6 調(diào)度問題的測試?yán)?，并且繪制出了作業(yè)調(diào)度的甘特圖。仿真實(shí)例證明了此算法的有效性。 關(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è)計(jì)（論文） 目錄

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實(shí)際車間調(diào)度問題的特點(diǎn) …………………………………………………………………3 1.5車間調(diào)度問題的研究方法 …………………………………………………………………4 1.6實(shí)際車間生產(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遺傳算法的特點(diǎn) ……………………………………………………………………………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è)計(jì)………………………………………………………………………………17 3.2.1編碼………………………………………………………………………………………17 3.2.2適應(yīng)度函數(shù)………………………………………………………………………………18 II 3.2.3遺傳算法的主要操作步驟……………………………………………………18 4仿真實(shí)例及結(jié)論 ………………

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

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

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

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

18、術(shù)的研究和應(yīng)用，已經(jīng)成為先進(jìn)制造技術(shù)實(shí)踐的基礎(chǔ)和關(guān)鍵，優(yōu)良的調(diào)度策略對于提高生產(chǎn)系統(tǒng)的最優(yōu)性、提高經(jīng)濟(jì)效益，有著極大的作用。在理論研究中，車間作業(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)度問題的研究不僅具有較大的實(shí)用價(jià)值，而且還有相當(dāng)大的理論意義。研究生產(chǎn)調(diào)度問題推動(dòng)了遺傳算法、模擬退火算法、啟發(fā)式方法等優(yōu)化方法的發(fā)展與融合，也為其他

19、領(lǐng)域類似問題的解決提供了條件與手段。通過將優(yōu)化算法與調(diào)度方法相結(jié)合，使制造系統(tǒng)提高運(yùn)行效率，滿足客戶的要求，增強(qiáng)企業(yè)在市場上的競爭力。 1.2車間調(diào)度問題研究現(xiàn)狀 由于調(diào)度問題是制造系統(tǒng)中最基本、最重要的問題之一，是生產(chǎn)管理的核心問題和關(guān)鍵技術(shù)，因此國內(nèi)外大量的學(xué)者對其進(jìn)行了廣泛的探討和研究。調(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)缺點(diǎn)[6]，所以，近年來，人們開始將各種算法組合起來進(jìn)行研究[7]，以揚(yáng)長避短，達(dá)到優(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)度可分為單機(jī)調(diào)度、作業(yè)車間調(diào)度(Job Shop)、流水車間(Flow Shop)調(diào)度、多機(jī)器并行加工調(diào)度。 (

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

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

23、問題的解析求解方法。 (2) 枚舉方法（enumerative methods）該類方法對小規(guī)模問題比較有效，但對于大規(guī)模問題計(jì)算量和存儲量難以承受。 ◆分支定界（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）。如移動(dòng)瓶頸過程，beam搜索等。 ◆ 插入方法（insertion algorithm）。如CDS，NEH法等。 (4) 領(lǐng)域搜索算法（local search method）。該類方法從若干解出發(fā)，對其領(lǐng)域的不斷搜索和當(dāng)前解的替換來實(shí)現(xiàn)優(yōu)化。 ◆ 迭代改進(jìn)法（iterative improvement）。 ◆ 模擬退火法（simulated annealing，SA）。 ◆ 進(jìn)化算法（evolutionary computation，EC）。它包括遺傳算法（genetic algorithm，GA）、進(jìn)

25、化規(guī)劃、進(jìn)化策略和遺傳編程。 ◆ 禁忌搜索（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ù)進(jìn)行搜索，譬如將優(yōu)化過程轉(zhuǎn)化成智能系統(tǒng)動(dòng)態(tài)的演化過程，基于系統(tǒng)動(dòng)態(tài)的演化

26、來實(shí)現(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實(shí)際車間生產(chǎn)調(diào)度研究中存在的主要問題 調(diào)度領(lǐng)域中的大部分問題都具有NP難問題，雖然對它的研究已經(jīng)有幾十年的歷史，但至今尚未形成一套系統(tǒng)的方法和理論。一些理論上的最優(yōu)化方法能提供最優(yōu)調(diào)度，但由于其計(jì)算的復(fù)雜性，并且忽略了很多實(shí)際因素，離實(shí)際運(yùn)用還有很大距離。 由于大多

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

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

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

30、之后，方能開始另一個(gè)加工任務(wù)； (3) 各工件必須按工藝路線以指定的次序在機(jī)器上加工； (4) 不考慮工件加工的優(yōu)先權(quán)； (5) 每個(gè)工件的工序一旦進(jìn)行就不能中斷； (6) 一個(gè)工件同一時(shí)間只能在一臺機(jī)器上加工，一臺機(jī)器同一時(shí)間只能加工一個(gè)工件，加工的開始時(shí)間為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在機(jī)器k上的完成時(shí)間和加工時(shí)間；M是一個(gè)足夠大的正數(shù)；分別為指示系數(shù)和指示變量。式(1-1)表示目標(biāo)函數(shù)，即調(diào)度的目標(biāo)為最大完成時(shí)間最小化；式(1-2)表示順序約束條件，即各個(gè)工件各操作的先后加工順序，保證每個(gè)工件的加工順序滿足預(yù)先的要求；式(1-3)表示資源約束條件，即機(jī)器加工各個(gè)工件的先后順序，保證每臺機(jī)器一次只能加工一個(gè)工件。 1.8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

60、重視。 (3) 互換變異 在染色體串中隨機(jī)的選擇兩個(gè)基因位，然后互換基因位上的值，完成變異操作。 變異前：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模型的基于活動(dòng)種群遺傳算法各操作的詳細(xì)設(shè)計(jì)，如圖中的編碼、解

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

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

63、S問題不僅要尋找最佳的排序方案，選擇最合適的機(jī)器，還要考慮各機(jī)器和工人加工的成本因素，所以更增添了求解的復(fù)雜性。 3.2.1 編碼 編碼方式：本文采用的是一種雙子串的基因編碼方式，第一子串編碼表示工序所選加工機(jī)器，第二子串編碼表示調(diào)度次序，用工序加工優(yōu)先權(quán)值標(biāo)示。結(jié)合實(shí)例具體的編碼方式如下： 1) 染色體的長度L為所加工工件的全部工序總和，這里L(fēng)=12。 2) Qij表示工件i的第j道工序可選用機(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}。 第一子串編碼表示工序所選的加工機(jī)器,在該工序的可選加工設(shè)備集中隨機(jī)選取。 第二子串編碼表示各工序加工的先后順序,數(shù)值越小說明越先加工(優(yōu)先權(quán)值) ,在 [1, L]中隨機(jī)產(chǎn)生。例如表3.1。 特別需要注意的是：由于第二子串編碼工序加工的先后順序是有講究的。在第一子串編碼確定的情況下得到的是未進(jìn)行排序的第二子串編碼，這里可能會(huì)產(chǎn)生不符合工藝順序的調(diào)度，必須進(jìn)

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