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

崔京城 瞿慧

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

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

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

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

0 引言

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

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

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

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

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

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

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

年庫(kù)存持有成本為：

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

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

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

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

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

2 煙花算法

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

2.1 爆炸運(yùn)算

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

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

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

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

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

2.2變異運(yùn)算

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

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

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

2.3 映射規(guī)則

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

2.4 選擇運(yùn)算

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

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

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

3.1 基于煙花算法的JRP問(wèn)題編碼解碼

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

4.2 算例分析

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

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

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

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

5 結(jié)語(yǔ)

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