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

王書勤, 黃 茜

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

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

王書勤, 黃 茜

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

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

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

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

1 指派問題

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

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

指派問題既是一個整數規劃模型也是一個線性規劃模型[5]。

2 蟻群算法

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

(1)

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

(2)

(3)

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

在ant-cycle system模型中:

(4)

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

3 求解指派問題的蟻群算法設計

3.1 指派問題轉化為TSP

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

3.2 算法改進

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

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

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

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

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

4 仿真試驗

圖1 算法流程圖

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

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

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

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

表1 算例1最優解比較表

表2 算例2最優解比較表

圖2 算例1最優值收斂曲線圖 圖3 算例2最優值收斂曲線圖

5 結 語

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

[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] 李言,陳祖安,徐躍飛,等.指派問題的遺傳算法研究與實現[J].西安理工大學學報,1996(4)：271-276.

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

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

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

[6] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,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] 秦玲.蟻群算法的改進與應用[D] .揚州：揚州大學，2004.

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

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

[編輯] 洪云飛

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

TP312

A

1673-1409(2012)10-N113-04