李強(qiáng)LI Qiang

（沈陽(yáng)大學(xué)機(jī)械工程學(xué)院，沈陽(yáng)110041）

0 引言

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

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

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

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

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

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

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

工件的工序加工時(shí)間見(jiàn)公式（1）：

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

零件在機(jī)器之間轉(zhuǎn)換所需的時(shí)間TT 見(jiàn)公式（2）：

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

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

本文的優(yōu)化目標(biāo)最小化加工時(shí)間見(jiàn)公式（4）：

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

2.1 編碼與解碼

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

圖1 零件對(duì)應(yīng)編碼方案

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

2.2 種群初始化

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

2.3 嗅覺(jué)搜索與視覺(jué)搜索

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

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

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

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

④機(jī)器變異操作：隨機(jī)從候選機(jī)器編碼串中選擇一個(gè)位置，在其可選的設(shè)備集合中選擇另一臺(tái)加工設(shè)備。

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

2.4 全面協(xié)作機(jī)制

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

2.4.1 特征序列交叉操作

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

圖2 特征序列交叉操作

2.4.2 工藝序列交叉操作

隨機(jī)選取兩個(gè)交叉點(diǎn)將工藝序列1 與工藝序列2 分割成三部分，直接將工藝序列1 的兩個(gè)交叉點(diǎn)之間的加工工藝序列復(fù)制到子代新加工序列的相應(yīng)位置；然后，將工藝序列2 的兩個(gè)交叉點(diǎn)兩頭的工藝序列復(fù)制到新加工工藝序列對(duì)應(yīng)的位置上，通過(guò)以上的交叉操作可以得到一個(gè)全新的子代加工工藝序列，具體操作如圖3 所示。

圖3 工藝序列交叉操作

2.4.3 機(jī)器序列交叉操作

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

圖4 機(jī)器序列交叉操作

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

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

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

3 數(shù)值實(shí)例測(cè)試

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

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

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

4 結(jié)論

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