蜉蝣算法在供應(yīng)鏈庫(kù)存優(yōu)化中的應(yīng)用

趙文丹, 韓雪

(沈陽(yáng)化工大學(xué)信息工程學(xué)院, 沈陽(yáng) 110142)

隨著經(jīng)濟(jì)和技術(shù)的快速發(fā)展,科學(xué)研究和工業(yè)生產(chǎn)中出現(xiàn)了大量的優(yōu)化問題,針對(duì)解決生產(chǎn)中優(yōu)化問題,許多群智能算法被提出。蜉蝣算法是由Zervoudakis等[1]在2020年提出的一種新型元啟發(fā)式算法,該算法以蜉蝣交配繁殖產(chǎn)生下一代的方式在空間中搜索,結(jié)構(gòu)簡(jiǎn)單。與其他元啟發(fā)式算法一樣,蜉蝣算法本身容易陷入局部最優(yōu),尋優(yōu)精度不高、求解結(jié)果過差的特點(diǎn)。通常有兩種方法可以提高蜉蝣算法的性能,第一類將蜉蝣算法與其他優(yōu)化理論和方法相結(jié)合。如王義等[2-3]引入融合Lévy飛行策略飛行軌跡來更新雄性蜉蝣速度,增加了蜉蝣種群多樣性,提高了全局搜索能力和收斂能力;Yi等[4]引入了可變步長(zhǎng)的Lévy飛行策略和自適應(yīng)算法,提高收斂速度和搜索精度;Shaheen等[5]、徐煥增等[6]采用混沌映射和蜉蝣之間的交配來尋找目標(biāo)函數(shù)的最優(yōu)解,增加種群多樣性同時(shí)提高種群密度;薛健侗等[7]、高新成等[8]將蜉蝣優(yōu)化算法引入K-means聚類分析中作為特征點(diǎn)提取,提出一種改進(jìn)的蜉蝣優(yōu)化算法。第二類為多個(gè)算法相結(jié)合來彌補(bǔ)單個(gè)算法的不足,提高算法的性能。劉書山等[9]將遺傳算法與模擬退火算法相結(jié)合提高收斂速度。

這些算法在各自的應(yīng)用領(lǐng)域中求解性能得到了改善,針對(duì)蜉蝣算法還有進(jìn)一步改善的空間。提出以下3種策略提升算法總體性能指標(biāo):一是引入自適應(yīng)慣性權(quán)重因子并提出改進(jìn)吸引力系數(shù),平衡搜索能力和局部開發(fā)能力。二是提出中值策略,加強(qiáng)種群間信息交流。Appiah等[10]將基于中值方法與動(dòng)態(tài)規(guī)劃結(jié)合在一起應(yīng)用于圖像降噪問題的研究。三是采用正弦余弦策略,增強(qiáng)全局搜索能力。Zhao等[11]將黃金正弦與交叉策略組合來處理優(yōu)化問題;正弦方法也被引入到其他優(yōu)化算法中,如差分進(jìn)化算法[12]、混沌優(yōu)化[13]與麻雀算法[14]。因此,正弦策略在蜉蝣算法(mayfly algorithm,MA)中的應(yīng)用也可以提高其探索和收斂性能。許多專家和學(xué)者相繼將不同的群智能優(yōu)化算法引入比例-積分-微分(proportion-integration-differentiation,PID)參數(shù)優(yōu)化中[15-17]。此外,這些方法有其優(yōu)點(diǎn),但也存在陷入局部最優(yōu)解和過早收斂等常見問題,因此,將改進(jìn)的算法用于供應(yīng)鏈庫(kù)存系統(tǒng)模型中,整定PID參數(shù),使系統(tǒng)達(dá)到更優(yōu)的指標(biāo)。

現(xiàn)提出多策略自適應(yīng)蜉蝣算法,在迭代前期執(zhí)行中值策略,為了彌補(bǔ)中值策略的不足,增加收斂速度,在迭代后期執(zhí)行正弦余弦策略,并改進(jìn)自適應(yīng)慣性權(quán)重因子。

1 基本的蜉蝣算法

蜉蝣算法的靈感來自蜉蝣交配過程,每只蜉蝣在空間位置上代表了問題的可行解,算法的工作原理如下:先產(chǎn)生兩組蜉蝣,分別代表雄性和雌性種群,每只蜉蝣的位置為x,在d維空間中表示為x=(x1,x2,…,xd),根據(jù)目標(biāo)函數(shù)f(x)對(duì)其性能進(jìn)行評(píng)價(jià)。設(shè)蜉蝣的速度v=(v1,v2,…,vd),蜉蝣的飛行方向是個(gè)體和社會(huì)經(jīng)驗(yàn)的交互作用,而每只蜉蝣會(huì)調(diào)整自己的軌跡,朝著個(gè)體最優(yōu)以及全局最優(yōu)位置移動(dòng)。

1.1 雄性蜉蝣的運(yùn)動(dòng)更新

(1)

雄性蜉蝣在水面上表演舞蹈,考慮到?jīng)]有很快的速度,蜉蝣不斷的移動(dòng),速度更新為

(2)

(3)

為了得到更好的位置,團(tuán)隊(duì)中最好的蜉蝣繼續(xù)表演舞蹈,更新它的速度,即

(4)

式(4)中:d為舞蹈系數(shù),設(shè)為5;r為取值[-1,1]的隨機(jī)系數(shù)。

1.2 雌性蜉蝣的運(yùn)動(dòng)更新

雄性蜉蝣容易聚集而雌性蜉蝣不會(huì)群體聚集,但是雌性蜉蝣會(huì)飛來與雄性蜉蝣交配繁殖。雌性蜉蝣的位置通過增加速度來更新,位置更新為

(5)

(6)

(7)

1.3 蜉蝣交配

雄性蜉蝣根據(jù)適應(yīng)度函數(shù)選擇雌性蜉蝣進(jìn)行交配。此外,具有最佳適應(yīng)度的雄性和最優(yōu)適應(yīng)度雌性進(jìn)行交配,交配的結(jié)果是產(chǎn)生適應(yīng)度最優(yōu)個(gè)體off1、適應(yīng)度次優(yōu)個(gè)體off2,公式如下。

off1=Lmale+(1-L)female

(8)

off2=Lfemale+(1-L)male

(9)

式中:L為[-1,1] 內(nèi)的隨機(jī)值;后代的初始速度被設(shè)定為0;male為父本;female為母本。

2 改進(jìn)蜉蝣算法

2.1 策略一:非線性重力系數(shù)和吸引力增強(qiáng)因子

蜉蝣優(yōu)化算法的重力系數(shù)類似于粒子群算法中的重力,有助于實(shí)現(xiàn)開采和勘探之間的平衡。采用的非線性重力系數(shù),使重力系數(shù)在開始迭代時(shí)緩慢減小,具有更好的探索開發(fā)能力,避免陷入局部最優(yōu),并能快速達(dá)到收斂精度,在迭代后期,重力系數(shù)減小,提高尋找最優(yōu)解的能力,引進(jìn)非線性重力系數(shù)公式,但隨著距離的增加,吸引力值開始迅速下降。為防止對(duì)遠(yuǎn)處的蜉蝣幾乎沒有吸引力,增加算法無效迭代的次數(shù),引進(jìn)吸引力增強(qiáng)因子K。

(10)

(11)

式中:g(t)為重力系數(shù);t為迭代次數(shù);Maxt為最大迭代次數(shù);h、b為常數(shù),初始值設(shè)為10、100。將重力系數(shù)及吸引力增強(qiáng)因子引入蜉蝣算法,雄性蜉蝣速度更新公式為

(12)

雌性蜉蝣速度更新公式為

(13)

2.2 策略二:引入中值策略

在統(tǒng)計(jì)學(xué)中,中值和平均值通常用于反映總體平均水平。在群體智能算法中,在空間搜索的初始階段,群體中個(gè)體的分布相對(duì)分散,并且有些個(gè)體的位置非常差。因此,提出了基于中值概念的群體中值位置,根據(jù)目標(biāo)函數(shù)值對(duì)所有蜉蝣個(gè)體進(jìn)行排序,在迭代前期,將蜉蝣的中值位置作為群體的中值位置,小組的每個(gè)成員,無論好壞,都可以貢獻(xiàn)自己的信息來影響整個(gè)運(yùn)動(dòng),增加種群多樣性,使其能夠跳出局部最優(yōu)解。

(14)

式(14)中:n為組數(shù),個(gè)體中值位置用作組的平均位置,加強(qiáng)信息交流,雄性蜉蝣速度更新表達(dá)式為

(15)

2.3 策略三:正弦余弦策略

由式(1)的位置更新公式可知,第i只蜉蝣位置會(huì)根據(jù)i只和第i-1只蜉蝣位置的中點(diǎn)進(jìn)行更新。在此過程中并沒有判斷xi是否優(yōu)于原來位置,這種單方向根據(jù)第i只蜉蝣更新位置,使種群收斂速度變慢。為使種群間信息利用率提高,提高收斂速度與精度,引入正弦余弦算法嵌入到蜉蝣算法中,一方面彌補(bǔ)蜉蝣算法位置更新的依賴性,無論正弦還是余弦都促使最優(yōu)信息在種群間傳遞,另一方面加強(qiáng)蜉蝣個(gè)體在不同搜索空間的全局搜索和局部開發(fā)。位置更新為

(16)

r1=a-ta/Maxt

(17)

引入正弦余弦算法作為局部?jī)?yōu)化算子嵌入蜉蝣算法中,在迭代后期,交配繁殖中產(chǎn)生子代off1、off2,對(duì)全部蜉蝣個(gè)體采用正弦余弦操作,更新位置公式為

(18)

(19)

2.4 算法的步驟

該算法將整個(gè)種群分為雌性和雄性兩個(gè)種群,兩個(gè)種群分別執(zhí)行不同的策略,并在種群間相互學(xué)習(xí),以兼顧全局搜索能力和局部收斂能力。對(duì)于雄性,前期為N1;對(duì)于雌性,前期為N2。在算法的后期全體種群執(zhí)行正弦余弦策略,流程圖如圖1所示。

圖1 蜉蝣算法流程圖Fig.1 Flowchart of the mayfly algorithm

N1=α1Maxt

(20)

N2=α2Maxt

(21)

式中:α1=0.3;α2=0.5。

3 工程算例

為保證函數(shù)多樣性,選取20種測(cè)試函數(shù)由于篇幅有限展示8種,名稱分別為:Sphere、Schwefel 2.22、Schwefel 2.21、Rosenbrock、Rastrigin、Ackley、Griewank、Hartman 3。為了測(cè)試改進(jìn)蜉蝣算法的性能,選取特定的幾種流行智能算法進(jìn)行比較,并采用粒子群算法(particle swarm optimization,PSO)、蜉蝣算法(MA)、改進(jìn)后蜉蝣算法(improved mayfly algorithm,IMA)、螢火蟲算法(firefly algorithm,FA),實(shí)驗(yàn)結(jié)果基于30次獨(dú)立運(yùn)行的這些性能指標(biāo)的分析,包括30次獨(dú)立測(cè)試的平均值、標(biāo)準(zhǔn)偏差、最佳函數(shù)值,最好的優(yōu)化結(jié)果用粗體表示,如表1所示。不同函數(shù)的平均收斂曲線如圖2所示。

表1 不同基準(zhǔn)函數(shù)結(jié)果比較Table 1 Comparison of results of different reference functions

圖2 F1～F4函數(shù)平均收斂曲線Fig.2 Average convergence curve of function F1 to function F4

3.1 基準(zhǔn)函數(shù)測(cè)試

從精度上看:F1、F2、F4、F8上,MOA均達(dá)到精度最高,F1、F2、F4、F8中MOA達(dá)到收斂速度最快。對(duì)于F3來說,PSO算法精度最高,MOA算法精度第二,收斂速度方面MA達(dá)到最優(yōu);MOA其次;對(duì)F5、F8來說,FA的收斂效率最高,MOA其次;其中,對(duì)于F1、F2、F4、F6來說,MOA在收斂精度上具有顯著的優(yōu)勢(shì),在F1、F2、F4、F6上,MOA在收斂效率上具有顯著優(yōu)勢(shì)。因此,MOA算法在大多數(shù)函數(shù)上精度最高,在絕大多數(shù)函數(shù)上,收斂速度最快。

3.2 工程算例

蜉蝣算法優(yōu)化PID參數(shù)用于供應(yīng)鏈系統(tǒng),三級(jí)供應(yīng)鏈由客戶、零售商、分銷商和供應(yīng)商組成,運(yùn)作方式是由客戶訂單拉動(dòng)的,零售商根據(jù)自身庫(kù)存判斷是否向上級(jí)訂貨,其中訂貨策略設(shè)為信息流用虛線表示,發(fā)貨策略表示為物料流用實(shí)線表示,如圖3、圖4所示。

圖3 三級(jí)供應(yīng)鏈中物料流與信息流Fig.3 Material flow and information flow in three-level supply chain

圖4 供應(yīng)鏈系統(tǒng)組成圖Fig.4 Supply chain system composition diagram

在MATLAB2018b中,用正弦信號(hào)模擬客戶三種產(chǎn)品的訂單,按照控制率零售商向上級(jí)訂貨,控制率為

ui=KP1(ukl-Invi)

(22)

Ui=KP1uln+KP2unm+KP3um

(23)

式中:u為下級(jí)向上級(jí)的訂單;i為節(jié)點(diǎn),i=o、l、n、m分別為客戶、零售商、分銷商、供應(yīng)商節(jié)點(diǎn);Inv為固定庫(kù)存;U為總訂單;KP1、KP2、KP3為庫(kù)存基本控制對(duì)應(yīng)的參數(shù)。

(24)

式(24)中:TC為供應(yīng)鏈總成本;k為節(jié)點(diǎn),分別表示供應(yīng)商、分銷商、零售商的節(jié)點(diǎn);p為客戶的數(shù)量;PCi為各節(jié)點(diǎn)生產(chǎn)成本;SCi為各節(jié)點(diǎn)單位存儲(chǔ)成本;TRCi為各節(jié)點(diǎn)單位運(yùn)輸成本;Wi為產(chǎn)品該節(jié)點(diǎn)生產(chǎn)單價(jià);Mi為該節(jié)點(diǎn)儲(chǔ)存單價(jià);ui為客戶向零售商訂貨量;τ為時(shí)間常數(shù)。

3.3 算法的流程

根據(jù)上述蜉蝣算法在供應(yīng)鏈PID參數(shù)優(yōu)化中的算法流程,具體步驟如下。

步驟1設(shè)置雄性蜉蝣、雌性蜉蝣以及后代的數(shù)量,設(shè)置學(xué)習(xí)因子、能見度系數(shù)和舞蹈系數(shù)等參數(shù);根據(jù)上述參數(shù),初始化種群的速度和位置,將供應(yīng)鏈的成本TC作為優(yōu)化算法的適應(yīng)度函數(shù)。

步驟2使用Simulink工具建立供應(yīng)鏈系統(tǒng)仿真模型,如圖4所示,然后開始迭代,計(jì)算每個(gè)蜉蝣的適應(yīng)度函數(shù)值,對(duì)值進(jìn)行排序,同時(shí)計(jì)算gbest、pbest和pm。

步驟3更新雄性蜉蝣和雌性蜉蝣的速度和位置,以及雄性蜉蝣和雌性蜉蝣之間的交配。

步驟4計(jì)算后代的適應(yīng)度函數(shù)值以及變異的適應(yīng)度函數(shù)值,更新個(gè)體適應(yīng)度和全局適應(yīng)度更新全局最優(yōu)值。

步驟5判斷迭代次數(shù)是否達(dá)到最大值,達(dá)到最大迭代次數(shù)則輸出結(jié)果,若沒有,則返回步驟2。

在確保參數(shù)優(yōu)化結(jié)果正確情況下,為了更加符合現(xiàn)實(shí)情況,把三級(jí)訂貨策略中KP的邊界設(shè)置為[0.1,10]、[0.1,5]、[0.1,5],周期運(yùn)行時(shí)間Ts設(shè)為300 s,最大迭代次數(shù)Tmax為100。每個(gè)算法獨(dú)立運(yùn)行30次,改進(jìn)后的蜉蝣算法與基本蜉蝣算法、粒子群算法、螢火蟲算法進(jìn)行比較,每個(gè)算法的參數(shù)設(shè)置如表2所示。優(yōu)化后供應(yīng)鏈成本如圖5所示。

表2 算法初始設(shè)定值Table 2 The initial setting of the algorithm

圖5 不同算法優(yōu)化供應(yīng)鏈成本結(jié)果對(duì)比Fig.5 Comparison of supply chain cost optimization results by different algorithms

將改進(jìn)后的蜉蝣算法應(yīng)用于三級(jí)供應(yīng)鏈庫(kù)存模型中,FA算法易陷入局部最優(yōu)解,MA算法收斂速度慢,PSO算法收斂精度沒有達(dá)到。MOA能夠避免陷入局部最優(yōu)解,同時(shí)成本減少9.5%,證明MOA用于供應(yīng)鏈庫(kù)存模型中有更快的收斂速度,更高的收斂精度。

4 結(jié)論

針對(duì)基本蜉蝣算法全局搜索能力不足、局部容易陷入最優(yōu)的現(xiàn)狀提出了多策略混合優(yōu)化的蜉蝣算法。一方面,受粒子群算法中慣性權(quán)重因子改進(jìn)的啟發(fā),引入了先慢后快的非線性慣性權(quán)重因子,在此基礎(chǔ)上又提出改進(jìn)種群間吸引力系數(shù)。另一方面,提出了組中值位置概念,并將其應(yīng)用于蜉蝣算法的速度更新中。通過8組測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)驗(yàn)證,證明改進(jìn)后的蜉蝣算法MOA在搜索速度、收斂精度上要優(yōu)于其他算法,并且優(yōu)勢(shì)明顯。同時(shí),將改進(jìn)后的MOA應(yīng)用在供應(yīng)鏈PID參數(shù)優(yōu)化上,通過優(yōu)化各節(jié)點(diǎn)訂貨策略降低供應(yīng)鏈總成本9.5%,通過MOA整定的PID參數(shù)可以使供應(yīng)鏈庫(kù)存系統(tǒng)有更好的性能。證明了MOA在實(shí)際應(yīng)用上的適用性。