煙花算法在聯合補貨問題中的應用研究

崔京城 瞿慧

摘要：煙花算法作為一種新型群體智能優化算法，在眾多領域得到成功應用。聯合采購品種的不斷擴大對算法性能提出了巨大挑戰。針對聯合補貨問題設計了基于煙花算法的求解方案，并利用基礎算例證明方案有效性。隨機生成的大規模算例表明，煙花算法相較于混合差分進化算法，在求解大規模聯合補貨問題時可獲得更優的近似最優解，具有更快的收斂速度和更高的穩定性，驗證了煙花算法在混合整數規劃方面的應用效果。

關鍵詞：煙花算法;聯合補貨;資源整合

DOI：10.11907/rjdk.192329 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP319文獻標識碼：A 文章編號：1672-7800（2020）006-0176-06

0 引言

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

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

本文首次嘗試應用FWA算法求解JRP問題，針對該問題設計基于FWA的JRP求解方案，通過已有文獻中JRP的基本算例進行計算，驗證求解方案和FWA有效性。為應對實踐聯合采購規模不斷擴大的趨勢，設計不同維度的JRP，生成隨機算例，將FWA運行結果與目前廣泛應用于聯合補貨問題的混合差分進化算法運行結果進行對比，證明FWA算法具有較強的尋優能力、魯棒性和收斂速度。

1 聯合補貨問題概述

經典聯合補貨問題（Joint Replenishment Problem，JRP）的假設條件與經濟訂貨批量模型比較相似，它假設每種物品的需求速度是均勻已知的，不允許缺貨，沒有數量折扣，訂貨后物品可立即得到補充，庫存持有成本為線性。JRP的目標是使總年平均成本最小化，總年平均成本由固定訂購費用、可變訂購費用和庫存持有費用3部分組成。聯合補貨策略主要通過將不同時期的采購物品按一定分組規則進行分組，對組內物品進行聯合采購，以達到經濟規模效益和分攤主要訂貨成本的目的，從而降低總采購成本。對聯合補貨策略而言，主要有兩種分組策略，即直接分組（Direct Grouping Strategy，DGS）與間接分組（Indirect Grouping Strategy，IGS）。為方便后續描述，對模型中使用的符號進行說明，如表1所示。

1.1 基于間接分組的聯合補貨模型

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

年庫存持有成本為：

目標是確定各個k_i和T，使總成本最小。

1.2 基于直接分組的聯合補貨模型

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

Eijs等對這兩種策略進行了對比，得出當主要準備費用比較高時，間接分組策略比直接分組策略更好。

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

2 煙花算法

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

2.1 爆炸運算

煙花算法爆炸運算中涉及兩個主要爆炸算子：每個煙花爆炸產生的火花數和爆炸半徑，前一個算子控制爆炸強度，后一個算子控制爆炸幅度。

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

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

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

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

2.2變異運算

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

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

其中，Gaussian（·）為高斯函數。

2.3 映射規則

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

2.4 選擇運算

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

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

3 基于煙花算法的聯合補貨模型求解方案設計

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

智能優化算法在進行應用之前，必須針對問題特點，對決策變量和目標函數進行分析，設計合理的編碼解碼機制，這是算法順利實施的前提。

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

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

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

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

（1）初始化。對算法參數、問題參數進行初始化。同時，根據編碼方式，結合求解算法初始化種群。

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

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

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

（5）合并爆炸火花和高斯變異火花，按2.3節的規則對出界火花進行處理。

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

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

4 仿真實驗與結果分析

4.1 參數設置

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

由于FWA在迭代過程中，爆炸火花總數是動態的，如果直接以進化次數作為迭代終止條件，則可能導致FWA參與尋優個體遠遠多于HDE和HSDE，缺乏比較的公平性。當火花總量（即參與尋優的個體數量）達到問題維度dim*10000時，FWA算法停止。據此，對應地將HDE和HSDE算法進化代數設為round（dim*10000/Np）（Np為種群數量）。盡管該設置方式會使FWA參與迭代的個體數偏多，但可達到相對公平性。

4.2 算例分析

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

結合表5、圖4-圖6可看出：

（1）在求解質量上，對于基礎算例，FWA可得到與文獻相同的最好最優解;當問題規模為10、50時，3種算法均能100%找到相同的最好最優解;當問題規模擴大到聯合采購100種物品時，無論是采用間接分組策略還是直接分組策略，FWA計算的最好最優解質量優于其它兩種算法。

（2）在收斂速度上，FWA可在偏離最好最優解最遠的情況下，快速收斂到最好最優解，在直接分組策略下的優勢更為明顯。

5 結語

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