楊 佩, 亓祥波, 原宇軒, 趙雨爽

(沈陽大學(xué) 機(jī)械工程學(xué)院, 沈陽 110044)

1 引言

置換流水車間調(diào)度問題(permutation flow-shop scheduling problem, PFSP)是典型的生產(chǎn)調(diào)度問題, 當(dāng)其規(guī)模大于3時已被證明是NP難問題. 群智能算法是一種新興的元啟發(fā)式計算技術(shù), 在求解此類復(fù)雜優(yōu)化問題上表現(xiàn)出了很大優(yōu)勢, 已成為越來越多研究者的關(guān)注焦點(diǎn).

群智能算法從問題的很多個解開始, 不斷改進(jìn)直到滿足終止條件為止. 由于同時從多個解出發(fā)進(jìn)行尋優(yōu), 如果某個解陷入局部最優(yōu)點(diǎn), 其他解可能會跳出局部最優(yōu)點(diǎn), 因此, 該類算法在優(yōu)化問題的搜索空間中具有很強(qiáng)的探索能力. 目前, 已有的群智能算法按照算法的基本原理大多數(shù)屬于模擬群居動物行為的算法, 如粒子群算法(particle swarm optimization, PSO)[1]、人工蜜蜂群算法(artificial bee colony, ABC)[2]、布谷鳥搜索算法(cuckoo search, CS)[3]等.

PSO 算法模擬了魚群、鳥群覓食時候有組織的群體行為. PSO算法的基本思想是在搜索空間中隨機(jī)初始化一個由沒有體積沒有質(zhì)量的粒子組成的種群, 將種群中的每個粒子視為優(yōu)化問題的一個可行解, 解的好壞由適應(yīng)度函數(shù)確定. 每個粒子在解空間中運(yùn)動, 并由一個速度向量決定其運(yùn)動的方向和位移. 算法中的每個粒子依賴本身的飛行經(jīng)驗并借鑒種群中其他粒子的飛行經(jīng)驗, 經(jīng)多次迭代收斂到最優(yōu)解. 在每一次迭代中, 本身的飛行經(jīng)驗是粒子本身迄今找到的最優(yōu)解, 其他粒子的飛行經(jīng)驗是整個種群迄今找到的最優(yōu)解. 作為一種經(jīng)典的群智能算法, PSO在求解置換流水車間調(diào)度問題上得到了應(yīng)用[4–6].

人工蜂群算法是受到蜜蜂群體覓食行為的啟發(fā)而提出的一種群智能算法[2]. 在ABC中, 每個個體被分為3種類型: 雇傭蜂、跟隨蜂和偵查蜂. 其中, 雇傭蜂的數(shù)量與跟隨蜂的數(shù)量是一致的, 各占整個種群的一半. 每一個雇傭蜂對應(yīng)某一個蜜源, 即優(yōu)化問題的解,雇傭蜂將位置信息與適應(yīng)度信息分享給跟隨蜂. 跟隨蜂根據(jù)雇傭蜂提供的解的信息選擇跟隨某只蜜蜂繼續(xù)挖掘高質(zhì)量的解, 一般采用輪盤賭的方式選擇跟隨哪一只雇傭蜂. 如果某個解一直沒有得到改善, 則它就變成一只偵查蜂, 在算法中用隨機(jī)生成一個新解來表示一只偵查蜂. 人工蜂群算法思想簡單, 參數(shù)少, 優(yōu)化效果良好, 在數(shù)值優(yōu)化和工程優(yōu)化中得到了廣泛的應(yīng)用[7,8].

CS是文獻(xiàn)[3]中提出的一種基于布谷鳥的巢寄生性和萊維飛行機(jī)制的群智能優(yōu)化算法. 在CS算法中有兩種更新解的方式, 一種是布谷鳥尋找寄生巢下蛋的方式, 另一種是寄生鳥以一定的概率發(fā)現(xiàn)外來蛋后重新筑巢的方式. 前一種方式采用了萊維飛行的方式, 后一種方式采用隨機(jī)方式或者萊維飛行的方式. 萊維飛行方式是一種長步長與短步長相結(jié)合的方式[9]. CS也在求解置換流水車間調(diào)度問題上得到了應(yīng)用[10]. 文獻(xiàn)[11]將CS算法與差分進(jìn)化算法(differential evolution, DE)[12]相結(jié)合, 提出了混合的CSDE算法并求解了工程優(yōu)化問題.

綜上, 大多數(shù)群智能算法都是受到動物行為而產(chǎn)生的. 近來, 一種受到群體免疫概念啟發(fā)的冠狀病毒群體免疫優(yōu)化算法(coronavirus herd immunity optimization,CHIO)被提出來[13]. 在自然界中, 當(dāng)病毒找到宿主后,會在人群中迅速傳播和進(jìn)化. 冠狀病毒感染的傳播速度取決于感染者如何與其他社會成員直接接觸群體.衛(wèi)生部門建議用兩種方法對抗病毒傳播, 一種是將受感染者與他們的家人隔離, 包圍社區(qū)并隔離所有他們接觸的人; 另一種是利用群體免疫機(jī)制來阻止病毒傳播, 即當(dāng)一個群體中大部分人擁有免疫能力時, 他們對易感個體的保護(hù)行為就產(chǎn)生了群體免疫. 群體免疫是一種狀態(tài), 當(dāng)大多數(shù)人免疫時, 人群達(dá)到這種狀態(tài), 從而防止病毒傳播. CHIO 就是模擬了群體免疫策略和社會距離概念而提出的群智能算法.

本研究在原始的CHIO基礎(chǔ)上進(jìn)行了改進(jìn), 針對置換流水車間調(diào)度問題, 提出了動態(tài)改變擴(kuò)展速率的策略, 提高了解的探索與開發(fā)的平衡能力. 同時, 在算法的重生階段之后增加了基于差分進(jìn)化算子的交叉階段, 對群體進(jìn)行最優(yōu)解的挖掘, 提高了算法的尋優(yōu)能力.

2 PFSP問題描述

PFSP的描述如下:n個 作業(yè)N={J1,J2,···,Jn}在一系列m臺 機(jī)器M={M1,M2,···,Mm} 上依次處理.i表示作業(yè),j表示機(jī)器. 每個作業(yè)由一組操作組成, 每個操作都將在特定的機(jī)器上執(zhí)行, 所有作業(yè)Ji={Ui1,Ui2,···,Uim}的機(jī)器加工順序相同. 機(jī)器Mj上 作業(yè)Ji的處理時間用Pij(i=1,2,···,n;j=1,2,···,m)表示. 每個作業(yè)只能在一臺機(jī)器上處理, 每臺機(jī)器一次只能處理一個作業(yè). PFSP常見的求解目標(biāo)是找到最小化最大完工時間(Cmax)的作業(yè)排列. 作業(yè)排列表示為 π ={π1,π1,···,πn}.C(πi,m)表示πi在機(jī)器m上的作業(yè)完成時間.

根據(jù)以上對PFSP的描述, 給出其數(shù)學(xué)描述具體如下:

最大化完工時間可以定義為:

3 混合算法設(shè)計

3.1 原始的CHIO算法

原始的CHIO算法是受到群體免疫的概念而形成的一種群智能算法[13]. 假設(shè)優(yōu)化問題搜索空間的維度是D,種群大小是N. 問題的解可以用向量Xi=(X1i,X2i,···,XDi)表示. 其中,i是一個[ 1,N]內(nèi)的隨機(jī)數(shù). 所有個體分為3種類型: 易感個體、感染個體與免疫個體.

所有個體的類型可以用向量S=(S1,S2,···,SN)表示.Si=0 表示個體屬于易感個體,Si=1表示個體屬于感染個體,Si=2表示個體屬于免疫個體. CHIO的偽代碼如算法1所示. 從偽代碼可以看出, CHIO算法包括3個主要階段: 群體免疫進(jìn)化階段、群體更新階段與重生階段.

算法1. CHIO算法X S BR 1) 初始化種群()、狀態(tài)向量()、參數(shù) ;2) repeat 3) 遍歷每個個體// 群體免疫進(jìn)化階段:4) 開始遍歷每個維度r 5) 生成隨機(jī)數(shù)r BR/3 6) if (＜ ( )7) 隨機(jī)選擇一個感染個體8) 根據(jù)式(6)生成新個體isCorona(x)9) =1 r 2BR/3 10) elseif (＜ ( )11) 隨機(jī)選擇一個易感個體12) 根據(jù)式(6) 生成新個體13) else 14) 隨機(jī)選擇一個免疫個體15) 根據(jù)式(6)生成新個體16) 結(jié)束遍歷維度// 群體更新階段:17) if (新個體的適應(yīng)度好于原來個體的適應(yīng)度)18) 對兩個個體采用貪婪選擇19) else 20) if (原來個體是感染的個體)21) 記錄沒有改進(jìn)的次數(shù)22) endif isCorona(x)23) if ((新個體適應(yīng)度小于平均適應(yīng)度) and (個體的狀態(tài)等于0)and )24) 將個體的狀態(tài)設(shè)置為1.25) endif 26) if((新個體適應(yīng)度大于平均適應(yīng)度) and (個體的狀態(tài)等于1))27) 將個體的狀態(tài)設(shè)置為2.28) endif// 重生階段:29) if (個體適應(yīng)度在預(yù)定義的次數(shù)內(nèi)沒有得到改善)30) 隨機(jī)生成新個體替換該個體

31) endif 32) 記錄最佳個體33) 結(jié)束遍歷個體34) until(終止條件)

在群體免疫進(jìn)化階段, 解的每個維度依賴式(6)進(jìn)行更新:

其中,j∈(1,2,···,D),[-1, 1]區(qū)間內(nèi)的一個隨機(jī)數(shù).k是隨機(jī)選擇的個體, 其值是由擴(kuò)展速率參數(shù)BR決定. 假設(shè)r是一個隨機(jī)數(shù), 如果r∈[0,BR/3) , 則k從感染個體中隨機(jī)選擇; 如果r∈[BR/3,2BR/3) , 則k從易感個體中隨機(jī)選擇; 如果r∈[2BR/3,BR), 則k從免疫個體中隨機(jī)選擇.

在群體更新階段, 每一個個體的解的適應(yīng)度根據(jù)其目標(biāo)函數(shù)進(jìn)行計算. 所有個體的適應(yīng)度可以用向量F=(F1,F2,···,FN)表示. 用一個向量記錄感染個體的適應(yīng)度沒有得到改善的次數(shù). 根據(jù)式 (7) 對狀態(tài)向量進(jìn)行更新:

其中,i∈[1,N], m ean(F)是 種群的平均適應(yīng)度,isCorona(Xi)表示個體是否是感染者個體.

在重生階段, 如果感染個體的適應(yīng)度沒有得到改善的次數(shù)到達(dá)預(yù)定義的次數(shù), 則隨機(jī)生成一個個體替換當(dāng)前個體.

3.2 擴(kuò)展速率參數(shù)設(shè)計

在原始的CHIO算法中, 擴(kuò)展速率參數(shù)BR是一個用來決定解更新算子的重要參數(shù), 其值越小, 算法探索能力越弱; 其值越大, 算法的探索能力越強(qiáng). 在原始的CHIO算法中,BR被設(shè)置為常數(shù) 0.01. 為了平衡算法的探索能力與開發(fā)能力, 提出一種動態(tài)調(diào)整擴(kuò)展速率參數(shù)的方法, 如式(8)所示:

其中,BRmax是 擴(kuò)展速率參數(shù)的最大值,BRmin是擴(kuò)展速率參數(shù)的最小值,tmax是算法的最大迭代次數(shù),t是算法當(dāng)前的迭代次數(shù). 圖1是擴(kuò)展速率參數(shù)根據(jù)式(8)從0.5動態(tài)調(diào)整到0.005的效果.

圖1 動態(tài)調(diào)整效果

3.3 混合CHIO算法

為了增強(qiáng)CHIO算法的局部開發(fā)能力, 在原始算法的3個階段后加入基于DE[12]的解的開發(fā)階段, 形成一種混合的CHIO算法(Hybrid CHIO, HCHIO).DE具有很強(qiáng)的收斂能力[14]. 算法2給出了交叉階段的偽代碼. 圖2給出了HCHIO的流程圖.

圖2 HCHIO流程圖

算法2. 交叉算法CR F 1) 設(shè)置參數(shù)交叉概率( )與差分權(quán)重();2) 開始遍歷個體3) 開始遍歷每個維度r 4) 生成隨機(jī)數(shù)rCR 5) if (＜ )6) 根據(jù)式(9)生成新個體7) endif 8) 結(jié)束遍歷維度9) 計算新個體適應(yīng)度10) 在新個體與原個體之間采用貪婪選擇11) 結(jié)束遍歷個體

在交叉階段, 差分變異算子是主要的操作, 該算子如式(9)所示:

其中,i,r,p,q是4個區(qū)間[ 1,N]上 的不同數(shù)字.F是差分權(quán)重.

在交叉階段, 每個個體根據(jù)交叉概率都有機(jī)會執(zhí)行差分變異算子. 所以, 該階段可以大范圍挖掘最優(yōu)解.

4 仿真實驗

4.1 實驗方案

實驗采用Reeves測試集作為基準(zhǔn)測試實例, 該測試集是一種中到大規(guī)模問題測試集[15,16]. 實驗結(jié)果用每組測試集的最佳值的相對百分比偏差與平均值的相對百分比偏差表示.

每組實例上的最佳值的平均相對偏差:

每組實例上的平均值的平均相對偏差:

其中,C*是 在參考文獻(xiàn)中已知的最優(yōu)結(jié)果.k是測試集的測試實例個數(shù).

將原始的CHIO算法[13]、PSO算法[1]、ABC算法[2]、CS算法[3]、CSDE算法[11]以及DE算法[12]作為對比算法. 所有算法采用最小位置值[17]的方式實現(xiàn)置換流水車間調(diào)度問題解的編碼與解碼. 對比算法中的參數(shù)按照參考文獻(xiàn)中進(jìn)行設(shè)置. 使用適應(yīng)度評估次數(shù)作為算法終止條件, 最大評估次數(shù)設(shè)置為20 000. 為了得到有效的實驗結(jié)果, 每種算法獨(dú)立運(yùn)行20次.

4.2 實驗結(jié)果與分析

以最小化最大完工時間為優(yōu)化目標(biāo)在Reeves測試實例上進(jìn)行實驗. 表1與表2分別給出了各個算法在7組Reeves測試實例上的最佳值相對偏差與平均值相對偏差. 圖3給出了不同算法在Reeves測試實例上最佳值相對偏差的折線圖, 圖4給出了不同算法在Reeves測試實例上平均值相對偏差的折線圖.

從表1可以看出, HCHIO在7組測試集取得了最好的結(jié)果. 從表2上可以看出, HCHIO在7組測試集取得了最好的平均值. 圖3與圖4 以折線圖的形式給出了直觀的展示.

表1 算法在Reeves測試實例上的最佳值的平均相對偏差

表2 算法在Reeves測試實例上的平均值的平均相對偏差

圖3 算法在Reeves實例上的最佳相對偏差折線

圖4 算法在Reeves實例上的平均相對偏差折線

HCHIO在21個Reeves測試實例的16個單實例上取得了最好的結(jié)果, 圖5給出不同算法在這16個實例上的收斂曲線. 從收斂曲線上可以清晰地看到,HCHIO 相對于其他6種比較算法具有很強(qiáng)的收斂性.從收斂曲線上看出, 相對于原始的CHIO算法, 本文提出的動態(tài)改變擴(kuò)展速率參數(shù)的策略與基于DE的交叉策略在尋優(yōu)精度上起到了很大的改善作用.

圖 5 算法在Reeves實例上的收斂曲線

5 結(jié)論與展望

在原始的CHIO算法的基礎(chǔ)上采用動態(tài)改變擴(kuò)展速率參數(shù)的策略以平衡解的探索能力與開發(fā)能力, 增加基于DE的交叉階段以增強(qiáng)算法對最優(yōu)解的開發(fā)能力, 從而形成一種混合算法. 針對PFSP問題, 以最小化最大完工時間為優(yōu)化目標(biāo), 以原始CHIO算法以及其他6個智能算法作為對比算法, 在21個Reeves實例上進(jìn)行了仿真實驗, 實驗結(jié)果表明了提出的改進(jìn)策略有效提高了解的尋優(yōu)能力和收斂速度.