jiing's blog (jiing.org)

最近在整理老硬碟，找到了古早以前修課的期末報告的純文字檔，那時MATLAB還沒有基因演算法工具箱，在網路上雖然有找到一份程式碼，但是其交配法和課本所述的不同，於是一切都是自己重頭刻起的，現在MATLAB已有工具箱，想必學習基因演算法的人可以運用它來更快速地開發應用程式來求解問題了。圖是重新產生的，有的圖不見了，不過不是很重要，我也就沒有重畫了。大家稍微看看就好，我也只是作個紀念而己。
當時上課用的課本是：《Gen, M. and R. Cheng, Genetic Algorithm and Engineering Design, John Wiley & Sons, New York, 1997》，由於我手邊似乎只剩下純文字檔，缺了蠻多東西的，有興趣者可以去找那本書來對照著看。
遺傳演算法應用於Flow-Shop排程問題原始碼下載點在此
（本份程式碼採授權)
本軟體係採用 CC-GNU LGPL授權，請下載的人留個言吧！
這份程式碼似乎也不是我交出去的最終版，不過我以前沒有用版本控制系統，所以也不知這個是哪一版，不過個人在MATLAB2006a上大致試跑之後它是可執行的，使用的方式是在MATLAB command window打GA_fs，程式沒什麼技巧，因為是急就章（quick-and-dirty）之作，主要是應付一下基因演算法的期末報告。

1. 導論

Flow-shop問題自從Johnson(1954)出版了第一份在flow-shop排序(sequencing)的問題之後，Flow-shop問題己吸引了許多的研究者投入研究。
Flow-shop排序(sequencing)問題一般描述如下：有m個機台和n個工作，每個工作包含了m了個操作程序(operations)，且每個操作程序都需要一個不同的機台。n個工作需要以同樣的順序在m個機台上被加工，工作i在機台j上的加工時間已知為tij(i=1,....,n;j=1,...,m)。目標是去尋找能最小化最大的流程時間（也稱為makespan)的工作執行順序。
此問題主要的假設通常有以下幾點：

• 所有工作在時間0時，都可以被執行
  
• 每個工作必須經所有的機台，並以機台1,2,...,m的次序加工
  
• 每個機台一次只能加工一樣工作
  
• 每個工作一次只能在一台機台上加工
  
• 作業不可超前（non-preemptive）
  
• 設定時間（set-up time）與加工順序不相關（sequence-independence），且包含在加工時間（processing time）之中
  
• 工作的順序在每個機台都一樣，且共同的順序已被決定。
  

Flow-shop排序問題已被分類為以下三種：

• 定性的（deterministic）flow-shop問題
  
• 隨機的（stochastic）flow-shop問題
  
• 模糊的flow-shop問題
  

定性的問題假設工作的固定加工時間已知。在隨機flow-shop問題裡，加工時間根據所選擇的機率分配而變化。在模糊決策flow-shop問題中，一個模糊交期被分派到每個工作，以代表決策者對於工作完成時間滿意的程度。更進一步地，如困任何已知工作在一個或是數個機台上的加工時間為0，那麼這個flow-shop問題稱之為一般的flow-shop問題，否則則稱為純粹的(pure)flow-shop問題。過去30年中主要的研究都玫力於在純粹定性的flow-shop排序問題。這種問題通常以n/m/F/cmax標示，這代表了n-job/m-machine/flow-shop/maximum flow time。
通常會使用甘特圖（Gantt chart）來表示flow-shop問題的排程結果。圖1.1是一個4個工作在2個機台的問題的例子。
圖 1.1 flow-shop排序問題的甘特圖
(略)

2.Flow-Shop問題相關解法

2.1 二個機台的Flow-shop問題
以makespan作為目標的二個機台的flow-shop問題被稱作是Johnson's problem。二個機台問題的一個最佳化順序可以由廣為人知的Johnson's rule決定。Johnson's rule中的點子提供了一個作為之後m-machine問題啟發法的基礎。

Theorem(Johnson's Rule)
Job i preceedes job j in an optimal sequence if min{tj1,tj2}<=min{tj2,tj1}.

藉由採用以上的結果，最佳次序經由一次掃描的程序即可直接產生。令J表工作清單且令S表排程；則Johnson's alogrithm可以被描述如下：
演算法：Johnson's Rule
第一步：令U={j|tj1=tj2}
第二步：將在U中的工作以tj1非遞減的順序排序。
第三步：將在V中的工作以tj2非遞減的順序排序。
第四步：將排序好的V放在排序好的U之後即是最佳序列
為了說明演算法，考慮一個如在表2.1中八個工作(job)的問題。產生解的方式如下：
表 2.1 八個工作的例題
（待補）
第一步：工作集合U={2,3,6}, V={1,4,5,7,8}
第二步：排序U中的工作如下：
job i 3 2 6
til 1 2 3
第三步：排序V中的工作如下：
job i 5 4 7 1 8
ti2 6 5 2 2 1
第四步：最佳序列為{3,2,6,5,4,7,1,8}
圖 2.1 最佳排程的甘特圖
2.2 一般m-Machine問題的啟發式解法
過去三十年，許多的研究者已處理過了純粹的flow-shop問題：他們發現並不存在著可以提供最佳解的簡單演算法。你可以使用整數規劃和分枝界限法(branch-and-bound)技巧來尋求最佳解。然而，在大型或更甚至是中型問題上，這些技巧並不非常有效率。而flow-shop問題又已被證明是屬於NP-Complete。因此，許多啟發式法則已被發展來提供一個又好又快的解。以下將討論一些廣為人知的啟發式演算法。
2.2.1 Palmer 的啟發式演算法
Palmer提出了一個slope order index來根據加工時間來將在機台上的工作排出次序。這個點子是給予每個工作一個優先次序，使得工作從一機台到另一機台的加工時間會有增加傾向的，具有較高的優先次序，而工作從一機台到另一機台的加工時間有減少傾向的，具有較低的優先次序。工作i的斜率指標(Slope index)si可被計算如下：
（方程式2.1的圖形暫略）
則一個permutation schedule可由將工作以非遞增的si排序而得，如：
（方程式2.2的圖形暫略）
註：permutation schedule是一個所有機台上的工作都具有相同順序的排程
2.2.2 Gupta的啟發式演算法
Gupta提供了另一個啟發式演算法，這個演算法和Palmer的啟發法很像，除了他以甚它方式定義了slope order index，他將最佳化的Johnson's rule一些有趣的事實納入考慮到three-machine問題之中。工作i的slope order index si可以以下面的方式計算
（方程式2.3的圖形暫略）
其中
（方程式2.4的圖形暫略）
因此工作根據slope index (2.3)來排次序。
2.2.3 CDS 啟發式演算法
Campbell, Dudek和Smith(CDS)的啟發式演算法基本上是Johnson's alogrithm的延伸。它的效率依賴二個性質：
以啟發式的方式來使用Johnson's rule
通常會從最佳排程中產生數個排程以供選擇
這個演算法首先以將m個機台系統化地聚集成二大群的方式，產生m-1個two-machine問題的集合，然後應用Johnson的two-machine演算法來尋找m-1個排程。在階段一，以機台1和機台m的型式來考慮two-machine問題。在階段二，考慮人造的two-machine問題：人造機台1由機台群（1,2）組成，而人造機台2由機台群{m, m-1}組成。在階段k時，考慮人造的two machine問題：人造機台1的機台群為{1,2,...,k}，而人造機台2有機台群{m,...,m-k+1｝。表2.2有總計的加工時間。第k階段的總加工時間定義如下：
表 2.2 人造two-machine問題集
（待補）
（方程式2.5的圖形暫略）
CDS啟發法被發現是一個非常好且強固的啟發法則，它已經被許多研究當作是一個比較的標準。
2.2.4 RA 啟發式法則
Dannenbring發展了一個稱作rapid access（RA）的程序，此程序企圖結合Palmer's slope index和CDS法的優點。它的目的是儘量既快又好地去提供一個好的解。它不去解m-1個人造two-machine造問題，取而代之的，它只需用Johnson's rule去解一個人造問題。而此問題的加工時間是以一個權重的方法來決定，如下：
（方程式2.6的圖形暫略）
其中權重定義如下：
W1={Wj1 | j=1,2,...,m}={m,m-1,...,2,1}
W2={Wj2 | j=1,2,...,m}={1,2,...,m-1,m}
2.2.5 NEH 啟發式法則
Nawaz, Enscore, 和Ham(NEH)啟發法是根據在所有機台上有較長總加工處理時間的工作應該比有較短總加工時間的工作被給予較高的優先權這個假設。NEH演算法並不將原始m-machine問題轉換成單一人造two-machine造問題。它以積極的方式來建立最終序列，在每個階段增加一個新工作並且尋找最佳部份解。
Algorithm: NEH
步驟一：將n個工作在機台上的總加工時間以遞減的方式排序。
步驟二：取出前二個工作，並以最小化部份makespan的方式來將它們排程，就好像只有那兩個工作似的。
步驟三：對於k = 3 to n，要將第k個工作插入那k個可能的位置，使得部份makepan能最小化。

3. 研究方法

基因演算法已經被成功地應用來解flow-shop問題，在本研究中，我們發展了一個以遺傳演算法為基礎的啟發式方法來解決flow-shop排程問題，並實作了一可互動的測試程式，可以測試各種交配運算子及突變運算子的組合對結果的影響，並能將flow-shop排程的結果予以視覺化呈現。
基因演算法（Genetic Algorithm, GA）是由Holland(1965)模仿生物自然的演化規則所發展出來的方法、初始化母體及如何決定母體大小、母體中各染色體適合度的評估、選種策略、基因運算子及運算終止條件。以下則分別討論如何將這些部份應用於flow-shop問題之上。
3.1 表示法
在此僅考慮當flow-shop問題為permutation scheduling的情形，故我們可以使用工作的排列當作是染色體的表示方法，對於排序(sequencing)問題而言，染色體也是自然的表示方式。舉例來說，令第k個染色體為
vk = [3 2 4 1]
這表示工作順序為j3, j2, j4, j1
3.2 初始母體的產生及決定母體大小
基因演算法會因選擇一個好的初始母體及合適的母體大小而使得效率大增。由於flow-shop問題中染色體的表示法為簡單的整數排列，故對於n個工作的flow-shop問題，我們選擇的母體一定要小於n!，才能彰顯基因演算法的益處。
在本研究所發展的展示程式中，可由使用者指定母體大小來觀看不同母體大小對於搜尋速度的影響，各種母體大小對搜尋最佳解速度的詳細比較將於第五章中以實驗設計的方式仔細討論。
Reeves為了產生一個好的種子染色體(seed chromosome)，他混合了傳統的啟發式方法在初始世代。一個染色體由NEH啟發法產生，而剩下的染色體則隨機產生。他比較了這個混合方法和沒有種子母體的方法，並且下評論說：「有種子的母體似乎可以比較快達到最終解，且在解的品質上看來並沒有下降。」
Chen, Vempati和Alaber已經提出了一個相似的混合方法來產生初始母體。對於n個工作、m個機台的flow-shop問題，用CDS產生了m-1了個排程，RA啟發法產生了一個解，剩下的則由隨機突變已經產生的排程來產生。
3.3 染色體合適度評估函數
有一個簡單的方法可用來決定每個染色體的適合度，就是使用makespan的倒數，令Ck,max代表第k個染色體旳makespan，則適合度計算如下：
（方程式3.1的圖形暫略）
其中Cmax的計算方法如下：
如果我們令c(j,k)代表了工作ji在機台k的完成時間，並令(j1,j2,...,jn)表示工作排列，然後我們可以計算n個工作m個機台的flow-shop問題的完成時間如下：
（方程式3.2?3.6的圖形暫略）
3.4 選種、淘汰（Selection）策略
3.4.1 mu+rambda的選種策略
在此我們採用mu+rambda selection的方式來作為選種策略，即將經過突變及交配運算後的rambda染色體君在原來的母體mu之後，然後再從中選出較好的mu個染色體作為下一代的母體。
另有其它的選種策略，以下介紹Reeves的選種策略：
3.4.2 Reeves的選種策略
基本上，如果母體包含許多合適度(fitness)值相當接近的染色體，那麼「好」與「壞」染色體的鑑別力就不高。在本案例中，相關的合適度測度在分辨染色體時並不是很好。Reeves使用一個簡單的排序（ranking）方法當作是選種(selection)機制。雙親(parent)則根據以下的機率分配選出。
（方程式3.7的圖形暫略）
其中k指的是升冪排序的第k個染色體（即，makespan的降冪），而M指的是最合適的那一個。這可推導出中間值有1/M有的機率被選取，然而最合適的那一個（第M個染色體）有2/(M+1)有的機會，大約是中間那一個旳二倍。
3.5 基因運算子
基因運算子一般包含了交配運算子（crossover operator）及突變運算子(mtation operator)，有的還有複製運算子(reproduction operator)。各式各樣旳基因運算子被用來處理排序（sequencing）問題。對於排列表示法，有許多可行的交配及突變運算子。以下我們討論一些廣為人知的運算子。
3.5.1 交配（crossover）運算子
在本研究中，採用了OX(Order Crossover)了、PBX（Position-Based Crossover）、Order-Based Crossoveer三種交配方法（詳見Gen的第三章）。
單一切點（one-cut-point）交配隨機選取一個切點，然後取出在第一個parent的切點之前的部份，並將從第二個parent中取出的每個合法基因依序填到後代（offsprint）中，如圖3.1所示。
圖3.1 單一切點交配
使用以位置為基礎的交配運算（position-based crossover）和平移突變運算（shift mutation）。Syswerda討論了似位置為基礎的交配運算。交配運算隨機選取某些位置，然後從第一個父代（parent）的這些位置取出基因並且從第二個父代（parent）依序取出合法（註：在此「合法」指的是要讓子代的基因沒有重覆）基因填入子代（offspring），就如圖3.2所示一般。
圖3.2 以位置為基礎的交配運算
3.5.2 突變（mutation）運算子
在本研究中，我們試驗了二種突變法。第一種，交換突變（exchange mutation），是隨機選擇染色體內的二個基因來交換。
交換突變是設計來執行隨機交換（random exchange）：也就是，它的隨機選擇染色體內的二個基因，並且交換他們的位置。舉例如下：
圖3.3 交換突變
第二種，平移突變（shift mutation），是將一個基因（隨機選取）向右或向左平移隨機位數，圖3.4是平移突變（shift mutation）的示意圖。
圖3.4 平移突變

4. 發展互動式的視覺化展示程式

在本研究中，我們發展了二個系統，第一個是遺傳演算法的測試系統，它可以根據使用者輸入的參數來執行max_gen次的生物遺傳演算，在每一世代的演化中，動態地秀出目前的makespan值的變動曲線，並在結果時秀出甘特圖及makespan的變化曲線。第二個則可統計數回合（每一回合中有max_gen有個世代）中，結果的最大值、最小值、平均值及標準差等數據，並繪出其直方圖及圓餅圖，以便使用者做實驗結果分析。
4.1 系統功能及圖形使用介面
4.1.1 測試系統
我們以Matlab為程式發展工具，發展了一個具互動能力的基因演算法展示程式，以下我們將描述其基本功能：
如圖4.1，我們可以選擇是否使用隨機問題產生器，或是使用原先在檔案jobInfo.txt中定義的例子。

圖4.1 是否使用問題產生器的詢問介面
如圖4.2，我們可以選擇隨機問題的各參數：機台數目、工作數目及加工時間的分配。

圖4.2 問題產生器參數輸入介面
如圖4.3，我們可以在圖形使用者介面中輸入基因演算法各參數 Pm, Pc, pop_size, max_gen。


圖4.3 基本參數輸入介面
如圖4.4，我們可以選擇在這次試驗中欲使用的交配運算子。
(jiing:這裡好像有二個方法亂實作，會有誤)

圖4.4 交配運算子選單
我們也可以選擇在本次試驗中使用的突變方法，如圖4.5。

圖4.5 突變運算子選擇介面
在每次運算中，我們也可以選擇是否需要動態makespan折線圖來觀察目前最佳解的變化情形，如圖4.6。

圖4.6 選擇是否要動態繪製makespan折線圖
4.1.2統計系統
統計系統除了之前測試系統的功能之外，還多了每個回合執行之後的統計資料展現，以40個機台，30個job所產生的範例，加工時間為[5,10]之間的均勻分配。使用XX交配方法，XX突變方法，每個回合有100代，共執行100個回合的結果，我們可由圖4.7和圖4.8之中看到此展示系統收集了第一代找到目前最佳解的世代數、目前最佳解值和CPU執行時間的直方圖以及其平均數、標準差、最大值、最小值和分析目前最佳解出現的比例的圓餅圖。



圖 4.7 第一次找到目前最佳解的世代數、目前的最佳解值和CPU執行時間的各回合直方圖。
(這個好像在最終版的程式才有)
圖 4.8 目前最佳解出現的比例的圓餅圖
(這個好像在最終版的程式才有)
4.2 數值範例(下面大家可以用程式玩看看，我就不截圖了:D)