改進的蛙跳算法在庫存匹配中的研究

曾偉淵

(廈門軟件職業(yè)技術(shù)學院)

0 引言

當前庫存匹配問題主要集中在鋼鐵等流程行業(yè)，在鋼鐵、石化等流程行業(yè)的生產(chǎn)經(jīng)營主要面臨兩方面的問題:一方面要在復雜的工藝條件下實現(xiàn)生產(chǎn)的連續(xù)性，第二客戶對最終產(chǎn)品在規(guī)格、種類、數(shù)量和交貨期上的各種要求需要滿足［1］.與鋼鐵、石化等行業(yè)類似，在磁性材料生產(chǎn)管理過程中，為了實現(xiàn)非訂單庫存產(chǎn)品的有效利用，需要將其與客戶下達的生產(chǎn)訂單進行匹配.針對鋼鐵企業(yè)生產(chǎn)過程中訂單與庫存之間的匹配問題Trumbo等人對其做了重要的貢獻，他們主要針對工藝路線和生產(chǎn)組織等特殊的約束條件的庫存匹配問題進行研究，并提出了解決方法［2］.庫存匹配問題可以與多背包問題(MKP)進行類比，均屬于被證明為NP難的組合優(yōu)化問題［3－4］.

針對基本混洗蛙跳算法(SFLA)收斂速度慢、優(yōu)化精度低且易于陷入局部最優(yōu)的問題，對其進行多項改進.采用隨機分組策略，平衡各子群的尋優(yōu)能力，保持種群多樣性;打破最差蛙只向最優(yōu)蛙學習的模式，引入Minkowski距離，使最差蛙借助更多同伴信息選擇進化方向，增強種群適應性;針對最優(yōu)蛙進化機會少，引入精英策略和變異思想更新其位置，避免陷入局部極小，加快收斂速度，最后選取合適的目標函數(shù)，將改進前后混洗蛙跳算法(ISFLA)用于冷軋液壓伺服位置(APC)系統(tǒng)的PID參數(shù)整定，并將整定結(jié)果進行西門子PLC實驗驗證，結(jié)果表明改進后算法的有效性和高效性.

1 庫存匹配問題描述

庫存匹配的流程圖如圖1所示.

人工庫存匹配工作量大，庫存匹配時間長，生產(chǎn)訂單拖期嚴重，同時，選取的最終匹配結(jié)果，不一定是最優(yōu)的或近似最優(yōu)的.因此該文采用改進的蛙跳算法進行庫存匹配問題的研究的.

2 庫存匹配數(shù)學模型

針對庫存匹配問題，首先給出了參數(shù)與變量的符號定義.i:訂單序號;l:庫存微粉編號;IS:生產(chǎn)訂單集合;LS:庫存微粉集合;ai:計劃員給定的生產(chǎn)訂單i庫存匹配的優(yōu)先級系數(shù);di:訂單i的交貨日期;gi:生產(chǎn)訂單i的牌號編碼;bl:庫存微粉l的桶號;rl:庫存微粉l是否為預留微粉，若rl=1，則為預留微粉;否則，非預留微粉;Ωi:滿足生產(chǎn)訂單i要求的庫存微粉集合，;Ωi?LS:Ψl庫存微粉l能夠匹配的生產(chǎn)訂單集合，φl?IS;ωi:實際匹配生產(chǎn)訂單i庫存微粉集合，ωi?Ωi;xl(i):若庫存微粉l被匹配給生產(chǎn)訂單i，則為1;否則為0;Wl(i):若庫存微粉l被匹配給生產(chǎn)訂單i的重量.

圖1 庫存匹配流程圖

(2)目標函數(shù)和約束

目標函數(shù)(1)最大化庫存匹配的微粉重量;目標函數(shù)(2)最大化匹配出的微粉的入庫時間;目標函數(shù)(3)最大化匹配出的微粉的氧含量;目標函數(shù)(4)最小化匹配出的微粉的平均粒度.約束(5)庫存微粉的牌號與生產(chǎn)訂單的牌號屬于同一性能序列且不低于訂單要求;約束(6)一個生產(chǎn)訂單最多與三個庫存編號的微粉匹配;約束(7)與一個生產(chǎn)訂單匹配的多個微粉的入庫時間偏差不超過30 d;約束(8)生產(chǎn)訂單匹配的庫存粉重不能超過生產(chǎn)訂單的需求量.

3 改進的蛙跳算法

3.1 基本混洗蛙跳算法存在的問題

(1)對于基本的混洗蛙跳算法，有序的分組方法使得越靠前的子種群，其平均適應度值越高，全局最優(yōu)解往往存在于這樣的分組里，因此，即使每一組每代更新最差蛙，也是這樣的分組得到新的全局最優(yōu)解的概率最大，尋優(yōu)能力強于其他分組，這為整個種群容易陷入局部極值埋下了隱患.

(2)根據(jù)基本的混洗蛙跳算法，最差蛙可能的新位置被限制在當前位置和最優(yōu)蛙位置的線性區(qū)域，最差蛙永遠跳不出最優(yōu)蛙.即使當最差蛙的新位置無法得到改善而產(chǎn)生隨機解，然而并不能保證隨機解一定會更優(yōu).結(jié)果，這種蛙跳規(guī)則限制了本組進化的搜索空間.同時，最差蛙僅僅被最優(yōu)蛙影響，并沒有做到個體間充分的思想交流，降低了種群的適應性.除此之外，最優(yōu)蛙在跳躍過程中很少有機會進化，這造成算法的學習機制不充分，種群多樣性減少，從而導致早熟收斂［7］.

3.2 隨機分組策略

為解決基本混洗蛙跳算法的第一個缺陷，從改進全局搜索方式的角度出發(fā)該文提出了對青蛙進行隨機分組的策略.

隨機分組策略的主要思想是:首先，按照適應度值由大到小將N只青蛙進行排序;其次，將整個種群劃分成n個獨立的子種群;第三，實現(xiàn)每個子種群包含解的個數(shù)是m個，并且在算法迭代過程中，前n個解需要隨機進入不同的n個子種群，同時實現(xiàn)每個解只能進入一個子種群，依此類推，直到所有解分配完畢.

采用上述的隨機分組策略，使得各個子種群通過不斷的更新以得到新的全局最優(yōu)解的機會均等.該策略強化了子種群的尋優(yōu)能力，實現(xiàn)了種群的多樣性，避免了蛙跳算法陷入局部最優(yōu)［5］.

3.3 最差蛙改進策略

考慮原算法各子群中最差蛙的進化僅僅利用到最優(yōu)蛙的信息，于是在此基礎上引入Minkowski距離，使其不僅僅向最優(yōu)蛙學習，而且向該子群中其他個體學習，使得最差蛙能充分利用所得到的信息來判斷向哪個方向進化，而不是局限在和最優(yōu)蛙的單一的直線方向上，從而加快進化速度，并且當該系統(tǒng)突發(fā)擾動時，由于集體的力量，使得適應能力提高，魯棒性增強.最差蛙位置更新公式如式(9)所示.

其中，Xi表示子種群中的第i只青蛙，S(i)表示子種群中最差蛙受第i只青蛙影響后得到的實際步長，c1表示同一種群中最差青蛙和另外隨機選取的一只青蛙的學習因子，取值范圍是(0，1)之間的隨機數(shù).c2表示整個種群的全局最優(yōu)蛙與該種群中的最差蛙的學習因子，其中范圍為(0，1)之間的隨機數(shù).M(Xi，Xw)表示Minkowski距離，即子種群中的最差解與第i個解之間的實際距離.

3.4 次優(yōu)蛙改進策略

在基本混洗蛙跳算法中，最優(yōu)蛙幾乎不進化，大量仿真實驗證實最優(yōu)蛙的地位一般會被保持很多代，造成算法尋優(yōu)速度慢，易出現(xiàn)早熟收斂，不能真正尋到目標函數(shù)的最小值.

該文借鑒精英策略，保留每個種群中的最優(yōu)蛙，以防最優(yōu)蛙向較壞方向變異后造成沒有全局最優(yōu)解的局面，出現(xiàn)解的退化現(xiàn)象.因此次優(yōu)蛙的改進策略如下:首先，選擇每個子種群中的次優(yōu)蛙在小概率事件時出現(xiàn)變異;其次，讓其以自身所在的位置為中心，以到該種群中最優(yōu)蛙的距離作為最大半徑進行全方位的搜索，若適應度值無變化，則需要在種群中最優(yōu)蛙鄰域范圍內(nèi)產(chǎn)生一個新解，方式是采用隨機的方法［6，8］.其中，次優(yōu)蛙的變異公式如式(11)所示.其中，Xg'為每組次優(yōu)蛙變異完后的候選解，rmax為自身到本組最優(yōu)蛙之間的最大半徑，θ為(0，360°)之間的隨機數(shù).

4 仿真研究

為了實現(xiàn)對算法的有效性的進一步驗證，將該文提出的改進蛙跳算法與人工庫存匹配的排序搜索(largest first fit，LFF)規(guī)則進行比較，具體比較結(jié)果如下.

根據(jù)上文提出的LFF算法對應的規(guī)則以及兩種算法實際執(zhí)行過程中的策略，將其與該文提出的改進蛙跳算法進行了對比實驗，實驗結(jié)果見表1.針對磁性材料實際現(xiàn)場的中等規(guī)模問題，以計算時間、“以好充次”的比例和最終匹配的生產(chǎn)訂單總重量等三個作為評價指標的具體數(shù)值實驗結(jié)果.

表1 100桶微粉20個生產(chǎn)訂單的仿真結(jié)果

通過上面的仿真實驗可以得到以下的比較結(jié)果:

(1)與“LFF規(guī)則+策略A”的算法相比，該文提出的改進蛙跳算法雖然在匹配生產(chǎn)訂單總重量方面略差，但是在庫存微粉“以好充次”的比例方面有著非常大的優(yōu)勢，說明了算法的有效性.

(2)與“LFF規(guī)則+策略B”的算法相比，該文提出的改進蛙跳算法僅僅用少量的庫存微粉“以好充次”為代價，便獲得了在匹配生產(chǎn)訂單總重量方面非常好的效果，說明了算法的有效性.

(3)在計算時間方面，該文提出的改進蛙跳算法較LFF規(guī)則的算法略高.但是根據(jù)該實驗的仿真結(jié)果，該文提出算法的計算時間也在可接受的范圍內(nèi)，算法的效率是完全滿足實際現(xiàn)場要求的.

5 結(jié)束語

該文從基本混洗蛙跳算法的原理出發(fā)分析了其存在的問題，進而有針對性地提出了相關的改進策略;使得該文提出的混洗蛙跳算法能以更加接近生產(chǎn)實際的方式實現(xiàn)磁性材料庫存匹配問題的求解.通過該文仿真結(jié)果可以看出，改進后的混洗蛙跳算法優(yōu)化精度高、收斂速度快、適應性和魯棒性強，并有效克服了原算法早熟、易陷入局部最優(yōu)的缺陷，并且可以在較短的時間內(nèi)解決較大規(guī)模的生產(chǎn)訂單庫存匹配問題，并獲得完全滿足實際現(xiàn)場要求的可行解.

［1］Rajagopalan S.Make to order or make to stock:Model and application［J］.Management Science，2002，48(2):241–256.

［2］Tnunbo M，Kalagnanam J，Lee H.IBM Research Report:A Solution Architecture for Inventory Application Problems in the Steel Industry.Unpublished Results，1998.

［3］Pisinger D.An Exact Algorithm for Large Multiple Knapsack Problems.European Journal of Operational Research，1999，114(3):528–541.

［4］Martello S，Toth P.Knapsack Problems:Algorithms and Computer Implementations.Wiley，Chichester U K，1990.

［5］Pan Q K，Wang L，Gao L，et al.An effective shuffled frogleaping algorithm for lot－streaming flow shop scheduling problem［J］.Int J of Advanced Manufacturing Technology，2011，52(5/6/7/8):699－713.

［6］Rahimi－Vahed A，Mirzaei AH.A hybrid multi－objective shuffled frog－leaping algorithm for a mixed－model assembly line sequencing problem.Computers and Industrial Engineering，2007，53(4):642–66.

［7］王介生，高憲文.基于改進混合蛙跳算法的電渣重熔過程多變量 PID控制器設計［J］.控制與決策，2011，26(11):1731－1734.

［8］Huynh T H.A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllers［C］.IEEE Int Conf on Industrial Technology.Perth:IEEE Press，2008.1–6.