鮮奶采購計(jì)劃的改進(jìn)自適應(yīng)罰函數(shù)遺傳算法

鐘金宏 黃 玲

1.合肥工業(yè)大學(xué)，合肥，230009

2.過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，合肥，230009

0 引言

本文研究一個(gè)實(shí)際奶制品企業(yè)的經(jīng)濟(jì)批量問題。奶制品企業(yè)為迅速進(jìn)入某地市場，在當(dāng)?shù)卦O(shè)立加工分廠，分廠鮮奶主要來自總部的自有規(guī)模化養(yǎng)殖場，每天由奶罐車循環(huán)運(yùn)奶，分廠獨(dú)立經(jīng)營需付費(fèi)給總部；總部的鮮奶產(chǎn)量和奶罐車數(shù)量有限，而客戶的需求是變動的，因此分廠有時(shí)需要從當(dāng)?shù)夭少忰r奶；但為了保障品質(zhì)，將優(yōu)先考慮自產(chǎn)鮮奶。根據(jù)客戶訂單或市場預(yù)測，分廠可以計(jì)算出自己的鮮奶需求；但由于奶制品銷售受天氣和節(jié)假日等影響較大，在春節(jié)等銷售旺季，經(jīng)常出現(xiàn)斷貨和延期交貨的現(xiàn)象。該問題可建模為動態(tài)離散經(jīng)濟(jì)批量模型，從總部運(yùn)奶可看做是生產(chǎn)，從本地采購鮮奶可看作是外包，分廠的鮮奶需求可綜合考慮生產(chǎn)、外包、庫存和延期交貨等策略來滿足。

Wagner等［1］最先研究了該問題，但未考慮外包和生產(chǎn)能力限制。生產(chǎn)能力受限的經(jīng)濟(jì)批量問題是 NP難題［2－3］，僅在一些特殊情況下是多項(xiàng)式可解的［3－8］。外包是企業(yè)間協(xié)作的常見形式，也是企業(yè)應(yīng)對復(fù)雜多變需求的主要手段。目前，考慮外包（或失去銷售）的經(jīng)濟(jì)批量問題研究很少，文獻(xiàn)［9－13］中關(guān)于外包、轉(zhuǎn)包和失去銷售方面的經(jīng)濟(jì)批量研究可歸為此類研究，因?yàn)樗鼈儚慕５慕嵌葋碚f是一樣的?，F(xiàn)有研究可分為三類：無能力限制情況［9］、庫存有界情況［10］和生產(chǎn)能力受限情況［11－13］。Sandbothe等［11］分別研究了恒定和時(shí)變生產(chǎn)能力的情況，但成本參數(shù)是常量，且未考慮失去銷售量限制。Sandbothe等［12］又研究了有時(shí)變庫存和生產(chǎn)能力限制的同樣問題，但模型參數(shù)仍為常量。Atamtürk等［13］考慮了恒定生產(chǎn)能力約束情況，但未考慮外包量的限制，分別研究了一般凹成本和非投機(jī)性成本函數(shù)情況。文獻(xiàn)［11－13］均沒有考慮延期交貨策略。

根據(jù)問題實(shí)際情況，本文同時(shí)考慮時(shí)變成本參數(shù)、時(shí)變生產(chǎn)能力約束、外包量受限于當(dāng)前周期需求和允許延期交貨情況，提出了一個(gè)新的基于群體可行狀況和個(gè)體約束違背程度的自適應(yīng)罰函數(shù)，開發(fā)了相應(yīng)的遺傳算法，并通過大量仿真實(shí)驗(yàn)驗(yàn)證了所提自適應(yīng)罰函數(shù)的有效性，比較了自適應(yīng)罰函數(shù)相對其他罰函數(shù)的優(yōu)勢。

1 問題模型

通過推算，分廠可獲知在未來T周期規(guī)劃時(shí)段上的需求dt，dt＞0，t＝1，2，…，T。令xt和Lt分別表示周期t的生產(chǎn)量和外包量；It表示周期結(jié)束時(shí)的庫存；Ct表示周期t的生產(chǎn)能力；pt（xt）、λt（Lt）、ht（It）分別表示生產(chǎn)、外包和庫存/延期交貨成本函數(shù)，它們?yōu)橐话惆己瘮?shù)，則引言中描述的問題（P1）可表示為

目標(biāo)函數(shù)（1）用來最小化規(guī)劃時(shí)段內(nèi)的總體生產(chǎn)、外包、庫存及延期成本；狀態(tài)等式（2）為物料平衡公式；不等式（3）表示每周期生產(chǎn)量是非負(fù)的，且不超過當(dāng)前周期生產(chǎn)能力；約束（4）要求每周期外包量非負(fù)，且不超過當(dāng)周期需求；等式（5）表示規(guī)劃期開始和結(jié)束時(shí)庫存為0。顯然，該問題為NP難題。

2 自適應(yīng)罰函數(shù)遺傳算法

遺傳算法是求解優(yōu)化問題的有力工具，但其自身有較多參數(shù)需要確定，合理設(shè)定這些參數(shù)需根據(jù)問題具體處理，主觀性較強(qiáng)。根據(jù)當(dāng)前和前面的搜索情況，自適應(yīng)調(diào)整算法參數(shù)是一個(gè)很好的選擇，在文獻(xiàn)［14－19］中都有報(bào)道。其中，報(bào)道最多的是交叉及變異概率自適應(yīng)和罰函數(shù)參數(shù)自適應(yīng)。本文設(shè)計(jì)了一種新的能根據(jù)搜索過程反饋信息調(diào)整罰函數(shù)系數(shù)的自適應(yīng)遺傳算法，圖1為算法流程圖。

圖1 自適應(yīng)遺傳算法流程圖

遺傳算法本質(zhì)上只能求解無約束規(guī)劃問題，對約束規(guī)劃問題，常用處理方法有：罰函數(shù)方法；設(shè)計(jì)不可行解修正算法；設(shè)計(jì)特殊的編碼和遺傳算子。問題（P1）是約束規(guī)劃問題，存在兩類約束：每周期存在生產(chǎn)和外包能力約束；要求規(guī)劃期開始和結(jié)束時(shí)庫存為零。

2.1 生產(chǎn)和外包能力約束處理方案

在二進(jìn)制編碼的遺傳算法中，可行解是針對顯型空間來說的，在基因型層次，并沒有可行和不可行說法，因此，可通過設(shè)計(jì)特殊的解碼算子，直接將基因空間的基因型映射為顯型空間的可行顯型，從而解決不可行問題。在處理第一類約束時(shí)使用了該思想，有效地降低了需處理約束的個(gè)數(shù)，減小了算法在獲取可行解方面的代價(jià)。對n位二進(jìn)制編碼的基因段，假定它對應(yīng)的十進(jìn)制數(shù)為value，其在十進(jìn)制顯型空間的可行范圍為［fmin，fmax］，則可采用下式將它映射入可行區(qū)域：

式中，fvalue為映射的可行顯型值。

2.2 零庫存約束處理方案

問題假定規(guī)劃期開始時(shí)庫存為零，如不為零則可通過修正初始周期約束來轉(zhuǎn)換，成為開始庫存為零的等價(jià)問題。規(guī)劃期結(jié)束時(shí)庫存為零，這是所研究規(guī)劃問題的要求，但遺傳算法是一種有導(dǎo)向的隨機(jī)搜索過程，得到的解不一定能保證最終庫存為零，因此，它是算法需要處理的約束。但如因管理需要，在規(guī)劃期結(jié)束要保有庫存，這部分庫存在研究上可處理成最后周期需求。這里，規(guī)劃期結(jié)束庫存不為零是因算法本身造成的，而非管理策略要求的。

靜態(tài)罰函數(shù)法易導(dǎo)致算法早熟或收斂緩慢，動態(tài)罰函數(shù)法未根據(jù)算法的實(shí)際運(yùn)算情況動態(tài)調(diào)整懲罰系數(shù)，自適應(yīng)懲罰［14－16］利用迭代過程的反饋信息動態(tài)調(diào)整懲罰系數(shù)，避免了上述問題，在一些文獻(xiàn)的報(bào)道中均取得了較好效果。文獻(xiàn)［14－15］中的自適應(yīng)懲罰函數(shù)方法均不同程度地需要人工確定附加參數(shù)，影響了算法的可擴(kuò)展性。文獻(xiàn)［16］設(shè)計(jì)了一個(gè)基于當(dāng)前群體中不可行的狀況來改變懲罰程度的方案，避免了確定附加參數(shù)。該方法有利于避免算法早熟，但由于它過于強(qiáng)調(diào)不可行個(gè)體參與遺傳操作，經(jīng)常無法收斂至可行解，或搜索過程過于緩慢。特別是當(dāng)群體中可行個(gè)體很少或沒有可行個(gè)體時(shí)，由于懲罰微不足道，會使搜索發(fā)散。本文測試了該方法的可用性，在12周期、24周期、36周期和48周期規(guī)劃問題上，對選擇、交叉和定標(biāo)算子的120種組合分別進(jìn)行實(shí)驗(yàn)，每個(gè)組合運(yùn)行10次，沒有一次收斂至可行解。因此，無法使用該懲罰方案解決本文問題。

為此，本文基于當(dāng)前群體中可行的狀況來確定懲罰系數(shù)。在當(dāng)前群體中，可行個(gè)體多時(shí)，說明搜索是收斂的，應(yīng)降低懲罰程度，鼓勵不可行個(gè)體參與遺傳操作，擴(kuò)大搜索區(qū)域，避免早熟收斂；反之，可行個(gè)體少時(shí)，說明搜索是發(fā)散的，應(yīng)加大對可行個(gè)體懲罰，促其收斂。因此，本懲罰方法利用了群體特定信息（可行和不可行區(qū)域的比例）和染色體特定信息（不可行解距離可行區(qū)域的距離）。引入自適應(yīng)懲罰后的目標(biāo)函數(shù)為

其中，pop＿size為群體尺寸；feasibles為當(dāng)前群體中可行解個(gè)數(shù)，隨GA迭代動態(tài)變化，取值范圍為0～pop＿size，feasibles為0時(shí)懲罰系數(shù)取一大數(shù)，最低懲罰系數(shù)是1。

3 算法仿真實(shí)驗(yàn)

下面通過仿真實(shí)驗(yàn)，測試本文所提自適應(yīng)罰函數(shù)的有效性。問題實(shí)例隨機(jī)生成，采用文獻(xiàn)［8］中的季節(jié)性需求模式，其他參數(shù)由定義在某區(qū)間上的均勻分布隨機(jī)生成（具體設(shè)定區(qū)間見表1），其中生產(chǎn)能力和需求取整數(shù)，其他參數(shù)為實(shí)數(shù)。實(shí)例參數(shù)設(shè)定區(qū)間見表1。

表1 問題參數(shù)設(shè)定區(qū)間

3.1 算子組合與罰函數(shù)的組合實(shí)驗(yàn)

在12周期、24周期、36周期及48周期規(guī)劃問題上，針對不同算子組合進(jìn)行靜態(tài)懲罰（SPF）［17］、動 態(tài) 懲 罰 1（DPF1）［18］、動 態(tài) 懲 罰 2（DPF2）［19］、自適應(yīng)懲罰1（APF1）［15］和本文所提自適應(yīng)懲罰方案2（APF2）的對比實(shí)驗(yàn)，從而驗(yàn)證APF2的有效性，同時(shí)可確定最好的算子組合。實(shí)驗(yàn)中也比較了退火懲罰［14］，但其不能得到可行解，故沒有列出。

令＝｛單點(diǎn)，兩點(diǎn)，均勻，奇偶｝表示交叉算子集合，c′i（i＝1，2，3，4）表示第i個(gè)交叉算子。類似地，R′＝｛賭輪，聯(lián)賽，排序，隨機(jī)均勻采樣，確定性采樣，剩余隨機(jī)抽樣｝表示選擇算子集合，r′j（j＝1，2，…，6）表示第j個(gè)選擇算子，?＝ ｛無定標(biāo)，線性，冪函數(shù)，σ截?cái)啵m應(yīng)度值共享｝表示定標(biāo)方法的集合，?k（k＝1，2，…，5）為第k個(gè)定標(biāo)方法。c′ir′j?k表 示一個(gè)算 子 組 合，共 有120種 組合，按從左向右、深度優(yōu)先原則編號。與5種懲罰方法結(jié)合，共有600種組合，每個(gè)組合運(yùn)行10次，共運(yùn)行6000次。實(shí)驗(yàn)中，最大迭代代數(shù)為800，群體尺寸為50，交叉概率為0.9，變異概率為0.01。分別測試了12周期、24周期、36周期及48周期規(guī)劃問題。為全面反映實(shí)驗(yàn)情況，實(shí)驗(yàn)結(jié)果以圖形形式提供，見圖2。圖中，橫坐標(biāo)為算子組合標(biāo)號（1～120）；縱坐標(biāo)為10次運(yùn)行的最終解的成本平均值；“○”代表該算子組合的10次運(yùn)行最終解均不可行的情況。

由圖2可得：①在5種罰函數(shù)中，本文提出的自適應(yīng)懲罰方法（APF2）效果最好，在4個(gè)規(guī)劃問題上對所有算子組合都獲得了最低平均成本。②總體上，采用聯(lián)賽和排序選擇的組合效果較好，這兩類組合在4個(gè)規(guī)劃問題上都優(yōu)于其他組合，且對不同懲罰方法該結(jié)論基本上都成立；具體來說，對于12周期和24周期規(guī)劃問題，聯(lián)賽選擇的最終解均值要低于排序選擇；對于36周期規(guī)劃問題，排序選擇的最終解均值略好于聯(lián)賽選擇或基本相當(dāng)；對于48周期問題，排序選擇的最終解均值低于聯(lián)賽選擇。

圖2 算子和懲罰方法的組合實(shí)驗(yàn)結(jié)果

表2為表現(xiàn)較好的算子組合c′2r′2?4和c′1r′3?4的運(yùn)算結(jié)果展示，從表2中可看出，本文提出的自適應(yīng)懲罰方法效果最好，10次運(yùn)行的最終解均值小于其他懲罰方案。

表2 不同懲罰方法在4個(gè)規(guī)劃問題上的表現(xiàn)

3.2 遺傳算子概率對算法性能的影響

交叉和變異概率對GA的性能和行為有重要影響，常見的算子概率處理方式有：①選擇算子概率的指導(dǎo)規(guī)則，它未必適合所要解決的問題；②自主自適應(yīng)調(diào)整方案，對算子概率進(jìn)行編碼，進(jìn)行同步優(yōu)化，其計(jì)算代價(jià)較大；③自適應(yīng)動態(tài)調(diào)節(jié)研究，自適應(yīng)動態(tài)調(diào)節(jié)在無約束優(yōu)化問題中有很多報(bào)道，在約束優(yōu)化問題上有針對可行群體的概率調(diào)整報(bào)道，但保證群體可行需要采用特殊的約束處理方法，這比較困難。本文提出的懲罰函數(shù)處理約束方法不能保證每代群體中的所有個(gè)體都可行，因此，本文采用實(shí)驗(yàn)嘗試法選擇適合的算子概率，同時(shí)也觀察算法對算子概率的敏感性。

組合實(shí)驗(yàn)條件為：交叉概率變動范圍為0.5～1.0，步長為0.05；變異概率變動范圍為0～0.475，步長為0.025，每個(gè)組合運(yùn)行10次。實(shí)驗(yàn)中，采用兩點(diǎn)交叉、排序選擇和適應(yīng)度共享定標(biāo)。圖3所示為在12周期問題上的實(shí)驗(yàn)結(jié)果。圖中，橫坐標(biāo)為交叉概率Pc和變異概率Pm，在間隔［b，b＋0.05）內(nèi)，Pc＝b，Pm從 0 開 始 以 步 長0.025增至0.475；縱坐標(biāo)分別為10次運(yùn)行可行最終解的次數(shù)、收斂代數(shù)和成本的均值；“○”代表該組合的10次運(yùn)行最終解均不可行的情況。從圖3可看出，交叉概率在0.5～1.0之間變化，算法對其不敏感；變異概率應(yīng)大于零且小于0.025，在該范圍外會出現(xiàn)問題解不可行情況。后續(xù)實(shí)驗(yàn)中取交叉概率為0.9，變異概率為0.01。

圖3 概率組合對最終解可行的影響

3.3 最終實(shí)驗(yàn)結(jié)果

對12周期、24周期、36周期和48周期規(guī)劃問題和5種懲罰方法，算法分別運(yùn)行50次。根據(jù)前面實(shí)驗(yàn)，采用兩點(diǎn)交叉、排序選擇和適應(yīng)度共享定標(biāo)，交叉概率為0.9，變異概率為0.01。由于懲罰方法APF1在36周期和48周期問題上出現(xiàn)了不可行最終解，對這2個(gè)問題僅給出4種懲罰方法的運(yùn)行結(jié)果。

數(shù)據(jù)表適合少量數(shù)據(jù)的比較，但對于大量數(shù)據(jù)比較，則顯得雜亂和不直觀。由于實(shí)驗(yàn)中數(shù)據(jù)比較多，故采用雷達(dá)圖顯示實(shí)驗(yàn)結(jié)果，見圖4。圖中，極軸標(biāo)號1～50代表算法50次運(yùn)行的序號；每次運(yùn)行的最終解對應(yīng)成本作為極徑，標(biāo)注在相應(yīng)的極軸上，構(gòu)成一個(gè)極坐標(biāo)點(diǎn)，將50次運(yùn)行的極坐標(biāo)點(diǎn)連起來形成一個(gè)不規(guī)則閉環(huán)，描述了某種懲罰方法50次運(yùn)行中最終解對應(yīng)成本的變化。不同懲罰方法對應(yīng)顏色深淺不同的不規(guī)則閉環(huán)。位于最內(nèi)部的不規(guī)則閉環(huán)不會被其他閉環(huán)覆蓋，表示采用該懲罰方法，最好染色體的成本最低。從圖4可看出，在4個(gè)不同周期的規(guī)劃問題上，本文提出的懲罰方法APF2對應(yīng)的不規(guī)則閉環(huán)位于羅盤圖的最內(nèi)部，性能最好。

運(yùn)用本文設(shè)計(jì)的自適應(yīng)懲罰遺傳算法，可得到奶制品加工廠的鮮奶采購計(jì)劃，限于篇幅，這里以12周期規(guī)劃問題為例給出優(yōu)化結(jié)果，見表3。

圖4 不同懲罰方法的50次運(yùn)行結(jié)果的雷達(dá)圖比較

表3 12周期規(guī)劃問題的運(yùn)行結(jié)果（總成本為11862.5）

4 結(jié)語

本文研究了生產(chǎn)能力受限的動態(tài)經(jīng)濟(jì)批量問題，該問題抽象于一個(gè)實(shí)際奶制品加工廠的鮮奶采購問題，涉及企業(yè)如何合理運(yùn)用內(nèi)購（生產(chǎn)）、外購（外包）和延期交貨等策略來最優(yōu)地滿足客戶需求。提出了一個(gè)新的自適應(yīng)罰函數(shù)，設(shè)計(jì)了相應(yīng)的遺傳算法。與其他自適應(yīng)罰函數(shù)相比，本懲罰方案不需人工設(shè)定附加參數(shù)，且綜合考慮了當(dāng)前群體可行狀況和個(gè)體距離可行的距離。設(shè)計(jì)了大量仿真實(shí)驗(yàn)，驗(yàn)證了本懲罰方案的有效性和優(yōu)勢。

［1］Wagner H M，Whitin T M.Dynamic Version of the Economic Lot－size Model［J］.Management Science，1958，5（1）：89－96.

［2］Florian M，Lenstra J，Kan A R.Deterministic Production Planning：Algorithms and Complexity［J］.Management Science，1980，26（7）：669－679.

［3］Bitran G，Yanasse H.Computational Complexity of the Capacitated Lot Size Problem［J］.Management Science，1982，28（10）：1174－1186.

［4］Florian M，Klein M.Deterministic Production Planning with Concave Costs and Capacity Constraints［J］.Management Science，1971，18（1）：12－20.

［5］Janannathan R，Rao M.A Class of Deterministic Production Planning Problems［J］.Management Science，1973，19（11）：1295－1300.

［6］Hoesel C P，Wagelmans A P.An O（T3）Algorithm for the Economic Lot－sizing Problem with Constant Capacities［J］.Management Science，1996，42（1）：142－150.

［7］Chung C，Lin C.An O（T2）Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem［J］.Management Science，1988，34（2）：420－426.

［8］Heuvel W，Wagelmans A P.An Efficient Dynamic Programming Algorithm for a Special Case of the Capacitated Lot－sizing Problem［J］.Computers ＆Operations Research，2006，33（12）：3583－3599.

［9］Aksen D，Altinkemer K，Chand S.The Single－item Lot－sizing Problem with Immediate Lost Sales［J］.Eur.J.Oper.Res.，2003，147（3）：558－566.

［10］Chu F，Chu C.Single－item Dynamic Lot Sizing Models with Bounded Inventory and Outsourcing［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2008，30（1）：70－77.

［11］Sandbothe R A，Thompson G L.A Forward Algorithm for the Capacitated Lot Size Model with Stockouts［J］.Operation Research，1990，38（3）：474－486.

［12］Sandbothe R A，Thompson G L.Decision Horizons for the Capacitated Lot Size Model with Inventory Bounds and Stockouts［J］.Computers ＆ Operations Research，1993，20（5）：455－465.

［13］Atamtürk A，Hochbaum D S.Capacity Acquisition，Subcontracting，and Lot Sizing［J］.Management Science，2001，47（8）：1081－1100.

［14］Coello C A.Theoretical and Numerical Constraint－Handling Techniques Used with Evolutionary Algorithms：a Survey of the State of the Art［J］.Computer Methods in Applied Mechanics and Engineering，2002，191（11/12）：1245－1287.

［15］Hadj－Alouane A B，Bean J C.A Genetic Algorithm for the Multiple－Choice Integer Program［J］.Operations Research，1997，45（1）：92－101.

［16］Dadios E P，Ashraf J.Genetic Algorithm with Adaptive and Dynamic Penalty Functions for the Selection of Cleaner Production Measures：A Constrained Optimization Problem［J］.Clean Tech.Environ Policy，2006，8（2）：85－95.

［17］Homaifar A，Qi C X，Lai S H.Constrained Optimization Via Genetic Algorithms［J］.Simulation 1994，62（4）：242－254.

［18］Joines J，Houck C R.On the Use of Non－stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with Gas［C］//Proceedings of the First IEEE International Conference on Evolutionary Computation.Orlando，1994：579－584.

［19］Kazarlis S，Petridis V.Varying Fitness Functions in Genetic Algorithms：Studying the Rate of Increase in the Dynamic Penalty Terms［C］//Proceedings of the 5th Int.Conf.on Parallel Problem Solving from Nature.Berlin，1998：211－220.