指派問題的改進蟻群算法研究

王書勤, 黃 茜

(武警警官學(xué)院數(shù)理系,四川 成都 610213)

指派問題的改進蟻群算法研究

王書勤, 黃 茜

(武警警官學(xué)院數(shù)理系,四川 成都 610213)

指派問題是組合優(yōu)化問題的一個分支，也是生活中常見的問題。根據(jù)指派問題的特點，將效率矩陣的行標(biāo)看成旅行商問題的城市，提出了一種改進的蟻群算法，仿真試驗結(jié)果和其他文獻結(jié)果比較，證明了該改進算法的可行性。

蟻群算法；旅行商問題；信息素；指派問題

指派問題(Assignment Problem)又稱任務(wù)分配問題，是一類典型的組合優(yōu)化問題，同時又是一類常見的NP-Complete問題，它在軍事及民用領(lǐng)域都有廣泛應(yīng)用，如火力的最優(yōu)分配、任務(wù)的最優(yōu)安排、模式分類、工作調(diào)度、設(shè)備布置、生產(chǎn)安排及印刷電路板設(shè)計等，且很多其他組合優(yōu)化如旅行商問題，工作流問題，車輛運輸問題等問題都可以演化成指派問題求解。指派問題一般是用匈牙利法進行計算，但該法很難在計算機上實現(xiàn)[1]，近年來出現(xiàn)了如模擬退火算法、遺傳算法 、粒子群算法、神經(jīng)網(wǎng)絡(luò)算法等啟發(fā)式算法為求解任務(wù)指派問題提供了新的途徑。文獻[2]給出了指派問題的遺傳算法；文獻[3]給出了指派問題的改進粒子群優(yōu)化算法；文獻[4]給出了指派問題的變異蟻群算法。下面，筆者針對指派問題的特點，從另外一個角度提出了一種改進的蟻群算法，對蟻群算法的尋優(yōu)能力作了一定的探索。

1 指派問題

指派問題描述如下：n個單位，n項任務(wù)，一個單位只能受領(lǐng)完成其中的一項任務(wù)，一項任務(wù)只能交給一個單位，每個單位完成每項任務(wù)的效率已知，求使總效率最高的分配。指派問題也叫分派問題，其數(shù)學(xué)模型為：

用cij表示第i個人完成第j項工作所需的資源數(shù)，則效率系數(shù)矩陣可表示為C=(cij)n×n。

指派問題既是一個整數(shù)規(guī)劃模型也是一個線性規(guī)劃模型[5]。

2 蟻群算法

蟻群算法原理是對真實蟻群協(xié)作過程的模擬[6-7],算法主要由選擇策略、信息素更新和搜索算法組成。算法是根據(jù)真實螞蟻尋找最短路徑的方法提出來的，由于螞蟻會選擇信息素濃度大的路徑，并在經(jīng)過的路徑上留下信息素，隨著時間的推移和信息素的揮發(fā)，最短路徑上的信息素就會越來越濃，最終使得所有螞蟻選擇該路徑，從而找到最短路徑。下面以旅行商問題(TSP)為例說明算法的基本框架。

(1)

由i選擇j，當(dāng)所有螞蟻完成周游環(huán)路上的信息素按式(2)或式(3) ：

(2)

(3)

進行全局更新，最后計算每只螞蟻走過的路徑長度，保存最短路徑。式中，tabuk為螞蟻k已訪問的城市集合；α和β為信息量和自啟發(fā)量的權(quán)重。

在ant-cycle system模型中:

(4)

M.Dorigo給出了3種算法模型，分別為ant-cycle system, ant-quantity system, ant-density system，其區(qū)別就在于式(4)的不同[8]。

3 求解指派問題的蟻群算法設(shè)計

3.1 指派問題轉(zhuǎn)化為TSP

指派問題的解是得到一最優(yōu)指派方案，也就是將單位和任務(wù)進行配對，若首先讓單位(任務(wù))的次序固定，指派問題就變成了找任務(wù)(單位)的最優(yōu)次序問題，這時可將任務(wù)(單位)的序號看成TSP中的城市的序號，將效率cij看成是TSP中螞蟻所在城市到城市j間的距離，這樣就將指派問題轉(zhuǎn)化成了TSP，找到一行標(biāo)序列或列標(biāo)序列便得到問題的一個解。

3.2 算法改進

改進的蟻群算法是按從小到大的順序固定列標(biāo)，根據(jù)效率矩陣讓螞蟻逐列搜索按行標(biāo)找解，先隨機給定螞蟻第1列的一個行標(biāo)作為初始解，并將該行標(biāo)納入禁忌表，再搜索第2列得到下個行標(biāo)，直到搜索完所有列，得到所有行標(biāo)的一個序列，也就找到問題的一個解。根據(jù)指派問題的特點，算法主要作了以下改進。

1)動態(tài)設(shè)置算法參數(shù) 為使算法在迭代初期進行廣泛的搜索，中期既廣泛搜索又做到一定的收斂，后期做到較快收斂，將迭代次數(shù)分3段，對參數(shù)Q、ρ、α、β、q0進行了動態(tài)設(shè)置。

2)選擇概率的改進 將TSP中選擇概率中的自啟發(fā)因子ηij定義為1/cij(這里指最小化問題)，這樣cij越小，ηij越大。

5)最優(yōu)解檢驗方式的改進 計算螞蟻k所得路徑上的總效率ck，根據(jù)總效率最小原則改進保存最優(yōu)解。

根據(jù)以上對算法的改進和算法的基本思想，算法流程圖如圖1所示。

4 仿真試驗

圖1 算法流程圖

算例1[9]5個工件分配到5臺機床上，效率矩陣為

迭代200次，從圖2可以看出算法每一次均得到問題最優(yōu)解，最優(yōu)行標(biāo)序列為(5,2,3,4,1)，仿真結(jié)果及比較如表1所示，最優(yōu)值與文獻[2]結(jié)果相同。

算例2[10]10個任務(wù)分配給10臺機器，效率矩陣為：

迭代200次，從圖3可以看出算法迭代到第78次得到問題最優(yōu)解，得最優(yōu)行標(biāo)序列(7 ，5， 6 ，10， 9 ，3 ，2 ，1， 4， 8)，仿真結(jié)果及比較如表2所示，最優(yōu)值比文獻[10]結(jié)果略好。

表1 算例1最優(yōu)解比較表

表2 算例2最優(yōu)解比較表

圖2 算例1最優(yōu)值收斂曲線圖 圖3 算例2最優(yōu)值收斂曲線圖

5 結(jié) 語

通過將指派問題與TSP聯(lián)系起來，提出了一種改進的蟻群算法。實例仿真證明算法大規(guī)模問題求解上存在耗時長的缺點，但算法顯得簡單有效，是一種求解小規(guī)模指派問題的非常好的算法之一。

[1] Sukkarieh S, Nebot E M, Durrant-Whyte H F.A High Integrity IMU GPS Navigation Loop for Autonomous Land Vehicles Applications[J].IEEE, 1999, 15(3):572-578.

[2] 李言,陳祖安,徐躍飛,等.指派問題的遺傳算法研究與實現(xiàn)[J].西安理工大學(xué)學(xué)報,1996(4)：271-276.

[3] 談文芳 ,趙強,余勝陽,等.改進粒子群優(yōu)化算法求解任務(wù)指派問題[J].計算機應(yīng)用,2007(6)：50-52.

[4] 梁耀,覃征,楊利英,等.指派問題的變異蟻群算法求解[J].微電子學(xué)與計算機，2006(6):80-83.

[5] 董樹軍,張慶捷.軍事運籌學(xué)[M].北京：藍天出版社，2006.

[6] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005.

[7] Dorigo M, Gambardella L M.Ant colony system: a cooperative learning approach to the traveling salesman problem [J].IEEE Trans on Evolutional Computation, 1997,1(1):53-66.

[8] 秦玲.蟻群算法的改進與應(yīng)用[D] .揚州：揚州大學(xué)，2004.

[9] 李月秋,楊雅琴.最優(yōu)指派問題的一種新方法[J].高師理科學(xué)刊,2008(3)：15-17.

[10] 楊冬,王正歐.改進的螞蟻算法求解任務(wù)分配問題[J].天津大學(xué)學(xué)報,2004(4)：373-376.

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.10.035

TP312

A

1673-1409(2012)10-N113-04