学步园

不知道现在是否还有人在研究蚁群算法？应该有吧。当初为了找C或C++源代码而不可得，在阅读了多份"杂七杂八"的代码的基础，总算写出来了。运行了三个TSP经典用例，基本符合要求。2008年3月份写的，现在贴出来大家共享一下，注释加的应该算齐全。仅仅是一份按照蚁群算法的原理写的代码，没有做任何优化。至于我做优化后的代码，就不发出来了吧，呵呵。环境为:Windows XP SP2 + VC 6.0.

 /*********************************<br /> *作者:陈杰<br /> *单位:四川大学计算机学院<br /> *邮件地址:scucj@126.com<br /> *完成时间:2008年3月<br /> *********************************/</p> <p>#include<iostream><br /> #include<math.h><br /> #include<time.h><br /> using namespace std;</p> <p>//该程序是以蚁群系统为模型写的蚁群算法程序(强调：非蚂蚁周模型)，以三个著名的TSP问题为测试对象<br /> //通过微调参数，都可以获得较好的解</p> <p>/*<br /> //----------(1)问题一：Oliver 30 城市 TSP 问题 best_length = 423.7406; ------------------------<br /> //该程序最好的结果是423.741，可运行多次获得<br /> //城市节点数目<br /> #define N 30<br /> //城市坐标<br /> double C[N][2]={<br /> {2,99},{4,50},{7,64},{13,40},{18,54},{18,40},{22,60},{24,42},{25,62},{25,38},<br /> {37,84},{41,94},{41,26},{44,35},{45,21},{54,67},{54,62},{58,35},{58,69},{62,32},<br /> {64,60},{68,58},{71,44},{71,71},{74,78},{82,7},{83,46},{83,69},{87,76},{91,38}<br /> };<br /> //----------上面参数是固定的，下面的参数是可变的-----------<br /> //蚂蚁数量<br /> #define M 30<br /> //最大循环次数NcMax<br /> int NcMax = 500;<br /> //信息启发因子，期望启发式因子，全局信息素挥发参数，局部信息素挥发参数, 状态转移公式中的q0<br /> double alpha = 2, beta = 3, rou = 0.1, alpha1 = 0.1, qzero = 0.01;<br /> //-----------问题一结束------------------------------------------------------------------------<br /> */</p> <p>/*<br /> //----------(2)问题二：Elion50 城市 TSP 问题 best_length = 427.96; ----------------------------<br /> //该程序最好的结果是428.468，可运行多次获得<br /> //城市节点数目<br /> #define N 50<br /> //城市坐标<br /> double C[N][2]={<br /> {5,64}, {5,25}, {5,6}, {7,38}, {8,52}, {10,17},<br /> {12,42}, {13,13}, {16,57}, {17,33}, {17,63},<br /> {20,26}, {21,47}, {21,10}, {25,32}, {25,55},<br /> {27,68}, {27,23}, {30,48}, {30,15}, {31,62},<br /> {31,32}, {32,22}, {32,39}, {36,16}, {37,69},<br /> {37,52}, {38,46}, {39,10}, {40,30}, {42,57},<br /> {42,41}, {43,67}, {45,35}, {46,10}, {48,28},<br /> {49,49}, {51,21}, {52,33}, {52,41}, {52,64},<br /> {56,37}, {57,58}, {58,27}, {58,48}, {59,15},<br /> {61,33}, {62,42}, {62,63}, {63,69}<br /> };<br /> //----------上面参数是固定的，下面的参数是可变的-----------<br /> //蚂蚁数量<br /> #define M 50<br /> //最大循环次数NcMax<br /> int NcMax = 1000;<br /> //信息启发因子，期望启发式因子，全局信息素挥发参数，局部信息素挥发参数, 状态转移公式中的q0<br /> double alpha = 2, beta = 4, rou = 0.1, alpha1 = 0.1, qzero = 0.01;<br /> //-----------问题二结束------------------------------------------------------------------------<br /> */</p> <p>//----------(3)问题三：Elion75 城市 TSP 问题 best_length = 542.31;<br /> //该程序最好的结果是542.309，可运行多次获得<br /> //城市节点数目<br /> #define N 75<br /> //城市坐标<br /> double C[N][2]={<br /> {6,25}, {7,43}, {9,56}, {10,70}, {11,28},<br /> {12,17}, {12,38}, {15,5}, {15,14}, {15,56},<br /> {16,19}, {17,64}, {20,30}, {21,48}, {21,45},<br /> {21,36}, {22,53}, {22,22}, {26,29}, {26,13},<br /> {26,59}, {27,24}, {29,39}, {30,50}, {30,20},<br /> {30,60}, {31,76}, {33,34}, {33,44}, {35,51},<br /> {35,16}, {35,60}, {36,6}, {36,26}, {38,33},<br /> {40,37}, {40,66}, {40,60}, {40,20}, {41,46},<br /> {43,26}, {44,13}, {45,42}, {45,35}, {47,66},<br /> {48,21}, {50,30}, {50,40}, {50,50}, {50,70},<br /> {50,4}, {50,15}, {51,42}, {52,26}, {54,38},<br /> {54,10}, {55,34}, {55,45}, {55,50}, {55,65},<br /> {55,57}, {55,20}, {57,72}, {59,5}, {60,15},<br /> {62,57}, {62,48}, {62,35}, {62,24}, {64,4},<br /> {65,27}, {66,14}, {66,8}, {67,41}, {70,64}<br /> };<br /> //----------上面参数是固定的，下面的参数是可变的-----------<br /> //蚂蚁数量<br /> #define M 75<br /> //最大循环次数NcMax<br /> int NcMax =1000;<br /> //信息启发因子，期望启发式因子，全局信息素挥发参数，局部信息素挥发参数, 状态转移公式中的q0<br /> double alpha = 2, beta = 5, rou = 0.1, alpha1 = 0.1, qzero = 0.1;<br /> //-----------问题三结束------------------------------------------------------------------------</p> <p>//===========================================================================================================<br /> //局部更新时候使用的的常量，它是由最近邻方法得到的一个长度<br /> //什么是最近邻方法?:)就是从源节点出发，每次选择一个距离最短的点来遍历所有的节点得到的路径<br /> //每个节点都可能作为源节点来遍历<br /> double Lnn;<br /> //矩阵表示两两城市之间的距离<br /> double allDistance[N][N];</p> <p>//计算两个城市之间的距离<br /> double calculateDistance(int i, int j)<br /> {<br /> return sqrt(pow((C[i][0]-C[j][0]),2.0) + pow((C[i][1]-C[j][1]),2.0));<br /> }</p> <p>//由矩阵表示两两城市之间的距离<br /> void calculateAllDistance()<br /> {<br /> for(int i = 0; i < N; i++)<br /> {<br /> for(int j = 0; j < N; j++)<br /> {<br /> if (i != j)<br /> {<br /> allDistance[i][j] = calculateDistance(i, j);<br /> allDistance[j][i] = allDistance[i][j];<br /> }<br /> }<br /> }<br /> }</p> <p>//获得经过n个城市的路径长度<br /> double calculateSumOfDistance(int* tour)<br /> {<br /> double sum = 0;<br /> for(int i = 0; i< N ;i++)<br /> {<br /> int row = *(tour + 2 * i);<br /> int col = *(tour + 2* i + 1);<br /> sum += allDistance[row][col];<br /> }<br /> return sum;<br /> }</p> <p>class ACSAnt;</p> <p>class AntColonySystem<br /> {<br /> private:<br /> double info[N][N], visible[N][N];//节点之间的信息素强度,节点之间的能见度<br /> public:<br /> AntColonySystem()<br /> {<br /> }<br /> //计算当前节点到下一节点转移的概率<br /> double Transition(int i, int j);<br /> //局部更新规则<br /> void UpdateLocalPathRule(int i, int j);<br /> //初始化<br /> void InitParameter(double value);<br /> //全局信息素更新<br /> void UpdateGlobalPathRule(int* bestTour, int globalBestLength);<br /> };</p> <p>//计算当前节点到下一节点转移的概率<br /> double AntColonySystem::Transition(int i, int j)<br /> {<br /> if (i != j)<br /> {<br /> return (pow(info[i][j],alpha) * pow(visible[i][j], beta));<br /> }<br /> else<br /> {<br /> return 0.0;<br /> }<br /> }<br /> //局部更新规则<br /> void AntColonySystem::UpdateLocalPathRule(int i, int j)<br /> {<br /> info[i][j] = (1.0 - alpha1) * info[i][j] + alpha1 * (1.0 / (N * Lnn));<br /> info[j][i] = info[i][j];<br /> }<br /> //初始化<br /> void AntColonySystem::InitParameter(double value)<br /> {<br /> //初始化路径上的信息素强度tao0<br /> for(int i = 0; i < N; i++)<br /> {<br /> for(int j = 0; j < N; j++)<br /> {<br /> info[i][j] = value;<br /> info[j][i] = value;<br /> if (i != j)<br /> {<br /> visible[i][j] = 1.0 / allDistance[i][j];<br /> visible[j][i] = visible[i][j];<br /> }<br /> }<br /> }<br /> }</p> <p>//全局信息素更新<br /> void AntColonySystem::UpdateGlobalPathRule(int* bestTour, int globalBestLength)<br /> {<br /> for(int i = 0; i < N; i++)<br /> {<br /> int row = *(bestTour + 2 * i);<br /> int col = *(bestTour + 2* i + 1);<br /> info[row][col] = (1.0 - rou) * info[row][col] + rou * (1.0 / globalBestLength);<br /> info[col][row] =info[row][col];<br /> }<br /> }</p> <p>class ACSAnt<br /> {<br /> private:<br /> AntColonySystem* antColony;<br /> protected:<br /> int startCity, cururentCity;//初始城市编号，当前城市编号<br /> int allowed[N];//禁忌表<br /> int Tour[N][2];//当前路径<br /> int currentTourIndex;//当前路径索引，从0开始，存储蚂蚁经过城市的编号<br /> public:<br /> ACSAnt(AntColonySystem* acs, int start)<br /> {<br /> antColony = acs;<br /> startCity = start;<br /> }<br /> //开始搜索<br /> int* Search();<br /> //选择下一节点<br /> int Choose();<br /> //移动到下一节点<br /> void MoveToNextCity(int nextCity);</p> <p>};</p> <p>//开始搜索<br /> int* ACSAnt::Search()<br /> {<br /> cururentCity = startCity;<br /> int toCity;<br /> currentTourIndex = 0;<br /> for(int i = 0; i < N; i++)<br /> {<br /> allowed[i] = 1;<br /> }<br /> allowed[cururentCity] = 0;<br /> int endCity;<br /> int count = 0;<br /> do<br /> {<br /> count++;<br /> endCity = cururentCity;<br /> toCity = Choose();<br /> if (toCity >= 0)<br /> {<br /> MoveToNextCity(toCity);<br /> antColony->UpdateLocalPathRule(endCity, toCity);<br /> cururentCity = toCity;<br /> }<br /> }while(toCity >= 0);<br /> MoveToNextCity(startCity);<br /> antColony->UpdateLocalPathRule(endCity, startCity);</p> <p> return *Tour;<br /> }</p> <p>//选择下一节点<br /> int ACSAnt::Choose()<br /> {<br /> int nextCity = -1;<br /> double q = rand()/(double)RAND_MAX;<br /> //如果 q <= q0,按先验知识，否则则按概率转移，<br /> if (q <= qzero)<br /> {<br /> double probability = -1.0;//转移到下一节点的概率<br /> for(int i = 0; i < N; i++)<br /> {<br /> //去掉禁忌表中已走过的节点,从剩下节点中选择最大概率的可行节点<br /> if (1 == allowed[i])<br /> {<br /> double prob = antColony->Transition(cururentCity, i);<br /> if (prob > probability)<br /> {<br /> nextCity = i;<br /> probability = prob;<br /> }<br /> }<br /> }<br /> }<br /> else<br /> {<br /> //按概率转移<br /> double p = rand()/(double)RAND_MAX;//生成一个随机数,用来判断落在哪个区间段<br /> double sum = 0.0;<br /> double probability = 0.0;//概率的区间点，p 落在哪个区间段，则该点是转移的方向<br /> //计算概率公式的分母的值<br /> for(int i = 0; i < N; i++)<br /> {<br /> if (1 == allowed[i])<br /> {<br /> sum += antColony->Transition(cururentCity, i);<br /> }<br /> }<br /> for(int j = 0; j < N; j++)<br /> {<br /> if (1 == allowed[j] && sum > 0)<br /> {<br /> probability += antColony->Transition(cururentCity, j)/sum;<br /> if (probability >= p || (p > 0.9999 && probability > 0.9999))<br /> {<br /> nextCity = j;<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> return nextCity;<br /> }</p> <p>//移动到下一节点<br /> void ACSAnt::MoveToNextCity(int nextCity)<br /> {<br /> allowed[nextCity]=0;<br /> Tour[currentTourIndex][0] = cururentCity;<br /> Tour[currentTourIndex][1] = nextCity;<br /> currentTourIndex++;<br /> cururentCity = nextCity;<br /> }</p> <p>//------------------------------------------<br /> //选择下一个节点，配合下面的函数来计算的长度<br /> int ChooseNextNode(int currentNode, int visitedNode[])<br /> {<br /> int nextNode = -1;<br /> double shortDistance = 0.0;<br /> for(int i = 0; i < N; i++)<br /> {<br /> //去掉已走过的节点,从剩下节点中选择距离最近的节点<br /> if (1 == visitedNode[i])<br /> {<br /> if (shortDistance == 0.0)<br /> {<br /> shortDistance = allDistance[currentNode][i];<br /> nextNode = i;<br /> }<br /> if(shortDistance < allDistance[currentNode][i])<br /> {<br /> nextNode = i;<br /> }<br /> }<br /> }<br /> return nextNode;<br /> }</p> <p>//给一个节点由最近邻距离方法计算长度<br /> double CalAdjacentDistance(int node)<br /> {<br /> double sum = 0.0;<br /> int visitedNode[N];<br /> for(int j = 0; j < N; j++)<br /> {<br /> visitedNode[j] = 1;<br /> }<br /> visitedNode[node] = 0;<br /> int currentNode = node;<br /> int nextNode;<br /> do<br /> {<br /> nextNode = ChooseNextNode(currentNode, visitedNode);<br /> if (nextNode >= 0)<br /> {<br /> sum += allDistance[currentNode][nextNode];<br /> currentNode= nextNode;<br /> visitedNode[currentNode] = 0;<br /> }<br /> }while(nextNode >= 0);<br /> sum += allDistance[currentNode][node];<br /> return sum;<br /> }</p> <p>//---------------------------------结束---------------------------------------------</p> <p>//--------------------------主函数--------------------------------------------------<br /> int main()<br /> {<br /> time_t timer,timerl;</p> <p> time(&timer);<br /> unsigned long seed = timer;<br /> seed %= 56000;<br /> srand((unsigned int)seed);</p> <p> //由矩阵表示两两城市之间的距离<br /> calculateAllDistance();<br /> //蚁群系统对象<br /> AntColonySystem* acs = new AntColonySystem();<br /> ACSAnt* ants[M];<br /> //蚂蚁均匀分布在城市上<br /> for(int k = 0; k < M; k++)<br /> {<br /> ants[k] = new ACSAnt(acs, (int)(k%N));<br /> }<br /> calculateAllDistance();<br /> //随机选择一个节点计算由最近邻方法得到的一个长度<br /> int node = rand() % N;<br /> Lnn = CalAdjacentDistance(node);</p> <p> //各条路径上初始化的信息素强度<br /> double initInfo = 1 / (N * Lnn);<br /> acs->InitParameter(initInfo); </p> <p> //全局最优路径<br /> int globalTour[N][2];<br /> //全局最优长度<br /> double globalBestLength = 0.0;<br /> for(int i = 0; i < NcMax; i++)<br /> {<br /> //局部最优路径<br /> int localTour[N][2];<br /> //局部最优长度<br /> double localBestLength = 0.0;<br /> //当前路径长度<br /> double tourLength;<br /> for(int j = 0; j < M; j++)<br /> {<br /> int* tourPath = ants[j]->Search();<br /> tourLength = calculateSumOfDistance(tourPath);<br /> //局部比较，并记录路径和长度<br /> if(tourLength < localBestLength || abs(localBestLength - 0.0) < 0.000001)<br /> {<br /> for(int m = 0; m< N; m++)<br /> {<br /> int row = *(tourPath + 2 * m);<br /> int col = *(tourPath + 2* m + 1);<br /> localTour[m][0] = row;<br /> localTour[m][1] = col;<br /> }<br /> localBestLength = tourLength;<br /> }<br /> }<br /> //全局比较，并记录路径和长度<br /> if(localBestLength < globalBestLength || abs(globalBestLength - 0.0) < 0.000001)<br /> {<br /> for(int m = 0; m< N; m++)<br /> {<br /> globalTour[m][0] = localTour[m][0];<br /> globalTour[m][1] = localTour[m][1];<br /> }<br /> globalBestLength = localBestLength;<br /> }<br /> acs->UpdateGlobalPathRule(*globalTour, globalBestLength);<br /> //输出所有蚂蚁循环一次后的迭代最优路径<br /> cout<<"第 "<<i + 1<<" 迭代最优路径:"<<localBestLength<<"."<<endl;<br /> for(int m = 0; m< N; m++)<br /> {<br /> cout<<localTour[m][0]<<".";<br /> }<br /> cout<<endl;<br /> }<br /> //输出全局最优路径<br /> cout<<"全局最优路径长度:"<<globalBestLength<<endl;<br /> cout<<"全局最优路径:";<br /> for(int m = 0; m< N; m++)<br /> {<br /> cout<<globalTour[m][0]<<".";<br /> }<br /> cout<<endl;<br /> time(&timerl);<br /> int t = timerl - timer;<br /> return 0;<br /> }<br /> //--------------------------主函数结束--------------------------------------------------

源代码下载:

[1]蚁群算法源代码

PS:如果大家认为代码写的还算通俗易懂的话，就留个言吧。当然，扔个鸡蛋我也不反对。