C++下基于蚁群算法解决TSP问题

admin · 发表于 2024-7-16 23:09:23

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define m 100 //蚂蚁的个数
#define n 31 //城市的数量
const int NC_max = 100; //最大迭代次数
const double Alpha = 1; //表征信息素重要程度的参数
const double Beta = 5; //表征启发式因子重要程度的参数
const double Rho = 0.1; //信息素蒸发系数
const double Q = 100; //信息素增加强度系数
const double C[n][2] = //各个城市的坐标数据
{ { 1304, 2312 },
{ 3639, 1315 },
{ 4177, 2244 },
{ 3712, 1399 },
{ 3488, 1535 },
{ 3326, 1556 },
{ 3238, 1229 },
{ 4196, 1004 },
{ 4312, 790 },
{ 4386, 570 },
{ 3007, 1970 },
{ 2562, 1756 },
{ 2788, 1491 },
{ 2381, 1676 },
{ 1332, 695 },
{ 3715, 1678 },
{ 3918, 2179 },
{ 4061, 2370 },
{ 3780, 2212 },
{ 3676, 2578 },
{ 4029, 2838 },
{ 4263, 2931 },
{ 3429, 1908 },
{ 3507, 2367 },
{ 3394, 2643 },
{ 3439, 3201 },
{ 2935, 3240 },
{ 3140, 3550 },
{ 2545, 2357 },
{ 2778, 2826 },
{ 2370, 2975 }
};
double D[n][n]; //表示完全图的邻接矩阵
double Eta[n][n]; //表示启发式因子，为D中距离的倒数
double DeltaTau[n][n]; //表示启发式因子的变化量
double Tau[n][n]; //路径上面信息素的浓度
int Tabu[m][n]; //禁忌表，存储走过的路径
double L_best[NC_max]; //存储每次迭代的路径的最短长度
double L_ave[NC_max]; //存储每次迭代的路径的平均长度
int R_best[NC_max][n]; //存储每次迭代的最佳路线
void ValueInit(void) //变量初始化函数
{
for (int i = 0; i < n; i++) //初始化 D[n][n] 31
{
for (int j = 0; j < n; j++)//31
{
if (i != j)
D[i][j] = pow(pow((C[i][0] - C[j][0]), 2) + pow((C[i][1] - C[j][1]), 2), 0.5);
else
D[i][j] = DBL_EPSILON;//极小数，对角线上的数0
}
}
for (int i = 0; i < n; i++) //初始化 Eta[n][n] 启发式因子，距离矩阵倒数
for (int j = 0; j < n; j++)
Eta[i][j] = 1.0 / D[i][j];
for (int i = 0; i < n; i++) //初始化 DeltaEta[n][n] 启发式因子变化量
for (int j = 0; j < n; j++)
DeltaTau[i][j] = 0;
for (int i = 0; i < n; i++) //初始化 Tau[n][n] 信息素浓度
for (int j = 0; j < n; j++)
Tau[i][j] = 1.0;
for (int i = 0; i < m; i++) //初始化 Tabu[m][n] 存储走过的路径
for (int j = 0; j < n; j++)
Tabu[i][j] = 0;
}
void ValueDisplayTabu(int(*p)[n]) //禁忌表，存储走过的路径, 显示函数
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << *(*(p + i) + j) << ' ';
}
cout << endl;
}
}
void ValueDisplayTau(double(*p)[n]) //信息素的浓度,显示函数
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << *(*(p + i) + j) << ' ';
}
cout << endl;
}
}
double rnd(double lower, double uper) //生成lower和uper之间的一个double类型随机数
{
return (rand() / (double)RAND_MAX) * (uper - lower) + lower;
}
int main()
{
//第一步：进行变量的初始化
ValueInit(); //计算距离矩阵、初始化启发因子
int NC = 0;
while (NC < NC_max)//迭代次数100
{
//第二步：将m只蚂蚁随机放到n个城市上
vector<int> temp;
for (int i = 0; i < ceil((double)m / (double)n); i++) //m/n 蚂蚁数/城市数 100/31
{
for (int j = 0; j < n; j++)//31
temp.push_back(j);
}
random_shuffle(temp.begin(), temp.end()); //打乱temp数组中元素的次序
for (int i = 0; i < m; i++)//100
{
Tabu[i][0] = temp[i];//走过的路径，一共100个城市访问路径，第一个城市为随机选取的，temp里面有124个城市点
}
//第三步：m只蚂蚁按概率函数选择n中的下一座城市，完成各自的周游
for (int j = 1; j < n; j++)//31
{
for (int i = 0; i < m; i++)//100个路径
{
vector<int> visited; //第i只蚂蚁已访问过的城市
vector<int> J; //第i只蚂蚁待访问的城市
vector<double> P; //第i只蚂蚁待访问的城市的概率
double Psum = 0.0; //概率值和
double rate = 0.0; //随机数
double choose = 0.0; //轮盘赌算法累加值
int to_visit=0; //下一个要去的城市
for (int k = 0; k < j; k++)
visited.push_back(Tabu[i][k]); //visited初始化 0,0
for (int k = 0; k < n; k++)//31
{
if (find(visited.begin(), visited.end(), k) == visited.end()) //在visited中没有找到k
{
J.push_back(k); //J初始化待访问城市
P.push_back(0.0); //P初始化访问的概率
}
}
for (int k = 0; k < P.size(); k++)
{
//计算去某个城市的概率
int x = Tau[visited.back()][J[k]]; //Tau=1 Alpha=1 Beta=5 Eta=1/Distance(距离越小，这个值越大)
P[k] = pow(Tau[visited.back()][J[k]], Alpha) * pow(Eta[visited.back()][J[k]], Beta);//5
Psum += P[k];
}
//随机生成0~Psum之间的一个数
rate = rnd(0.0, Psum); //使用轮盘赌算法，挑选下一座要去的城市
for (int k = 0; k < P.size(); k++)
{
choose += P[k];
if (rate < choose)
{
to_visit = J[k];//待访问城市
break;
}
}
//访问的路径
Tabu[i][j] = to_visit; //更新禁忌表 100条访问城市的路径每个城市初始信息素
}
}
//第四步：记录本次迭代蚂蚁行走的路线数据
double L[m]; //记录本代每只蚂蚁走的路程，并初始化 100个路径
for (int i = 0; i < m; i++)
{
L[i] = 0.0;
}
for (int i = 0; i < m; i++)//100
{
for (int j = 0; j < n - 1; j++)//31
{
L[i] += D[Tabu[i][j]][Tabu[i][j + 1]];//L[i]代表第i个路径的代价
}
L[i] += D[Tabu[i][0]][Tabu[i][n - 1]]; //终点和起点的距离
}
double min_value = L[0]; //声明求本代所有蚂蚁行走距离最小值的临时变量
double sum_value = L[0]; //声明求本代所有蚂蚁行走距离总值的临时变量
int min_index = 0; //记录本代所有蚂蚁行走距离最小值的下标
for (int i = 1; i < m; i++)
{
sum_value += L[i];
if (L[i] < min_value)
{
min_value = L[i];
min_index = i;
}
}
L_best[NC] = min_value; //每代中路径的最短长度
L_ave[NC] = sum_value / m; //每代中路径的平均长度
for (int i = 0; i < n; i++)
{
R_best[NC][i] = Tabu[min_index][i]; //记录每代最短的路径数据
}
cout << NC << ": best cost is: " << L_best[NC] << ' ' << "the avg of ever iter is: " << L_ave[NC] << endl; //打印各代距离信息
NC++; //迭代继续
//第五步：更新信息素
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n - 1; j++)
{
//DeltaTau[i][j]信息素增量,表示蚂蚁在i到j路径上留下的信息素，L[i]表示蚂蚁已经走过路径的总长度
//所以总长度越小，信息素越多
DeltaTau[Tabu[i][j]][Tabu[i][j + 1]] += Q / L[i]; //此次循环在整个路径上的信息素增量 Q=100
}
DeltaTau[Tabu[i][n - 1]][Tabu[i][0]] += Q / L[i];
}
for (int i = 0; i < n; i++)//100
{
for (int j = 0; j < n; j++)
{
//Tau[i][j] 路径i到j上的信息素残余量
Tau[i][j] = (1 - Rho) * Tau[i][j] + DeltaTau[i][j]; //考虑信息素挥发，更新后的信息素 T = p * T + delta Qho=0.1，信息素挥发速度
}
}
for (int i = 0; i < m; i++) //信息素清零
for (int j = 0; j < n; j++)
Tabu[i][j] = 0;
}
//第六步：取出最优结果
double min_L = L_best[0]; //所有迭代中最短距离
int min_L_index = 0; //所有迭代中最优路径的下标
int Shortest_Route[n]; //所有迭代中的最优路径
for (int i = 0; i < NC; i++)
{
if (L_best[i] < min_L)
{
min_L = L_best[i];
min_L_index = i;
}
}
cout << "The length of the shortest route is " << min_L << endl;
cout << "The number of iteration is " << min_L_index << endl;
cout << "The Shortest route is： " << endl;
for (int i = 0; i < n; i++) //所有迭代中的最优路径
{
Shortest_Route[i] = R_best[min_L_index][i];
if (i == n - 1) {
cout << Shortest_Route[i];
}
else {
cout << Shortest_Route[i] << " -> ";
}
}
std::cout<<std::endl;
system("pause");
return 0;
}

复制代码

		自动登录	找回密码
密码			立即注册