【正文】 這可能造成計(jì)劃在實(shí)際調(diào)度中的不可行問題。 柔性車間作業(yè)調(diào)度問題 問題描述 一般的車間調(diào)度問題都是對(duì)于具體生產(chǎn)環(huán)境中復(fù)雜動(dòng)態(tài)、多目標(biāo)、多約束調(diào)度的一種抽象和簡化，其首要問題是對(duì)調(diào)度問題進(jìn)行建模。在傳統(tǒng)的 Job Shop調(diào)度問題研究中，僅考慮各工序在唯一確定的機(jī)床上加工的情況，即先有確定的加工計(jì)劃，再進(jìn)行作業(yè)調(diào)度，缺乏一定 的 柔性。研 究具有路徑柔性的車間調(diào)度 (Flexible Job Shop Scheduling，簡稱 FJSS)問題具有重要的理論和應(yīng)用意義。因此在建立 FJSS模型之前，首先要對(duì) FJSS問題有個(gè)清楚的描述，明確問題的特點(diǎn)、目標(biāo)、約束及輸入輸出。 調(diào)度目標(biāo)是為每道工序選擇最合適的機(jī)器，以及確定每臺(tái)機(jī)器上各工件工序的最佳加工順序及開工時(shí)間，使系統(tǒng)的某些性能指標(biāo)達(dá)到最優(yōu)。 數(shù)學(xué)描述： 目標(biāo)函數(shù) ： min ? ?ikni1mk1 cmax max ???? (11) S． t． ；，；，）（ mkhnM ?? 21,21ica1tc ihi h kikik ???? (12) ；，；， mknjitxMcc jki h kikjk ?? 2121)1( ?????? (13) ；，；， mkniik ?? 2,1210c ??? (14) 其中： ???? 其他情況， 加工工件先于機(jī)器機(jī)器，01a ikhi h k (15) ???? 其他情況， 上加工在機(jī)器先于工件工件，01x i jk kji (16) 華北電力大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 6 i,j = 1,2,… n； h,k = 1,2,… m； 其中， ikik tc 和 分別為工件 i在機(jī)器 k上的完成時(shí)間和加工時(shí)間； M是一個(gè)足夠大的正數(shù)；ijkihk xa 和 分別為指示系數(shù)和指示變量。 Gantt 圖 對(duì)于 m 臺(tái)機(jī)器 (Machine)(M1， M2， …， Mm)， n 個(gè)工件 (Job)(J1， J2， …， Jn)的加工過程，調(diào)度通常用 Gantt 圖表示。它基本上是一種線條圖，橫軸表示時(shí)間，縱軸表示要安排的活動(dòng)，線條表示在整個(gè)期間計(jì)劃的和實(shí)際的活動(dòng)完成情況。 Gantt 圖使車間的計(jì)劃安排情況一目了然，成為管理人員了解全局，安排車間進(jìn)度的有效工具。以 Gantt 圖表示的該實(shí)例的一個(gè)可行調(diào)度，如圖 所示。它最早由美國密執(zhí)安大學(xué)的 Holland教授提出，起源于 60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究 [12]． 70年代 De Gong基于 GA的思 想在計(jì)算機(jī)上進(jìn)行大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn) [13]。近幾年來， GA主要在復(fù)雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應(yīng)用，取得了一些令人信服的結(jié)果。 遺傳算法的基本思想 遺傳算法 (Geic Algorithms)的基本思想來源于分子遺傳學(xué)和生物進(jìn)化論，其基本原理是，產(chǎn)生若干代表問題候選解的成員，并組成一個(gè)群 體，按照某一評(píng)價(jià)函數(shù)或算法對(duì)群體中的每個(gè)成員進(jìn)行評(píng)估，評(píng)估結(jié)果代表解的良好性。利用遺傳操作對(duì)群體中的成員進(jìn)行遺傳操作，產(chǎn)生新的后代，這種后代能繼承雙親的特征。此過程反復(fù)執(zhí)行，這構(gòu)成一代代的群體。 遺傳算法的特點(diǎn) 遺傳算法是解決搜索問題的一種通用算法，對(duì)于大部分搜索問題都能夠使用，首先在此先闡述一下搜索算法的共同特 征 [14]： (1) 首先生成一組候選解，即構(gòu)造算法的初始解集； (2) 依據(jù)設(shè)定的適應(yīng)性條件計(jì)算這些解的適應(yīng)度； (3) 依據(jù)適應(yīng)度，選擇保留適應(yīng)度高的個(gè)體，去除適應(yīng)度低的個(gè)體； (4) 對(duì)篩選出的新個(gè)體進(jìn)行新的操作，生成新的適應(yīng)度個(gè)體。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。這是遺傳算法與傳統(tǒng)優(yōu)化算法的較大區(qū)別。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)，克服了早熟的缺點(diǎn)。遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化 。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以 任意設(shè)定。 (4) 遺傳算法使用的選擇、交叉、變異這三個(gè)算子都是隨機(jī)操作，而不是確定性規(guī)則。 (5) 遺傳算法最善于搜索復(fù)雜地區(qū)，從中找出期望值高的區(qū)域和個(gè)體。 綜上所述， GA 算法較之傳統(tǒng)優(yōu)化方法，具有良好的全局搜索能力，是一種全局優(yōu)化算法。因?yàn)檫z傳算法是一類基于 “產(chǎn)生 +測試 ”方式的迭代搜索 算法，盡管算法在一定條件具有全局收斂性，但算法的交叉、變異、選擇等操作一般都是在概率意義下隨機(jī)進(jìn)行的，雖 然 保證了種群的群體進(jìn)化性，但一定程度上不可避免退化現(xiàn)象的出現(xiàn)。這些概念如下： (1) 串 (String)：它是個(gè)體 (Individual)的形式，在算法中為表現(xiàn)為字符串， 并對(duì)應(yīng)于遺傳學(xué)中的染色體 (Chromosome)。 (3) 群體的大小 (Population Size)：在群體中個(gè)體的數(shù)量為群體的大小。 (5) 適應(yīng)度 (Fitness)：表示某個(gè)體對(duì)于環(huán)境的適應(yīng)程度。 標(biāo)準(zhǔn)遺傳算法的主要步驟如描述下： (1) 確定問題的編碼方案。 (2) 適應(yīng)度函數(shù)的構(gòu)造和應(yīng)用。適應(yīng)度函數(shù)基本上依據(jù)優(yōu)化問題的目標(biāo)函數(shù)而定，當(dāng)適應(yīng)度函數(shù)確定以后，自然選擇規(guī)律是以適應(yīng)度函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰，生存下來的染色體組成種群，形成一個(gè)可以繁殖下一代的群 體。通常包括；種群大小、交叉概率、變異概率、進(jìn)化代數(shù)等。通常包括：初始化、選擇、交叉、變異和替換操作等。新產(chǎn)生個(gè)體中可能發(fā)生基因變異，變異使解有更大的遍歷性。終止準(zhǔn)則應(yīng)根據(jù)所求解問題的性質(zhì)，在優(yōu)化質(zhì)量和效率方面作合理均衡或側(cè)重。因此如何確定 GA的最優(yōu)參數(shù)仍然是一個(gè)熱點(diǎn)問題，也是研究 GA的重點(diǎn)課題之一。當(dāng)種群數(shù)目設(shè)得過小時(shí)，不能提供足夠的采樣點(diǎn)來搜索整個(gè)解空間，以致算法性能很差；當(dāng)種群數(shù)目設(shè)得過大時(shí)，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會(huì)增加計(jì)算量，從而使收斂時(shí)間太長，算法效率偏低。 (2)交叉概率 (Crossover Rate) 交叉概率用于控制交叉操作發(fā)生的頻率。 一般建議的取值范圍是 。 (3)變異概率 (Mutation Rate) 變異概率是保證種群多樣性的重要因素。但是，變異概 率太小則不會(huì)產(chǎn)生新個(gè)體，概率太大則使GA成為隨機(jī)搜索。另外，也可使用自適應(yīng)的思想來確定變異概率。 (4)代溝 (G) 代溝用于控制每代中種群被替換的比例。在標(biāo)準(zhǔn) GA中， G=100％，而有些替換策略中 G值與新舊個(gè)體的適應(yīng)度好壞有關(guān)而且是變化的。對(duì)于最大化函數(shù)優(yōu)化問題，個(gè)體 x的適應(yīng)度可以定義為： u(x)=f(X)一 fmin (21) 其中 f(x)為其目標(biāo)值， fmin為問題的最小目標(biāo)值。許多方法用算法當(dāng)前進(jìn)程發(fā)現(xiàn)的最小目標(biāo)值 f’min作為替代。 (6)選擇策略 (S) 通常有兩種選擇策略：其一為純選擇，即種群中每一個(gè)體根據(jù)其適應(yīng)度作比例選擇；其二為保優(yōu)策略，即先用純選擇作選擇，然后將最優(yōu)個(gè)體加入下一代種群，該策略可防止最優(yōu)解的遺失。編碼是應(yīng)用 GA時(shí)要解決的首要問題，也是設(shè)計(jì) GA時(shí)的一個(gè)關(guān)鍵步驟。 GA的一個(gè)顯著特點(diǎn)是它交替地在編碼空間和解空間中工作，它在編碼空間對(duì)染色體進(jìn)行遺傳操作，而在解空間對(duì)解進(jìn)行評(píng)估和選擇。 (2)染色體的合法性是指編碼空間中的編碼是否可以映射到解空間中的一個(gè)解。 華北電力大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 11 (3)映射的唯一性從編碼空間到解空間的映射可以是 1對(duì) 1映射、 X對(duì) 1映射或 1對(duì) X映射，顯然， 1對(duì) 1映射是最好的，而 1對(duì) X映射是最不值得提倡的。而解碼 (decoding)是 GA表達(dá)空間到問題的解空 間 的一種映射，如圖 。 有效調(diào)度，如圖 。 解 碼 空 間解 空 間可 行 區(qū) 域可 行不 可 行非 法 圖 調(diào)度的可行性和 合 法性 注： 不可行指的是某個(gè)染色體解碼出來的解在給定問題的可行區(qū)域之外的現(xiàn)象；而非法性指的是某個(gè)染色體不能代表給定問題的解的現(xiàn)象 針對(duì)函數(shù)優(yōu)化的編碼技術(shù)主要有二進(jìn)制編碼、十進(jìn)制編碼、 Gray 編碼、實(shí)數(shù)編碼等。二進(jìn)制編碼類似生物染色體的組成，從而使算法易于用生物遺傳理論來解釋。另外，采用二進(jìn)制編碼算法的處理模式很多，但是可能使相鄰整數(shù)具有較大的 Hamming[16]距離。這種缺陷造成了 Hamming懸崖將降低遺傳算子的搜索效率。 由于很多數(shù)值與非數(shù)值優(yōu)化問題都可以用二進(jìn)制編碼來應(yīng)用遺傳算法，同時(shí)表達(dá)的模式最多，所以二進(jìn)制編碼方法是遺傳算法中最常用的一種編碼方法，它具有以下優(yōu)點(diǎn)： 1) 編碼、解碼操作簡單易行。 3) 符合最小字符集編碼原則。 (2) 格雷碼編碼方法 華北電力大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 12 作為一種新的編碼方法具有自己獨(dú)特的優(yōu)勢，但本質(zhì)上還是和二進(jìn)制編碼方法有相似之處。 格雷碼是將二進(jìn)制編碼通過一個(gè)轉(zhuǎn)換而得到的編碼。則將二進(jìn)制轉(zhuǎn)化為格雷碼的公式為： 1 1 , 2 , . . . , 2 , 1mmi i igbg b g i m m???? ? ? ? ? ?? (22) 其中 ⊕ 為異或運(yùn)算符，而格雷碼轉(zhuǎn)化為二進(jìn)制的運(yùn)算公式為 : 1 1 , 2 , . . . , 2 , 1mmi i ibgb b g i m m???? ? ? ? ? ?? (23) (3) 實(shí)數(shù)編碼 為了克服二進(jìn)制編碼的缺點(diǎn)，對(duì)問題的變量是實(shí)向量的情形，可以直接采用實(shí)數(shù)編碼。遺傳算法在求高維、復(fù)雜優(yōu)化問題時(shí)通常采用實(shí)數(shù)編碼 [18]。適應(yīng)度函數(shù)表明個(gè)體對(duì)環(huán)境適應(yīng)能力的強(qiáng)弱，是區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn)，也是進(jìn)行自然選擇的唯一依據(jù)。 c(X)為個(gè)體的目標(biāo)值， a0。 對(duì)于適應(yīng)度和目標(biāo)函數(shù)值，有多種設(shè)計(jì)方法。采用妥協(xié)方法 [19]的基本思想是：通過 最大完成時(shí)間來確定后悔值 r，進(jìn)而求得相應(yīng)染色體的適應(yīng)度。加權(quán) Lp范數(shù) [21]被用作距離度量方式來確定后悔值 r即 其中 (z1*， z2*， … ， zq*)是判據(jù)空間 Z中的正理想點(diǎn)，權(quán)重 (w1， w2， … ， wq)被分配給目標(biāo)并用來強(qiáng)調(diào)其不同的重要程度。理想解實(shí)際上無法達(dá)到，然而它可以成為評(píng)價(jià)可達(dá)到的非支配解的標(biāo)準(zhǔn)。 )42(),。該系數(shù)有兩個(gè)作用：避免式 (25)產(chǎn)生被零除錯(cuò)誤；可以將選擇方式從適應(yīng)值比例選擇調(diào)整到純粹隨機(jī)選擇 ( ??? )。因此，對(duì)于評(píng)價(jià)過程復(fù)雜的問題，如 仿真優(yōu)化問題，如何提出有效的評(píng)價(jià)機(jī)制來加速或簡化評(píng)價(jià)過程，將有利于提高 GA的優(yōu)化效率。但考慮到搜索效率和質(zhì)量，最好采用如下策略設(shè)定 [21]： 1) 根據(jù)問題固有知識(shí)，設(shè)法把握最優(yōu)解所占空間在整個(gè)問題空間中的分布范圍，然后，在此范圍內(nèi)設(shè)定初始種群。 選擇算子 遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。 最常用的選擇方法是適應(yīng)度比例選擇、最優(yōu)個(gè)體保存選擇和錦標(biāo)賽選擇。 比例選擇的基本思想是：根據(jù)染色體的適應(yīng)度值的大小，分配繁殖機(jī)會(huì)，適應(yīng)度相對(duì)低的個(gè)體則產(chǎn)生的后代數(shù)目將減 少 。設(shè)群體大小為 M，個(gè)體 i的適應(yīng)度為 Fi，則個(gè)體 i被選中的概率 Pi，為 Pi = ??Mi iiFF1 (2 6) 由上式可見，適應(yīng)度越高的個(gè)體被選中的概率越大；反之，適應(yīng)度越低的個(gè)體被選中的概率越小。首先將種群中所有個(gè)體由好到壞進(jìn)行排列，然后以一定方式分配給各個(gè)體一定的選擇概率，具體分配方式不限，如線性方式、非線性方式，但要要求越好的個(gè)體分配的概率越大，且所有個(gè)體所分配 的概率之和為 l。首先在父代種群中隨機(jī)選取 k個(gè)個(gè)體，然后令其中適配值或目標(biāo)值最好的個(gè)體為被選中的個(gè)體。 交叉算子 遺傳算法中起核心作用的是交叉算子，也稱為基因重組 (rebination)。子代應(yīng)能夠部分或者全部地繼承父代的結(jié)構(gòu)特征和有效的基因。 下面我們來介紹在遺傳算法中主要應(yīng)用的兩種交叉方法： (1) 單點(diǎn)交叉 首先在相互配對(duì)的染色體中隨機(jī)確定一個(gè)交叉位置，然后對(duì)換交叉點(diǎn)后的子串。 P1→(1100 ∣ 100) C1→(1100 ∣ 011) P2