改進(jìn)的蟻群算法在ＴＳＰ中的應(yīng)用

禹旺明　熊紅云

摘要：介紹了蟻群算法的特點(diǎn)，提出了基于蟻群算法的TSP問(wèn)題的求解方法，并分別建立基本蟻群算法及MAX—MIN蟻群算法模型，并引入“三步走”法確定模型參數(shù)的最優(yōu)組合，還結(jié)合了交叉局部?jī)?yōu)化相關(guān)的求凸殼頂點(diǎn)的算法進(jìn)行預(yù)處理，進(jìn)行仿真分析比較。實(shí)驗(yàn)結(jié)果表明基于MMAS模型相對(duì)于基本蟻群算法模型，有比較好最短路徑選擇能力及良好的可擴(kuò)展性能，能夠較好地適應(yīng)物流配送系統(tǒng)的要求。

關(guān)鍵詞：TSP；MMAS；信息素；三步走法

中圖分類號(hào)：F224文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1002-3100(2009)01-0027-03

Abstract: Introduces the features of ant colony optimization, puts forward solving method of TSP based on ant colony optimization, establishes these models of basic ant colony optimization and max-min ant colony optimization respectively, ascertains optimum combination of model parametric by three-step method and carries out reprocessing combining algorithm of convex hull peak related to cross-regional optimization to carry on simulation analysis and comparison. The result indicates that MMAS is superior to basic ant colony optimization because it chooses the shortest path and better meets the demand of logistics distribution system.

Key words: TSP; MMAS; pheromone; three-step method

0引言

蟻群算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)，由Marco Dorigo于1992年在他的博士論文中引入，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，經(jīng)過(guò)各種數(shù)值仿真結(jié)果表明該算法具有許多優(yōu)良的性質(zhì)，具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值，是一種求解組合最優(yōu)化問(wèn)題的新型通用啟發(fā)式方法，具有正反饋、分布式計(jì)算和富于建設(shè)性的貪婪啟發(fā)式搜索的特點(diǎn)，通過(guò)建立適當(dāng)?shù)臄?shù)學(xué)模型，可以解決一維靜態(tài)優(yōu)化問(wèn)題甚至多維動(dòng)態(tài)組合優(yōu)化問(wèn)題。

本文采用蟻群算法對(duì)TSP問(wèn)題進(jìn)行研究，設(shè)計(jì)一個(gè)基本的蟻群算法解決最短路徑問(wèn)題的模型，并提出一種最大——最小螞蟻系統(tǒng)（MMAS）模型，通過(guò)引入“三步走”法確定模型參數(shù)的最優(yōu)組合，使所選參數(shù)讓性能達(dá)到最優(yōu)；改進(jìn)信息素更新規(guī)律及動(dòng)態(tài)調(diào)整參數(shù)；并且引進(jìn)去交叉局部?jī)?yōu)化相關(guān)的求凸殼頂點(diǎn)的算法，改進(jìn)算法的局部搜索能力，對(duì)MMAS模型加以改進(jìn)，最終使收斂速度和收斂效果達(dá)到令人滿意的結(jié)果。

1基本蟻群算法及MMAS在TSP中的應(yīng)用

1.1問(wèn)題描述

旅行商問(wèn)題（traveling salesman problem，TSP）是著名NP 完全問(wèn)題之一，常被用于測(cè)試和評(píng)價(jià)算法的性能。該問(wèn)題可以簡(jiǎn)單描述如下：有一個(gè)商人需要選擇一條最短的哈密頓回路拜訪各城市，即所有城市必須經(jīng)過(guò)且只經(jīng)過(guò)一次，而最后要回到原來(lái)出發(fā)的城市。如果用窮舉的辦法解決該問(wèn)題，時(shí)間復(fù)雜度顯然是很大。當(dāng)比較大的時(shí)候，現(xiàn)有的計(jì)算機(jī)是無(wú)法在可接受的時(shí)間內(nèi)求解該問(wèn)題的。因此很多高效的算法被用于嘗試求解TSP。本文采用蟻群算法對(duì)TSP問(wèn)題進(jìn)行研究，并通過(guò)基本蟻群算法、MMAS、改進(jìn)的MMAS三者直接的比較得出最優(yōu)解。

1.2算法設(shè)計(jì)

（1）蟻群算法構(gòu)造TSP問(wèn)題的基本數(shù)學(xué)模型

設(shè)bt表示t時(shí)刻位于元素i城市的螞蟻數(shù)目，m表示螞蟻的總數(shù)目，n表示城市的規(guī)模：

t+n=p?t+△t（1）

t為t時(shí)刻路徑i,j上的信息量，則m=bt在初始時(shí)刻各路徑上的信息量相等，并設(shè)0＝const。

螞蟻kk＝1,2,…,m在運(yùn)動(dòng)過(guò)程中，根據(jù)各路徑上的信息量決定其轉(zhuǎn)移方向。這里用禁忌表tabu（k＝1,2,3,…,m）來(lái)記錄螞蟻k當(dāng)前所走過(guò)的城市，集合隨著tabu進(jìn)化過(guò)程做動(dòng)態(tài)調(diào)整。在搜索過(guò)程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來(lái)計(jì)算狀態(tài)轉(zhuǎn)移概率：pt表示在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率：

pt=，若j∈allowed0，否則 （2）

上式中，allowed＝C-tabu表示螞蟻下一步允許選擇的城市，C表示所有城市的集合；表示路徑i,j距離d的倒數(shù)即

=1/d；α、β分別表示信息素和路徑信息對(duì)轉(zhuǎn)移概率的影響程度。隨著時(shí)間的推移，以前留下來(lái)的信息素會(huì)逐漸揮發(fā)，用參數(shù)p表示信息素的揮發(fā)程度。經(jīng)過(guò)n個(gè)時(shí)刻，每個(gè)螞蟻都完成一次循環(huán)，各條路徑上的信息素須做調(diào)整：

t+n=1-p?t+△ （3）

其中0＜p＜1，△表示本次循環(huán)中所有經(jīng)歷過(guò)的路徑ij的螞蟻留在該路徑上的信息量的增量，局部調(diào)整用ant-cycle system調(diào)整信息素的方法：

△=Q/L，ant經(jīng)過(guò)i,j0，否則 （4）

其中，Q為常數(shù)，表示螞蟻循環(huán)一周所釋放的總信息量，L表示ant在這次循環(huán)中所走的路徑的長(zhǎng)度。

（2）最大最小信息素算法（MMAS）

MMAS與基本蟻群算法的主要區(qū)別在于把信息素?cái)?shù)量＝,，較好地避免了搜索面的局部停滯（早熟現(xiàn)象）。每次迭代路徑上增加的最大信息素為1/Ls，其中Ls為對(duì)應(yīng)全局最好解的路徑長(zhǎng)度，更新最好解時(shí)，同時(shí)更新，，與信息素?fù)]發(fā)因子p及Ls成反比，而與精英螞蟻的數(shù)目成正比。這里可按照以下策略動(dòng)態(tài)的確定t和t。

①在最初信息素還未得到更新時(shí)（即產(chǎn)生第一代解前），采用下式確定t和t：

t=g （5）

t= （6）

②一旦信息素更新以后則采用下式才更新t：

t=g+ （7）

（3）去交叉局部?jī)?yōu)化

在這里引進(jìn)去交叉局部?jī)?yōu)化相關(guān)的求凸殼頂點(diǎn)的算法對(duì)MMAS算法進(jìn)行改進(jìn)，凸殼問(wèn)題（convex hull problem）是幾何學(xué)中的基本問(wèn)題之一，在TSP中主要是對(duì)各點(diǎn)進(jìn)行預(yù)處理。設(shè)S是平面上的非空點(diǎn)集，z和z是S中的任意兩點(diǎn)，t是0與1之間的任意實(shí)數(shù)。如果滿足公式8的點(diǎn)Z屬于S，則S為凸集。

z＝tz+1-tz0≤t≤1（8）

凸集S中的凸殼是包含S的周長(zhǎng)最小的凸多邊形，凸殼必包含凸集，在TSP的預(yù)處理算法中，從某一凸殼的頂點(diǎn)開(kāi)始，需要判斷與其不相鄰的下一個(gè)凸殼頂點(diǎn)是否在同一條直線上，若不是，則消去此線，然后以此類推對(duì)其余的凸殼頂點(diǎn)進(jìn)行同樣處理。

2實(shí)例仿真

實(shí)例：中國(guó)的31個(gè)省會(huì)城市的坐標(biāo)C=[1 304 2 312；3 639 1 315；4 177 2 244；3 712 1 399；3 488 1 535；3 326 1 556；3 238 1 229；4 196 1 004；4 312 790；4 386 570；3 007 1 970；2 562 1 756；2 788 1 491；2 381 1 676；1 332 695；3 715

1 678；3 918 2 179；4 061 2 370；3 780 2 212；3 676 2 578；4 029 2 838；4 263 2 931；3 429 1 908；3 507 2 367；3 394

2 643；3 439 3 201；2 935 3 240；3 140 3 550；2 545 2 357；2 778 2 826；2 370 2 975]，下面以31個(gè)城市的坐標(biāo)為參考模型，分別建模仿真。

首先采用“三步走”方法選擇蟻群算法的最優(yōu)參數(shù)組合：

（1）確定螞蟻的數(shù)目，當(dāng)城市規(guī)模大致是螞蟻數(shù)目的1.5倍時(shí)，蟻群算法的全局收斂性和收斂速度都比較好。顯然這里螞蟻數(shù)目m選20比較適宜，城市n選31。

（2）參數(shù)粗調(diào)，調(diào)整取值范圍較大的信息啟發(fā)因子，期望啟發(fā)式因子β以及信息素強(qiáng)度Q等參數(shù)以得到較理想的解。經(jīng)過(guò)調(diào)整?。?.0，β＝5.0，Q=100。

（3）參數(shù)微調(diào)，在較小范圍內(nèi)調(diào)整信息素?fù)]發(fā)因子ρ。信息揮發(fā)素ρ取值為0.04。

實(shí)踐證明運(yùn)用此方法后在減少計(jì)算量、快速搜索、收斂性、收斂速度等方面都有較好的效果。在MMAS模型中σ取5，0＝2。進(jìn)行仿真后得到以下數(shù)據(jù)：圖1為運(yùn)行10次基本蟻群算法模型得到的最優(yōu)路徑；圖2為運(yùn)行10次改進(jìn)的MMAS模型得到的最優(yōu)路徑；圖3為運(yùn)行10次未改進(jìn)的MMAS模型得到的最優(yōu)路徑；表1中為兩種方法中的最短路徑的距離、平均距離、得到最優(yōu)最小迭代數(shù)及平均迭代數(shù)。

上述數(shù)據(jù)表明改進(jìn)型的MMAS對(duì)于基本蟻群算法及MMAS有一定的優(yōu)越性，所得的結(jié)果在收斂性、穩(wěn)定性、收斂速度等方面都有很大的改進(jìn)，并且改進(jìn)型MMAS不會(huì)出現(xiàn)圖3中的那種交叉路徑，能夠起到避免出現(xiàn)過(guò)早呆滯和及時(shí)糾正交叉的作用。圖4列出改進(jìn)的MMAS在實(shí)驗(yàn)過(guò)程中得到實(shí)時(shí)路徑數(shù)據(jù)。

3小結(jié)

本文主要是分析了蟻群算法及兩種類型蟻群算法在旅行商問(wèn)題中的應(yīng)用，通過(guò)MATLAB編程仿真了所建立模型，并把獲得的結(jié)果進(jìn)行了比較分析，由實(shí)時(shí)路徑圖也可以看到此算法的穩(wěn)定性能較強(qiáng)，能夠較好的應(yīng)用來(lái)解決旅行商問(wèn)題。

參考文獻(xiàn)：

[1] 段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)技術(shù)出版社，2005.

[2] 趙霞. MAX-MIN螞蟻系統(tǒng)算法及其收斂性證明[J]. 計(jì)算機(jī)工程與應(yīng)用，2006(8):70-72.

[3] 陳寶文，宋申民. 應(yīng)用于車輛路徑問(wèn)題的多蟻群算法[C]//第25屆中國(guó)控制會(huì)議論文集（下冊(cè)），2006:1723-1726.

[4] Yang Haiqing, Yang Haihong. An self-organizing neural network with convex-hull expanding property for TSP[C]//Neural Net-works and Brain, ICNN&B;' 05, International Conference on Volume1，2005:379-383.

[5] 蔡之華，彭錦國(guó)，高偉,等. 一種改進(jìn)的求解TSP問(wèn)題的演化算法[J]. 計(jì)算機(jī)學(xué)報(bào)，2005(28):823-828.

[6] 周培德. 求凸包定點(diǎn)的一種算法[J]. 北京理工大學(xué)學(xué)報(bào)，1993(13):69-72.

[7]趙凱，熊紅云. 模糊車輛配送問(wèn)題的改進(jìn)算法[J]. 物流科技，2008(2):24-27.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。