戰(zhàn)后武器裝備車間調(diào)度遺傳算法的參數(shù)優(yōu)化*

曾艾婧，劉永姜，孟小玲，溫海駿，邵延君

（中北大學(xué)，太原 030051）

0 引言

武器裝備對(duì)于戰(zhàn)爭(zhēng)來(lái)說(shuō)尤為重要，一個(gè)國(guó)家的軍事和社會(huì)發(fā)展水平均可以通過(guò)武器的發(fā)展和管理來(lái)反映［1］。而武器裝備使用一定期限后，就會(huì)造成一些零部件的嚴(yán)重?fù)p傷，導(dǎo)致武器裝備的性能指標(biāo)有所降低，許多裝備都將到壽或被替代，那么就需要對(duì)戰(zhàn)后武器裝備進(jìn)行回收再制造處理［2］。車間調(diào)度是對(duì)戰(zhàn)后武器裝備回收再制造的重要一步，對(duì)戰(zhàn)損的武器裝備進(jìn)行高效的車間調(diào)度不僅可以提高生產(chǎn)設(shè)備的利用率，而且可以大大縮短裝備的交貨期，甚至?xí)绊懙杰娛卵b備的發(fā)展和戰(zhàn)斗力的提高等重大軍事和經(jīng)濟(jì)問(wèn)題［3］。因此，研究戰(zhàn)后武器裝備車間調(diào)度問(wèn)題具有重要的現(xiàn)實(shí)意義。

GA 方法被認(rèn)為是解決JSP 問(wèn)題最有效的進(jìn)化算法之一，目前許多國(guó)內(nèi)外學(xué)者已對(duì)使用遺傳算法進(jìn)行車間調(diào)度有了一定的研究。M.Kamrul Hasan［4］等人在研究車間調(diào)度問(wèn)題時(shí)，對(duì)傳統(tǒng)的遺傳算法進(jìn)行改善，通過(guò)設(shè)置一些優(yōu)先規(guī)則，來(lái)減少更換裝備的時(shí)間間隙，提高了算法的性能。鞠錄巖［5-6］等人基于非支配排序遺傳算法，提出了一種改進(jìn)非劣前沿分級(jí)的方法，并采用了精英保留策略，該方法不但繼承了遺傳算法全局搜索能力還防止了提早陷入局部最優(yōu)。葉婉秋［7］等人針對(duì)不確定的生產(chǎn)環(huán)境，提出了遺傳算法與RL 結(jié)合的車間調(diào)度算法，該算法采用了自適應(yīng)交叉而獲得較優(yōu)的交叉率，使得算法性能有所提高。曹慶奎［8-9］等人提出一種模擬退火與遺傳算法相結(jié)合的算法來(lái)解決車間調(diào)度問(wèn)題，該算法利用遺傳算法收斂較快的優(yōu)點(diǎn)克服了模擬退火算法收斂較慢的問(wèn)題，進(jìn)而提高了算法的性能。在現(xiàn)有的文獻(xiàn)中，通過(guò)尋求遺傳算法最優(yōu)的參數(shù)組合，來(lái)改善戰(zhàn)后武器裝備車間調(diào)度的研究還不夠全面，需要進(jìn)一步的探討。

基于此，本文采用響應(yīng)面法（Response surface method，RSM）來(lái)尋求遺傳算法的最優(yōu)參數(shù)組合。選取遺傳算法中交叉率、變異率、個(gè)體數(shù)目、迭代次數(shù)這4 個(gè)關(guān)鍵參數(shù)，根據(jù)中心復(fù)合實(shí)驗(yàn)設(shè)計(jì)得到實(shí)驗(yàn)方案，利用MATLAB 仿真軟件對(duì)每種方案進(jìn)行仿真，得出每種方案下的最小完成工時(shí)，在此基礎(chǔ)上進(jìn)行響應(yīng)面分析，建立這4 個(gè)關(guān)鍵參數(shù)對(duì)遺傳算法車間調(diào)度的響應(yīng)函數(shù)，并考慮參數(shù)之間的交互作用對(duì)仿真結(jié)果的影響，以尋求使得調(diào)度達(dá)到最小完成工時(shí)的最優(yōu)參數(shù)組合。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

對(duì)戰(zhàn)損的武器裝備進(jìn)行再制造維修車間調(diào)度的問(wèn)題可描述為：n 臺(tái)戰(zhàn)后武器裝備需在m 臺(tái)機(jī)器上進(jìn)行再制造維修，每個(gè)裝備都不只有一道工序，各工序的加工順序是設(shè)定好的，同一工序能在幾臺(tái)不同的機(jī)器上加工且不同機(jī)器上的加工時(shí)間也不相同。通過(guò)給每個(gè)工序安排合適的加工機(jī)器，并確定每臺(tái)機(jī)器上對(duì)應(yīng)工序的加工順序，使得戰(zhàn)后武器裝備再制造維修時(shí)間最短。為了方便建立模型和求解，該問(wèn)題還應(yīng)滿足以下約束：1）每個(gè)回收裝備都擁有相同的優(yōu)先級(jí)；2）各裝備所有工序間的先后順序已知；3）同一裝備的待加工工序必須是在它前面的工序加工完后才能開始加工；4）每臺(tái)機(jī)器上同一時(shí)間有且只能加工一道工序；5）每道工序一旦開始加工就不能中途暫停；6）各機(jī)器上相鄰的兩個(gè)加工工序之間切換時(shí)間為零。

對(duì)該問(wèn)題進(jìn)行建模，建模所引入的符號(hào)如下：

i：裝備號(hào)，i=1，2，3，…，n

j：工序號(hào)，j=1，2，3，…，n

k：機(jī)器號(hào)，k=1，2，3，…，n

tik：裝備i 在機(jī)器k 上的加工時(shí)間

Cik：裝備i 在機(jī)器k 上的完工時(shí)間

本文采用的是6 臺(tái)武器裝備，每臺(tái)裝備6 道工序，將其安排在10 臺(tái)機(jī)器上進(jìn)行再制造維修的車間調(diào)度問(wèn)題。該車間調(diào)度問(wèn)題描述如表1、表2 所示。

1.2 模型建立

對(duì)于戰(zhàn)后武器裝備車間調(diào)度問(wèn)題的求解就是要獲取一種調(diào)度方法，使得對(duì)其再制造維修的總作業(yè)時(shí)間最短。戰(zhàn)后武器裝備再制造車間調(diào)度的模型如下：

表1 加工工序可選機(jī)器

表2 工序加工時(shí)間

模型中式（1）表示把調(diào)度的總作業(yè)時(shí)間最短作為優(yōu)化目標(biāo)；式（2）為同一裝備在機(jī)器上的加工順序的約束關(guān)系；式（3）表示同一機(jī)器上各個(gè)裝備加工順序的約束關(guān)系，A 為充分大的正數(shù)；式（4）表示裝備的完工時(shí)間為最后一臺(tái)機(jī)器上的完工時(shí)間；式（5）為非負(fù)約束；式（6）和式（7）為機(jī)器順序約束和裝備順序約束系數(shù)。

1.3 算法設(shè)計(jì)

1.3.1 染色體

1.3.2 適應(yīng)度函數(shù)

將全部回收裝備的總完成時(shí)間作為染色體的適應(yīng)度值，其函數(shù)為：

1.3.3 選擇操作

對(duì)染色體進(jìn)行選擇時(shí)是采用輪盤賭法，根據(jù)染色體的適應(yīng)度值進(jìn)行選擇，染色體被選中的概率是適應(yīng)度值的倒數(shù)。

1.3.4 交叉操作

基于兩層編碼進(jìn)行交叉操作時(shí)，只對(duì)染色體的前半部分進(jìn)行交叉。交叉后，由于工序發(fā)生了改變，所以要用交叉后缺少的工序來(lái)替換交叉后多余的工序，最后按交叉前工序所對(duì)應(yīng)的加工機(jī)器來(lái)調(diào)整后半部分的染色體。

1.3.5 變異操作

變異操作是將一個(gè)隨機(jī)選取的個(gè)體以一定的概率進(jìn)行變異，最后把變異前個(gè)體對(duì)于的加工機(jī)器序號(hào)對(duì)換，從而產(chǎn)生新的個(gè)體。

2 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

響應(yīng)面法（RSM）［11］是一種將統(tǒng)計(jì)和數(shù)學(xué)建模結(jié)合起來(lái)，進(jìn)行預(yù)測(cè)的優(yōu)化方法。響應(yīng)面法具有實(shí)驗(yàn)次數(shù)少、周期短，求得預(yù)測(cè)回歸模型精度高等優(yōu)勢(shì)［12］。它的基本思想是通過(guò)中心復(fù)合設(shè)計(jì)實(shí)驗(yàn)得到合理的實(shí)驗(yàn)方案，并通過(guò)仿真得到實(shí)驗(yàn)結(jié)果，根據(jù)響應(yīng)變量與響應(yīng)值之間的擬合關(guān)系，得出預(yù)測(cè)回歸模型，最后通過(guò)因素之間的交互作用來(lái)尋求最優(yōu)參數(shù)組合［13］。

本文通過(guò)對(duì)遺傳算法中的關(guān)鍵參數(shù)進(jìn)行優(yōu)化，從而得到更好的調(diào)度方法，使完工時(shí)間最小，即選擇的優(yōu)化參數(shù)有：A（交叉率）、B（變異率）、C（個(gè)體數(shù)目）、D（迭代次數(shù)），響應(yīng)值為M（最小完工時(shí)間）。為了可以得到理想的回歸模型，本文將采用四因素三水平的中心復(fù)合設(shè)計(jì)實(shí)驗(yàn)方案。根據(jù)文獻(xiàn)［14-15］，確定了4 個(gè)優(yōu)化參數(shù)的取值范圍，表3 為遺傳算法關(guān)鍵參數(shù)水平編碼表。

表3 遺傳算法關(guān)鍵參數(shù)水平編碼表

依據(jù)中心復(fù)合實(shí)驗(yàn)設(shè)計(jì)原理，當(dāng)選取4 個(gè)優(yōu)化參數(shù)時(shí)，需要進(jìn)行30 組實(shí)驗(yàn)。所有實(shí)驗(yàn)方案均通過(guò)MATLAB 進(jìn)行戰(zhàn)后武器裝備車間調(diào)度模擬，將30組最小完工時(shí)間作為實(shí)驗(yàn)結(jié)果。下頁(yè)表4 為具體的實(shí)驗(yàn)方案與實(shí)驗(yàn)結(jié)果，其中將每組參數(shù)進(jìn)行MATLAB 仿真時(shí)，每次仿真工序的排列順序并不完全相同，所以本文提到的最小完工時(shí)間實(shí)則是將每組參數(shù)各仿真10 次后，所求得的平均最小完工時(shí)間。

3 實(shí)驗(yàn)結(jié)果分析與優(yōu)化

3.1 響應(yīng)預(yù)測(cè)模型的建立及顯著性分析

根據(jù)上述實(shí)驗(yàn)結(jié)果，借助Design-Expert 數(shù)據(jù)分析軟件對(duì)這幾個(gè)關(guān)鍵因素進(jìn)行回歸擬合分析，并剔除不顯著的變量，建立的最小完工時(shí)間（W）回歸模型如下：

為評(píng)價(jià)模型的擬合程度，采用方差分析進(jìn)行分析，方差表中的P 值為顯著性水平，用來(lái)說(shuō)明該實(shí)驗(yàn)因素對(duì)優(yōu)化目標(biāo)的影響水平。對(duì)上式進(jìn)行方差分析，分析結(jié)果見表5。

從表5 看出，整體模型的F 值為10.09，P＜0.000 1，表明該模型有較高的擬合度。模型的失擬項(xiàng)反應(yīng)了模型預(yù)測(cè)值與實(shí)驗(yàn)測(cè)量值不擬合的概率，該模型失擬項(xiàng)P=0.187 7＞0.05，說(shuō)明失擬項(xiàng)不顯著，表明方程擬合良好。圖1 為W 模型的殘差正態(tài)概率圖，由于每一個(gè)點(diǎn)都遵循一個(gè)直線模式，沒有違規(guī)跡象，這意味著實(shí)際值較高程度地符合了預(yù)測(cè)值，進(jìn)一步說(shuō)明了該回歸模型具有較高的可行性。

圖1 W 殘差正態(tài)概率圖

另一方面，根據(jù)表3 可知，在該模型中，B（變異率）、C（個(gè)體數(shù)目）、D（迭代次數(shù)）對(duì)最小完成工時(shí)影響特別顯著；AC、AD、BD 對(duì)最小完成工時(shí)影響較為顯著；A（交叉率）、AB、BC、CD（P＞0.1）對(duì)最小完成工時(shí)不顯著。同時(shí)，該模型中各影響因素的均方值反映了其對(duì)響應(yīng)值得影響程度。均方越大，對(duì)響應(yīng)值的影響越大［16］，則由表5 可得，影響最小完成工時(shí)（W）的4 個(gè)關(guān)鍵因素的主次順序?yàn)椋築＞D＞C＞A。

3.2 參數(shù)的交互作用分析

通過(guò)對(duì)回歸預(yù)測(cè)模型進(jìn)行方程分析，得出不同因素對(duì)響應(yīng)值的影響程度，而響應(yīng)面圖能反應(yīng)不同因素之間的交互作用?；陬A(yù)測(cè)模型，得出具有顯著性交互作用項(xiàng)AC、AD、BD，因此，對(duì)這3 個(gè)一級(jí)交互作用進(jìn)行具體分析。

圖2 交叉率與迭代次數(shù)交互作用響應(yīng)面圖

圖2 為變異率與個(gè)體數(shù)目處于零水平時(shí)，交叉率與迭代次數(shù)交互作用響應(yīng)面圖。由圖2 可得，當(dāng)?shù)螖?shù)達(dá)到50 次時(shí)，交叉率從0.4 增加到0.99，最小完工時(shí)間縮短幅度最大為3 min 左右；當(dāng)變異率為0.4 時(shí)，迭代次數(shù)從50 次增加到200 次，最小完工時(shí)間縮短幅度最大為6 左右，可見這兩個(gè)因素對(duì)最小完工時(shí)間的影響并不同步，迭代次數(shù)的影響更為顯著，由于迭代次數(shù)的增加，最小完工時(shí)間明顯縮短，當(dāng)?shù)螖?shù)達(dá)到125 次時(shí)，尋找到了最優(yōu)解，算法也已經(jīng)收斂，而當(dāng)?shù)螖?shù)處于125～200次時(shí)，曲面趨于平滑，說(shuō)明迭代次數(shù)的改變對(duì)最小完工時(shí)間的影響很小。

表4 實(shí)驗(yàn)方案設(shè)計(jì)與結(jié)

表5 最短加工時(shí)間回歸模型方差分析

圖3 為變異率與迭代次數(shù)處于零水平時(shí)，交叉率與個(gè)體數(shù)目交互作用響應(yīng)面圖。圖3 直觀地給出了最小完工時(shí)間隨交叉率和個(gè)體數(shù)目變化的規(guī)律，由圖3 可看出，隨著個(gè)體數(shù)目的增加，最小完工時(shí)間的變化幅度大于隨交叉率變化的變化幅度，因此，個(gè)體數(shù)目的影響更為顯著。個(gè)體數(shù)目影響顯著是因?yàn)殡S個(gè)體數(shù)目的不斷增大，算法搜索到最優(yōu)值的概率也會(huì)增大，即全局搜索能力增強(qiáng)，而且，在對(duì)最優(yōu)解進(jìn)行搜索時(shí)，最優(yōu)解可以在較少的代數(shù)中被找到，那么尋找到最小加工時(shí)間也會(huì)縮短。

圖3 交叉率與個(gè)體數(shù)目交互作用響應(yīng)圖

圖4 為交叉率與迭代次數(shù)處于零水平時(shí)，變異率與個(gè)體數(shù)目交互作用響應(yīng)圖。由圖4 可清晰地看出，當(dāng)變異率為0.1 時(shí)，個(gè)體數(shù)目從40 增大到100，最小完工時(shí)間縮短幅度最大為2 min 左右；當(dāng)個(gè)體數(shù)目為40 時(shí)，變異率從0.000 1 增加到0.1，最小完工時(shí)間縮短幅度最大為4 左右，可見變異率為主要影響因素。最小完工時(shí)間隨變異率的增大而縮短，這是因?yàn)樽儺惵瘦^小時(shí)新個(gè)體的出現(xiàn)少，這就很難尋找到最小完工時(shí)間，當(dāng)變異率到達(dá)0.1 左右時(shí)，得到了最小完工時(shí)間。

圖4 變異率與個(gè)體數(shù)目交互作用響應(yīng)圖

3.3 最優(yōu)參數(shù)模擬驗(yàn)證

采用Design-Expert 軟件中的優(yōu)化功能Numer ical 對(duì)遺傳算法車間調(diào)度的關(guān)鍵參數(shù)進(jìn)行優(yōu)化，設(shè)計(jì)優(yōu)化條件為調(diào)度完工時(shí)間最小。當(dāng)算法的性能達(dá)到最好，即調(diào)度完工時(shí)間最小時(shí)，各關(guān)鍵參數(shù)的取值為：交叉率（A）為0.99，變異率（B）為0.1，迭代次數(shù)（C）為131 次，個(gè)體數(shù)目（D）為77 個(gè)，此時(shí)的最小完工時(shí)間W=43.881 9 min。將優(yōu)化結(jié)果進(jìn)行模擬仿真，得到的最短完工時(shí)間為45 min，相對(duì)誤差為2.5%，說(shuō)明該回歸模型的預(yù)測(cè)精度是較高的，即采用響應(yīng)面法對(duì)遺傳算法車間調(diào)度進(jìn)行優(yōu)化分析是可行的，具有實(shí)用價(jià)值。

將優(yōu)化前后的結(jié)果進(jìn)行對(duì)比可得：運(yùn)用響應(yīng)面法對(duì)遺傳算法關(guān)鍵參數(shù)進(jìn)行優(yōu)化后，戰(zhàn)后武器裝備調(diào)度的最小完工時(shí)間明顯縮短。表6 為算法優(yōu)化前后性能的對(duì)比，由表6 可以看出，優(yōu)化后車間調(diào)度的效率比優(yōu)化前提高了13.46 %。圖5 與圖6 分別為優(yōu)化前后的算法迭代過(guò)程圖與加工順序甘特圖。

表6 算法優(yōu)化前后對(duì)比

圖5 優(yōu)化前算法迭代過(guò)程圖與加工順序甘特圖

圖6 優(yōu)化后算法迭代過(guò)程圖與加工順序甘特圖

4 結(jié)論

本文針對(duì)戰(zhàn)后武器裝備再制造遺傳算法車間調(diào)度基于響應(yīng)面分析法對(duì)交叉率、變異率、個(gè)體數(shù)目、迭代次數(shù)4 個(gè)關(guān)鍵參數(shù)進(jìn)行優(yōu)化研究，并分析了它們之間的交互作用對(duì)最小完工時(shí)間（W）的影響，最后建立相應(yīng)的回歸預(yù)測(cè)模型。主要結(jié)論如下：

1）通過(guò)方差分析以及響應(yīng)面圖得出了在遺傳算法車間調(diào)度中，對(duì)最小完工時(shí)間的影響顯著性從大到小依次為變異率、個(gè)體數(shù)目、迭代次數(shù)、交叉率。而且優(yōu)化變量之間存在著交互作用，交叉率與迭代次數(shù)的交互作用，交叉率與個(gè)體數(shù)目的交互作用以及變異率與個(gè)體數(shù)目的交互作用的影響比較顯著。

2）基于響應(yīng)面分析獲得考慮交互作用下的最優(yōu)參數(shù)組合為：交叉率=0.99，變異率=0.1，個(gè)體數(shù)目=77 個(gè)，迭代次數(shù)=131 次。

3）本文以戰(zhàn)后武器裝備為背景，對(duì)戰(zhàn)后損傷的武器裝備進(jìn)行遺傳算法車間調(diào)度，并利用響應(yīng)面分析法對(duì)遺傳算法關(guān)鍵參數(shù)進(jìn)行優(yōu)化，最終得到最優(yōu)參數(shù)組合，此研究對(duì)于更多戰(zhàn)后武器裝備車間調(diào)度優(yōu)化具有參考作用。