應用混沌煙花算法求解置換流水車間問題

曹 磊 葉春明 黃 霞

(上海理工大學管理學院 上海 200093)

?

應用混沌煙花算法求解置換流水車間問題

曹 磊 葉春明 黃 霞

(上海理工大學管理學院 上海 200093)

改進煙花算法求解置換流水車間問題。用最大位置法編碼，將連續(xù)變量映射到離散空間。引入動態(tài)半徑因子，平衡局部搜索與全局搜索。精英個體混沌搜索,進一步挖掘個體信息。用錦標賽策略替代原有的選擇算子，群體中的優(yōu)良個體被選擇的概率增大。通過正交實驗選擇合適參數(shù)，求解Car類和Rec類基準問題。與基本煙花算法、螢火蟲算法和粒子群算法的對比實驗說明，改進后的混沌煙花算法在尋優(yōu)率、尋優(yōu)速度等上具有一定的優(yōu)勢，是求解置換流水車間問題的有效工具。

煙花算法 混沌搜索 置換流水車間問題

0 引 言

置換流水車間問題是許多實際生產系統(tǒng)的抽象模型，屬于組合優(yōu)化問題?，F(xiàn)已證明3臺以上的置換流水車間問題為NP-Hard問題[1]。因此，對于此類問題的求解具有一定的理論與實際價值。

解決此類問題的方法一般有：精確算法、啟發(fā)式算法、智能算法等。精確算法在理論上可以求得問題最優(yōu)解，但是耗時較長。啟發(fā)式算法能較快地找到問題的近似最優(yōu)解，但是求解精度較差。智能算法是如今發(fā)展較快尋優(yōu)方法，它能在較短的時間內尋得問題最優(yōu)解或近似最優(yōu)解。

煙花算法FWA(fireworks algorithm)是一種新穎的群智能算法，是由Tan等人于2010年根據(jù)煙花爆炸產生火花這一自然現(xiàn)象提出的[2]。FWA自提出后被應用于許多領域的優(yōu)化問題，主要應用領域有參數(shù)優(yōu)化[3]、配電網重構優(yōu)化[4]、濾波器設計[5]、圖像識別[6]、施肥問題[7]等。從現(xiàn)有研究來看，將煙花算法應用于生產調度的文章暫時未有。

很多智能算法易于陷入局部最優(yōu)，選取合適的方法使搜索跳出局部極值是改進算法的有效手段?；煦缡且环N較為普遍的現(xiàn)象，它指系統(tǒng)中看似無序，類似隨機的現(xiàn)象?；煦缇哂须S機性、遍歷性、規(guī)律性等特點。李兵[8]首先利用此現(xiàn)象提出混沌優(yōu)化算法。由于混沌算法的隨機性及遍歷性等特點，其具有跳出局部極值的能力，更易于達到全局最優(yōu)。自提出之后，混沌優(yōu)化算法得到了廣泛應用[9-11]。

在分析基本煙花算法的基礎上，本文將混沌搜索策略運用到煙花尋優(yōu)的過程中。通過引入邏輯自映射函數(shù)產生混沌序列，對每一代中的精英個體進行混沌搜索，挖掘精英個體的信息。并通過應用動態(tài)半徑因子、錦標賽選擇策略進一步加強改進煙花算法在置換流水調度問題中的尋優(yōu)性能。

1 混沌煙花算法

1.1 煙花算法

受煙花爆炸啟發(fā)，譚營提出了煙花算法[1,12]。在煙花算法中，每個煙花可看成一可行解，爆炸產生火花的過程可視為鄰域搜索尋優(yōu)的過程。煙花算法中存在這樣的機制：適應度差的煙花爆炸半徑較大，使其具有全局搜索能力；而適應度好的煙花爆炸半徑較小，使其具備局部搜索能力。這與實際煙花爆炸機理是吻合的。一般而言，好的煙花是多而密，差的煙花是少而稀。在煙花算法中存在兩種形式的火花，即爆炸火花和高斯變異火花。爆炸火花為煙花在其鄰近區(qū)域內產生的火花，可視為煙花的子代，用于搜尋鄰域內更優(yōu)解。而高斯變異火花的引入增強了種群的多樣性，在一定程度上避免了陷入局部最優(yōu)。

在煙花算法中，爆炸算子、變異算子和選擇策略是決定煙花算法性能優(yōu)劣的要素。

1.1.1 爆炸算子

爆炸火花通過爆炸算子產生。每個火花由特定的煙花產生，并且其位置同樣由父代煙花決定。適應度好的煙花產生較多的爆炸火花，火花分布于煙花周圍。因此，適應度高的煙花附近聚集較多的火花；適應度低的火花周圍分布較少的火花，且火花距離中心煙花較遠。對于煙花i子代火花個數(shù)Si以及分布半徑Ri定義如下：

(1)

(2)

其中：SN為爆炸火花數(shù)，A為基本爆炸半徑，fi為煙花i的適應度值，ymax為當前煙花種群中的最大適應度值，ymin為當前煙花種群中的最小適應度值，ε為機器最小值，避免除零操作。為了保證每個煙花爆炸而來的火花數(shù)為整數(shù)，一般對式(1)、式(2)產生的數(shù)四舍五入取整。

為了控制較好煙花的火花數(shù)不過多，較差煙花的火花數(shù)不過少，對煙花i的火花數(shù)有如下控制：

(3)

式中，a、b是兩個常數(shù)，round是根據(jù)四舍五入原則的取整函數(shù)。根據(jù)式(1)、式(2)，由煙花i生成的火花，按照下式進行位置更新：

(4)

若出現(xiàn)超界，通過式(5)將火花映射到有效區(qū)域。

(5)

式中，LBk、UBk為解空間在維度k上的上邊界和下邊界，mod為取余函數(shù)。

1.1.2 變異算子

高斯火花由變異算子產生。高斯火花的存在增加了種群的多樣性。在煙花種群中隨機選擇一定數(shù)目的煙花，對每一個煙花隨機選擇一定數(shù)目的維度進行高斯變異操作。對于煙花i的某一個維度k執(zhí)行高斯變異操作為：

(6)

其中有e～N(1,1)，N(1,1)表示均值為1、方差為1的高斯分布。高斯變異火花可能超出可行域的邊界范圍，通過式(5)將超界火花映射到區(qū)域內。

1.1.3 選擇策略

在原始煙花算法中，存在這樣的選擇規(guī)則：由煙花、爆炸火花和高斯火花共同組成候選集合K，從集合中選取N個個體作為下一代煙花。除最優(yōu)個體外，其余N-1個個體均由輪盤賭規(guī)則選出，每個個體被選擇的概率為：

(7)

式中，dij為第i和j個煙花個體之間的歐式距離，定義如下：

dij=‖xi-xj‖

(8)

從式(7)、式(8)可以看出，在所有個體中，與其他個體總偏離越大的，其被選擇的概率越大。此種選擇機制避免了群體密集位置被選擇概率過大，陷入局部最優(yōu)，但其并不一定能指引群體向優(yōu)良方向進化。

1.2 煙花算法性能分析及改進

1.2.1 編碼

基本煙花算法優(yōu)化的是連續(xù)問題，而置換流水車間問題需要解決的是工件排序問題，屬于離散調度。因此，需要建立連續(xù)空間到離散空間的映射。采用最大位置法LOV(Largest Order Value)對煙花及其火花進行編碼[13]。煙花位置分量中，最小的數(shù)值標記為1，次小的位置分量標記為2，直至所有位置分量被標記。位置分量相同時，規(guī)定近左先編碼。這樣，一個煙花的位置量就映射為唯一的工件加工序列。

1.2.2 選擇策略

在原始煙花算法的選擇策略中，優(yōu)良個體不一定被選中，而與群體偏離最多的個體被選擇的概率較大。本文采用一種基于適應度大小的錦標賽選擇策略，按照一定的組規(guī)模(百分比)r選擇一定數(shù)量的個體作為候選集合J。比較它們的適應度，適應度最大的被選擇(同適應度時，序號靠前的優(yōu)先被選)，重復此操作直到選出N個煙花。偽代碼如下：

P={}

for i 1 to N

generate set J and size J= round(r*N)%生成指定規(guī)模候選集合J

if f(Xi)=min(f(J))

P=P∪Xi

end if

end for

return P

1.2.3 動態(tài)半徑因子

根據(jù)式(1)，性能優(yōu)良的煙花會產生較多的爆炸火花。通過式(2)，適應度高的煙花的搜索半徑會相對較小。當A設置過小時，每一個煙花的搜索半徑均較小，搜索半徑具有一定的趨同性，不利于種群的尋優(yōu)。當A設置較大時，意味著算法尋優(yōu)步長相對較大，一方面會出現(xiàn)超界現(xiàn)象，產生較多的非可行解；另一方面會降低局部尋優(yōu)的能力。引入自適應半徑因子A(t)，定義如下：

(9)

式(2)可更新為：

(10)

其中，t為當前迭代次數(shù)，Ainitial為初始半徑，Afinal為最終搜索半徑，maxgen為最大迭代次數(shù)。迭代初期，種群整體搜索半徑相對較大，有利于種群在全局范圍尋優(yōu)。隨著迭代次數(shù)的增加，煙花會在鄰域以較小的搜索半徑尋找最優(yōu)解。因此，自適應半徑因子可很好地平衡全局尋優(yōu)與局部尋優(yōu)。

1.3 混沌搜索策略

混沌搜索具有隨機性、遍歷性等特點，在一定程度上可以使煙花算法跳出局部最優(yōu)?；舅枷胧菍⑦M行混沌搜索的煙花個體通過混沌映射規(guī)則對應為混沌搜索空間中的混沌變量，利用混沌變量做遍歷性尋優(yōu)搜索，將遍歷到的混沌變量序列轉換為解向量序列，找到本次混沌優(yōu)化得到的最好解向量，來更新混沌搜索之前的煙花個體。

在尋優(yōu)過程中，為了在運算速度和求解精度之間保持平衡，采用精英獎勵策略。對選取的優(yōu)質個體進行混沌優(yōu)化搜索，而對于性能相對較差的個體，用隨機重新產生的個體代替，保證進化種群的多樣性和跳離局部極值的能力。

產生混沌序列的模型很多，本文采用具有更好遍歷性的邏輯自映射函數(shù)來產生混沌序列[14,15]，表示為：

(11)

在方程中只要迭代初值不為零，混沌就會發(fā)生，邏輯自映射函數(shù)的定義域為(-1，1)且不為0和0.5?；煦鐑?yōu)化的過程為：在搜索過程中的某個時刻，煙花個體xi先按照下式將個體空間位置映射到混沌區(qū)域(-1，1)中：

(12)

然后按照式(11)進行混沌遍歷搜索得到混沌變量序列，再將獲得的混沌變量序列按照式(13)變換到原解空間進行性能評價。

(13)

2 置換流水車間問題及其求解

2.1 置換流水車間問題

置換流水車間調度問題研究n個工件在m臺機器上的流水加工過程，每個工件需要m道工序。約定每臺機器加工的各工件順序也相同，每個工件在各機器上加工順序相同，每個工件在某時刻只能被一臺機器加工，每臺機器在某時刻只能加工一個工件。已知各工件在各機器上所需的加工時間和準備時間，求使某項生產指標(最小最大完工時間、總流經時間、總拖期時間等)最優(yōu)的調度方案。 本文尋優(yōu)目標為最小化完工時間。

假設PN,M表示工件N在機器M上的加工時間(假設各工件的加工準備時間已包含在加工時間PN,M內或為零)，Γ為所有排序的集合，π=(j1,j2,…,jn)表示工件集合的一個排序，π*表示其中最優(yōu)調度排序；C(ji,k)表示工件ji。

在機器k上的加工時間,π排序的數(shù)學描述如下：

C(j1,1)=Pj1,1

(14)

C(ji,1)=C(ji-1,1)+Pji,1

(15)

C(j1,k)=C(j1,k-1)+Pj1,k

(16)

C(ji,k)=max{C(ji,k-1),C(ji-1,k)}+Pji,k

(17)

Cmax(π)=C(jn,m)

(18)

Cmax(π*)=min(Cmax(π)) ?π∈Γ

(19)

其中，k=2,3,…,m;i=1,2,…,n。

2.2 混沌煙花算法求解置換流水車間問題

通過1.2節(jié)、1.3節(jié)之于煙花算法的分析，將混沌搜索策略加入到煙花算法尋優(yōu)過程中。尋優(yōu)過程如下：

Step1 初始化算法基本參數(shù)，包括煙花個數(shù)N、基本火花個數(shù)SN、高斯火花個數(shù)M、基本煙花半徑A、上下邊界等；

Step2 初始煙花位置：根據(jù)ROV規(guī)則，將煙花位置轉化為工件排序，計算每個煙花的適應度值；

Step3 N個煙花開始爆炸，根據(jù)式(1)和式(10)計算火花數(shù)目和爆炸半徑；

Step4 生成爆炸火花和高斯變異火花；

Step5 根據(jù)適應度值，通過錦標賽選擇策略，從煙花、爆炸火花、高斯火花中選擇N個作為下一代的煙花；

Step6 根據(jù)1.3節(jié)中混沌搜索策略，對新生成的煙花群體進行混沌搜索，并更新群體；

Step6 判斷是否超出最大迭代次數(shù)。若否，則進入Step3；若是，則退出循環(huán)，輸出最優(yōu)值。

3 參數(shù)分析與仿真對比

本文實驗環(huán)境為：PC計算機處理器主頻2.1 GHz，內存2 GB，Windows 7操作系統(tǒng)，MATLAB R2010b編程環(huán)境。針對置換流水車間的基準問題Car類和Rec類問題進行參數(shù)分析及對比實驗。

3.1 參數(shù)分析

煙花算法中主要的參數(shù)有煙花個數(shù)N、基本火花個數(shù)SN、變異火花個數(shù)M、基本半徑A。

對Car3問題，通過正交實驗，研究煙花算法參數(shù)對問題尋優(yōu)的影響。建立四因素、三水平正交實驗表(L9(34))，如表1、表2所示。每組參數(shù)組合獨立運行20次，以平均性能AVG作為評價指標，實驗結果見表2所示。為分析各參數(shù)對算法性能的影響趨勢，計算各參數(shù)的極差和重要程度，如表3所示。由表3可以看出,參數(shù)SN的極差最大,等級最高。這說明，在四個參數(shù)中，基本火花數(shù)目對算法的尋優(yōu)性能影響最大?；净鸹〝?shù)目越大，每個煙花對應的爆炸火花越多，這在一定程度上增加了種群的規(guī)模。而同樣與種群規(guī)模有關的參數(shù)煙花個數(shù)N與變異火花數(shù)目M則對算法性能提升相對不明顯。而基本煙花半徑A對算法尋優(yōu)性能影響較大，從圖1可以直觀地看出，A較大或較小均影響算法的尋優(yōu)性能。A較大使得爆炸火花的搜索半徑較大，挖掘局部信息的能力較弱，而較小的A使得算法不易跳出局部極值。因此，A較大或較小均不合適。

表1 參數(shù)水平

表2 正交實驗表

表3 參數(shù)性能分析

圖1 不同參數(shù)水平下的尋優(yōu)性能

通過以上分析，并結合實驗數(shù)據(jù)，建議給出參數(shù)為：N=15,SN=40,M=15,A=5。

3.2 仿真實驗

以Car類和Rec類基準問題為例[16]，同粒子群算法(PSO)、基本煙花算法(FWA)和螢火蟲算法(FA)對比，測試改進煙花算法的尋優(yōu)性能。

算法參數(shù)設置為：煙花算法中煙花個數(shù)N=15、基本火花個數(shù)SN=40、高斯火花個數(shù)M=15、基本半徑5、最大邊界5、最小邊界-5；混沌煙花算法中，初始半徑5、最終半徑0.01、組規(guī)模0.3，其他參數(shù)與基本煙花算法一致；粒子群算法中粒子個數(shù)70、學習因子1.5、慣性權重0.9、最大邊界5、最小邊界-5、最大速度0.5、最小速度-0.5；螢火蟲算法中種群規(guī)模70、光吸收系數(shù)1、最大吸引度1、步長因子0.2。以上每種算法均迭代300次，獨立運行20次。仿真結果如表4和表5所示。

表4 算法尋優(yōu)性能比較分析(CDWA和FWA)

表5 算法尋優(yōu)性能比較分析(PSO和FA)

續(xù)表5

針對Car類問題中較難尋優(yōu)的Car3、Car5和Car6問題，繪制四種算法單次尋優(yōu)曲線，如圖2、圖3和圖4所示。

圖2 Car3迭代曲線對比

圖3 Car5迭代曲線對比

圖4 Car6迭代曲線對比

從尋優(yōu)率上來看，較之于粒子群算法、螢火蟲算法以及基本煙花算法，混沌煙花算法尋優(yōu)率較高?；煦鐭熁ㄋ惴ㄔ谇蠼釩ar1、Car4、Car7和Car8問題時，尋優(yōu)率達到了100%，求解其他Car類問題時尋優(yōu)率也在一個較高水平。

從尋優(yōu)穩(wěn)定性上來看，混沌煙花算法在Car類所有問題，Rec01、Rec03和Rec17問題上平均偏移率ARE以及最大偏移率WRE均最小。與其他算法相比，混沌煙花算法每次尋優(yōu)更能尋得最優(yōu)或近似最優(yōu)解。

從尋優(yōu)速度來看，針對Car3、Car5和Car6問題，混沌煙花算法較之其他三種算法，收斂更快。從圖2、圖3和圖4可以看出，混沌煙花算法可以在較短的迭代次數(shù)中，找到問題的最優(yōu)解。對于Car3問題，煙花算法、粒子群算法和螢火蟲算法均未找到其最優(yōu)解，混沌煙花算法在第11代時找到最優(yōu)解；對于Car5問題，混沌煙花算法和煙花算法分別在第9代和第230代找到問題的最優(yōu)解，其他兩種算法未找到最優(yōu)解；對于Car6問題，只有PSO未找到問題最優(yōu)解，混沌煙花算法、煙花算法和螢火蟲算法分別在170代、220代和280代找到該問題的最優(yōu)解。

4 結 語

在分析基本算法尋優(yōu)機理的基礎上，主要從編碼、搜索半徑、選擇策略和精英混沌搜索四方面對原始算法加以改進。針對置換流水車間基準問題(Car類和Rec類)求解，混沌煙花算法在尋優(yōu)率、尋優(yōu)穩(wěn)定性、尋優(yōu)速度等方面較之煙花算法、粒子群算法和螢火蟲算法具有一定的優(yōu)勢。對于煙花算法的改進策略是有效的，改進后的煙花算法可以用來求解置換流水車間問題。將來可以將改進算法應用于大規(guī)模置換流水車間調度以及其他離散調度(作業(yè)車間、可重入調度等)中去。

[1] Tan Y,Zhu Y C.Fireworks algorithm for optimization[C]//Advances in Swarm Intelligence.Springer,2010:355-364.

[2] He W R,Mi G Y,Tan Y.Parameter optimization of local-concentration model for spam detection by using local-concentration model for spam detection by using fireworks algorithm[C]//Advances in swarm intelligence.Springer,2013:439-450.

[3] Imran A M,Kowsalya M.A new power system reconfiguration scheme for power loss minimization and voltage profile enhancement using Fireworks Algorithm[J].International Journal of Electrical Power and Energy Systems,2014,62:312-322.

[4] Gao H Y,Diao M.Cultural firework algorithm and its application for digital filters design[J].International Journal of Modelling Identification and Control,2011,14(4):324-331.

[5] Zheng S Q,Tan Y.A unified distance measure scheme for orientation coding in identification[C]//Information Science and Technology (ICIST),2013 International Conference on.IEEE,2013:979-985.

[6] Zheng Y J,Song Q,Chen S Y.Multiobjective fireworks optimization for variable-rate fertilization in oil crop production[J].Applied Soft Computing,2013,13(11):4253-4263.

[7] 李兵,蔣慰孫.混沌優(yōu)化方法及其應用[J].控制理論與應用,1997,14(4):613-615.

[8] 李新杰,胡鐵松,郭旭寧,等.0-1測試方法的徑流時間序列混沌特性應用[J].水科學進展,2012,23(6):861-868.

[9] 婁素華,吳耀武,熊信艮.電力系統(tǒng)無功優(yōu)化的變尺度混沌優(yōu)化算法[J].電網技術,2005,29(11):20-24,29.

[10] 張沫.改進混合蛙跳算法的云計算資源調度[J].計算機應用與軟件,2015,32(4):330-333.

[11] Garey M R,Johnson D S,Sethi R.The complexity of flow shop and job shop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.

[12] 譚營,鄭少秋.煙花算法研究進展[J].智能系統(tǒng)學報,2014,9(5):515-528.

[13] Qian B,Wang L,Huang D X,et al.An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers[J].Computers and Operations Research,2009,36(1):209-233.

[14] Awad El-Gohary,A S Al-Ruzaiza.Chaos and Adaptive Control in Two Prey,One Predator System With Nonlinear Feedback[J].Chaos,Solitons and Fractals,2007,34(2):443-453.

[15] 劉長平,葉春明.基于邏輯自映射的變尺度混沌粒子群優(yōu)化算法[J].計算機應用研究,2011,28(8):2825-2827.

[16] 王凌.車間調度及其遺傳算法[M].北京:清華大學出版社,2003.

APPLYING CHAOTIC FIREWORKS ALGORITHM IN SOLVING PERMUTATION FLOW SHOP PROBLEM

Cao Lei Ye Chunming Huang Xia

(SchoolofBusiness,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

We improved the fireworks algorithm to solve PFSP. By encoding with maximum position method, we mapped the continuous variables onto discrete space. To strike a balance between global searching and local searching, we introduced dynamic radius factor. We further mined the individual information with elite individual chaotic search. We replaced original selection operator with champion contest strategy, and as a result, the excellent ones in population could be selected at a higher rate of probability. We chose right parameters through orthogonal experiment for solving the benchmark problems of Car class and Rec class. Comparative experiments on basic fireworks algorithm, firefly algorithm and particle swarm optimisation illustrated that the improved chaotic fireworks algorithm has certain advantage over other algorithms in searching rate and searching speed and is an effective tool of solving permutation flow shop problem.

Fireworks algorithm Chaotic searching Permutation flow shop problem

2015-06-21。國家自然科學基金項目(71271138)；上海市一流學科建設項目(S1201YLXK)；滬江基金項目(A14006)；上海理工大學人文社科攀登計劃項目(14XPB01)。曹磊，博士生，主研領域：智能算法，生產調度。葉春明，教授。黃霞，講師。

TP301

A

10.3969/j.issn.1000-386x.2016.11.044