蚂蚁算法商旅问题.doc

用蚂蚁算法求解商旅问题1 研究背景1.1 商旅问题（Traveling salesman problem）也被称作邮递员路径问题。这个问题字面的描述是：一个商人，要到n个城市兜售商品，他要从一个城市出发，走一条经过且仅经过所有每个城市一次的最短路径。这个问题由来已久，是一个经典的NP完全问题，由于应用范围广泛，在世界上受到很高度的重视。商旅问题最直接的解法就是穷举法，找出所有可能的路径比较长短。但是显而易见，随着城市数的增多，路径的数量将成指数级增长，很快这个数字就会增长到用穷举法无法计算的地步。因此，目前已经出现了多种有效的降低计算量而求解商旅问题的方法。求解TSP问题的方法有很多，比如经典的遗传算法，贪心算法等。由于TSP问题的重要性，近几年来它依然是很热的问题，从2007年到2009年也出现了很多研究TSP问题的重要文献，相继提出了优化遗传算法，多路遗传算法，蚁群算法，模拟退火算法等一些更高效更实用的求解方法。可见对TSP问题的求解还在进行当中，我们也期待更高效的求解方法的出现。本文将使用之前老师们提出的混合蚂蚁算法来对小规模城市数的TSP问题进行验证求解，以求得到学习的目的。1.2 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚂蚁在运动觅食过程中，分泌一种信息素，蚂蚁走过的路径就会残留一定浓度的信息素，当后来的蚂蚁再走过这段路径的时候，它们会以较大的概率选择信息素浓度大的路径行走，同时再放出信息素。这就形成了一个正反馈，最优路径上的信息素浓度越来越大，最终可以找到最优路径。2 总体设计本文将对小规模TSP问题进行求解，城市数N将设定为10。该TSP问题的实质是在一个顶点数为10的带权完全无向图中，找到一个权值最小的Hamilton回路。其精确描述为：G = （V , E）是一个带权图，V = 1 , 2 , 10 为顶点集，E = eij = (i , j)i , jV , i j为边集。dij (i , j V , i j)为顶点i到j的距离，其中dij0且dij ，同时dij = dji （i ，jV）。任务目标则是在顶点集V中找到一个完全序列（从i点出发，经过所有点一次），使其形成的回路中dij最小。在求解过程中，文中将使用一种改进的混合蚂蚁算法。次进化蚂蚁算法是相对基本蚂蚁算法而言的，基本蚂蚁算法存在着一些缺陷，为了使算法更加准确，更加有效率，针对基本蚂蚁算法的缺陷我们做了相应的改进。具体有：初始化时每条边上信息素浓度的设置；蚂蚁的转移策略设置；信息素的更新方法；引入局部优化策略，优化蚂蚁所走路径等。3 详细设计3.1 初始化 本文的混合蚂蚁算法中，有几个重要的参数如下：最大的循环次数 NcMax；城市的数目 N；蚂蚁的总数 M；信息素总量 Q；程序开始的时候，令时间t = 0；循环次数 NcMax = 0；信息素总量Q 设置为1000；并且令 M = 8 只蚂蚁随机的分布在 N= 10 座城市中。并且每条城市之间的路径有一定的初始信息素浓度。同时，为了保证一只蚂蚁从一个城市转移到另一个城市的时候，只在一定数量的相对较近的城市中选择，定义了以下两个数据结构：集合ptabu存放城市i的最近的前K个城市的编号。数据Sumtabui 存放距城市i到与其最近的前K个城市的距离之和。通过对每个城市i的相邻城市按距离排序，选择前K个城市置于ptabu中，并且根据其距离计算Sumtabui。 10座城市的之间的距离由一个二维数组int distanceNN保存。具体距离由下边给出（是一对称矩阵，并且同城之间的距离设置为Max）：表一城市编号123456789101Max5876152116982Max17614113021963Max319242019774Max213171222105Max921188136Max152316117Max2212308Max21279Max1510Max3.2 初始边上的信息素量的设置在基本的蚂蚁算法中，一般在开始的时候，每条边上的信息素的量是相等的，以便使蚂蚁可以初始时可以完全随机的选择下一次要移动的城市。但是在优化的蚂蚁算法中，为了使蚂蚁相对的倾向选择较近的城市，本文中算法在初始化时对每个顶点的相邻顶点按路径长短不同设置了不同量的信息素，公式如下：signaltab = d * Q Sumtabui * KN。3.3 信息素的更新基本蚂蚁算法采用的信息素更新方法，或者只考虑路径长度而不考虑每条边对减小路径长度所做的贡献，或者不考虑路径长度，另外，对所有蚂蚁所走过的路径均更新信息素，这些更新方法均不利于信息素向最优路径上集中。本算法中，只对部分较短路径更新信息素。更新方法为:对所有蚂蚁走过的路径按长度排序，选择前F个较短路径更新路径上的信息素。3.4 程序流程（1）初始化M个蚂蚁,使其随机的分布在N个城市上；（2）初始化ptabu函数，sumtabu函数，signaltab函数，状态转移概率的计算函数，信息素的更新函数；（3）每一蚂蚁所走过的路径 并且初值为1；（4）记录每个蚂蚁所走的路径的长度和，并且初值为0；（5）根据状态转移概率公式计算的概率选择城市；（6）记录蚂蚁所走过的路径；（7）修改禁忌表指针；（8）更新每条路径上的信息浓度；（9）循环计算直到到达设置的循环次数。4 实验数据本文的处理对象已经在表一中给出。相关参数的设定如下：循环次数 NcMax = 5000 ；总城市数 N = 10 ；总蚂蚁数M = 8 ；相邻最近距离城市数 K = 5 ；同城距离设定MAX = 10000; 信息素总量 Q = 1000;对参数 c 分别取 0.1 0.9 计算最短路径如下表：表二参数C最短路径0.1 1120.21120.3970.4970.51120.6970.71020.8970.9126平均值106.2对于表一中所给的城市数据，经过穷举法计算得到最短路径长度为97（出发点均为城市1），由于算法本身的缺陷和循环次数的限制，在9次计算中，得到最优解的次数为4次，正确率为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,MAX,22,12,30,16,21,19,12,18,23,22,MAX,21,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 InitialAnt()int LocateCity = -1;/初始化for(int i = 0 ; i M ; i+)LocateCity = rand()%N;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+)sumtabui = 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;elsesignaltabij = (double)distanceij * Q / sumtabui * K / N;/*状态转移概率的计算函数/变量m表示所要计算的蚂蚁位于城市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 = 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;sum = sum + pow(signaltabmRandCity , a) * pow(double)P / distancemRandCity , b);/根据公式计算概率并找到最大概率的城市for(i = 0 ; i probability)CityNum = i;probability = TempProbability;return CityNum;/*信息素的更新*/void UpdateSignal()int PathLengthM;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 0 ; j-)if(PathLengthj PathLengthj-1)swap(PathLengthj , PathLengthj-1);swap(LessLengthNumj , LessLengthNumj-1);/更新信息素for(i = 0 ; i F ; i+)for(int j = 0 ; j N-1 ; j+)if(PathCityLessLengthNumij != -1 & PathCityLessLengthNumij+1 != -1)signaltabPathCityLessLengthNumijPathCityLessLengthNumij+1 = (double)c * signaltabPathCityLessLengthNumijPathCityLessLengthNumij+1 + (double)Q / (PathLengthi * distancePathCityLessLengthNumijPathCityLessLengthNumij+1);signaltabPathCityLessLengthNumij+1PathCityLessLengthNumij = (double)c * signaltabPathCityLessLengthNumij+1PathCityLessLengthNumij + (double)Q / (PathLengthi * distancePathCityLessLengthNumijPathCityLessLengthNumij+1);/*根据信息素的分布信息，找到近似的最优路径*/void DisplayResult()int TheBestPathN;/记录最优的路径，并初始化为1for(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;/对每个城市的信息素进行由大到小的排序for(i = 0 ; i N ; i+)for(int k = 0 ; k 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 != -1)if(TheBestPathi = itemCurrentCity-1m)break;i+;if(TheBestPathi = -1)CityNum+;TheBestPathCityNum = itemCurrentCity-1m;CurrentCity = itemCurrentCity-1m;TheLength = TheLength + distanceTheBestPathCityNum-1TheBestPathCityNum-1-1;break;elsem+;cout The Length is : TheLength endl;int main()/*/InitialAnt();FindPtabu();/ptab数组保存与各个蚂蚁最近的K条边FindSumtabu();/与各个蚂蚁最近的K条边的路程和FindSignaltab()