遺傳算法與模擬退火算法在FMS中的混合應(yīng)用

王 濤，吳林彥，張如偉，王 琪，裴 翦

（1.山東建筑大學(xué)，濟(jì)南 250100；2.山推工程機(jī)械股份有限公司，濟(jì)寧 272023）

0 引言

FMS中的機(jī)器裝載問題為通過滿足技術(shù)約束（如可用機(jī)器時間和工具槽約束）來分配機(jī)器、所選作業(yè)的操作以及執(zhí)行這些操作所需的工具，以確保系統(tǒng)不平衡性的最小化和吞吐量的最大化，同時求解目標(biāo)函數(shù)，使結(jié)果更接近FMS環(huán)境的真實(shí)假設(shè)[1]。目前有許多針對FMS中的機(jī)器負(fù)載問題的研究，并提出了啟發(fā)式算法來優(yōu)化系統(tǒng)的不平衡和吞吐量。然而到目前為止，探討的都是單一的算法而混合算法并沒有被廣泛應(yīng)用于FMS問題中。因此針對柔性制造系統(tǒng)中的機(jī)器裝載問題，提出了一種結(jié)合GA和SA的高效混合進(jìn)化啟發(fā)式算法，并進(jìn)行了驗(yàn)證。

1 研究背景

本文所考慮的柔性制造系統(tǒng)是由一些多功能的數(shù)控機(jī)床和其他能夠執(zhí)行多種操作的設(shè)施組成。制造系統(tǒng)中的作業(yè)工序是批量可用的，同時每道子工序在加工過程中可以以隨機(jī)順序進(jìn)行排列。當(dāng)我們已知批次大小、操作次數(shù)、加工時間和每個作業(yè)所需的刀具槽數(shù)，假設(shè)有一套工具和一套機(jī)器可以生產(chǎn)我們所需的各種各樣零件。同時假設(shè)加工時間和刀具槽隨著分配給不同機(jī)器的工件變化而變化，那么就會出現(xiàn)有時某個工具槽工件短缺的情況。對于工件操作來說，通常分為兩種：

1）必選操作-此操作只能在特定的機(jī)器上進(jìn)行。

2）可選操作-此操作可以在具有相同或相似加工時間和刀具槽的多臺機(jī)器上執(zhí)行。

因此工序中的可選操作使得整個工作流程具有彈性的可能。本文所考慮的FMS具有四個多功能機(jī)器，每個機(jī)器具有480min的可用處理時間（8HRS＝1個移位）和5個工具槽。本文中符號的含義如表1所示。

表1 符號含義圖

表1（續(xù)）

本文討論的FMS問題列于表2中。機(jī)器裝載問題可以定義為：給定要生產(chǎn)的一組作業(yè)、給定在一組機(jī)器上處理作業(yè)所需的一組工具，用以上的資源分配簡化整個系統(tǒng)工作流程[1]。

表2 示例FMS問題

機(jī)器裝載問題通常被表述為二元目標(biāo)問題，問題包含兩個主要目標(biāo)函數(shù)，即系統(tǒng)不平衡性最小化和系統(tǒng)吞吐量最大化，并且細(xì)節(jié)如下[2]：

最小化系統(tǒng)不平衡性：即使得分配所有可行的作業(yè)后機(jī)器上剩余的空閑時間的總和，而系統(tǒng)中機(jī)的剩余時間總和必須是0（即實(shí)現(xiàn)系統(tǒng)中所有機(jī)器100%利用率）或是一個可以接受的數(shù)值。

最大化吞吐量：即使得計(jì)劃范圍內(nèi)所有選定作業(yè)的批次大小的總和最大。

即：

因此組合目標(biāo)函數(shù)（COF）為：

文獻(xiàn)[1～11]使用十個數(shù)據(jù)集來測試他們的方法的性能。而本文也使用相同的數(shù)據(jù)集來評估所提出的算法的性能。

2 混合進(jìn)化啟發(fā)式算法

在其他文獻(xiàn)中，研究人員提出了兩種啟發(fā)式方法來選擇某一操作是否可以在幾臺機(jī)器上進(jìn)行。Swarnkar和Tiwari根據(jù)機(jī)器中最高可用時間選擇機(jī)器[1]，MukopaDyayet等人實(shí)現(xiàn)了在可選操作的情況下根據(jù)操作所占的重要性比率選擇機(jī)器的方法[2]。本章主要描述了GASA的混合算法在解決機(jī)器裝載問題中的應(yīng)用，同時討論了有關(guān)混合GASA算法實(shí)現(xiàn)過程中的各種設(shè)計(jì)問題。本文所提出的模型的結(jié)構(gòu)如圖1所示，并在本章中討論了模型中各種模塊的實(shí)現(xiàn)。為了通過實(shí)例說明算法流程，本文采用的數(shù)據(jù)集如表2所示。

圖1 混合進(jìn)化啟發(fā)式算法GASA流程圖

2.1 初始化

首先采用最短處理時間（SPT）規(guī)則生成初始序列，SPT規(guī)則所需的每個作業(yè)的總處理時間，已在表3中給出[12]。隨后以從最低處理時間到最高處理時間的升序排列作業(yè)。以表3給出的作業(yè)序列為例，生成的排列后的初始序列如圖2所示。而生成初始序列后，采用循環(huán)移位法生成其他n-1個序列，其中n=N。由于程序中的種群大小固定為10，而之前的操作只能產(chǎn)生6個種群，因此剩余的染色體是隨機(jī)產(chǎn)生的，而生成后每一個隨機(jī)產(chǎn)生的染色體用現(xiàn)有染色體檢查，避免染色體重復(fù)。

表3 作業(yè)所需的加工時間

2.2 適應(yīng)度評價(jià)

通過目標(biāo)函數(shù)作為約束條件確定染色體的適應(yīng)值。目標(biāo)函數(shù)的具體公式在上文已給出。

2.3 啟發(fā)式機(jī)器選擇

例如，考慮序列S=[6 1 5 2 3 4]。表4給出了每臺機(jī)器上可用的加工時間和刀具槽。

表4 四臺機(jī)器的加工時間和刀具槽

以第6號作業(yè)為例進(jìn)行計(jì)算：

由表1可知，作業(yè)中的子工序?yàn)?1，必要操作數(shù)為1，可選操作數(shù)為0。對于必要操作1，可用的機(jī)器編號為2，T2＝480-21×11＝249，t2＝5-3＝2。由于RTS1＝5＞0，RTS2＝2＞0，RTS3＝5＞0，RTS4＝5＞0；同時RTM1+RTM2+RTM3+RTM4＝480＋249＋480＋480＝480＝1689>=0。表示第6號作業(yè)選擇完畢。而在分配第6號作業(yè)之后可用的處理時間和工具槽在如表5所示。

表5 選擇作業(yè)6后四臺機(jī)器的加工時間和刀具槽

隨后我們對第1號作業(yè)進(jìn)行計(jì)算：

作業(yè)中的子工序?yàn)?5，必要操作數(shù)為0，可選操作數(shù)為1。對于可選操作1，可用機(jī)器是4和2。在可選操作的情況下，采用啟發(fā)式方法選擇可用機(jī)器，啟發(fā)式方法的工作方式在圖3中給出。根據(jù)計(jì)算選取比值最高的機(jī)器，由圖3可知選擇機(jī)器4來執(zhí)行可選操作。T4＝480-10×15＝330，t4＝5-2＝3。由于RTS1＝5＞0，RTS2＝2＞0，RTS3＝5＞0，RTS4＝3＞0，并且RTM1+RTM2+RTM3+RTM4＝480＋249＋480＋330＝1539＞=0。表示第1號作業(yè)選擇完畢。而在分配第1號作業(yè)之后可用的處理時間和工具槽在如表6所示。

表6 選擇作業(yè)6后四臺機(jī)器的加工時間和刀具槽

圖3 作業(yè)1選擇示意圖

按照同樣步驟完成對所有工序的機(jī)器選擇和作業(yè)分配，最終機(jī)器上可用的加工時間和刀具槽如表7所示。此時已分配的工作序列AS=[6 1 5 2 3]，未分配的工作UAS=[4]。

表7 分配作業(yè)完畢后加工時間和刀具槽

此時目標(biāo)函數(shù)值的計(jì)算過程如下：

系統(tǒng)不平衡性等于所有機(jī)器分配后所有機(jī)器的過度使用或未充分利用時間的總和。從表7中，機(jī)器1和機(jī)器3被過度利用，機(jī)器2和機(jī)器4未被充分利用。因此，SU＝（240 +249302＋330）＝37。

吞吐量等于產(chǎn)生的工作單位。分配的作業(yè)AS＝[6 1 5 2 3]。因此，TH＝11＋15＋16＋10＋12＝64。

目標(biāo)函數(shù)等于適應(yīng)度值為（TH/所有作業(yè)的總和）+（1-(SU/工廠中所有機(jī)器的可用時間總和））=（64/73）+（1-（37/1920））=0.8767+0.9807=1.8574。

2.4 模擬退火算法

模擬退火算法的本質(zhì)為接受劣解以清除局部最優(yōu)通道并接近全局最優(yōu)，模擬退火算法在本流程中的主要功能為：將染色體群體中提取的最優(yōu)和最差序列通過模擬退火算法選擇出來[13]。模擬退火算法中，初始溫度T在過程開始時設(shè)定為10。溫度T是一個參數(shù)，其作用類似于迭代每次減少0.9。溫度T每獲得一個新值，進(jìn)行一次迭代。對于每次迭代，染色體S將會生成一個鄰域（S'）。將解S'與當(dāng)前最優(yōu)解S進(jìn)行比較，如果S'的目標(biāo)函數(shù)值優(yōu)于S，則自動替換S'為當(dāng)前最優(yōu)解。否則，按照接受概率來接受S'。因此，當(dāng)溫度T較高時，較低的解決方案被接受的可能性較高。通常凍結(jié)溫度可以根據(jù)程序所需的迭代次數(shù)來確定，本實(shí)驗(yàn)設(shè)直到溫度低于0.7時迭代中止。一旦溫度降到凍結(jié)溫度以下，將染色體S作為當(dāng)前最佳染色體返回到種群。這個過程同時作用于效果最優(yōu)的和效果最差的染色體上，采用循環(huán)移位攝動法生成鄰域，且其接受概率為e(delta/T)。

2.5 選擇、交叉與變異

選擇操作將決定進(jìn)化過程的流程，為遺傳算法提供了驅(qū)動力。在過去的二十年中，研究者們已經(jīng)提出了許多選擇方法。經(jīng)過驗(yàn)證和比較之后本文提出的GASA采用簡單的輪盤賭選擇方法。本研究根據(jù)文獻(xiàn)[12]采用了四個不同的交叉算子：循環(huán)交叉，部分映射交叉，線性順序交叉和邊緣重組交叉，交叉概率為0.7。GASA從這四個交叉算子中隨機(jī)選擇。此外文獻(xiàn)[14]也提供了三個變異算子：相互交換突變、插入突變和反轉(zhuǎn)突變，突變概率為0.3。GASA從這三個變異算子中隨機(jī)選擇。

3 結(jié)果與討論

經(jīng)過實(shí)驗(yàn)和比較，GASA的最優(yōu)控制參數(shù)如表8所示。同時本文采用文獻(xiàn)[1～11]中的數(shù)據(jù)集對所提出的GASA性能進(jìn)行評價(jià)，并與文獻(xiàn)中采用的啟發(fā)式算法進(jìn)行比較，結(jié)果如表9所示。

從表9可以看出，本文提出的GASA對于對于被測試的10個數(shù)據(jù)集中的7個能夠達(dá)到最佳解，表9最后一行中的平均COF（1.7401）表示本文提出的其優(yōu)于考慮用于評估的其他啟發(fā)式的性能。

表8 GASA中各項(xiàng)參數(shù)

表9 GASA算法與文獻(xiàn)中算法的比較

表9（續(xù)）