基于人工蜂群算法的食品供應鏈召回優(yōu)化

陸 欣， 沈艷霞 ， 張君繼

(江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫214122)

近年來，各類由于原料問題導致的食品質量安全事故頻發(fā)，引起了食品質量監(jiān)管部門、加工企業(yè)與消費者的重視［1］。消費者迫切要求監(jiān)管部門建立起食品供應鏈的全程追溯系統(tǒng)，在食品質量出現(xiàn)問題后，企業(yè)能夠及時追蹤到發(fā)生質量問題的源頭并召回相關批次，將危害降到最低［2］。從農場到餐桌的食品供應鏈包括原料的供應、食品的加工、物流、餐飲等環(huán)節(jié)［3］。其中最為重要的是加工環(huán)節(jié)，加工流程與加工工藝直接改變了食品的性狀，也增加了追溯的難度。因此，實現(xiàn)食品加工環(huán)節(jié)的召回優(yōu)化，對食品的供應鏈全程追溯有重要意義。

將電子和通信技術應用到食品追溯領域，如二維碼和RFID 技術，能夠準確有效地溯源并在發(fā)生食品質量危機時實現(xiàn)召回，但這些技術無助于減小召回規(guī)模。在發(fā)生食品質量安全事故時，企業(yè)必須對存在潛在質量問題的全部批次產(chǎn)品召回和銷毀，這影響了企業(yè)對于建立供應鏈追溯的積極性［4］。只有兼顧消費者和食品加工企業(yè)的利益，在食品加工環(huán)節(jié)對原材料批次分散進行優(yōu)化，降低召回規(guī)模，減小損失，提高召回效率，監(jiān)管部門才能建立起有效的食品供應鏈全程追溯系統(tǒng)［5］。

針對食品供應鏈加工環(huán)節(jié)的召回優(yōu)化問題，國內外學者展開了相關研究。Dorp 等［6］采用高津托圖(Gozinto graphs)描 述 追 溯 模 型;Dupuy 等［7］在Dorp 基礎上，根據(jù)法國香腸加工業(yè)的實際情況提出批次分散(Batch dispersion)模型，并給出該模型的混合整數(shù)線性規(guī)劃 (Mixed-Integer Linear Programming，MILP)，同時采用LINGO 進行優(yōu)化求解;Dabbene 等［8］基于批次分散模型，提出最壞召回代價和平均召回代價，同時采用3 層模型對評估指標進行優(yōu)化;Lobna 等［9］給出了模型形式化描述，并分析算法強度，指出該模型為NP 難度問題，提出啟發(fā)式算法進行求解;Tamayo 等［10］提出用遺傳算法優(yōu)化該追溯模型，但僅適用于小規(guī)模的召回模型;李鋒等［11］通過分段門限粒子替換策略的改進粒子群算法進行優(yōu)化，取得了較為滿意的效果。但改進粒子群算法所需選擇門限參數(shù)多達7 個，在實際復雜生產(chǎn)環(huán)節(jié)中，很難保證參數(shù)設置的合理性，實際應用效果有限。

Karaboga 等［12］于2005 年提出了人工蜂群算法(Artificial Bee Colony，ABC)，它是一種基于蜜蜂采蜜行為的群智能優(yōu)化算法。該算法的主要特點是設置參數(shù)少、收斂速度快、求優(yōu)精確度高，通過人工蜂群個體的局部尋優(yōu)，從而在群體中凸顯全局最優(yōu)值。該算法提出之后，已被用于求解旅行商問題、車輛路徑問題、車間調度問題，都取得了較好的求解效果，有效地解決了高維、多極值、多約束等工程問題［13-14］。

因此，文中提出將人工蜂群算法應用到食品供應鏈追溯系統(tǒng)召回優(yōu)化問題。首先對食品加工環(huán)節(jié)進行分析，給出食品召回的批次分散模型;然后針對多層批次分散模型巨大，難以求解的問題，引入人工蜂群算法進行優(yōu)化求解，提高優(yōu)化性能。

1 食品加工環(huán)節(jié)批次分散模型

食品供應鏈全程追溯系統(tǒng)，可對加工環(huán)節(jié)進行批次分散優(yōu)化，在發(fā)生食品安全事件后能有效減少召回批次［15］。食品加工環(huán)節(jié)批次分散模型及追溯示意如圖1 所示。

圖1 食品加工環(huán)節(jié)批次分散模型及追溯示意Fig.1 Tracking and tracing model based on batch

圖1 中食品加工環(huán)節(jié)分成原料、部件、半成品、成品4 個層次。模型將加工流程抽象化為分解、組合、包裝3 個步驟。在加工流程中，同一種類的不同批次按照優(yōu)化后的分解比例、組合比例、包裝比例加工為成品。當食品質量安全事件發(fā)生后，首先根據(jù)成品批次，自下而上溯源到原料批次，然后再根據(jù)原料批次，自上而下追蹤到所有包含該原料批次的成品批次，實現(xiàn)召回。

根據(jù)圖1 給出的分散批次模型，定義食品加工環(huán)節(jié)4 個層次批次集合。包括J 個批次的原料R，K個批次的部件C，M 個批次的半成品S，H 個批次的成品F。集合定義如下

定義從原料Rj到部件Ck的分解比例為RCjk，即Ck占Rj的比例;從部件Ck到半成品Sm的組合比例為CSkm，即Ck占Sm的比例;從半成品Sm到成品Fh包裝比例為SFmh，即Sm占Fh的比例。滿足如下關系式

在實際加工環(huán)節(jié)中，考慮到生產(chǎn)線的效率、倉儲容量、人員限制等經(jīng)濟因素，部件與半成品的數(shù)量要在一定范圍之內［16］。定義部件和半成品數(shù)量約束式如下:

定義從原料到成品的批次分散布爾變量為Bjh，即批次為h 的成品中是否包含有批次為j 的原料。若包含，則布爾變量Bjh 為1，否則為0。同理，定義加工環(huán)節(jié)相鄰層次間的布爾變量分別為，滿足以下關系

根據(jù)Dabbene 等提出的分散批次規(guī)模BDC，最壞召回規(guī)模定義為

當原料批次Rj出現(xiàn)質量問題時，所有包含該批次原料的成品都需要被召回。定義平均召回規(guī)模為

基于以上定義，以平均召回規(guī)模ARC 式(13)為目標函數(shù)，以式(5)～式(7)為數(shù)量等式約束，以式(8)、式(9)為數(shù)量不等約束，給出食品供應鏈加工環(huán)節(jié)召回優(yōu)化模型:

該批次分散模型涉及較多變量和約束，在滿足約束的基礎上，對批次分散情況進行優(yōu)化，達到平均召回規(guī)模最小的目標。該優(yōu)化問題為典型NP 難度問題，較難求解，故采用智能算法進行求解。

2 基于人蜂群算法的召回優(yōu)化策略

2.1 人工蜂群算法模型

人工蜂群算法模型包含3 個要素:蜜源、雇傭蜂、非雇傭蜂［17］。雇傭蜂尋找蜜源，并將信息與其他蜜蜂按概率分享。非雇傭蜂分為跟隨蜂和偵查蜂，跟隨蜂通過雇傭蜂分享的信息尋找高收益蜜源，偵查蜂隨機搜索新蜜源。該模型包含3 種基本行為:蜜源招募蜜蜂，搜索蜜源，放棄蜜源。以上元素組成基本行為模式的自組織過程，本質上是一種通過蜜蜂個體的局部尋優(yōu)行為凸顯全局最優(yōu)的尋優(yōu)方式。人工蜂群算法主要步驟如圖2 所示。

圖2 人工蜂群算法步驟Fig.2 Main steps of the ABC algorithm

設蜜源、跟隨蜂、雇傭蜂數(shù)量為SN，雇傭蜂重復搜索限制次數(shù)LIM，最大迭代次數(shù)MCN。首先，根據(jù)在搜索空間隨機產(chǎn)生SN 個初始蜜源位置(初始解)xp，每個解xp是一個D 維向量。搜索開始后，每個雇傭蜂通過式(15)在初始位置附近隨機尋找新蜜源(新解):

式中vpq為隨機尋找新蜜源，t ∈{1，2，…，SN}，q ∈{1，2，…，D}，p 與q 隨機選取且p ≠q，φpq為［－1，1］的隨機數(shù)，對應初始解的fitp鄰域。檢驗新解是否優(yōu)于舊解，若新解優(yōu)，則忘記舊解;反之，保留舊解。雇傭蜂完成搜索過程后，返回蜂巢把解的信息和fitp信息共享給跟隨蜂，跟隨蜂根據(jù)式(16)計算每個解的概率:

跟隨蜂在［0，1］內產(chǎn)生一個隨機數(shù)，如果解的概率大于該隨機數(shù)，則跟隨蜂根據(jù)式(15)產(chǎn)生一個新解，并檢驗fitp是否比舊解好，記住優(yōu)解。如果在LIM 次數(shù)之內不能改良，則該蜜源被舍棄，同時該雇傭蜂轉變成非雇傭蜂。偵查蜂通過式(17)產(chǎn)生一個新蜜源代替被舍棄的蜜源:

同時，該偵查蜂轉變成雇傭蜂，重復循環(huán)。雇傭蜂進行貪婪算法時，按式(18)進行選擇:

對于優(yōu)化函數(shù)為最大值問題，適應度函數(shù)即目標函數(shù);對于優(yōu)化目標為最小值問題，適應度函數(shù)用式(19)表示:

2.2 基于人蜂群算法的召回優(yōu)化

文中所述的食品供應鏈召回模型有較多約束，首先將等號約束轉化成不等約束，并引入內懲罰函數(shù)解決不等約束的問題［18］，設控制誤差| hj|≤ω，ω = 0.001，懲罰因子縮小系數(shù)γ1，γ2，γ3∈(0，1)，λ1，λ2，λ3，λ4∈(0，1)，將約束轉化為無約束優(yōu)化問題。目標函數(shù)如下

式中:Ck為k 批次部件C 的數(shù)量;Sm為m 批次半成品S 的數(shù)量;λ1，λ2，λ3，λ4為Ck與Sm超出部件和半成品數(shù)量約束的懲罰系數(shù)。∑RtCab，∑CtSbc，∑StFcd為相鄰加工環(huán)節(jié)批次分散比例之和;γ1，γ2，γ3為比例之和超出范圍的懲罰系數(shù)。

文中將相鄰加工環(huán)節(jié)的批次分散比例設置為優(yōu)化變量。圖3 為原料RM1，RM2分解成部件CM1，CM3的分散比例，［X1，X2，X3…，X36］為R1，R2，R3，R4，R5，R6分解至C1，C2，C3，C7，C8，C9的批次分散比例矩陣。

圖3 批次分散比例Fig.3 Proportion of batch dispersion

下面給出文中提出的食品召回優(yōu)化方法的實現(xiàn)步驟:

1)初始化。設置相關參數(shù)，雇傭蜂與非雇傭蜂的種群數(shù)，蜜源個數(shù)，最大循環(huán)次數(shù)和最大迭代次數(shù)。每個蜜源xi代表了一個D 維解，每一維為相鄰環(huán)節(jié)批次分散比例矩陣。

2)依據(jù)部件和半成品的數(shù)量限制，設置尋優(yōu)范圍，并在尋優(yōu)范圍內產(chǎn)生隨機的解。

3)以平均召回規(guī)模ARC 為目標函數(shù)，并計算各個隨機解的適應度值fitxi。標記fitxi最小的值為優(yōu)秀蜜源。

4)雇傭蜂按式(15)在原蜜源附近尋找新蜜源，并與原蜜源比較，擇優(yōu)標記蜜源。

5)跟隨蜂在蜜源中按式(16)選擇合適蜜源，并與原蜜源比較，擇優(yōu)標記蜜源。

6)偵查蜂通過式(17)產(chǎn)生一個新蜜源代替被舍棄的蜜源。

7)判斷是否達到最大循環(huán)次數(shù)或者最大迭代次數(shù)，如果達到，轉至5)，否則轉至4)。

8)輸出各個批次部件和半成品的數(shù)量，即為最優(yōu)批次分散結果。

3 食品供應鏈召回算例及優(yōu)化

分析Dabbene 等給出的算例，針對原料的不同批次進行批次分散優(yōu)化，能夠更加準確地追溯包含某批次原料的成品，并減少召回規(guī)模。綜合文獻［7，10-11］給出的算例，適當調整參數(shù)，給出文中算例，對人工蜂群算法進行驗證，并進行性能對比。圖4 給出了算例分解比例、組合比例、包裝比例。其中

R = 12，C = 12，S = 12，F(xiàn) = 12，R1= 16 000，R2= 16 000，R3= 4 000，R4= 2 000，R5= 1 000，R6= 1 000，R7= 20 000，R8= 1 000，R9= 4 000，R10= 5 000，R11= 5 000，R12= 5 000，F(xiàn)1= 5 000，F(xiàn)2= 4 000，F(xiàn)3= 1 000，F(xiàn)4= 15 000，F(xiàn)5= 10 000，F(xiàn)6= 5 000，F(xiàn)7= 5 000，F(xiàn)8= 5 000， F9= 10 000，F(xiàn)10= 5 000，F(xiàn)11= 10 000，F(xiàn)12= 5 000。

圖4 召回優(yōu)化算例Fig.4 Example of batch dispersion optimization

設置MCN = 6 000，LIM = 200，SN = 100，搜索范圍為［1 000，20 000］，文中采用人工蜂群算法進行求解。得到如圖5 所示的優(yōu)化后各批次的分散情況。

圖5 優(yōu)化后批次分散情況Fig.5 Optimization result of the batch dispersion model

采用人工蜂群算法(ABC)和改進粒子群算法(MPSO)進行優(yōu)化性能對比。分別對比平均召回規(guī)模(ARC)，批次分散規(guī)模(BDC)，最壞召回規(guī)模(WRC)和運算時間(t)。改進粒子群算法的參數(shù)設置與文獻［11］相同。比較結果見表1，圖6 為2 種算法的平均召回規(guī)模收斂曲線。

表1 2 種優(yōu)化算法性能對比Tab.1 Performance comparison of two algorithms

圖6 平均召回規(guī)模收斂曲線Fig.6 Convergence rate curves of two algorithms

對比平均召回規(guī)模ARC，ABC 優(yōu)化后的平均召回規(guī)模為12 750，比MPSO 優(yōu)化結果降低了14.29%;對比批次分散規(guī)模BDC，ABC 的批次分散規(guī)模與MPSO 相同;對比最壞召回規(guī)模WRC，ABC優(yōu)化后的最壞召回規(guī)模略大于MPSO，考慮到最壞召回發(fā)生的可能性較低，且僅比MPSO 大1 000，因此在可接受范圍之內;對比運算開銷t，ABC 算法運算時間明顯小于MPSO，約為MPSO 的38.6%。MPSO 采用了分段門限替換策略，每個迭代周期都根據(jù)粒子的適應度函數(shù)進行最優(yōu)粒子替換，因而在進化初期，粒子快速向最優(yōu)解聚集，而在進化后期(迭代2 000 次之后)，采用了較小的替換門限，粒子的收斂速度減慢，運算開銷顯著增加(為ABC 算法的2.5 倍左右)。ABC 算法中蜜蜂相互分工與合作，收斂快(迭代1 000 次即趨于最優(yōu))、尋優(yōu)效果好。

4 結 語

針對食品供應鏈加工環(huán)節(jié)召回優(yōu)化的問題，給出了批次分散模型，引入人工蜂群算法優(yōu)化該模型。與文獻［11］提出的MPSO 法相比，文中提出的算法尋優(yōu)效果好、收斂速度快、復雜度不高，能夠有效減少平均召回規(guī)模，減小運算開銷。對于食品加工企業(yè)而言，平均召回成本這個性能指標的重要性遠大于最壞召回規(guī)模，在其他性能指標有大幅提高的前提下是可以接受的，因此適用于食品供應鏈召回優(yōu)化。

［1］Pizzuti T，Mirabelli G，Sanz-Bobi M A，et al.Food track and trace ontology for helping the food traceability control［J］.Journal of Food Engineering，2014，120:17-30.

［2］Dabbene F，Gay P，Tortia C.Traceability issues in food supply chain management:a review［J］.Biosystems Engineering，2014，120:65-80.

［3］Aung M M，Chang Y S.Traceability in a food supply chain:safety and quality perspectives［J］.Food Control，2014，39:172-184.

［4］Alfaro J A，Rábade L A.Traceability as a strategic tool to improve inventory management:a case study in the food industry［J］.International Journal of Production Economics，2009，118(1):104-110.

［5］Kramer M N，Coto D，Weidner J D.The science of recalls［J］.Meat Science，2005，71(1):158-163.

［6］Van Dorp C A. A traceability application based on gozinto graphs［C］//Proceedings of EFITA 2003 Conference. Debrecen，Hungary:IOS Press，2003.

［7］Dupuy C，Botta-Genoulaz V，Guinet A. Batch dispersion model to optimise traceability in food industry［J］. Journal of Food Engineering，2005，70(3):333-339.

［8］Dabbene F，Gay P. Food traceability systems:performance evaluation and optimization［J］. Computers and Electronics in Agriculture，2011，75(1):139-146.

［9］Kallel L，Benaissa M.A production model to reduce batch dispersion and optimize traceability［C］//Logistics (LOGISTIQUA)，2011 4th International Conference on.Hammamet:IEEE，2011:144-149.

［10］Tamayo S，Monteiro T，Sauer N. Deliveries optimization by exploiting production traceability information［J］. Enginering Applications of Artificial Intelligence，2009，22(4):557-568.

［11］李鋒，吳華瑞，朱華吉，等.基于改進粒子群算法的農產(chǎn)品召回優(yōu)化［J］.農業(yè)工程學報，2013，29(7):238-245.

LI Feng，WU Huarui，ZHU Huaji，et al. Optimization of agricultural products recall based on modified particle swarm algorithm［J］.Transactions of the Chinese Society of Agricultural Engineering，2013，29(7):238-245.(in Chinese)

［12］Karaboga D.An idea based on honey bee swarm for numerical optimization［R］.Kayzeri:Erciyes University，2005.

［13］張長勝.多目標人工蜂群算法及遺傳算法的研究與應用［M］.沈陽:東北大學出版社，2013.

［14］陳久梅.兩級定位-路徑問題的人工蜂群算法［J］.計算機工程，2014，40(1):172-176.

CHEN Jiumei.Artificial bee colony algorithm for two-echelon location-routing problem［J］.Computer Engineering，2014，40(1):172-176.(in Chinese)

［15］崔明，沈瑾，李延云，等.中國農產(chǎn)品加工技術現(xiàn)狀及其推廣體系的建設［J］.農業(yè)工程學報，2008，24(10):274-278.

CUI Ming，SHEN Jin，LI Yanyun，et al. Status of agricultural product processing technology and construction of its promotion system in China［J］.Transactions of the Chinese Society of Agricultural Engineering，2008，24(10):274-278.(in Chinese)

［16］Dhouib S，Dhouib S，Chabchoub H. Artificial bee colony metaheuristic to optimize traceability in food industry［C］//Advanced Logistics and Transport (ICALT)，2013 International Conference on.Sousse:IEEE，2013:417-420.

［17］雷秀娟.群智能優(yōu)化算法及其應用［M］.北京:科學出版社，2012.

［18］Karaboga D，Basturk B.On the performance of artificial bee colony (ABC)algorithm［J］.Applied Soft Computing，2008，8(1):687-697.