陸 欣， 沈艷霞 ， 張君繼

(江南大學(xué) 輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫214122)

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

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

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

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

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

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

食品供應(yīng)鏈全程追溯系統(tǒng)，可對(duì)加工環(huán)節(jié)進(jìn)行批次分散優(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 個(gè)層次。模型將加工流程抽象化為分解、組合、包裝3 個(gè)步驟。在加工流程中，同一種類的不同批次按照優(yōu)化后的分解比例、組合比例、包裝比例加工為成品。當(dāng)食品質(zhì)量安全事件發(fā)生后，首先根據(jù)成品批次，自下而上溯源到原料批次，然后再根據(jù)原料批次，自上而下追蹤到所有包含該原料批次的成品批次，實(shí)現(xiàn)召回。

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

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

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

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

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

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

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

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

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

2.1 人工蜂群算法模型

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

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

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

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

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

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

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

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

文中所述的食品供應(yīng)鏈召回模型有較多約束，首先將等號(hào)約束轉(zhuǎn)化成不等約束，并引入內(nèi)懲罰函數(shù)解決不等約束的問題［18］，設(shè)控制誤差| hj|≤ω，ω = 0.001，懲罰因子縮小系數(shù)γ1，γ2，γ3∈(0，1)，λ1，λ2，λ3，λ4∈(0，1)，將約束轉(zhuǎn)化為無(wú)約束優(yōu)化問題。目標(biāo)函數(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é)的批次分散比例設(shè)置為優(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)化方法的實(shí)現(xiàn)步驟:

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

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

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

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

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

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

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

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

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

分析Dabbene 等給出的算例，針對(duì)原料的不同批次進(jìn)行批次分散優(yōu)化，能夠更加準(zhǔn)確地追溯包含某批次原料的成品，并減少召回規(guī)模。綜合文獻(xiàn)［7，10-11］給出的算例，適當(dāng)調(diào)整參數(shù)，給出文中算例，對(duì)人工蜂群算法進(jìn)行驗(yàn)證，并進(jìn)行性能對(duì)比。圖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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

針對(duì)食品供應(yīng)鏈加工環(huán)節(jié)召回優(yōu)化的問題，給出了批次分散模型，引入人工蜂群算法優(yōu)化該模型。與文獻(xiàn)［11］提出的MPSO 法相比，文中提出的算法尋優(yōu)效果好、收斂速度快、復(fù)雜度不高，能夠有效減少平均召回規(guī)模，減小運(yùn)算開銷。對(duì)于食品加工企業(yè)而言，平均召回成本這個(gè)性能指標(biāo)的重要性遠(yuǎn)大于最壞召回規(guī)模，在其他性能指標(biāo)有大幅提高的前提下是可以接受的，因此適用于食品供應(yīng)鏈召回優(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］李鋒，吳華瑞，朱華吉，等.基于改進(jìn)粒子群算法的農(nóng)產(chǎn)品召回優(yōu)化［J］.農(nóng)業(yè)工程學(xué)報(bào)，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］張長(zhǎng)勝.多目標(biāo)人工蜂群算法及遺傳算法的研究與應(yīng)用［M］.沈陽(yáng):東北大學(xué)出版社，2013.

［14］陳久梅.兩級(jí)定位-路徑問題的人工蜂群算法［J］.計(jì)算機(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］崔明，沈瑾，李延云，等.中國(guó)農(nóng)產(chǎn)品加工技術(shù)現(xiàn)狀及其推廣體系的建設(shè)［J］.農(nóng)業(yè)工程學(xué)報(bào)，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)化算法及其應(yīng)用［M］.北京:科學(xué)出版社，2012.

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