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

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

1 引言

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

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

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

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

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

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

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

2 PFSP問題描述

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

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

最大化完工時(shí)間可以定義為:

3 混合算法設(shè)計(jì)

3.1 原始的CHIO算法

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

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

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

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

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

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

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

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

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

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

在原始的CHIO算法中, 擴(kuò)展速率參數(shù)BR是一個(gè)用來決定解更新算子的重要參數(shù), 其值越小, 算法探索能力越弱; 其值越大, 算法的探索能力越強(qiáng). 在原始的CHIO算法中,BR被設(shè)置為常數(shù) 0.01. 為了平衡算法的探索能力與開發(fā)能力, 提出一種動(dòng)態(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動(dòng)態(tài)調(diào)整到0.005的效果.

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

3.3 混合CHIO算法

為了增強(qiáng)CHIO算法的局部開發(fā)能力, 在原始算法的3個(gè)階段后加入基于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) 開始遍歷個(gè)體3) 開始遍歷每個(gè)維度r 4) 生成隨機(jī)數(shù)rCR 5) if (＜ )6) 根據(jù)式(9)生成新個(gè)體7) endif 8) 結(jié)束遍歷維度9) 計(jì)算新個(gè)體適應(yīng)度10) 在新個(gè)體與原個(gè)體之間采用貪婪選擇11) 結(jié)束遍歷個(gè)體

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

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

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)方案

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

每組實(shí)例上的最佳值的平均相對(duì)偏差:

每組實(shí)例上的平均值的平均相對(duì)偏差:

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

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

表1 算法在Reeves測(cè)試實(shí)例上的最佳值的平均相對(duì)偏差

表2 算法在Reeves測(cè)試實(shí)例上的平均值的平均相對(duì)偏差

圖3 算法在Reeves實(shí)例上的最佳相對(duì)偏差折線

圖4 算法在Reeves實(shí)例上的平均相對(duì)偏差折線

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

圖 5 算法在Reeves實(shí)例上的收斂曲線

5 結(jié)論與展望

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