《基本蚁群算法.doc》由会员分享，可在线阅读，更多相关《基本蚁群算法.doc（7页珍藏版）》请在三一文库上搜索。
1、蚁群算法浅析摘要：介绍了什么是蚁群算法，蚁群算法的种类，对四种不同的蚁群算法进行了分析对比。 详细阐述了蚁群算法的基本原理，将其应用于旅行商问题，有效地解决了问题。通过对旅行 商问题C+莫拟仿真程序的详细分析，更加深刻地理解与掌握了蚁群算法。 关键词：蚁群算法；旅行商问题；信息素；轮盘选择 一、引言蚁群算法( Ant Colony Optimization, ACO )，是一种用来在图中寻找优化路径的算法。 它由 Marco Dorigo 于 1992 年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中 发现路径的行为。蚁群算法是一种莫拟进化算法，初步的研究表明该算法具有许多优良的性 质
2、。蚁群算法成功解决了旅行商问题( Traveling Salesman Problem, TSP )：一个商人要到 若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个 城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最 短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。最基本的蚁群算法见第二节。目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。二、基本蚁群算法(一)算法思想各个蚂蚁在没有事先告诉他们食物在什么地
3、方的前提下开始寻找食物。当一只找到食物 以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更 多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样 多(或者较长的路上蚂蚁多， 这也无关紧要)。当蚂蚁沿着一条路到达终点以后会马上返回来， 这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走 过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下 更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。蚁群算法的基本思想如下图表示：图1等概率选择图2最优路径图3最优比重
4、（二）算法描述基本蚁群算法的算法简单描述如下：1 所有蚂蚁遇到障碍物时按照等概率选择路径，并留下信息素;2 随着时间的推移，较短路径的信息素浓度升高；3 蚂蚁再次遇到障碍物时，会选择信息素浓度高的路径；4 较短路径的信息素浓度继续升高，最终最优路径被选择出来。三、随机蚁群算法（一）算法思想在基本蚁群算法中，蚂蚁会在多条可选择的路径中，自动选择出最短的一条路径。但是, 一旦蚁群选择了一条比之前短的路径，就会认为这条路径是最好的，在这条路径上一直走下 去。这样的算法存在问题：蚂蚁可能只是找到了局部的最短路径，而忽略了全局最优解。因此，在基本蚁群算法的基础上，需要对蚂蚁选路的方案加以改善：有些蚂蚁并
5、没有象 其它蚂蚁一样总重复同样的路，他们会另辟蹊径，也就是它会按照一定的概率不往信息素高 的地方。如果令开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这 条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复 着，这就是优化的随机蚁群算法。为了实现蚂蚁的“随机”选路，我们需要做以下假设：1 范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径，如果半径等 于 2 ，那么它能观察到的范围就是 2*2 个方格世界，并且能移动的距离也在这个范围之内。2环境：环境以一定的速率让信息素消失。3觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就
6、直接过去。否则看 是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，那么它朝哪个方向走的概 率就大。这就意味着每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。4避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且 有信息素指引的话，它会按照觅食的规则行为。5播撒信息素规则：每只蚂蚁在找到食物后撒发的信息素。 自然想到一个问题：开始时环境没有信息素，蚂蚁为什么会相对有效的找到食物呢 这个问题用蚂蚁的移动规则同样可以解释。首先，它要能尽量保持某种惯性，这样使得 蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向） ，而不是原地无谓的打转或者 震动；其次
7、，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运 动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持 原来的方向，但又有新的试探，这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然 能找到隐蔽得很好的食物。（二）算法描述随机蚁群算法的算法描述如下：算法输入：城市数量N,两两城市间的距离，所有路径的信息素浓度算法输出：蚂蚁走过的路径长度1设置全部城市都没有去过，走过的路径长度为 0；2随机选择一个出发的城市；3i = 14while（i < N）4根据可选择路径的信息素浓度，计算出各自选中的概率；5根据不同选择的概率，使用轮盘选择算法，
8、得到选择的下一个城市；6将所在城市标记为不可选择；7end8计算走过路径的长度； 用随机蚁群算法解决旅行商问题，实际上是多次使用蚁群算法，不断更新最短路径的过 程。由此，我们容易得到旅行商问题的算法描述：算法输入：所有城市的X、丫坐标，蚂蚁数量n，迭代次数K 算法输出：旅行商的最短路径1计算两两城市间的距离，初始化所有路径信息素为0；2for i = 1 : K3 for j = 1 : n4第 j 只蚂蚁搜索一遍；567if 走过的路径小于最短路径更新最短路径；更新走过路径的信息素；8end9end四、改进的随机蚁群算法（一）排序蚁群算法与随机蚁群算法不同的是，当蚂蚁遇到障碍物选择路径时，根
9、据不同路径上信息素的浓 度，通过计算可能达到最优解的概率算法，将路径进行排序，选择最好的路径作为下一个通 往的城市。（二）最大最小蚁群算法 与随机蚁群算法和排序蚁群算法都不同的是，当蚂蚁遇到障碍物选择路径时，使用贪心 策略，优先选择达到下一个城市最短的城市，即得到局部最优解。这样以来，更多的信息素 将在较短的路径聚集，使算法更快地得到全局最短路径。五、算法比较本文介绍了四种蚁群算法，其中第一种比较简单，描述了最基本的蚁群算法思想。但是， 它忽略了更优路径存在的可能性，没有考虑到更普遍的情况。因此，该算法只适用于小规模， 无特殊情况的问题。后三种蚁群算法属于实际中典型的蚁群算法，对不同情况的考虑
10、比较全面，因此应用比 较广泛。三者的差别主要在于蚂蚁对不同路径的选择上，其中，随机蚁群算法首先根据不同 路径上信息素的浓度，计算出选择各条路径的概率，而后使用轮盘算法选择一条路径，适用 于规模不太大的场合；排序蚁群算法则根据选择各条路径的概率，对路径进行优先排序，选 择最好的路径作为下一个通往的城市，这样做增加了空间复杂度，有效改善了时间复杂度， 适用于规模较大的场合；最大最小蚁群算法则是采用贪心策略，优先选择达到下一个城市最 短的城市，先得到局部最优解，再通过聚类效应得到全局最短路径，适合对时间和空间要求 都较高的场合。参考文献：1. 丁洋 . 蚁群优化算法分析 . 论文期刊 . .蚁群优化
11、算法 . 附录：1预编译所需头文件#pragma once_nPathj;n=m_cAntAryi.m_nPathj-1;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;_nPath0;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;earch();_dbPathLength <m_cBestAnt=m_cAntAryj;f",i+1,;printf(cBuf);9
12、 main 函数主文件#include ""#include ""int main()/ 初始化随机种子time_t tm;time(&tm);unsigned int nSeed=(unsigned int)tm;srand(nSeed);/ 旅行商开始搜索CTsp tsp;();();/ 输出结果printf("nThe best tour is :nn");char cBuf128;for (int i=0;i<N_CITY_COUNT;i+)sprintf_s(cBuf,"%d ", printf(cBuf);sprintf_s(cBuf,"nnThe rand seed is : %d ",nSeed); printf(cBuf);printf("nnPress any key to exit!");getchar();return 0;