PFSP 問題的混和CHIO算法優化①

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

(沈陽大學 機械工程學院, 沈陽 110044)

1 引言

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

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

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

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

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

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

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

2 PFSP問題描述

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

根據以上對PFSP的描述, 給出其數學描述具體如下:

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

3 混合算法設計

3.1 原始的CHIO算法

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

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

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

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

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

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

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

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

在重生階段, 如果感染個體的適應度沒有得到改善的次數到達預定義的次數, 則隨機生成一個個體替換當前個體.

3.2 擴展速率參數設計

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

其中,BRmax是 擴展速率參數的最大值,BRmin是擴展速率參數的最小值,tmax是算法的最大迭代次數,t是算法當前的迭代次數. 圖1是擴展速率參數根據式(8)從0.5動態調整到0.005的效果.

圖1 動態調整效果

3.3 混合CHIO算法

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

圖2 HCHIO流程圖

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

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

其中,i,r,p,q是4個區間[ 1,N]上 的不同數字.F是差分權重.

在交叉階段, 每個個體根據交叉概率都有機會執行差分變異算子. 所以, 該階段可以大范圍挖掘最優解.

4 仿真實驗

4.1 實驗方案

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

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

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

其中,C*是 在參考文獻中已知的最優結果.k是測試集的測試實例個數.

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

4.2 實驗結果與分析

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

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

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

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

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

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

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

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

5 結論與展望

在原始的CHIO算法的基礎上采用動態改變擴展速率參數的策略以平衡解的探索能力與開發能力, 增加基于DE的交叉階段以增強算法對最優解的開發能力, 從而形成一種混合算法. 針對PFSP問題, 以最小化最大完工時間為優化目標, 以原始CHIO算法以及其他6個智能算法作為對比算法, 在21個Reeves實例上進行了仿真實驗, 實驗結果表明了提出的改進策略有效提高了解的尋優能力和收斂速度.