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

曹 磊 葉春明 黃 霞

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

?

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

曹 磊 葉春明 黃 霞

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

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

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

0 引 言

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

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

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

很多智能算法易于陷入局部最優，選取合適的方法使搜索跳出局部極值是改進算法的有效手段。混沌是一種較為普遍的現象，它指系統中看似無序，類似隨機的現象。混沌具有隨機性、遍歷性、規律性等特點。李兵[8]首先利用此現象提出混沌優化算法。由于混沌算法的隨機性及遍歷性等特點，其具有跳出局部極值的能力，更易于達到全局最優。自提出之后，混沌優化算法得到了廣泛應用[9-11]。

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

1 混沌煙花算法

1.1 煙花算法

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

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

1.1.1 爆炸算子

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

(1)

(2)

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

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

(3)

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

(4)

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

(5)

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

1.1.2 變異算子

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

(6)

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

1.1.3 選擇策略

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

(7)

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

dij=‖xi-xj‖

(8)

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

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

1.2.1 編碼

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

1.2.2 選擇策略

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

P={}

for i 1 to N

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

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

P=P∪Xi

end if

end for

return P

1.2.3 動態半徑因子

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

(9)

式(2)可更新為：

(10)

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

1.3 混沌搜索策略

混沌搜索具有隨機性、遍歷性等特點，在一定程度上可以使煙花算法跳出局部最優。基本思想是將進行混沌搜索的煙花個體通過混沌映射規則對應為混沌搜索空間中的混沌變量，利用混沌變量做遍歷性尋優搜索，將遍歷到的混沌變量序列轉換為解向量序列，找到本次混沌優化得到的最好解向量，來更新混沌搜索之前的煙花個體。

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

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

(11)

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

(12)

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

(13)

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

2.1 置換流水車間問題

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

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

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

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節、1.3節之于煙花算法的分析，將混沌搜索策略加入到煙花算法尋優過程中。尋優過程如下：

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

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

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

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

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

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

Step6 判斷是否超出最大迭代次數。若否，則進入Step3；若是，則退出循環，輸出最優值。

3 參數分析與仿真對比

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

3.1 參數分析

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

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

表1 參數水平

表2 正交實驗表

表3 參數性能分析

圖1 不同參數水平下的尋優性能

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

3.2 仿真實驗

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

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

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

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

續表5

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

圖2 Car3迭代曲線對比

圖3 Car5迭代曲線對比

圖4 Car6迭代曲線對比

從尋優率上來看，較之于粒子群算法、螢火蟲算法以及基本煙花算法，混沌煙花算法尋優率較高。混沌煙花算法在求解Car1、Car4、Car7和Car8問題時，尋優率達到了100%，求解其他Car類問題時尋優率也在一個較高水平。

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

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

4 結 語

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

[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] 李兵,蔣慰孫.混沌優化方法及其應用[J].控制理論與應用,1997,14(4):613-615.

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

[9] 婁素華,吳耀武,熊信艮.電力系統無功優化的變尺度混沌優化算法[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].智能系統學報,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] 劉長平,葉春明.基于邏輯自映射的變尺度混沌粒子群優化算法[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