基于寄生行為的雙種群螢火蟲算法及其在柴油調(diào)合中的應用

孔祥東, 錢 鋒(華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)

基于寄生行為的雙種群螢火蟲算法及其在柴油調(diào)合中的應用

孔祥東, 錢 鋒
(華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)

在實際的化工過程中會遇到許多非線性優(yōu)化問題。常規(guī)群智能優(yōu)化算法在解決這類問題時,常出現(xiàn)收斂精度差和容易陷入局部最優(yōu),本文針對此提出了一種基于寄生行為的雙種群螢火蟲算法(FAPB)。該算法將進化種群均分為兩個種群,通過生物的寄生行為將兩個種群聯(lián)系起來,共享進化信息,提高了全局搜索能力;為防止算法陷入局部最優(yōu),引入基于自適應系數(shù)的高斯變異機制,提高了局部搜索能力。對4個經(jīng)典測試函數(shù)進行仿真,結(jié)果表明:與標準FA算法、FALS算法、LDPSO算法比較,FAPB算法在收斂精度和全局搜索能力上都有較大提升。將該算法應用于柴油調(diào)合過程,結(jié)果驗證了其在實際應用中的可行性。

螢火蟲算法; 寄生行為; 局部搜索; 高斯變異; 柴油調(diào)合

在現(xiàn)實的工藝流程中會遇到許多非線性優(yōu)化問題,這類問題的優(yōu)化結(jié)果往往直接關(guān)系到工廠的經(jīng)濟效益,所以逐漸成為一個重要的研究方向。針對這類非線性優(yōu)化問題,常規(guī)的解決方法是采用群智能搜索算法,引入各種策略,通過不斷地迭代最終找到最優(yōu)解。常規(guī)的群智能算法在尋找最優(yōu)解的過程中,很容易陷入局部最優(yōu),導致搜索效果不理想。后來,部分學者開始嘗試將不同的算法進行結(jié)合,通過不同算法的優(yōu)缺點互補來提高算法的整體性能。

受自然界中螢火蟲發(fā)光特性和群體搜索特性的影響,劍橋?qū)W者Yang[1]提出了螢火蟲算法 (Firefly Algorithm,FA)。Shruti等[2]將全局最優(yōu)因子引入到FA模型中,提高了模型的全局搜索能力和搜索精度。Farahani等[3]將高斯變異的機制加入到FA模型的搜索公式中,提高了算法的局部搜索能力和范圍,但是,算法在搜索的后期搜索速度會減慢。

針對常規(guī)FA及其改進算法的缺點,本文引入了基于寄生行為的雙種群螢火蟲算法(FAPB)來解決非線性優(yōu)化問題。該算法通過混沌進行初始化,使初始種群更加均勻地分布在解空間;在進化過程中,通過將寄生行為的策略引入到雙種群[4]的FA模型中,極大地提高了種群的搜索能力和收斂精度;在算法后期,為了防止算法陷入局部最優(yōu)解,將高斯變異引入到局部搜索策略中,提高了算法的局部搜索[5]特性。通過4個測試函數(shù)證明了算法的有效性。最后,將該算法應用于柴油調(diào)合過程,驗證了算法的實際可行性。

1 螢火蟲算法

螢火蟲算法是基于螢火蟲的趨光特性和群體移動特性而提出的一種新興元啟發(fā)算法[6],該算法的關(guān)鍵因素在于螢火蟲的相對亮度和吸引度[7]。亮度低的螢火蟲在移動過程中總是向著亮度高的螢火蟲移動,而吸引度的大小則決定了移動距離的大小。所有螢火蟲根據(jù)亮度和吸引度的不同,不斷地搜索和移動,最終聚集在亮度最強的螢火蟲附近,從而實現(xiàn)尋優(yōu)。

螢火蟲的相對亮度:

(1)

式中:I0為當前螢火蟲的亮度,與所在位置的適應度相關(guān);γ為光在傳播介質(zhì)中的衰減度;rij為空間中2只螢火蟲的歐氏距離。

螢火蟲的吸引度:

(2)

式中β0為r=0處的吸引度。

螢火蟲的位置更新公式:

(3)

式中:αt為搜索步長;rand為(0,1)的隨機數(shù)。

2 寄生行為

生物共生行為的概念最早是由德國科學家德貝里在1879年提出的[8]?！肮采笔侵竷煞N生物生活相互交織,共同維持生存的一種狀態(tài)。共生的兩種生物會產(chǎn)生對方需要的物質(zhì),維持彼此的生命活動。生物的共生行為具體可分為:互利共生、共棲和寄生。互利共生是指兩種生物分別從對方獲得好處,維持共同生存;共棲是指只有其中的一方會獲得好處,并且另一方不受干擾;寄生是指一種生物寄生在另一生物上不斷汲取營養(yǎng)才能生存,獲益的一方成為寄生生物,被侵害的生物成為宿主生物。

生物的寄生行為是在生物進化的過程中不斷演變而來的。寄生生物和宿主生物根據(jù)自然法則,相互競爭、不斷適應,最終達到了寄生關(guān)系。通常認為,寄生生物會不斷汲取宿主生物的營養(yǎng)來維持自身的生命活動;而宿主生物在被寄生生物入侵之后,會獲得相應的免疫力,當同種寄生物再次入侵時,會有一定的抵抗力,這一抵抗力又稱為獲得性免疫。寄生生物和宿主生物共同生活,不斷進化,可能會使得寄生生物的入侵能力不斷“削弱”,甚至最后達到共生效果[9]。

3 改進的螢火蟲算法

3.1 基于寄生行為的雙種群搜索策略

在標準FA中,每次迭代螢火蟲都會向著周圍亮度較強的螢火蟲移動,缺少與全局范圍內(nèi)螢火蟲信息的交流。為了克服標準FA的缺點,本文將進化種群均分為兩個種群,并將生物寄生行為引入到迭代過程中,加強了全局范圍內(nèi)的信息交流,提高了算法的收斂精度和全局搜索能力[10]。

首先對種群進行初始化,并將種群均分為寄生種群Pop1和宿主種群Pop2。在每代的進化過程中會發(fā)生寄生行為,具體表現(xiàn)為:對Pop1和Pop2中的粒子按照適應度重新進行排序,將排序后的前50%粒子賦值給寄生種群Pop1,后50%粒子賦值給宿主種群Pop2,完成寄生行為[11]。

寄生行為結(jié)束后,寄生種群會繼續(xù)按照式(3)進行進化。宿主種群由于被寄生種群入侵后產(chǎn)生了獲得性免疫,所以在進化時會同時受到鄰域粒子和寄生種群粒子的共同影響,按照式(4)進行進化。

(4)

每一代進化結(jié)束后,會在Pop1和Pop2中選出全局最優(yōu)值gbest,并與上一代全局最優(yōu)位置進行比較,如果比上一代的全局最優(yōu)位置優(yōu)越,則替代;否則不做改變。

3.2 基于自適應系數(shù)的局部搜索策略

針對進化算法容易陷入局部最優(yōu)的缺點,本文結(jié)合gbest信息,提出了基于自適應系數(shù)的局部搜索策略。

首先,通過式(5)對gbest進行局部搜索,得到一組全局最優(yōu)信息的鄰域值。

(5)

式中:ε為自適應系數(shù),其值由式(6)決定。

(6)

式中:MaxIt為最大迭代次數(shù);t為當前迭代次數(shù)。

將新得到的gbest的鄰域值與gbest進行逐個比較,選出適應度更優(yōu)的作為新的gbest。

3.3 改進算法步驟

綜上所述,FAPB算法步驟如下:

(1) 初始化螢火蟲位置,將其均分為Pop1和Pop2,并確定相關(guān)參數(shù)。

(2) 計算Pop1和Pop2的適應度并排序,更新全局最優(yōu)值gbest。

(3) 計算螢火蟲種群的相對亮度I和吸引度β。

(4) 通過寄生行為,對寄生種群和宿主種群分別采用式(3)和式(4)進行位置更新。

(5) 執(zhí)行步驟(2),對gbest進行局部搜索策略。

(6) 判斷是否滿足終止條件,若滿足則結(jié)束;否則轉(zhuǎn)步驟(3)。

4 仿真結(jié)果與分析

為了驗證FAPB算法的性能,本文選用4個經(jīng)典測試函數(shù)進行仿真,如表1所示,其中D為測試函數(shù)維度,Q為搜索空間范圍,fmin為測試函數(shù)最優(yōu)值。將FAPB與LDPSO[12]、標準FA[6]、FALS算法(在標準FA算法中引入本文的局部搜索策略)進行測試對比。為增加結(jié)果對比性,公共參數(shù)取值均相等,其中最大迭代次數(shù)tmax=1 000,種群大小NPop=50,測試函數(shù)維度D=30,迭代公式的β0=γ=1。表2示出了對4個測試函數(shù)進行30次獨立實驗的結(jié)果。

為了更加直觀地看出本文算法的收斂特性,結(jié)合圖1和圖2,對比FAPB算法和FA算法在各個進化階段的種群收斂情況。從圖中可以看出,FAPB算法收斂速度更快,在100代時已經(jīng)進入了精確搜索的范圍,到500代時已經(jīng)找到了較精確的解;而FA算法直到200代才找到較精確的搜索范圍,到500代時也沒有找到較精確的解,收斂速度較慢。

圖3～圖6示出了進化代數(shù)與測試函數(shù)最優(yōu)值之間的關(guān)系。

表1 基準測試函數(shù)

表2 測試結(jié)果

圖1 FAPB算法的種群收斂情況

由圖3～圖6可知,標準FA和LDPSO算法的搜索速度較慢,在算法后期容易陷入局部最優(yōu)。FALS算法由于引入局部搜索策略,雖然有一定跳出局部最優(yōu)的能力,但是全局尋優(yōu)能力仍然較差,收斂精度低。而FAPB算法在FALS的基礎(chǔ)上,又引入了基于寄生行為的雙種群搜索策略,保證了全局范圍內(nèi)粒子信息的交流,提高了算法的全局尋優(yōu)能力,收斂精度也得到了較大提高。表2結(jié)合4個測試函數(shù),從最小值、最大值及平均值3個方面,證明了FAPB在搜索精度和全局收斂性上的優(yōu)越性。

圖2 FA算法的種群收斂情況

圖3 Schaffer函數(shù)進化曲線

圖4 Rastrigin函數(shù)進化曲線

圖5 Ackleys函數(shù)進化曲線

圖6 Griwank函數(shù)進化曲線

5 應用研究

5.1 問題描述

本文以某煉油廠柴油調(diào)合[13]為背景,7種組分油為:I加氫裂化、渣蠟加氫、II柴油加氫、III柴油加氫、IV柴油加氫、II加氫裂化和烷返油。

(1) 目標函數(shù)。本文目標函數(shù)為各個指標成本最低和質(zhì)量過剩最小,目標函數(shù)模型[14]如下:

(7)

(2) 約束條件。

物料平衡約束:

(8)

庫存約束:

(9)

流量約束:

(10)

指標約束:

(11)

(12)

由于調(diào)合效應[15]的存在,常規(guī)調(diào)合模型中線性計算方法已經(jīng)不能滿足實際需求。因此,本文引入指標補償機制,在計算成品油的各個屬性時,對各個屬性進行補償:

(13)

式中:Pzi為每代進化完成后各個組分油的屬性值;ΔPbi為各個組分油的屬性補償,通過對每代組分油屬性值進行線性回歸可得其具體值。

5.2 數(shù)據(jù)及結(jié)果分析

結(jié)合表3中的數(shù)據(jù),分別對LDPSO[12]、FA[6]和FAPB算法進行了10次實驗,其中種群的大小為100,ω1和ω2都為0.5,結(jié)果如圖7所示。

表3 各個組分油的屬性

從圖7可以看出,FAPB算法在全局搜索能力和收斂精度兩個方面均得到了較大提升。在全局搜索能力方面,LDPSO算法在120代以后趨于穩(wěn)定,FA算法在150代左右趨于穩(wěn)定,而FAPB算法由于寄生行為和雙種群策略的引入,全局搜索能力得到了提高,在50代左右已經(jīng)找到了全局最優(yōu)值;在收斂精度方面,LDPSO算法沒有解決容易陷入局部最優(yōu)的問題,找到的最優(yōu)值約為4 263.25,FA算法也是受局部搜索能力的影響,找到的最優(yōu)值約為4 182.49,而FAPB算法引入局部搜索策略,提高了局部搜索能力,最終得到的目標函數(shù)值約為4 002.81,優(yōu)化配方為[0.033 2,0.238 3,0.083 3,0.250 1,0.127 1,0.207 5,0.060 5]。通過對比,可以看出FAPB算法在實際應用中的可行性。

圖7 目標函數(shù)進化曲線

6 結(jié) 論

本文在螢火蟲算法(FA)的基礎(chǔ)之上,提出了一種基于寄生行為的雙種群螢火蟲算法(FAPB)。該算法將初始種群均分為兩個種群,并將寄生行為加入到進化過程中,提高了種群的全局搜索能力和搜索精度;基于自適應系數(shù)的局部搜索策略,提高了種群的局部搜索能力(寄生行為、雙種群策略和局部搜索策略的引入,在提高搜索能力和收斂精度的同時,也帶來了相應的計算量,算法的運行時間在一定程度上也會相應延長)。通過對4個測試函數(shù)的仿真,證明了該算法具有較好的收斂能力和收斂精度。最后,通過柴油調(diào)合模型也驗證了該算法的可行性。

[1]YANG Xinshe.Nature-Inspires Metaheuristic Algorithms [M].[s.l.]:Luniver Press,2008:83-96.

[2]GOEL S,PANCHAL V K.Performance evaluation of a newmodified firefly algorithm[C]//International Conference on Reliability,INFOCOM Technologies and Optimization.USA:IEEE,2014:1-6.

[3]FARAHANI S M,NASIRI B,ABSHOURI A A,etal.An improved firefly algorithm with directed movement[C]//IEEE International Conference on Computer Science & Information Technology. USA:IEEE,2011:248-251.

[4]李婷,賴旭芝,吳敏.基于雙種群粒子群優(yōu)化新算法的最優(yōu)潮流求解[J].中南大學學報(自然科學版),2007,38(1):133-137.

[5]劉三陽,張平,朱明敏.基于局部搜索的人工蜂群算法[J].控制與決策,2014(1):123-128.

[6]YANNG Xinshe.Firefly algorithms for mult-imodal optimization[C]//Proceedings of the 5th International Symposium on Stochastic Algorithms:Foundations and Applications.Berlin:Heidelberg Springer-Verlag 2009:169-178.

[7]YANG Xinshe,DEB S.Eagle strategy using lévy walk and firefly algorithms for stochastic optimization[J].Studies in Computational Intelligence,2010,284:101-111.

[8]MCNALLY S F.Symbiosis:Anintroduction to biological associations[J].Bryologist,1988,89(4):88-94.

[9]LI W X,WANG G T.Regulation of parasites on host population:A brief review[J].Acta Hydrobiologica Sinica,2002(5):550-554.

[10]HASSANZADEH T,MEYBODI M R.A new hybrid approach for data clustering using firefly algorithm and K-means[C]// CSI International Symposium on Artificial Intelligence and Signal Processing.USA:IEEE,2012:007-011.

[11]谷金蔚,顧滿占,顧幸生.量子寄生遺傳算法求解Flow Shop及兩階段配送的集成調(diào)度問題[J].華東理工大學學報(自然科學版),2014,40(2):235-243.

[12]SHI Y,Eberhart R C.Empirical study of particle swarm optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation.USA:IEEE,1999:168-175.

[13]ZHANG B,HUA B,CHEN Q.Optimization of gasoline blending and scheduling in refinery complexes[J].Journal of Chemical Industry & Engineering,2007,58(1):168-175.

[14]崔巍,賈舒晨,周雪山,等.柴油在線優(yōu)化調(diào)和系統(tǒng)在廣西石化的應用[J].計算機與應用化學,2013(11):1347-1350.

[15]ZHAO J,CHAI T,PING Z.Modified bio-inspired algorithm based on membrane computing and application in gasoline blending[J].Ciesc Journal,2012,63(9):2965-2971.

A Double Population Firefly Algorithm Based on Parasitic Behavior and Its Application in Diesel Blending

KONG Xiang-dong, QIAN Feng

(Key Laboratory of Advanced Control and Optimization for Chemical Process,Ministry of Education, East China University of Science and Technology,Shanghai 200237,China)

There exist many nonlinear optimization problems in the actual chemical process,for which the conventional swarm intelligence optimization algorithm easily falls into local optimum.This paper presents a parasitic behavior (FAPB) based double population firefly algorithm.By dividing into the evolutionary population into two ones linked together via the parasitic behavior of organisms,these population can share the information and improve the global searching ability.In order to prevent the algorithm from falling into local optimum,this paper further introduces Gauss mutation mechanism based on the adaptive coefficient to improve the local search ability.By simulations on four classical test functions,it is shown that,compared with the standard FA algorithm,FALS algorithm and LDPSO algorithm,the proposed FAPB algorithm can effectively improve the convergence accuracy and global search capability.Finally,the feasibility of the proposed algorithm is also demonstrated via diesel blending.

firefly algorithm; parasitic behavior; local search; Gauss variation; diesel blending

1006-3080(2017)02-0213-07

10.14135/j.cnki.1006-3080.2017.02.010

2016-09-09

國家自然科學基金重點項目(61333010);國家自然科學基金面上項目(21376077,61403141);上海市“科技創(chuàng)新行動計劃”研發(fā)平臺建設(shè)項目(13DZ2295300)

孔祥東(1990-),男,碩士生,研究方向為化工過程優(yōu)化。E-mail:425589306@qq.com

錢 鋒,E-mail:fqian@ecust.edu.cn

TE624

A