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

趙 麗， 馮 毅 ZHAO Li,FENG Yi

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

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

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

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

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

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

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

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

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

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

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

Step1：選定初始溫度t=t0

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

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

Step2：確定初始群體initpop

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

其次，用實數(shù)編碼方法對人數(shù)m進行編碼且可以隨機抽?。?/p>

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

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

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

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

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

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

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

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

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

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

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

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

（2）再進行變異，交叉率ε，生成mutpop；

（3）生成子代children。

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

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

3 算例演示

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

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

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

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

4 結(jié) 論

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

表3

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

[2] 焦永蘭.管理運籌學[M].北京：中國鐵道出版社，2000.

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

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

[5] 張新輝.任務(wù)數(shù)多于人數(shù)的指派問題[J].運籌與管理，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.