遺傳演算法求解混合流水車間調度問題（附C++代碼）
遺傳演算法求解混合流水車間調度問題（附C++代碼）
欲獲取相關代碼，請關注我們的微信公眾號：數據魔術師。在後台回復遺傳車間調度即可下載。
0 前言
各位讀者大家好，好久沒有介紹演算法的推文了，感覺愧對了讀者們熱愛學習的心靈。於是，今天我們帶來了一個神奇的優化演算法——遺傳演算法！
它的優點包括但不限於：遺傳演算法對所求解的優化問題沒有太多的數學要求，由於他的進化特性，搜索過程中不需要問題的內在性質，對於任意形式的目標函數和約束，無論是線性的還是非線性的，離散的還是連續的都可處理。進化運算元的遍歷性（各態歷經性）使得遺傳演算法能夠非常有效地進行概率意義的全局搜素。
遺傳演算法對於各種特殊問題可以提供極大的靈活性來混合構造領域特有的啟發式，從而保證演算法的有效性看完了是不是頓時覺得遺傳演算法很強大呢？其實遺傳演算法在我們之前的推文中就已經出現啦，在乾貨 | 遺傳演算法(Genetic Algorithm) （附代碼及注釋）以及乾貨 | 遺傳演算法(Genetic Algorithm) Java 詳細代碼及注釋里你都可以學到遺傳演算法的相關知識。這次我們要介紹的是遺傳演算法解決混合流水車間調度問題。需要注意的是，在以上兩篇推文中求解的是連續優化問題，採用浮點數編碼方式可以更好達到精度和空間要求（具體見兩篇推文）。而本文求解的是離散優化問題，使用二進位編碼和浮點數編碼會存在精度誤差，使用符號編碼是更好的選擇。符號編碼法是指個體染色體編碼串中的基因值取自一個無數值含義、而只有代碼含義的符號集如｛A,B,C…｝、{1,2,3...}（數字僅表示為符號）、{A1、A2、A3...}等。本文採用了符號編碼中的數字元號編碼。廢話不多說，我們趕緊來學習一下這麼niubility的演算法吧~
1 遺傳演算法
1.1 遺傳演算法簡介遺傳演算法（Genetic Algorithm，GA）是一種模擬自然選擇和生物進化過程的智能優化演算法。在自然界中，自從達爾文提出「優勝劣汰，適者生存」物種進化理論之後，研究學者對生物進化的過程進行了長久而又深遠的研究。物種通過母代的繁衍形成新的下一代個體，新一代個體中，大多數個體由於發生染色體交叉過程會與母代類似，少數個體由於發生了變異則與母代不同。大自然作為自然選擇的執行者，在生存資源和外界環境的變化、個體不斷進行競爭的過程中，將適應能力強的個體留下，而淘汰適應能力差的個體，這種自然選擇的過程為人類提供了一種全新的解決問題的方式。
1965年，John H. Holland首次引用了生物的進化機制來解決問題，他的學生在論文中也首次提出「遺傳演算法」的概念。1975年， Holland概括性總結論述了遺傳演算法。幾十年來，越來越多的研究學者加入到遺傳演算法的研究中，並取得了豐富的研究成果。隨著研究的深入，遺傳演算法以其操作簡單、容易實現等優點，逐漸應用於各個領域，不僅在函數優化、組合優化等方面有所建樹，同時在應用層面如機器學習、生產調度、自動控制、圖像處理、數據挖掘等方面也有很廣泛的應用。1.2 遺傳演算法的基本思想生物的進化是通過染色體來實現的，染色體上有著許多控制生物性狀的基因，這些基因會在遺傳過程中隨著染色體的交叉進行重新組合，同時會以一定概率發生變異。遺傳演算法的基本思路與此類似，可以將待優化問題的求解看作生物努力適應環境的過程，問題的解對應生物種群中的個體，演算法的搜索便是種群一代代進化最終形成穩定物種的過程。1.3 遺傳演算法的基本步驟
遺傳演算法的結構框架可以簡述如下：
1、初始化：依據每個種群的特徵隨機生成第一代種群的全部個體；
2、求個體適應度：計算每個個體的適應度；3、選擇過程：依據一定的選擇規範，選出一部分優秀個體參與交叉和變異操作；4、交叉過程：群體中兩兩配對，交換部分染色體基因，完成交叉操作；5、變異過程：隨機改變個體中的部分基因，來實現變異操作；6、終止判斷：若新一代種群滿足終止條件，停止演算法迭代，記錄此時的最優解為問題的最優解；否則，迭代次數加1，返回步驟2；附遺傳演算法的演算法流程圖：
2 混合流水車間調度問題
2.1 混合流水車間調度問題簡介混合流水車間調度問題（Hybrid Flow Shop Scheduling Problem, HFSSP）也稱為柔性流水車間調度問題，是經典流水車間調度的推廣。它綜合了經典流水車間和並行機兩種調度的特點，符合實際生產的要求，具有很高的研究價值和應用背景。
下圖簡單表示了HFSSP問題，其中假設有c加工階段，每個階段i有c_i（i=1，2，…m）台機器。
2.2 問題描述本文中HFSSP考慮在一條流水線上進行生產。n個工件在包含c個階段（機器中心）的流水線上進行加工。每個工件都要依次通過每個階段。每個階段至少有一台加工機器並且至少有一個階段包含多台並行機器（若每階段有且僅有一台加工機器，則稱為經典流水車間調度問題Flow Shop Scheduling Problem, FSSP）。
已知各工件的加工時間，優化目標是如何確定工件的加工順序以及每階段工件在機器上的分配情況，使得最大完工時間極小化。2.3 假設條件
1）同一階段中所有機器都相同；
2）每個工件可以在某階段的任意一台機器上進行加工；3）任意時刻每個工件至多在一台機器上加工；4）每台機器某時刻只能加工一個工件；5）工件的加工過程不允許中斷。
2.4 符號釋義
2.5 模型建立
對於種群中任一個體的編碼，首先加工第一道工序，在空閑機器上按編碼中工件順序依次加工相應的工件；
加工第二道工序時，按照先完工先加工的原則，在空閑機器上優先加工當前可用工件（已在上一階段完成加工），以此類推直到最後一個工件在最後一個階段結束完工。遞推過程如下：
(1)式表示第1個工件第1道工序的加工時間等於該工件在第一階段的完工時間；
(2)式表示第1個工件第k道工序完工的時間等於該工件緊前工序的完工時間加上當前工序的加工時間；(3)式表示工件j第1道工序的完工時間，等於同一機器上緊前工件第1道工序的完工時間加上工件j第1道工序的加工時間；
(4)式表示工件j在階段k的完工時間，等於工件j緊前工序的完工時間或同一機器緊前工件j-1的完工時間中的最大值加上工件j在階段k的加工時間。因此目標函數表示如下：
即求最後一個工件在最後一個階段完工時間的最小值。
3 遺傳演算法求解HFSSP基本思路
3.1 編碼
先將工件按照1-n的順序編號，這裡編碼方式採用工件編號隨機全排列的方法。編碼代表了工件被處理的優先順序，編碼方式如下圖所示（以7個工件為例），1號工件的編碼順序比4號工件編碼順序靠前，那麼1號工件被處理的優先順序就高於4號工件，因此，當有空閑機器時且滿足加工條件時，優先考慮加工1號工件。
有時，也可以採用工件在第一階段開始加工時間由小到大的順序對給定的工件序列進行編碼，通常是在非隨機生成的初始種群中會用到。
3.2 解碼
解碼過程是從編碼到最大完工時間的映射。下面舉例說明該編碼的解碼過程：
為了簡便，假設有3個工件，2道工序，2台並行機。工件在各階段的加工時間為：
首先根據編碼的優先順序順序，先對工件2進行處理，此時可進行工序1加工的機器都空閑，因此把工件2默認放在工序1機器1上進行加工。
接下來處理第二優先順序的工件，此時可加工工序1的空閑機器只有機器2，因此將工件1放在工序1機器2上進行加工。
工件3的加工需要比較工序1兩台機器完工時間，從加工時間我們可以看出，p(1,1)=3,p(1,2)=6,因此1號工件最先加工完，機器2比機器1最先空閑，我們將工件3放在機器2上進行加工。
考慮工序2的加工時，我們按照先完工先生產的原則，優先加工工序1中先完工的工件，由圖中可以看出，1號工件最先完工，且工序2中兩台加工機器都空閑，因此將1號工件放在機器1上加工。
同樣的，我們進行工件2和工件3第2道工序的加工，當最後一個工件最後一道工序加工完成之後，工序2機器1最晚完成加工，因此最大完工時間就是工序2機器1的完工時間，由已知的加工時間可知，
該問題的最大完工時間(Makespan)為p(1,1)+p(2,1)+p(2,3)=12
3.3 適應度函數 適應度函數作為評價個體優劣的標準，適應度越高，則個體越接近最優解，適應度越低，則個體解越差。本文將(5)式取倒數，作為適應度函數來進行計算,即
Fitness=1/Makespan3.4 選擇操作 本文採用輪盤賭的方法來選擇個體。根據適應度函數求解種群中全部個體的適應度，採用輪盤賭的方式重新選擇個體。
設置種群的總數M，個體i適應度為
，那麼個體i被選中的概率為
由該式可見，適應度高的個體被選中進入下一代的概率大，適應度低的個體被選中進入下一代的概率相對較小。
3.5 交叉操作 種群中的個體隨機進行兩兩配對，配對成功的兩個個體作為父代1和父代2進行交叉操作。
隨機生成兩個不同的基因點位，子代1繼承父代2交叉點位之間的基因片段，其餘基因按順序繼承父代1中未重複的基因；子代2繼承父代1交叉點位之間的基因片段，其餘基因按順序繼承父代2中未重複的基因。如圖所示：
3.6 變異操作 採用兩點變異的方式，隨機生成兩個基因位，並交換兩個基因位上的基因。
3.7 終止條件 常見的遺傳演算法終止條件有：
1、迭代固定次數後取最優值2、運行固定時間後取最優值
3、確定一個優化目標，達到優化目標後就停止本文採用第一種方法3.8 測試問題 測試問題參數取值：
工件數量n：6工序數量c：3每道工序並行機器數量m:2已知各工件各道工序的加工時間如下表所示：
GA的關鍵參數，一般通過正交實驗來確定。本文取值如下：
種群個數N取200個，交叉概率0.6，變異概率0.05，種群迭代次數G為100。4 運行結果 下圖是一次測試所得到的最優解，最優的加工順序為4，5，1，2，6，3，最終所用的時間為25。
將運行結果以甘特圖的形式表示出來，如下圖所示。
ps.input文件輸入格式如下
根據中各工件各工序的加工時間，在工程文件夾下新建「input.txt」文件，並按照如下格式輸入到txt文件中。 2 4 6 4 9 2 4 2 8 9 5 6 5 2 7 9 4 3-- the end --
文案 && 代碼：李濤編輯：陳俞丞
指導老師：王愷（武漢大學經濟與管理學院副教授）
審稿老師：白丹宇（南京林業大學教授）
如對文中內容有疑問，歡迎交流。PS:部分資料來自網路。
如有需求，可以聯繫：王愷（[email protected]）白丹宇（[email protected]）李濤（華中科技大學管理學院18級碩士研究生：[email protected]）陳俞丞（華中科技大學管理學院本科二年級 : [email protected]）推薦閱讀：
