蚁群算法在旅行商问题中的应用.doc

姓名：徐嬴 学号：3008216107 成绩： 人工智能实验报告 一．项目内容 1.题目： 基于蚁群算法的旅行商问题 2.问题的初步理解 1.旅行商问题： 旅行商问题（tsp）是在寻求单一旅行者由起点城市出发，通过所有给定的城市之后，最后再回到原点的最小路径成本的问题。既是求解一个n个结点完全图的最小消耗汉密尔顿回路问题，搜索空间是 n的阶乘的级别，随着n的增长，算法复杂度迅速增长，产生组合爆炸现象，所以目前大多数算法都是启发式算法。 2.蚁群算法 蚁群算法（ACO）是一种用来在途中寻找优化路径的几率型算法。该方法受到了蚁群在寻找食物的过程中经过一段时间找到一条最短的路径的启发而形成的启发式算法。 蚁群在寻找食物过程中的过程中遵循以下几条规则： （1）蚂蚁的可行范围； （2）蚂蚁的行为，觅食规则和移动规则，通过感知周围的信息素，朝信息素多的方向移动，如果周围没有信息素，则按惯性移动，如果周围有障碍物，则会随机选择一个方向运动； （3）蚂蚁所处的环境，信息量以一定的速率消失； （4）播撒信息素原则，蚂蚁在找到食物或者窝的时候散发的信息素最多，并随着它走远的距离，信息量越来越少。 二：运行环境 系统环境是windows7，32位操作系统，编程环境为eclipse，CPU配置为ADM Sempron CPU 2.00GHz内存（RAM）：1.00GB 三．实现方法 1.数据结构 程序中大量使用二维数组保存节点距离，周游路径，节点间的信息素和可见度参数。 2.算法描述 蚁群算法解决旅行商问题，由于大量采用概率和随机，所以很难得到最优解，它只能得到在可以接受范围内的比较优化的解。其基本思想就是，模拟蚁群在觅食的过程中播散信息素的过程，在走过的路径上进行播撒信息素，而后蚂蚁又根据信息素的量来进行选择该走的路，如此达到正反馈的机制，即越来越多的蚂蚁走较为优化的路，该路上的信息素也越撒越多，最后得到一条较优的路径。其中，有两个问题需要说明，如下： （1）信息素的更新原则： A:信息素全局更新规则，程序中采用的规则如下： Tij(t+n)=（1-a）*Tij+a*Hij， 其中Tij(t+n)表示进行了一次周游后，i,j 两点间的信息素量，Tij(t)为i,j路径上原本的信息素的量，Hij的值为（1 / globalBestLength），globalBestlength为当前全局最优路径的长度。 B:信息素的局部更新，局部更新时，是更新一个固定的常数，是（1/（N*Length））,这里的length取值就是一个估计的均值，是旅行一周所走的距离，N是城市的个数。 （2）蚂蚁在行进过程中在每个城市的转移概率如下所示： （此为截图） 其中表示蚂蚁由i城市转移到j城市的概率，表示i到城市j的可见度，普遍的取值为i城到j城距离的倒数。其中alpha和beta是启发式因子，查找的资料中称alpha为信息启发式因子，作用是反映蚂蚁运动所引起的影响占整个信息素的影响的份额的大小，beta成为期望启发式因子，反映蚂蚁运动过程中倾向于贪心规则的程度。 （3）除了按照概率进行转移外，还要注意蚂蚁有小概率的犯错机会，这样才不会使结果过早地局限住。 3.算法的具体步骤 （1）初始化，共四步：L赋值循环的总次数，k记录当前循环次数，赋值为0；初始化信息量Tij和Hij；取M个蚂蚁，随机的放在N个城市上；计算N个城市间的距离，保存在距离矩阵中； （2）将个蚂蚁的出发位置记录于一个数组中，对每个蚂蚁计算下一步转移的概率，按转移的概率函数进行转移，此过程还要注意蚂蚁有小概率的出错情况，如此循环下去，完成对N个城市的访问； （3）计算一次迭代过程中各蚂蚁的旅程长度，比较，得出当前最好解，如果当前循环最优解小于全局最优解，则更新全局最优解为当前解； （4）按照得到的当前全局最优解进行全局信息素的更新； （5）循环次数增加，k=k+1; （6）若kL，转（2）。 4、结果分析 在此问题中，我采用两组值进行测试：（测试数据为网上下载） 第一组测试情况： 共三十个数据：{2,99},{4,50},{7,64},{13,40},{18,54},{18,40},{22,60},{24,42},{25,62},{25,38},{37,84},{41,94},{41,26},{44,35},{45,21},{54,67},{54,62},{58,35},{58,69},{62,32},{64,60},{68,58},{71,44},{71,71},{74,78},{82,7},{83,46},{83,69},{87,76},{91,38} 最优路径：best_length = 423.7406 我的测试结果为：在循环100次的情况下，最差情况出现了429.380298012607， 最好