C++下基于蚁群算法解决TSP问题
#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 = //各个城市的坐标数据
{ { 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; //表示完全图的邻接矩阵
double Eta; //表示启发式因子，为D中距离的倒数
double DeltaTau; //表示启发式因子的变化量
double Tau; //路径上面信息素的浓度
int Tabu; //禁忌表，存储走过的路径
double L_best; //存储每次迭代的路径的最短长度
double L_ave; //存储每次迭代的路径的平均长度
int R_best; //存储每次迭代的最佳路线
void ValueInit(void) //变量初始化函数
{
for (int i = 0; i < n; i++) //初始化 D31
{
for (int j = 0; j < n; j++)//31
{
if (i != j)
D = pow(pow((C - C), 2) + pow((C - C), 2), 0.5);
else
D = DBL_EPSILON;//极小数，对角线上的数0
}
}
for (int i = 0; i < n; i++) //初始化 Eta启发式因子，距离矩阵倒数
for (int j = 0; j < n; j++)
Eta = 1.0 / D;
for (int i = 0; i < n; i++) //初始化 DeltaEta启发式因子变化量
for (int j = 0; j < n; j++)
DeltaTau = 0;
for (int i = 0; i < n; i++) //初始化 Tau信息素浓度
for (int j = 0; j < n; j++)
Tau = 1.0;
for (int i = 0; i < m; i++) //初始化 Tabu存储走过的路径
for (int j = 0; j < n; j++)
Tabu = 0;
}
void ValueDisplayTabu(int(*p)) //禁忌表，存储走过的路径, 显示函数
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << *(*(p + i) + j) << ' ';
}
cout << endl;
}
}
void ValueDisplayTau(double(*p)) //信息素的浓度,显示函数
{
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 = temp;//走过的路径，一共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); //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];//Tau=1Alpha=1 Beta=5Eta=1/Distance(距离越小，这个值越大)
P = pow(Tau], Alpha) * pow(Eta], Beta);//5
Psum += P;
}
//随机生成0~Psum之间的一个数
rate = rnd(0.0, Psum); //使用轮盘赌算法，挑选下一座要去的城市
for (int k = 0; k < P.size(); k++)
{
choose += P;
if (rate < choose)
{
to_visit = J;//待访问城市
break;
}
}
//访问的路径
Tabu = to_visit; //更新禁忌表 100条访问城市的路径每个城市初始信息素
}
}
//第四步：记录本次迭代蚂蚁行走的路线数据
double L; //记录本代每只蚂蚁走的路程，并初始化 100个路径
for (int i = 0; i < m; i++)
{
L = 0.0;
}
for (int i = 0; i < m; i++)//100
{
for (int j = 0; j < n - 1; j++)//31
{
L += D]];//L代表第i个路径的代价
}
L += D]]; //终点和起点的距离
}
double min_value = L; //声明求本代所有蚂蚁行走距离最小值的临时变量
double sum_value = L; //声明求本代所有蚂蚁行走距离总值的临时变量
int min_index = 0; //记录本代所有蚂蚁行走距离最小值的下标
for (int i = 1; i < m; i++)
{
sum_value += L;
if (L < min_value)
{
min_value = L;
min_index = i;
}
}
L_best = min_value; //每代中路径的最短长度
L_ave = sum_value / m; //每代中路径的平均长度
for (int i = 0; i < n; i++)
{
R_best = Tabu; //记录每代最短的路径数据
}
cout << NC << ": best cost is: " << L_best << ' ' << "the avg of ever iter is: " << L_ave << endl; //打印各代距离信息
NC++; //迭代继续
//第五步：更新信息素
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n - 1; j++)
{
//DeltaTau信息素增量,表示蚂蚁在i到j路径上留下的信息素，L表示蚂蚁已经走过路径的总长度
//所以总长度越小，信息素越多
DeltaTau]] += Q / L; //此次循环在整个路径上的信息素增量 Q=100
}
DeltaTau]] += Q / L;
}
for (int i = 0; i < n; i++)//100
{
for (int j = 0; j < n; j++)
{
//Tau 路径i到j上的信息素残余量
Tau = (1 - Rho) * Tau + DeltaTau; //考虑信息素挥发，更新后的信息素 T = p * T + deltaQho=0.1，信息素挥发速度
}
}
for (int i = 0; i < m; i++) //信息素清零
for (int j = 0; j < n; j++)
Tabu = 0;
}
//第六步：取出最优结果
double min_L = L_best; //所有迭代中最短距离
int min_L_index = 0; //所有迭代中最优路径的下标
int Shortest_Route; //所有迭代中的最优路径
for (int i = 0; i < NC; i++)
{
if (L_best < min_L)
{
min_L = L_best;
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 = R_best;
if (i == n - 1) {
cout << Shortest_Route;
}
else {
cout << Shortest_Route << " -> ";
}
}
std::cout<<std::endl;
system("pause");
return 0;
}
页:
[1]