蚂蚁算法商旅问题

1、1 研究背景1.1 商旅问题( Traveling salesman problem )也被称作邮递员路径问题。这个问题字面的描 述是：一个商人，要到n个城市兜售商品，他要从一个城市出发，走一条经过且仅经过所有每个城市一次的最短路径。这个问题由来已久，是一个经典的 NP 完全问题，由于应用范围 广泛， 在世界上受到很高度的重视。 商旅问题最直接的解法就是穷举法， 找出所有可能的路 径比较长短。但是显而易见，随着城市数的增多， 路径的数量将成指数级增长，很快这个数 字就会增长到用穷举法无法计算的地步。 因此，目前已经出现了多种有效的降低计算量而求 解商旅问题的方法。求解 TSP 问题的方法有很多

2、，比如经典的遗传算法，贪心算法等。由于TSP 问题的重要性，近几年来它依然是很热的问题，从 2007 年到 2009年也出现了很多研究 TSP 问题 的重要文献，相继提出了优化遗传算法， 多路遗传算法， 蚁群算法，模拟退火算法等一些更 高效更实用的求解方法。可见对 TSP 问题的求解还在进行当中，我们也期待更高效的求解 方法的出现。本文将使用之前老师们提出的混合蚂蚁算法来对小规模城市数的TSP 问题进行验证求解，以求得到学习的目的。1.2 蚁群算法 (ant colony optimization, ACO)，又称蚂蚁算法， 是一种用来在图中寻找优化路径的机率型技术。 它由 Marco Dor

3、igo 于 1992 年在他的博士论文中引入， 其灵 感来源于蚂蚁在寻找食物过程中发现路径的行为。蚂蚁在运动觅食过程中，分泌一种 信息素，蚂蚁走过的路径就会残留一定浓度的信息素，当后来的蚂蚁再走过这段路径 的时候，它们会以较大的概率选择信息素浓度大的路径行走，同时再放出信息素。这 就形成了一个正反馈，最优路径上的信息素浓度越来越大，最终可以找到最优路径。2 总体设计本文将对小规模 TSP 问题进行求解， 城市数 N 将设定为 10。该 TSP 问题的实质是在一 个顶点数为 10 的带权完全无向图中，找到一个权值最小的 Hamilton 回路。其精确描述为： G = ( V , E)是一个带权图

4、，V = 1 , 2 ,10为顶点集，E = ej = (i , j) /i , j V , i 工 j 为边集。dij (i , j V , i丰j)为顶点i到j的距离，其中dij > 0且dj工同时dj = dji (i , j V)。任务目标则是在顶点集 V中找到一个完全序列(从 i点出发，经过所有点一次)， 使其形成的回路中 刀dj最小。在求解过程中，文中将使用一种改进的混合蚂蚁算法。次进 化蚂蚁算法是相对基本蚂蚁算法而言的， 基本蚂蚁算法存在着一些缺陷， 为了使算法更加准 确，更加有效率，针对基本蚂蚁算法的缺陷我们做了相应的改进。具体有： 初始化时每条边上信息素浓度的设置；蚂蚁

5、的转移策略设置； 信息素的更新方法； 引入局部优化策略， 优化 蚂蚁所走路径等。3 详细设计3.1 初始化本文的混合蚂蚁算法中，有几个重要的参数如下：最大的循环次数NcMax ；城市的数目N ;蚂蚁的总数 M ;信息素总量 Q;程序开始的时候， 令时间t = 0;循环次数 NcMax = 0；信息素总量 Q 设置为 1000；并且令 M = 8 只蚂蚁随机的分布在 N= 10 座城市中。并 且每条城市之间的路径有一定的初始信息素浓度。 同时，为了保证一只蚂蚁从一个城市转移 到另一个城市的时候，只在一定数量的相对较近的城市中选择，定义了以下两个数据结构： 集合 ptabu 存放城市 i 的最近的

6、前 K 个城市的编号。 数据 Sumtabui 存放距城市 i 到与其最 近的前 K 个城市的距离之和。通过对每个城市 i 的相邻城市按距离排序，选择前 K 个城市 置于 ptabu 中，并且根据其距离计算 Sumtabui 。10座城市的之间的距离由一个二维数组int distanceNN保存。具体距离由下边给出(是对称矩阵，并且同城之间的距离设置为Max)：表城市编号123456789101Max5876152116982Max17614113021963Max319242019774Max213171222105Max921188136Max152316117Max2212308Max2

7、1279Max1510Max3.2初始边上的信息素量的设置在基本的蚂蚁算法中，一般在开始的时候，每条边上的信息素的量是相等的，以便使 蚂蚁可以初始时可以完全随机的选择下一次要移动的城市。但是在优化的蚂蚁算法中，为了使蚂蚁相对的倾向选择较近的城市，本文中算法在初始化时对每个顶点的相邻顶点按路径长 短不同设置了不同量的信息素，公式如下：signaltab = d * Q /Sumtabui * K /N。3.3信息素的更新基本蚂蚁算法采用的信息素更新方法，或者只考虑路径长度而不考虑每条边对减小路 径长度所做的贡献，或者不考虑路径长度，另外，对所有蚂蚁所走过的路径均更新信息素， 这些更新方法均不利于

8、信息素向最优路径上集中。本算法中，只对部分较短路径更新信息素。更新方法为：对所有蚂蚁走过的路径按长度排序，选择前F个较短路径更新路径上的信息素。3.4程序流程(1) 初始化M个蚂蚁，使其随机的分布在 N个城市上；(2) 初始化ptabu函数，sumtabu函数，signaltab函数，状态转移概率的计算函数，信息素 的更新函数；(3 )每一蚂蚁所走过的路径并且初值为1;(4) 记录每个蚂蚁所走的路径的长度和，并且初值为0;(5) 根据状态转移概率公式计算的概率选择城市；(6) 记录蚂蚁所走过的路径；(7) 修改禁忌表指针；(8 )更新每条路径上的信息浓度；(9 )循环计算直到到达设置的循环次数

9、。4实验数据本文的处理对象已经在表一中给出。相关参数的设定如下:循环次数 NcMax = 5000 ;总城市数 N = 10 ; 总蚂蚁数M = 8 ;相邻最近距离城市数K = 5 ;同城距离设定 MAX = 10000;信息素总量 Q = 1000 ; 对参数c分别取0.10.9 计算最短路径如下表： 表二参数C最短路径0.11120.21120.3970.4970.51120.6970.71020.8970.9126平均值106.2对于表一中所给的城市数据，经过穷举法计算得到最短路径长度为97 (出发点均为城市1),由于算法本身的缺陷和循环次数的限制，在9次计算中，得到最优解的次数为4次,

10、正确率为44.44%;而最终求得的平均值为 106.2，与最优解97相比的误差率为 9.48%。因 此可以看出经改进的蚂蚁算法在求得最优解上有些力不从心，而最短路径的平均值在可接受的范围之内。5程序源码int distanceNN = MAX,5,8,7,6,15,21,16,9,8,5,MAX,17,6,14,11,30,21,9,6, 8,17,MAX,3,19,24,20,19,7,7,7,6,3,MAX,21,3,17,12,22,10,6,14,19,21,MAX,9,21,18,8,13, 15,11,24,3,9,MAX,15,23,16,11,21,30,20,17,21,15

11、,MAX,22,12,30,16,21,19,12,18,23,22,MAX,2 1,27,9,9,7,22,8,16,12,21,MAX,15,8,6,7,10,13,11,30,27,15,MAX;int ptabuNN;int sumtabuN;double signaltabNN;int PathCityMN;int FindPathLengthM;/* 初始化M个蚂蚁，使其随机的分布在 N个城市上*/void lnitialAnt()int LocateCity = -1;/初始化for(int i = 0 ; i < M ; i+)LocateCity = rand()%N;

12、PathCityi0 = LocateCity;/* 寻找 ptabu 函数*/void FindPtabu()int itemNN;for(int i = 0 ; i < N ; i+)for(int j = 0 ; j < N ; j+) itemij = distanceij;/ 初始化for(i = 0 ; i < N ; i+)for(int j = 0 ; j < N ; j+)ptabuij = j+1;/* 寻找 sumtabu 函数*/void FindSumtabu()/ 初始化for(int i = 0 ; i < N ; i+)sumtab

13、ui = 0;/ 求解 sumtabufor(i = 0 ; i < N ; i+)for(int j = 0 ; j < K ; j+)sumtabui = sumtabui + distanceiptabuij;/* 寻找 signaltab 函数*/void FindSignaltab()/ 求解 signaltabfor(int i = 0 ; i < N ; i+)for(int j = 0 ; j < N ; j+) if(distanceij = MAX) signaltabij = 0;elseK / N; signaltabij = (double)d

14、istanceij * Q / sumtabui/*状态转移概率的计算函数/变量m表示所要计算的蚂蚁位于城市*/int ComputeProbability(int m)int CityNum = -1;/ 最终确定的转移城市double probability = 0;double sum = 0;double TempProbability = 0;/ 记录可以转移的城市int EnableTabN;for(int i = 0 ; i < N ; i+)EnableTabi = 0;/ 计算状态转移概率的分母for(i = 0 ; i < K ; i+)for(int j =

15、0 ; j < N ; j+) if(ptabumi = PathCitymj)break; if(ptabumi != PathCitymj && j < N)EnableTabj = 1;sum = sum + pow(signaltabmi , a) * pow(double)P / distancemi , b); if(j = N)int RandCity = rand() % N;EnableTabRandCity = 1;pow(double)P /* pow(double)P /sum = sum + pow(signaltabmRandCity ,

16、 a) * distancemRandCity , b);/ 根据公式计算概率并找到最大概率的城市for(i = 0 ; i < N ; i+)if(EnableTabi) if(sum) TempProbability = (double)pow(signaltabmi , a) distancemi , b) / sum;if(TempProbability > probability)CityNum = i; probability = TempProbability;return CityNum;/* 信息素的更新*/void UpdateSignal()int PathL

17、engthM;for(int i = 0 ; i < M ; i+) PathLengthi = FindPathLengthi;int LessLengthNumM;/ 记录所有蚂蚁走过的路径前 F 的蚂蚁 for(i = 0 ; i < M ; i+)LessLengthNumi = i;/ 寻找前 F 的蚂蚁 for(i = 0 ; i < F ; i+)for(int j = M-1 ; j > 0 ; j-) if(PathLengthj > PathLengthj-1)swap(PathLengthj , PathLengthj-1); swap(Le

18、ssLengthNumj , LessLengthNumj-1);/ 更新信息素for(i = 0 ; i < F ; i+)for(int j = 0 ; j < N-1 ; j+)!= -1) if(PathCityLessLengthNumij != -1 &&PathCityLessLengthNumij+1 signaltabPathCityLessLengthNumijPathCityLessLengthNumij+1(double)c signaltabPathCityLessLengthNumijPathCityLessLengthNumij+1 +

19、(double)Q / (PathLengthi distancePathCityLessLengthNumijPathCityLessLengthNumij+1);signaltabPathCityLessLengthNumij+1PathCityLessLengthNumij(double)c signaltabPathCityLessLengthNumij+1PathCityLessLengthNumij +(double)Q / (PathLengthi distancePathCityLessLengthNumijPathCityLessLengthNumij+1);/* 根据信息素

20、的分布信息，找到近似的最优路径*/void DisplayResult()int TheBestPathN;/ 记录最优的路径，并初始化为 1 for(int i = 0 ; i < N ; i+)TheBestPathi = -1;int TheLength = 0;int CurrentCity = 1;int CityNum = 0;int itemNN;/ 记录与每个城市相邻的城市的信息素由大到小的城市号 for(i = 0 ; i < N ; i+)for(int j = 0 ; j < N ; j+)itemij = j+1;/ 对每个城市的信息素进行由大到小的排

21、序for(i = 0 ; i < N ; i+)for(int k = 0 ; k < N ; k+)for(int j = N-1 ; j > 0 ; j-)if(signaltabij > signaltabij-1)swap(signaltabij , signaltabij-1); swap(itemij , itemij-1);/ 寻找最优路径while(CityNum < N-1)TheBestPathCityNum = CurrentCity;int m = 0;while(m < N)int i = 0;while(TheBestPathi

22、!= -1)if(TheBestPathi = itemCurrentCity-1m)break;i+;if(TheBestPathi = -1)CityNum+;TheBestPathCityNum = itemCurrentCity-1m;CurrentCity = itemCurrentCity-1m;TheLengthTheLengthdistanceTheBestPathCityNum-1TheBestPathCityNum-1-1;break;elsem+;cout << "The Length is : " << TheLength << endl;int main()/*/InitialAnt();FindPtabu();/ptab数组保存与各个蚂蚁最近的 K 条边FindSumtabu();/与各个蚂蚁最近的 K 条边的路程和FindSignaltab();/记录各条边上的信