基于果蠅優(yōu)化算法的柔性工藝規(guī)劃問題研究

李強LI Qiang

（沈陽大學機械工程學院，沈陽110041）

0 引言

工藝規(guī)劃作為制造系統(tǒng)中的重要環(huán)節(jié)，是一個系統(tǒng)性的決策過程。由于傳統(tǒng)的制造系統(tǒng)向著智能制造系統(tǒng)的轉變，柔性工藝規(guī)劃已經(jīng)成為了工藝規(guī)劃研究的重要內(nèi)容。在智能制造系統(tǒng)中，帶有多種柔性的工藝規(guī)劃研究可以大大的提高車間的柔性，并且為車間提供更加靈活多樣的加工方案，在企業(yè)的加工生產(chǎn)中起著非常重要的作用。

隨著計算機技術的發(fā)展，智能優(yōu)化算法也進入了一個高速發(fā)展的時期，越來越多的研究人員通過各種算法對工藝規(guī)劃問題進行求解。例如蟻獅算法[1]、蝙蝠算法[2]、粒子群算法[3]等。果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm,FOA）是由臺灣學者提出的一種群智能算法[4]。其與原有的進化算法相比，具有參數(shù)簡單、原理易懂、搜索速度快等優(yōu)點。在短短幾年時間，就被成功地應用于多維背包問題[5]、混合流水車間調度問題[6]等諸多領域。

本文將采用果蠅優(yōu)化算法對柔性工藝規(guī)劃問題進行解決。首先，在基本FOA 算法的基礎上，根據(jù)柔性工藝規(guī)劃問題的特點，設計特殊的編碼解碼方式，以及適用于該問題的嗅覺搜索。其次，引入全局協(xié)作機制，增強算法的搜索能力。最后，通過實例對所提出算法進行測試，驗證了FOA 算法的有效性。

1 柔性工藝規(guī)劃模型

柔性工藝規(guī)劃問題可以描述為：每個即將開始生產(chǎn)的工件都有著一種或幾種加工特征，任何一個加工特征都含有一個或者多個可以挑選的加工工藝，所有加工工藝又有一個或者多個加工工序，每個加工工序又可被多臺機器進行加工，并且零件的不同特征之間存在著先后順序的約束。該問題的研究目標就是從加工工件的多條可選工藝路線中，選出一條合理可行并且使得某種優(yōu)化指標最優(yōu)的工藝路線。關于柔性工藝規(guī)劃問題，以表1 所給出的零件工藝信息為例。該零件共有6 個加工特征，其中特征2 由兩條可以相互替換的加工工藝進行加工。由5 臺可選加工設備對零件的不同工序進行加工。同時，各個加工特征在加工時不能違反所存在的次序約束。

表1 某零件加工工藝信息表

本文的數(shù)學模型如下：

工件的工序加工時間見公式（1）：

其中n 表示的是待加工工件工藝路線中所包含的工藝數(shù)量，PTi表示的是待加工工件第i 道工藝所需要的加工時間。

零件在機器之間轉換所需的時間TT 見公式（2）：

其中TTMi，Mi+1表示的是零件在選定的工藝路線中從加工第i 道工序的機器轉換到加工第i+1 道工序的機器所需時間。

公式（3）為判斷函數(shù)，當零件的工藝路線中相鄰的兩道工序在不更換機器生產(chǎn)的情況下，公式（3）取值為0；當相鄰兩道工序在不同的機器上進行加工時，式（3）取值為1。

本文的優(yōu)化目標最小化加工時間見公式（4）：

2 果蠅優(yōu)化算法求解柔性工藝規(guī)劃問題

2.1 編碼與解碼

由于基本的果蠅優(yōu)化算法通常被用于解決連續(xù)優(yōu)化問題，所以基本的果蠅優(yōu)化算法是無法直接求解離散型的柔性工藝規(guī)劃問題。需要根據(jù)工藝規(guī)劃的相關特征設計與之相符合的編碼與解碼過程才能對柔性工藝規(guī)劃問題進行求解。在工藝規(guī)劃中，必須對工序的順序進行排序，并為每道工序選擇合適的機器。種群中的每只果蠅都表示工藝規(guī)劃的一個解決方案，并且每條工藝路線都由三個部分組成。第一部分是特征串，第二部分是候選工藝串，第三部分是候選機器串。三個部分是相對獨立的，它們共同確定零件的加工工藝路線。圖1 為表1 零件的一個可行編碼方案，該零件具有6 個加工特征，因此特征串和候選工藝串的長度為6，候選機器串則等于總工序的數(shù)目，在工件中一共有9 道工序，因此候選機器串的長度為9。

圖1 零件對應編碼方案

由圖1 中的編碼信息可知該工件的各加工特征順序為F1-F5-F3-F4-F2-F6；工件具體的加工工序順序為O1-O8-O6-O7-O4-O5-O9；結合設備的選擇和加工工序的信息解碼后可以得到該工件的工藝路線為：O1（M4）-O8（M5）-O6（M4）-O7（M1）-O4（M3）-O5（M2）-O9（M2）。

2.2 種群初始化

果蠅種群代表了柔性工藝規(guī)劃問題的解空間，而在種群中的每個果蠅代表著一條工藝路線。種群中有NS 個果蠅，每一只果蠅都由三個向量表示。由于種群的每個個體都由三段編碼序列組成且代表著一條可行的工藝路線，因此需要分別對這三個部分進行初始化。假設某零件包含m個加工特征，特征串是采用隨機的方法生成一個1 到m的編碼序列。由于零件的加工特征之間存在著次序關系，隨機初始化的方法可能會產(chǎn)生不符合次序約束的特征編碼序列。因此，本文通過文獻[7]的約束調整方法對產(chǎn)生的不合理特征序列進行重新排序。對于候選工序串，如果該零件的第n 個加工特征的可選工藝數(shù)量為m，那么在1 到m 的整數(shù)中隨機選取一個整數(shù)，填入該序列的第n 個位置；同理，對于候選機器編碼串，采用與生成候選工藝串相同的方法對候選機器序列進行生成。

2.3 嗅覺搜索與視覺搜索

在規(guī)范的果蠅算法中，嗅覺搜索是果蠅算法的核心搜索過程，果蠅種群采用鄰域搜索的方法進行尋優(yōu)。為了解決本文所研究的柔性工藝規(guī)劃問題，本文使用了三種十分有效的鄰域搜索方式：交換、插入、變異，其中變異操作又包含工序變異以及設備變異，交換和插入均作用于特征序列，因此在產(chǎn)生鄰域時隨機選擇其中一種對特征序列進行改變，這三種操作可以讓每一個果蠅個體生成多個鄰域解。并且果蠅會圍繞中心位置采用隨機的搜索方向以及搜索距離進行尋優(yōu)，這種隨機的方式可以大大提升算法的全局尋優(yōu)能力，增加解的多樣性，相關具體操作如下所示：

①交換操作：隨機從特征串編碼中選擇兩個不同的位置，并將這兩個位置上的數(shù)值進行交換，對出現(xiàn)的不合理的編碼使用約束調整方法進行調整。

②插入操作：隨機從特征串編碼中隨機選擇一個位置，并將其插入特征串中的另一個位置，對于出現(xiàn)的不符合特征先后次序約束的編碼，使用約束調整方法進行調整。

③工序變異操作：隨機從候選工序編碼串中選擇一個位置，在其可選加工資源中，選擇另外一種加工資源。

④機器變異操作：隨機從候選機器編碼串中選擇一個位置，在其可選的設備集合中選擇另一臺加工設備。

在嗅覺搜索階段，種群中的每個個體都會生成S 個鄰域個體。在基于局部的視覺搜索中，這個階段需要在S+1個方案種挑選出最佳的一個解決方案。對于嗅覺搜索中新生成的果蠅進行評價，然后采用貪婪的選擇策略對每只父代果蠅進行更新。

2.4 全面協(xié)作機制

本文參考果蠅種群在覓食時的相互協(xié)作行為，在基本的果蠅優(yōu)化算法中加入了全局協(xié)作機制對算法的尋優(yōu)能力進行提高。根據(jù)柔性工藝規(guī)劃問題的特點，本文采用兩點交叉的方法對果蠅種群進行協(xié)作具體操作如下所示。

2.4.1 特征序列交叉操作

隨機取兩個交叉點將加工特征序列1 和加工特征序列2 分割成三部分，直接將加工特征序列1 中兩個交叉點之間的特征數(shù)復制到新的加工特征序列的相應位置。在加工特征2 中，將已經(jīng)從加工特征序列1 中復制到新的加工序列中的特征進行刪除，然后將加工特征2 中其余的編碼數(shù)按先后的順序依次復制到新加工特征序列中的空白處，由此一條新的加工特征序列就被成功生成，具體操作如圖2 所示。

圖2 特征序列交叉操作

2.4.2 工藝序列交叉操作

隨機選取兩個交叉點將工藝序列1 與工藝序列2 分割成三部分，直接將工藝序列1 的兩個交叉點之間的加工工藝序列復制到子代新加工序列的相應位置；然后，將工藝序列2 的兩個交叉點兩頭的工藝序列復制到新加工工藝序列對應的位置上，通過以上的交叉操作可以得到一個全新的子代加工工藝序列，具體操作如圖3 所示。

圖3 工藝序列交叉操作

2.4.3 機器序列交叉操作

此部分操作與候選工藝串的交叉操作類似，此處就不多贅述，如圖4 所示。

圖4 機器序列交叉操作

2.5 FOA 求解柔性工藝規(guī)劃問題總流程

基于以上分析，求解柔性工藝規(guī)劃問題的改進果蠅優(yōu)化算法的使用流程如圖5 所示。

圖5 改進果蠅優(yōu)化算法總流程

3 數(shù)值實例測試

本文將通過Matlab 平臺對該過程進行實現(xiàn)，本文的測試實例中的零件1 包含14 個加工特征20 道可選加工工序，具體加工工藝信息以及工件在不同機器之間的運輸時間見文獻[3]，優(yōu)化目標為加工時間最小。果蠅優(yōu)化算法參數(shù)設置如下：NP（初始化果蠅總數(shù)）=50；S（鄰域解個數(shù)）=4；Maxgen（最大迭代次數(shù)）=200。由于需要與前人的研究結果進行對比，因此，參照文獻[3]將果蠅優(yōu)化算法程序運行20 次，并將程序運行20 次的實驗結果進行統(tǒng)計，分別記錄仿真結果中得到的最優(yōu)值、平均值以及最優(yōu)值平均收斂代數(shù)。最后，通過將FOA 算法求得的目標優(yōu)化值與文獻[3]中的三種算法所求得的優(yōu)化結果進行比較，實例的優(yōu)化結果對比統(tǒng)計后如表2 所示。

表2 零件1 的工藝路線優(yōu)化結果對比

由表2 的對比結果可見，F(xiàn)OA 算法在20 次的運行中，每一次都可以搜尋到最優(yōu)解。對四種方法的最優(yōu)值進行統(tǒng)計分析，F(xiàn)OA 所求的平均值要小于其他三種算法所求的平均值，與最優(yōu)值相同，也就是說FOA 每一次都可以搜索到最優(yōu)解。因此，F(xiàn)OA 在解決柔性工藝規(guī)劃問題上體現(xiàn)出了更好的穩(wěn)定性。而且在20 次的FOA 算法運行中，F(xiàn)OA算法每次找到最優(yōu)值所需要的收斂代數(shù)的平均值也較SA、GA 及MPSO 要少很多，具有更好的求解效率。

4 結論

本文針對工藝規(guī)劃問題中的多種柔性，使用了三段式的編碼結構。并且根據(jù)該問題的特點，對FOA 算法的嗅覺搜索階段進行了改進，同時采用交叉操作進行種群間的協(xié)作，增強了FOA 算法的尋優(yōu)能力。最后，通過數(shù)值實例對所提出的算法進行測試，實驗結果表明，F(xiàn)OA 算法具有更好的求解效率以及穩(wěn)定性。