煙花算法在聯(lián)合補(bǔ)貨問題中的應(yīng)用研究

崔京城 瞿慧

摘要：煙花算法作為一種新型群體智能優(yōu)化算法，在眾多領(lǐng)域得到成功應(yīng)用。聯(lián)合采購品種的不斷擴(kuò)大對算法性能提出了巨大挑戰(zhàn)。針對聯(lián)合補(bǔ)貨問題設(shè)計了基于煙花算法的求解方案，并利用基礎(chǔ)算例證明方案有效性。隨機(jī)生成的大規(guī)模算例表明，煙花算法相較于混合差分進(jìn)化算法，在求解大規(guī)模聯(lián)合補(bǔ)貨問題時可獲得更優(yōu)的近似最優(yōu)解，具有更快的收斂速度和更高的穩(wěn)定性，驗證了煙花算法在混合整數(shù)規(guī)劃方面的應(yīng)用效果。

關(guān)鍵詞：煙花算法;聯(lián)合補(bǔ)貨;資源整合

DOI：10.11907/rjdk.192329 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP319文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2020）006-0176-06

0 引言

為響應(yīng)國家節(jié)能減排的號召，順應(yīng)采購全球化發(fā)展趨勢，眾多大中型制造業(yè)、零售業(yè)企業(yè)逐步認(rèn)識到資源整合利用是企業(yè)成本控制的關(guān)鍵，并在實際運作中聯(lián)合同行或供應(yīng)鏈合作者進(jìn)行采購、運輸資源的整合利用。例如，2016年蘇寧和天貓首次對部分商品進(jìn)行聯(lián)合采購，以節(jié)約采購和管理成本;白云山等6家藥企擬籌建聯(lián)合采購平臺。在這種運作模式下，聯(lián)盟企業(yè)不僅能分?jǐn)偛少彙⑦\輸過程中的固定成本，還能達(dá)到采購、運輸?shù)囊?guī)模效應(yīng)。隨著更多企業(yè)采用該模式，聯(lián)合補(bǔ)貨的品種規(guī)模越來越大，成本優(yōu)化時產(chǎn)生的數(shù)據(jù)量大幅增加。由于聯(lián)合補(bǔ)貨問題（Joint Replenishment Problem，JRP）已被證實為非確定性多項式困難（Non-deterministic Polynomial Hard，NP-hard）問題，問題規(guī)模的擴(kuò)大勢必對求解算法的性能提出更高要求。

2010年了an&Zhutzl根據(jù)煙花爆炸產(chǎn)生火花這一自然現(xiàn)象提出煙花算法（Fireworks Algorithm，F(xiàn)WA）。作為一種新穎的群體智能算法，其被成功應(yīng)用于眾多領(lǐng)域的優(yōu)化問題，如車間調(diào)度、設(shè)施選址、物流運輸調(diào)度、路徑優(yōu)化問題、倉庫系統(tǒng)布局、圖像識別與處理、施肥問題等。從現(xiàn)有研究來看，尚無文獻(xiàn)用FWA求解庫存組合優(yōu)化問題。

本文首次嘗試應(yīng)用FWA算法求解JRP問題，針對該問題設(shè)計基于FWA的JRP求解方案，通過已有文獻(xiàn)中JRP的基本算例進(jìn)行計算，驗證求解方案和FWA有效性。為應(yīng)對實踐聯(lián)合采購規(guī)模不斷擴(kuò)大的趨勢，設(shè)計不同維度的JRP，生成隨機(jī)算例，將FWA運行結(jié)果與目前廣泛應(yīng)用于聯(lián)合補(bǔ)貨問題的混合差分進(jìn)化算法運行結(jié)果進(jìn)行對比，證明FWA算法具有較強(qiáng)的尋優(yōu)能力、魯棒性和收斂速度。

1 聯(lián)合補(bǔ)貨問題概述

經(jīng)典聯(lián)合補(bǔ)貨問題（Joint Replenishment Problem，JRP）的假設(shè)條件與經(jīng)濟(jì)訂貨批量模型比較相似，它假設(shè)每種物品的需求速度是均勻已知的，不允許缺貨，沒有數(shù)量折扣，訂貨后物品可立即得到補(bǔ)充，庫存持有成本為線性。JRP的目標(biāo)是使總年平均成本最小化，總年平均成本由固定訂購費用、可變訂購費用和庫存持有費用3部分組成。聯(lián)合補(bǔ)貨策略主要通過將不同時期的采購物品按一定分組規(guī)則進(jìn)行分組，對組內(nèi)物品進(jìn)行聯(lián)合采購，以達(dá)到經(jīng)濟(jì)規(guī)模效益和分?jǐn)傊饕嗀洺杀镜哪康模瑥亩档涂偛少彸杀尽β?lián)合補(bǔ)貨策略而言，主要有兩種分組策略，即直接分組（Direct Grouping Strategy，DGS）與間接分組（Indirect Grouping Strategy，IGS）。為方便后續(xù)描述，對模型中使用的符號進(jìn)行說明，如表1所示。

1.1 基于間接分組的聯(lián)合補(bǔ)貨模型

在間接分組策略下，每類物品補(bǔ)貨周期T_i是T的整數(shù)倍k_i，則物品i的補(bǔ)貨周期為T_i=k_iT，物品t的補(bǔ)貨量為Q_i=D_iT_i=D_ik_iT。

年庫存持有成本為：

目標(biāo)是確定各個k_i和T，使總成本最小。

1.2 基于直接分組的聯(lián)合補(bǔ)貨模型

直接分組是直接將n種物品分為m組，每組均確定一個固定的補(bǔ)貨周期T_j（j=1，2，…，m），在每次訂貨時每組中的每個物品均需要進(jìn)行補(bǔ)貨。依據(jù)式（3），可以得出在直接分組策略下總年平均成本TC的公式。

Eijs等對這兩種策略進(jìn)行了對比，得出當(dāng)主要準(zhǔn)備費用比較高時，間接分組策略比直接分組策略更好。

綜上可知，間接分組模式下，物品不是預(yù)先進(jìn)行分組，而是根據(jù)各自補(bǔ)貨周期乘子k_i動態(tài)分組。在循環(huán)周期內(nèi)如果物品補(bǔ)貨周期乘子眾;具有倍數(shù)關(guān)系或相同公倍數(shù)（如1，2，3，2，1），則在其倍數(shù)或相同公倍數(shù)的補(bǔ)貨時期，對應(yīng)物品自動分配在一組進(jìn)行補(bǔ)貨（第2個時期——倍數(shù)關(guān)系，物品1、2、4、5一起補(bǔ)貨;第6個周期——相同公倍數(shù)，所有物品一起補(bǔ)貨），從而達(dá)到分組補(bǔ)貨的目的。簡而言之，間接分組是根據(jù)物品補(bǔ)貨周期動態(tài)分組，而直接分組則是直接劃分物品，劃分在一組的物品具有相同補(bǔ)貨周期。

2 煙花算法

研究者通過模擬煙花爆炸“由一到眾”產(chǎn)生新生代火花并照亮周圍區(qū)域的現(xiàn)象，提出煙花算法對種群個體進(jìn)行多點同時爆炸式搜索，使其在求解復(fù)雜的優(yōu)化問題時表現(xiàn)出非常優(yōu)良的性能。這種區(qū)別于傳統(tǒng)算法的新型搜索方法能夠在全局搜索和局部搜索中達(dá)到一個平衡，以更高的概率跳出局部最優(yōu)解的“坑”，避免出現(xiàn)“早熟”現(xiàn)象。煙花算法基本流程與其它群體智能優(yōu)化算法類似，包括3個基本運算：煙花爆炸、煙花變異和下一代煙花的選擇。煙花算法基本執(zhí)行流程如圖1所示。

2.1 爆炸運算

煙花算法爆炸運算中涉及兩個主要爆炸算子：每個煙花爆炸產(chǎn)生的火花數(shù)和爆炸半徑，前一個算子控制爆炸強(qiáng)度，后一個算子控制爆炸幅度。

（1）爆炸火花數(shù)。煙花算法通過該算子讓適應(yīng)度數(shù)值好的煙花產(chǎn)生的火花數(shù)較多，避免尋優(yōu)時火花個體總在最優(yōu)值附件擺動。反之，對于適應(yīng)度值差的火花，減少其產(chǎn)生的火花數(shù)，適度進(jìn)行其余空間探索。假設(shè)總共有N個煙花，則第i（i=1，2，…，N）個煙花x_i爆炸時產(chǎn)生的火花數(shù)量F_S_i計算公式為：

其中，SN為常數(shù)，用來限制產(chǎn)生的火花總數(shù);Y_worst為當(dāng)前種群中最差適應(yīng)度值;f（x_i）為個體x_i的適應(yīng)度值;ε為一個極小常數(shù)，避免出現(xiàn)除零運算。此外，為防止煙花爆炸產(chǎn)生的火花數(shù)過多或過少，對F_S_i進(jìn)行修正運算。

其中，round（·）為取整函數(shù);a、b為給定常數(shù)。

（2）爆炸半徑。該爆炸算子基本思想是讓適應(yīng)度數(shù)值好的煙花爆炸幅度較小，以實現(xiàn)很好的開采性能;適應(yīng)度數(shù)值差的煙花產(chǎn)生較大的爆炸幅度，對搜索空間有效勘探。第i（i=1，2，…，N）個煙花x_i爆炸半徑由式（7）得到。

2.2變異運算

為了增加種群多樣性，煙花算法利用高斯變異按照預(yù)設(shè)參數(shù)產(chǎn)生GN個高斯變異火花。第l（l=1，2，…，GN）個火花第k（k=1，2，…，z）維數(shù)值計算公式為：

x_l，k=x_l，k+Gaussian（1，1） （9）

其中，Gaussian（·）為高斯函數(shù)。

2.3 映射規(guī)則

煙花算法在執(zhí)行爆炸和變異的過程中，所產(chǎn)生的火花有可能超過原有解空間范圍，為了對超出邊界范圍的火花進(jìn)行修正，采用式（10）的映射規(guī)則進(jìn)行處理。

2.4 選擇運算

執(zhí)行爆炸運算和變異運算后，煙花、爆炸火花和高斯變異火花中的最優(yōu)個體自動保留到下一代，采用輪盤賭的方式選擇剩余N-1個個體，個體x_i被選擇的概率為：

其中d（x_i，x_j）表示個體x_i和個體x_j之間的歐式距離，M為煙花、爆炸火花和變異火花總數(shù)。

3 基于煙花算法的聯(lián)合補(bǔ)貨模型求解方案設(shè)計

3.1 基于煙花算法的JRP問題編碼解碼

智能優(yōu)化算法在進(jìn)行應(yīng)用之前，必須針對問題特點，對決策變量和目標(biāo)函數(shù)進(jìn)行分析，設(shè)計合理的編碼解碼機(jī)制，這是算法順利實施的前提。

因此，在間接分組策略下JRP問題的編碼解碼設(shè)計思路為：編碼時，隨機(jī)生成n維0-1之間的隨機(jī)數(shù);再通過變量上下界，對n維隨機(jī)數(shù)按式（14）進(jìn)行解碼得到補(bǔ)貨周期乘子，即可將補(bǔ)貨周期乘子帶人式（13）得到對應(yīng)的最優(yōu)成本值。

假設(shè)決策變量k_i的上界為10，JRP問題編碼解碼如圖2所示。

此時編碼和解碼方式同間接分組策略下的方式，由圖3可知，通過解碼，物品1分在第1組;物品2和物品3分在第2組，依次類推。

3.2 基于煙花算法的JRP求解流程

（1）初始化。對算法參數(shù)、問題參數(shù)進(jìn)行初始化。同時，根據(jù)編碼方式，結(jié)合求解算法初始化種群。

（2）計算初始煙花適應(yīng)度。首先按式（14）對個體進(jìn)行解碼，解碼過程中，按照文獻(xiàn)和文獻(xiàn)中的方法設(shè)置決策變量上下界。解碼后，在間接分組策略下，根據(jù)式（13）計算總成本;直接分組策略下，根據(jù)式（15）先分別計算每組物品的JRP成本，再對每組物品JRP成本進(jìn)行累加，得到總成本。

（3）按2.1節(jié)中的描述計算爆炸算子，執(zhí)行爆炸運算，得到爆炸火花。

（4）按2.2節(jié)中的描述執(zhí)行變異運算，得到高斯變異火花。

（5）合并爆炸火花和高斯變異火花，按2.3節(jié)的規(guī)則對出界火花進(jìn)行處理。

（6）按2.4節(jié)的方式，采用輪盤賭的方式從初始煙花、爆炸火花和高斯變異火花中選擇下一代煙花，并保存當(dāng)前最好值。

（7）判斷是否達(dá)到終止條件，如果迭代次數(shù)達(dá)到了既定的最大迭代次數(shù)或求解精度達(dá)到要求，則停止搜索操作，輸出最優(yōu)值;否則，對新煙花種群再次執(zhí)行步驟（3）-（6）中的操作，直至滿足條件為止。

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

4.1 參數(shù)設(shè)置

為測試、分析FWA求解JRP問題的性能，本文選取文獻(xiàn)中的問題參數(shù)（見表2），同時擴(kuò)大問題維度，隨機(jī)生成算例進(jìn)行仿真實驗。隨機(jī)算例問題參數(shù)見表3。FWA求解結(jié)果與目前應(yīng)用于JRP問題中表現(xiàn)良好的混合差分進(jìn)化算法（Hybrid Differential Evolution Algorithm，HDE）、混合自適應(yīng)差分進(jìn)化算法（Hybrid Self-adaptive Differential Evolution Algorithm，HSDE）的計算結(jié)果進(jìn)行比較，算法參數(shù)設(shè)置見表4。

由于FWA在迭代過程中，爆炸火花總數(shù)是動態(tài)的，如果直接以進(jìn)化次數(shù)作為迭代終止條件，則可能導(dǎo)致FWA參與尋優(yōu)個體遠(yuǎn)遠(yuǎn)多于HDE和HSDE，缺乏比較的公平性。當(dāng)火花總量（即參與尋優(yōu)的個體數(shù)量）達(dá)到問題維度dim*10000時，F(xiàn)WA算法停止。據(jù)此，對應(yīng)地將HDE和HSDE算法進(jìn)化代數(shù)設(shè)為round（dim*10000/Np）（Np為種群數(shù)量）。盡管該設(shè)置方式會使FWA參與迭代的個體數(shù)偏多，但可達(dá)到相對公平性。

4.2 算例分析

隨機(jī)性算例在不同規(guī)模下分別隨機(jī)生成5個問題，針對每個問題3種對比算法均在Matlab中分別運行20次，平均最好最優(yōu)廠C見表5。圖4和圖5分別為在間接分組策略下和直接分組策略下，3種算法分別運行基礎(chǔ)算例的收斂曲線。圖6為問題規(guī)模擴(kuò)大到100時，3種算法單次運行隨機(jī)生成算例的收斂曲線。

結(jié)合表5、圖4-圖6可看出：

（1）在求解質(zhì)量上，對于基礎(chǔ)算例，F(xiàn)WA可得到與文獻(xiàn)相同的最好最優(yōu)解;當(dāng)問題規(guī)模為10、50時，3種算法均能100%找到相同的最好最優(yōu)解;當(dāng)問題規(guī)模擴(kuò)大到聯(lián)合采購100種物品時，無論是采用間接分組策略還是直接分組策略，F(xiàn)WA計算的最好最優(yōu)解質(zhì)量優(yōu)于其它兩種算法。

（2）在收斂速度上，F(xiàn)WA可在偏離最好最優(yōu)解最遠(yuǎn)的情況下，快速收斂到最好最優(yōu)解，在直接分組策略下的優(yōu)勢更為明顯。

5 結(jié)語

本文首次嘗試采用煙花算法求解聯(lián)合補(bǔ)貨問題，設(shè)計了基于煙花算法的聯(lián)合補(bǔ)貨問題求解方案，通過已有文獻(xiàn)中的基礎(chǔ)算例驗證了求解方案和算法有效性;為應(yīng)對實踐中聯(lián)合采購規(guī)模不斷擴(kuò)大的趨勢，將問題規(guī)模擴(kuò)大到100，選取目前應(yīng)用效果較好的HDE算法、HSDE算法與該算法進(jìn)行對比分析，結(jié)果證明煙花算法在求解質(zhì)量、收斂速度和魯棒性方面表現(xiàn)更佳，可作為應(yīng)對大規(guī)模JRP問題及其拓展優(yōu)化問題的一個備選算法。本文是煙花算法在聯(lián)合補(bǔ)貨領(lǐng)域的探索性研究，針對擴(kuò)展的聯(lián)合補(bǔ)貨問題，如何結(jié)合問題特點和算法機(jī)理，對算法進(jìn)行改進(jìn)，使之更好地應(yīng)用于更復(fù)雜的現(xiàn)實問題是后續(xù)研究方向。