曾偉淵

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

0 引言

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

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

1 庫(kù)存匹配問(wèn)題描述

庫(kù)存匹配的流程圖如圖1所示.

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

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

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

圖1 庫(kù)存匹配流程圖

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

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

3 改進(jìn)的蛙跳算法

3.1 基本混洗蛙跳算法存在的問(wèn)題

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

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

3.2 隨機(jī)分組策略

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

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

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

3.3 最差蛙改進(jìn)策略

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

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

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

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

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

4 仿真研究

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

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

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

通過(guò)上面的仿真實(shí)驗(yàn)可以得到以下的比較結(jié)果:

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

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

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

5 結(jié)束語(yǔ)

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

［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］王介生，高憲文.基于改進(jìn)混合蛙跳算法的電渣重熔過(guò)程多變量 PID控制器設(shè)計(jì)［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.