基于模擬退火遺傳混合算法的指派問題研究

趙 麗， 馮 毅 ZHAO Li,FENG Yi

（1.蘭州交通大學(xué)，甘肅 蘭州 730070；2.蘭州理工大學(xué)，甘肅 蘭州 730050）

指派問題是物流活動中經(jīng)常遇到的組合性優(yōu)化問題，應(yīng)用十分廣泛，因此對其研究較多。在實(shí)際物流活動中指派問題通常有平衡與非平衡兩種類型，即有n項(xiàng)任務(wù)，指派n個人員來分派完成稱為平衡指派問題；有n項(xiàng)任務(wù)，指派m個人員來分派完成稱為非平衡指派問題。近幾年來模擬退火算法和遺傳算法對指派問題在優(yōu)化領(lǐng)域得到廣泛深入的研究和應(yīng)用，并得到很好的效果。在此基礎(chǔ)上本文研究模擬退火遺傳混合算法對指派問題的思路及求解。經(jīng)實(shí)例計(jì)算該方法收斂較快，搜索效率較高。

1 指派問題數(shù)學(xué)模型

為方便研究將平衡與非平衡兩種指派問題歸納為如下兩種形式研究：

設(shè)有n項(xiàng)任務(wù)，要派m個人去完成，Cij表示第i個人完成第j項(xiàng)任務(wù)要付出的代價(jià)，tij表示第i個人完成第j項(xiàng)任務(wù)所需時間，則如何分派會使整體效益最好，即用時少費(fèi)用低。

為建立模型引入0－1變量：

1.1 人數(shù)大于或等于工作項(xiàng)目時m≥（）n

1.2 人數(shù)小于工作項(xiàng)目時m<（）n

式中b——每人限制的最大工作量

2 指派問題的模擬退火遺傳混合算法實(shí)現(xiàn)

2.1 模擬退火遺傳混合算法思想

Step1：選定初始溫度t=t0

利用模擬退火算法的溫度控制方法選定較合適的初始溫度。如果初始溫度選擇過高會導(dǎo)致計(jì)算時間較長，從而降低計(jì)算效率。如果初始溫度選擇過低又有可能使最終收斂得不到最優(yōu)解。因此根據(jù) （14）式的條件來確定初始溫度t0。

式中 Δfij——任意兩個相鄰的溫度差

Step2：確定初始群體initpop

首先，用實(shí)數(shù)編碼方法對任務(wù)數(shù)n進(jìn)行編碼且不變；

其次，用實(shí)數(shù)編碼方法對人數(shù)m進(jìn)行編碼且可以隨機(jī)抽取；

最后，利用隨機(jī)生成法對l!l=m-（）1 個解中隨機(jī)選取一個解為初始群體initpop。

Step3：構(gòu)造適應(yīng)函數(shù)f0=fitfun1，ft=fitfun1

Step4：利用遺傳算法對初始群體initpop進(jìn)行優(yōu)化，產(chǎn)生種群seedpop1

（1） 確定評價(jià)函數(shù)eval（ Vi）

（2）利用評價(jià)函數(shù)可以確定進(jìn)入種群的個體

當(dāng)qi-1≤γ≤qi時 （γ為 （0～1）的偽隨機(jī)數(shù)），第i個染色體進(jìn)入種群，從而形成種群seedpop1。

Step5：利用模擬退火算法對種群seedpop1進(jìn)行訓(xùn)練，產(chǎn)生更優(yōu)的新種群seedpop2

（1）對seedpop1中1～m個體的適應(yīng)值與初始群體中f0的值進(jìn)行比較，滿足條件的進(jìn)入seedpop2；

（2）否則，根據(jù)評價(jià)函數(shù)來判斷進(jìn)入seedpop2的個體。當(dāng)個體的適應(yīng)值滿足時，則選擇進(jìn)入seedpop2；

（3）經(jīng)過優(yōu)化訓(xùn)練，產(chǎn)生新種群seedpop2。

Step6：對新種群seedpop2進(jìn)行交叉、變異，產(chǎn)生子代children

（1）對新種群seedpop2進(jìn)行雙親雙子法交叉，交叉率β，生成crosspop；

（2）再進(jìn)行變異，交叉率ε，生成mutpop；

（3）生成子代children。

Step7：返回Step4，直到滿足終止條件

Step8：得到最優(yōu)解

3 算例演示

某大型生產(chǎn)企業(yè)為生產(chǎn)和人員安全每年都要定期對生產(chǎn)設(shè)備進(jìn)行檢修，檢修分為平時檢修和7月分大檢修。現(xiàn)取其中一個車間來做算例，該車間只有3個維修工，平時每次平均會有2個地方出現(xiàn)故障，到7月大檢修時該車間5個檢修點(diǎn)都要停止運(yùn)作重新進(jìn)行檢查和修理。已知工人維修故障所需時間Pij見表1，每個維修工的基本維修費(fèi)用Cij見表2，注：在7月份大檢修時天氣比較炎熱為保證維修工安全要求每個工人至多維修兩個故障點(diǎn)。

表1 完成任務(wù)所需時間 單位：小時

表2 完成任務(wù)所付費(fèi)用 單位：百元

混合算法相關(guān)參數(shù)選擇α、初始時間t0=6、交叉率β＝0.2、變異率＝0.05。利用前面設(shè)計(jì)的混合算法進(jìn)行運(yùn)算得到結(jié)果及比較結(jié)果見表3，運(yùn)行次數(shù)都為10次。按照該方案進(jìn)行分配所得到的完成任務(wù)的花費(fèi)時間大約要比單一使用模擬退火或遺傳算法獲得最優(yōu)解短五分之二。

4 結(jié) 論

本文結(jié)合模擬退火算法和遺傳算法的優(yōu)點(diǎn)，提出模擬退火遺傳混合算法來解決實(shí)際中的指派問題。指派問題屬于組合優(yōu)化問題，很適合用本文研究的算法來實(shí)現(xiàn)。這種混合算法能夠準(zhǔn)確快速地求解最優(yōu)結(jié)果或分配方案，針對較大規(guī)模的指派問題，能夠縮短搜索時間，取得良好的效果。

表3

[1] 賀國先.現(xiàn)代物流系統(tǒng)仿真[M].北京：中國鐵道出版社，2008.

[2] 焦永蘭.管理運(yùn)籌學(xué)[M].北京：中國鐵道出版社，2000.

[3] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京：清華大學(xué)出版社，2005.

[4] 謝凡榮.求解指派問題的一個算法[J].運(yùn)籌與管理，2004(6):24-26.

[5] 張新輝.任務(wù)數(shù)多于人數(shù)的指派問題[J].運(yùn)籌與管理，1997(3):15-18.

[6] Cattrysse D G,Van Wassenhove L N.A survey of algoirths for the generalized assignment problem[J].Europena Joumla of Operationla Research,1992,60(3):260-272.

[7] Marco Dorigo,Vittorio Maniezzo,Alberto Colomi.Ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Cybernetics,1996(26):55-57.