基于蚁优化算法的TSP问题求解计算智能实验报告

--

智能计算实验报告

学院：

班级:

学号：

姓名:

成绩：

日期：

--

--

实验名称：基于蚁优化算法的ＴSP问题求解

题目要求：

利用蚁优化算法对给定的TＳP问题进行求解,求出一条最短路径。

蚁优化算法简介:

蚁算法是一中求解复杂优化问题的启发式算法,该方法通过模拟蚁对“信息

素”的控制和利用进行搜索食物的过程,达到求解最优结果的目的。它具有智能

搜索、全局优化、稳健性强、易于其它方法结合等优点,适应于解决组合优化问

题，包括运输路径优化问题。

TSP数据文件格式分析：

本次课程设计采用的TSＰ文件是att4８.tsp,文件是由48组城市坐标构成的,文件

共分成三列，第一列为城市编号,第二列为城市横坐标,第三列为城市纵坐标。数

据结构如下所示:

城市编号城市横坐标城市纵坐标

实验操作过程:

1、TSＰ文件的读取：

classcｈｅnｇshｉ{

inｔnｏ；

doｕbｌex;

dｏubleｙ;

chenｇsｈi(intnｏ,dｏubｌｅx,doｕblｅｙ）｛

=no;

thｉｓ.x＝x;

this.y＝ｙ；

}

pｒiｖatedoｕblegｅtDｉsｔaｎce(cheｎｇsｈichengshｉ){

rｅturnsqrt（pow（(x-cｈengｓhｉ.ｘ),2）+ｐow((y

-ｃhenｇshi.y),2))；

}

｝

ｔｒy{

/／定义HaｓhMap保存读取的坐标信息

--

--

HaｓhMap＜Ｉｎtegｅr,chengshi>map=newHashMap

ｅr,cｈengshi>();

//读取文件

BufferedRｅaderreadeｒ=neｗＢｕffｅredReaｄer(ｎｅw

FileReader（neｗＦile（fileｎａｍe)));

ｆor(Strinｇｓtr=ｒeader．ｒeaｄLｉne();str！＝ｎu

ｌl;ｓtr=reader.rｅａdLine（)){

//将读到的信息保存入HashMap

if(ｓtr.ｍａtches("([０－９]+)（s*)([０-９］+)(.?)(［0－9]*)

（s＊）([0-9]+)(.？）([0-９]＊)")){

Strinｇ［]ｄａｔa=sｔｒ.splｉt(＂（＼ｓ+）");

chengshicｈengshi＝newcｈeｎgshi(Inｔegｅ

ｅInt(dａｔa[０］),

Ｄｏｕblｅ.ｐarsｅＤouｂle（dａta［1］）,

Doublｅ.ｐarsｅDoubｌｅ(ｄatａ

[２]))；

mａ（chｅnｇsｈ,cｈengshi);

}

}

//分配距离矩阵存储空间

disｔanｃｅ＝newdoublｅ[map.sｉｚｅ()＋1］[mａp．s

ｉze()+1］;

/／分配距离倒数矩阵存储空间

ｈeuｒｉｓtic=ｎewdoｕｂle［ｍap.ｓize()+1][maｐ.ｓize（)

+1］;

//分配信息素矩阵存储空间

pheromｏne=nｅｗdoubｌe［map．sｉｚe()+１][mａp.ｓi

ｚe（)+１];

ｆor（ｉnｔｉ=1;i<ｍａ()＋1;ｉ＋+）｛

for(iｎｔｊ=１;ｊ<ｍaｐ.ｓize（）+1;j++){

／/计算城市间的距离，并存入距离矩阵

diｓtance[i][j]=maｐ.geｔ(i)．getDisｔancｅ(mａ

(j)）;

／/计算距离倒数,并存入距离倒数矩阵

heuｒisｔiｃ［ｉ][j]=1/dｉsｔanｃe[ｉ］［j］;

//初始化信息素矩阵

phｅromｏne［i][j]=1；

}

}

}catｃh(Exceptiｏnexceｐtion）{

Syｓtem．ｉｎtln（"初始化数据失败！");

｝

}

2、TSＰ作图处理：

--

--

ｐrivatｅvoideｖapoｒａtｅＰheｒomonｅ(）{

for(iｎtｉ=1;i

for(intｊ=1;j

pｈerｏｍｏｎe[i][j］*＝１-rate；

}

ﻩ}

3、关键源代码(带简单的注释):

蚂蚁类代码:

ｃｌａｓｓｍayi{

//已访问城市列表

privatebooleａｎ[]vｉsiｔｅd;

//访问顺序表

ｐｒivaｔeiｎt［]touｒ;

/／已访问城市的个数

privatｅinｔn;

/／总的距离

privaｔedｏublｅｔoｔal;

mayi（){

//给访问顺序表分配空间

toｕr=ｎｅwinｔ[dｉｓtancｅ.lｅngｔｈ＋１］;

//已存入城市数量为n，刚开始为0

n=0；

//将起始城市１,放入访问结点顺序表第一项

ｔoｕr[+＋n]=1；

//给已访问城市结点分配空间

vｉsited=ｎｅｗbooｌｅan[dｉｓtａｎce．length］;

//第一个城市为出发城市，设置为已访问

visiteｄ[touｒ[n]]=true;

}

ｐrivateintchooｓeｃhengshi(){

//用来rａndｏm的随机数

--

--

ｄｏubｌｅｍ＝0;

//获得当前所在的城市号放入j,如果和j相邻的城市没有被访问,那

么加入m

ｆoｒ(ｉnｔｉ=１,j=tour[ｎ];i＜pheromｏｎe.ｌ

engtｈ;i++){

if(!visited［i]){

m+=pow(pheｒoｍoｎe[ｊ］[ｉ],alpｈa)*pow

（heurｉstic[ｊ]［i],ｂｅta);

}

｝

//保存随机数

dｏuｂleｐ=m*randoｍ()；

//寻随机城市

dｏublek=０;

/／保存城市

iｎtq=0;

for（inti=1,j=tour[n];k＜p;ｉ++){

if(!ｖisiｔeｄ［i]）｛

k+=pｏw(ｐheromone[j]［ｉ］,alｐha)＊p

ｏw(heｕristic[ｊ］［i］,betａ);

ｑ=i;

}

}

ｒｅｔurnq;

}

城市选择代码:

privａteinｔchooｓeｃｈｅngshi(){

//用来ranｄｏm的随机数

doublem=０;

--

--

//获得当前所在的城市号放入ｊ,如果和j相邻的城市没有被访

问，那么加入m

foｒ(intｉ=1，j＝tｏｕr[ｎ];i＜ｐｈeｒomoｎe.l

ｅngｔh；i＋+){

if(!ｖisｉtｅd[i]){

ｍ＋=ｐow（ｐheromｏnｅ[j][i］,ａlpha）*p

ｏw(heuriｓｔic[j]［i]，ｂetａ);

}

}

//保存随机数

ｄoｕblｅｐ=m*randｏm(）;

／／寻随机城市

dｏuｂlek=0;

//保存城市

iｎｔq＝0;

foｒ(intｉ=1,ｊ＝touｒ[n］;ｋ

iｆ(!vｉsited[ｉ］)｛

ｋ+=pｏｗ(pherｏmonｅ［ｊ][i],aｌpｈ

ａ)*pｏw(hｅurｉstic[ｊ］[i],beta);

q=i；

}

}

rｅtｕｒnｑ;

}

4、算法运行收敛图(即运行到第几步,求得的最优值是多少）:

ｒuｎ：

本次为倒数第100次迭代，当前最优路径长度为41６34.６0

本次为倒数第9９次迭代,当前最优路径长度为４１514.21

本次为倒数第98次迭代,当前最优路径长度为３８5１1.61

--

--

本次为倒数第97次迭代,当前最优路径长度为３８511.６1

本次为倒数第9６次迭代,当前最优路径长度为3851１．61

本次为倒数第９５次迭代，当前最优路径长度为38５11.61

本次为倒数第94次迭代,当前最优路径长度为３72９3．0７

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

本次为倒数第６次迭代,当前最优路径长度为37２９3．07

本次为倒数第5次迭代,当前最优路径长度为3７２93．０7

本次为倒数第4次迭代，当前最优路径长度为37293．07

本次为倒数第3次迭代,当前最优路径长度为37293.0７

本次为倒数第２次迭代,当前最优路径长度为3７29３.07

本次为倒数第１次迭代,当前最优路径长度为37293．07

得到的最优的路径长度为:3729３.07

5、最终求得的最优解的TSＰ图像：

最优路径如下：

→1→９→38→３1→44→18→7→２8→37→１9→６→30→43→2７→1７→

36→４6→33→15→12→11→23→14→2５→13→2０→47→21→3９→32→

48→5→29→2→２6→4→35→45→10→4２→２4→34→４1→１６→22→3

→４0→8→1成功生成(总时间：３秒)

实验结果分析:

本次通过JAVＡ语言实现蚁优化算法,我们发现虽然我们到了问题的最

优解，但是最优解的收敛性并不乐观，并不能求得问题的精确解，并且随着参数

的调节运行结果有随机性。另外,在蚁算法求解过程中，蚂蚁的数量和城市的

数量差距对结果也是具有一定影响的。

信息素的蒸发速度,对结果也有重要影响。目前来看,蚂蚁系统只是蚁算法

的一个最初的版本,他还有有待提高。这种算法，蚂蚁在其爬过的边上释放与其

构建路径长度成反比的信息素量,蚂蚁构建的路径越好，属于路径的各个边上所

获得的信息素就越多,这些边在以后的迭代中被蚂蚁选择的几率也就越大,但是我

们不难想象，当城市的规模较大的时候,问题的复杂度呈指数增长,仅仅靠这样一

个基础单一的信息素更新机制引导搜索偏向,搜索效率有瓶颈。针对这种现象，

--

--

我们可以在AS的基础上给蚂蚁要释放的信息素大小加上一个权值，加大各个边

信息素的差异，以指导搜索。在每一轮所有蚂蚁构建完路径后，他们将按照所的

路径的长短进行排名，只有生成了至今最优路径的蚂蚁和排名在前(W-1)的蚂蚁

才被允许释放信息素,蚂蚁在边(I,J)上释放的信息素的权值有蚂蚁的排名决定。

--