智能水滴算法求解TSP問題的研究

趙 莉，丁海軍

(河海大學(xué)常州校區(qū) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

智能水滴算法求解TSP問題的研究

趙 莉，丁海軍

(河海大學(xué)常州校區(qū) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

智能水滴算法是一種模擬自然界中河水和河床相互作用的算法，根據(jù)智能水滴算法易于收斂于局部最優(yōu)解，通過設(shè)置路徑間最大、最小泥土量對算法進(jìn)行改進(jìn)，實(shí)現(xiàn)了水滴優(yōu)化算法，并且將其運(yùn)用到TSP(旅行商問題)的求解中.并對TSP51、TSP76問題進(jìn)行仿真分析，結(jié)果表明改進(jìn)的水滴群算法比原智能水滴算法具有更好的求最優(yōu)解的能力，收斂速度更快，效果更好.

智能水滴算法；旅行商問題;最優(yōu)解

智能水滴算法(IDW)是2007年由Shah-Hosseini[1]首先提出來的，這個算法是由模仿自然界水系統(tǒng)和其周圍環(huán)境的相互作用而形成河道的過程進(jìn)行迭代運(yùn)算，最后得到優(yōu)化的結(jié)果.它提供了一種新的解決方案來解決NP難的問題.目前，智能水滴算法已經(jīng)被用于機(jī)器人路徑規(guī)劃[2]，n皇后問題[3]，多維背包問題 (MKP)[4]等一系列復(fù)雜優(yōu)化問題中,并取得了較好的實(shí)驗(yàn)結(jié)果.與已有的智能算法相比，如蟻群算法[6]、蜂群算法[7]、遺傳算法[8]等,智能水滴算法在解決復(fù)雜優(yōu)化問題中具有一定的優(yōu)勢，這表明智能水滴算法是一種具有發(fā)展前景的算法.

1 智能水滴

在自然界中，流動的水滴和河道之間的關(guān)系是通過作用力與反作用力形成的.無數(shù)的流動的水滴形成了一個非常大的流動群體，所以就創(chuàng)造了河流流經(jīng)的河道.流動的水滴一般具有2個基本的屬性：水滴前行的速度velocity(IWD)，水滴當(dāng)中攜帶的泥土含量soil(IWD).當(dāng)一個水滴點(diǎn)流動到其下方另外一點(diǎn)時，水滴的前行速度會變大，水滴自身攜帶的泥土含量會變多，在2個節(jié)點(diǎn)之間的河床上的泥土含量會變少.

對于每一個水滴來說，2個基本的屬性velocity和soil在水滴流動的過程中會發(fā)生變化，水滴流動的周圍環(huán)境就表示需要解決的問題，而智能水滴的作用其實(shí)就是為這些需要解決的問題找到一條最短的路徑.

2 智能水滴算法的TSP求解

TSP(旅行商問題)的目標(biāo)是在給定地圖上城市間所有可能行程中找到一條總長度最短的行程.假設(shè)G=(C,L)是一個有向完全圖，TSP的目標(biāo)是從有向完全圖G中找出一條長度最短的路徑，即一條對C={c1,c2,…,cn}中n個城市訪問且訪問一次的最短的封閉曲線.

2.1 邊緣選擇機(jī)制

當(dāng)?shù)趉個水滴在節(jié)點(diǎn)i時，選擇下一個節(jié)點(diǎn)j的概率如下：

(1)

其中：ηij=1/dij，dij為城市i和城市j之間的距離，ηij表示路徑(i,j)上的泥土量的啟發(fā)式因子.α是路徑中的泥土量在指導(dǎo)水滴群搜索中的相對重要度，其值越大，路徑中的泥土量在水滴選擇下一個要到的城市中起到的作用越大.β是水滴在流動過程中路徑長度信息在指導(dǎo)水滴群搜索中的相對重要性，其值越大，啟發(fā)式因子在水滴群選擇下一個城市時所起到的作用越大.

f是與路徑中泥土量相關(guān)的函數(shù)：

(2)

其中常數(shù)εs是一個非常小的正數(shù)，通常取值為0.01.用來防止函數(shù)f的分母為0，函數(shù)g用來確保將位置i與位置j之間的路徑泥土量轉(zhuǎn)換為正數(shù)，其表達(dá)式為：

(3)

其中函數(shù)min用來得到當(dāng)前位置與所有可能的下一個位置之間的泥土量的最小值.

2.2 更新當(dāng)前的動能和泥土含量

第k個水滴在t+1時刻從點(diǎn)i移動到下一點(diǎn)j的動能變換為vk(t+1)：

(4)

其中av，bv，cv是用戶選定的大于0的靜態(tài)參數(shù)，路徑上的泥土量soil(i,j)和第k個水滴中的泥土量都是由Δsoil(i,j)來更新的.

Δsoil(i,j)是指路徑中被移除的泥土量或是水滴中攜帶的泥土量，其中Δsoil(i,j)非線性正比于vIWDK的倒數(shù)：

(6)

Lk表示第k個水滴走過的路徑長度.

水滴從節(jié)點(diǎn)i移動到j(luò)路徑中的泥土量和水滴中含有的泥土量更新如下：

soil(i,j)=(1-ρn)soil(i,j)-ρnΔsoil(i,j).

(7)

soilIWDk=soilIWDk+Δsoil(i,j).

(8)

其中ρn通常取值0.9.

2.3 全局的泥土量更新

在每一次的IWD算法迭代結(jié)束后，對于一條迭代最優(yōu)的解決方法更新它的全局路徑中的泥土量：

soil(i,j)=(1+ρIWD)·soil(i,j)-

ρIWD·1/(NIB-1)·soilIWD.

(9)

其中ρIWD是全局泥土量更新參數(shù)，通常取值0.9.NIB是此次迭代中節(jié)點(diǎn)的數(shù)目.

3 改進(jìn)的智能水滴算法

由于路徑中的泥土含量隨著水滴的移動是不斷變化的，因此在算法搜索陷入局部最優(yōu)時，若某段路徑弧段的泥土含量的數(shù)量比其他的路徑上的泥土含量的數(shù)量多得多的時候，會導(dǎo)致算法提早進(jìn)入收斂狀況，針對這一不足點(diǎn)，文章通過借助MMAS思想，對各個路徑上的泥土量實(shí)施了最大和最小量的限制，即：

smin≤sij(t)≤smax.

式中：smin，smax分別表示各邊泥土量的最大值，最小值.按照文獻(xiàn)[5]中的漸進(jìn)估計方法，smin和smax取值如下：

(10)

其中Pbest在本文中取為0.5，n為城市的數(shù)目，E(sgb)是目前為止找到的最短解.

在每一次循環(huán)后，必須確保泥土量sij(t)遵循這一限制條件，若有sij(t)>smax，則設(shè)置sij(t)=smax；若sij(t)

算法具體步驟如下:

1) 初始化算法中的各個參數(shù)，開始時,循環(huán)次數(shù)iterc為0，并設(shè)置最大循環(huán)次數(shù)itercmax,并將m個水滴置于n個城市上；

2) 當(dāng)iterc≤itercmax時，iterc向上加1，并轉(zhuǎn)到步驟3)，否則，跳轉(zhuǎn)到步驟8)；

3) 對水滴的禁忌表索引號k=1；

4) 水滴依據(jù)狀態(tài)轉(zhuǎn)移概率公式計算得到概率選擇城市j來前進(jìn)，j∈{C-tabuk}；

5) 修改禁忌表，并將水滴轉(zhuǎn)移到新的城市，把新城市轉(zhuǎn)移到水滴的禁忌表中；

6) 對于每一個從節(jié)點(diǎn)i移動到節(jié)點(diǎn)j的水滴，更新其動能并計算泥土量.并轉(zhuǎn)到4)；

7)當(dāng)所有城市遍歷完，并找到一條迭代最優(yōu)的路徑，更新全局的泥土量，清空禁忌表且轉(zhuǎn)到步驟2)；

8) 輸出最終結(jié)果.

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法的有效性，算法由Java語言實(shí)現(xiàn)，并在Javascript環(huán)境下編譯，在不同的TSP問題上進(jìn)行驗(yàn)證，在所有的實(shí)驗(yàn)中設(shè)置靜態(tài)參數(shù)av,bv,cv和as,bs,cs分別為1，0.1，1.節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的泥土量初始化sinit=1 000.每一個水滴的動能初始為vinit=200.α=0.4，β=0.8.水滴的數(shù)目m和城市的數(shù)目相等，最大迭代次數(shù)為 1 000，每個程序運(yùn)行50次.

表1 TSP51問題實(shí)驗(yàn)仿真結(jié)果

表2 TSP76問題實(shí)驗(yàn)仿真結(jié)果

由上述的實(shí)驗(yàn)結(jié)果可知，改進(jìn)的智能水滴算法在對各個路徑上的泥土量進(jìn)行了最大最小的限制以后，由表1、2的結(jié)果在最佳路徑長度上較基本的智能水滴算法略優(yōu)，在運(yùn)行時間上，也占有一定的優(yōu)勢，這是因?yàn)橥ㄟ^對路徑上的泥土量設(shè)置上下限，能夠降低算法的時間復(fù)雜度，避免算法出現(xiàn)停滯.由圖1、2可知，改進(jìn)的智能水滴算法比基本的智能水滴算法在收斂速度及尋找最優(yōu)解方面更加有效，進(jìn)一步加強(qiáng)了該算法求最優(yōu)解的能力，防止算法陷入局部最優(yōu).

5 結(jié)語

研究結(jié)果表明，改進(jìn)的智能水滴算法在對路徑中的泥土含量進(jìn)行了限制以后，提高了算法的收斂速度，有效地防止算法陷入局部最優(yōu)解，該改進(jìn)算法能夠在迭代次數(shù)較少的情況下，較基本的智能水滴算法更能找到一條最優(yōu)解.但是智能水滴算法參數(shù)較多，設(shè)置的值不同可能會導(dǎo)致該算法的效率不同，如何有效設(shè)置參數(shù),提升算法的效率與精度，這是今后的研究方向.

[1] SHAH-HOSSEINI H.Problem solving by intelligent water drops[C]//Evolutionary Computation,2007.IEEE,2007:3226-3231.

[2] DUAN H,LIU S,LEI X.Air robot path planning based on intelligent water drops optimization[C]//Neural Networks,2008.IEEE,2008:1397-1401.

[3] 劉娟,歐陽建權(quán),陳良軍.用混合遺傳算法求解n皇后問題[J].湘潭大學(xué)學(xué)報：自然科學(xué)版,2007,29(2):37-41.

[4] SHAH-HOSSEINI H.Optimization with the nature-inspired intelligent water drops algorithm [J].Evolutionary Computation,2009:297-320.

[5] EBERHART R C,KENNEDY J.A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science.1995(1):39-43.

[6] DORIGO M,GAMBARDELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].Evolutionary Computation,IEEE Transactions on,1997,1(1):53-66.

[7] WONG L P,LOW M Y H,CHONG C S.A bee colony optimization algorithm for traveling salesman problem[C]//Proceedings of the 2008 Second Asia International Conference on Modelling & Simulation (AMS).IEEE Computer Society,2008:818-823.[8] GREFENSTETTE J,GOPAL R,ROSMAITA B,et al.Genetic algorithms for the traveling salesman problem[C]//Proceedings of the first International Conference on Genetic Algorithms and their Applications.New Jersey:Lawrence Erlbaum,1985:160-168.

(責(zé)任編輯 莊紅林)

Intelligent water drops algorithm for solving TSP

ZHAO Li，DING Hai-jun

(1.College of Internet of Things Engineering,Hohai University at Changzhou,Changzhou 213022,China)

Intelligent water drops algorithm is a meta-heuristic method that imitates some natural phenomena of a swarm of water drops with the soil onto the river-bed.Because it is easy to converge to a local optimal solution, this paper gives an improved algorithm by setting the maximum and minimum amount of soil on the path. The paper applies it to the Traveling Salesman Problem (TSP), and gives a simulation analysis of TSP51 and TSP76 problems. The experimental results show that theis improved water drops algorithm is better than the previous one.

intelligent water drops algorithm;TSP;optimal solution

2014-06-03.

趙莉(1990-)，女，碩士研究生．主要研究方向:數(shù)據(jù)挖掘．

丁海軍(1963-)，男，碩士，副教授，碩士生導(dǎo)師．主要研究方向:數(shù)據(jù)挖掘．

TN929.5

A

1672-8513(2015)01-0062-04