蚁群算法解决TSP问题(含详细注释+200行代码)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了蚁群算法解决TSP问题(含详细注释+200行代码)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6155字，纯文字阅读大概需要9分钟。
内容图文
一、蚁群算法
蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。
二、算法实现步骤（结合本题代码）
- 设置各种参数（迭代次数、蚁群数量、城市数量、信息素挥发速率等）
- 根据城市坐标点计算城市之间距离，并且初始化城市间路线上的信息素
- 判断迭代次数是否达到目标值，若达到目标值则跳出循环，输出当前路线长度最短的最佳路径，程序结束；否则进入步骤4
- 判断在某次迭代中，判断完成旅行的蚂蚁数量是否达到目标值，若达到目标值则结束当前迭代，并且迭代次数加1，更新最短路径和最短路径值，并且利用蚁环模型更新信息素，进入步骤3。否则进入步骤5
- 判断当前蚂蚁走过的城市数是否等于所有城市数，若完成旅行，则完成旅行的蚂蚁数量加1，进入步骤4。否则进入步骤6
- 计算蚂蚁从当前城市到所有未经过的下一个城市的概率，并通过轮盘算法进行选择下一个城市，则当前蚂蚁走过的城市数+1，修改禁忌表，进入步骤5
三、实现代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
using namespace std;
int CityPos[30][2]={{87,7},{91,38},{83,46},{71,44},{64,60},{68,58},{83,69},{87,76},{74,78},{71,71},{58,69},{54,62},{51,67},{37,84},{41,94},{2,99},{7,64},{22,60},{25,62},{18,54},{4,50},{13,40},{18,40},{24,42},{25,38},{41,26},{45,21},{44,35},{58,35},{62,32}};
#define CITYNUM 20 //城市数量
#define ANTNUM 30 //蚁群数量
#define ITER 10 //迭代最大次数
#define R 0.5 //误差大小
#define ALPHA 1 // 信息素重要程度的参数
#define BETA 4 // 启发式因子重要程度的参数
#define Q 100 //信息素残留参数
const int maxn = 100;
double dis[maxn][maxn]; //距离
double info[maxn][maxn]; //信息素矩阵
int vis[CITYNUM][CITYNUM];
const double maxx = 10e9+10;
int random1(int l,int h){ //针对整数
return l+(h-l)*rand()/(RAND_MAX+1);
}
double random2(double l,double h){ //针对浮点数
double temp=rand()/((double)RAND_MAX+1.0);
return l+temp*(h-l);
}
void city_init(){
//计算两两城市间距离 可以考虑放在城市初始化中
for (int i = 0; i < CITYNUM; i++){
for (int j = 0; j < CITYNUM; j++){
double temp1=CityPos[j][0]-CityPos[i][0];
double temp2=CityPos[j][1]-CityPos[i][1];
dis[i][j] = sqrt(temp1*temp1+temp2*temp2);
}
}
//初始化环境信息素
for (int i=0; i<CITYNUM; i++){
for (int j=0; j<CITYNUM; j++){
info[i][j]=1; //线路上的信息素
}
}
}
class Ant{
public:
int path[CITYNUM]; //蚂蚁走的路径
double length; //路径总长度
int vis[CITYNUM]; //走过城市标记
int cur_pos; //当前城市
int arrived_city; //到达的城市数量
//初始化
Ant(){}
void init(){
memset(vis, 0, sizeof(vis));
length = 0;
cur_pos = random1(0, CITYNUM);//随机选择一个出发城市
path[0] = cur_pos;
vis[cur_pos] = 1;
arrived_city = 1;
}
//选择下一个要走的城市
int NextCity(){
int index=-1; //下一个要走的城市的下标
double sum_p=0; //未经历过的城市的信息素的总和
double p[CITYNUM]; //各个城市被选中的概率
for(int i = 0; i < CITYNUM; i++){
if (!vis[i]){
p[i]=pow(info[cur_pos][i],ALPHA)*pow(1.0/dis[cur_pos][i], BETA);
sum_p += p[i]; //计算当前点到未访问城市点的路线的的总信息素
}
}
for(int i = 0; i < CITYNUM; i++){
if (!vis[i]){ //计算未被访问的城市被选中做下一个访问城市的概率
p[i]/=sum_p;
}
else p[i] = 0; //代表已经被访问，因此被选中的概率为0
}
//进行轮盘赌法选择下一个城市
double temp=0; //总的信息素值大于0
if (sum_p > 0){
temp = random2(0,1);
for (int i = 0; i < CITYNUM; i++){
if (!vis[i]){
temp -= p[i];
if (temp < 0){ //代表当前城市被选中
index = i;
break;
}
}
}
}
if (index == -1){ //若轮盘赌法不成功，则选择编号最小的未去过的城市作为下一个目标
for (int i=0; i<CITYNUM; i++){
if (!vis[i]){ //城市没去过
index=i;
break;
}
}
}
return index;
}
//蚂蚁在城市间移动
void move(){
int city_index = NextCity();//选择下一个城市
path[arrived_city] = city_index;//保存蚂蚁走的路径
vis[city_index] = 1;//把这个城市设置成已经去过
cur_pos = city_index;//更新当前位置
length += dis[path[arrived_city-1]][path[arrived_city]];
arrived_city++;
}
void start(){ //蚂蚁开始出发完成一次环线
init();
while(arrived_city < CITYNUM){ //移动数小于所有城市数时则一直移动
move();
}
length += dis[path[CITYNUM-1]][path[0]];
}
};
class TSP{
public:
Ant ant[ANTNUM]; //定义一群蚂蚁
Ant target; //保存最好结果的蚂蚁
TSP(){
target.length = maxx; //初始化为最大值
}
//进行信息素的更新
void update()
{
double addInfo[CITYNUM][CITYNUM];
memset(addInfo, 0, sizeof(addInfo));
int m = 0;
int n = 0;
//遍历每只蚂蚁，更新路线信息素
for (int i = 0; i <ANTNUM; i++) {
for (int j = 1; j < CITYNUM; j++){
m = ant[i].path[j];
n = ant[i].path[j-1];
addInfo[n][m] = addInfo[n][m]+Q/ant[i].length; //使用的是蚁环模型来增加信息素
addInfo[m][n] = addInfo[n][m];
}
//更新起始和结束城市间路线的信息素
n = ant[i].path[0];
addInfo[n][m] = addInfo[n][m]+Q/ant[i].length;
addInfo[m][n] = addInfo[n][m];
}
//更新总体环境信息素
for (int i = 0; i < CITYNUM; i++){
for (int j = 0; j < CITYNUM; j++) {
info[i][j] = info[i][j]*R + addInfo[i][j]; //R为信息素挥发速率
}
}
}
void start(){ //TSP问题的开始
for (int i = 0; i < ITER; i++) { //蚁群需要的迭代次数
// printf("current iteration times %d\n", i);
cout<<"current iteration times :"<<i<<endl;
for (int j = 0; j <ANTNUM; j++) { //对于每只蚂蚁开始移动
ant[j].start();
cout<<"ant "<<j<<" path:";
for(int k=0;k<CITYNUM;k++){ //把每个蚂蚁的路径打印出来
cout<<ant[j].path[k]<<" ";
}
cout<<endl;
}
for (int j = 0; j <ANTNUM; j++) {
if (target.length > ant[j].length) {
target = ant[j]; //不断更新最佳结果
}
}
update(); //每一次蚁群完成环线后进行信息素的更新
printf("the shortest length %lf", target.length);
cout<<" in iteration "<<i<<endl;
cout<<"The best path in iteration"<<i<<": ";
for (int i = 0; i < CITYNUM; i++) {
cout<<target.path[i]<<" ";
}
cout<<endl<<endl<<endl;
}
}
};
int main(){
srand((unsigned)time(NULL));
city_init();
TSP tsp;
tsp.start();
cout<<"The final route:"<<endl;
for (int i = 0; i < CITYNUM; i++) {
cout<<tsp.target.path[i]<<" ";
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的蚁群算法解决TSP问题(含详细注释+200行代码)全部内容，希望文章能够帮你解决蚁群算法解决TSP问题(含详细注释+200行代码)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】