ACO蚁群优化算法求解TSP旅行商问题C++（2020.10.13）

admin · 发表于 2024-7-16 23:18:17

const int CityCount = 29, AntCount = 29;//城市数量和蚂蚁数量
int besttour[CityCount];//最佳路线
const double α = 1, β = 5,ρ = 0.5, Q = 1;
Graph Map_City;//城市地图，存储城市信息、信息素等
Ant ant[AntCount]//蚁群
const int CityCount = 29, AntCount = 29;//城市数量和蚂蚁数量
int besttour[CityCount];//最佳路线
const double α = 1, β = 5,ρ = 0.5, Q = 1;
Graph Map_City;//城市地图，存储城市信息、信息素等
Ant ant[AntCount]//蚁群
void Ant::Next_City()
{
int currentcity = tour[tour_citycount - 1];//计算下一步先找到上一步所到的城市
double temp = 0, sum_probability = 0;
for (int i = 0; i < CityCount; i++)
{
if (can_visit[i] == true)
temp += pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β);
}
for (int i = 0; i < CityCount; i++)
{
if (can_visit[i] == false)
select_probability[i] = 0;//已经到过的城市选择概率为0
else
{
select_probability[i] = pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β) / temp;//对于未到过的城市，则计算选择概率
sum_probability += select_probability[i];
}
}
double r = random(0, sum_probability);//取概率区间的随机浮点数
double p = 0;
int nextcity = -1;
for (int j = 0; j < CityCount; j++)
{
if (can_visit[j] == true) p += select_probability[j];
if (p >= r)
{
nextcity = j; break;
}
}
/*if (nextcity == -1)
{
temp = -1;
for (int i = 0; i<CityCount; i++)
{
if (can_visit[i] == true)
if (temp<pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β))
{
temp = pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β);
nextcity = i;
}
}
}*/
Addcity(nextcity);
}
void UpdatePheromones(Graph Map_City,Ant ant[AntCount])//更新信息素的函数
{
for (int i = 0; i<AntCount; i++)
{
for (int j = 0; j<CityCount - 1; j++)
{
Map_City.Deltτ[ant[i].tour[j]][ant[i].tour[j + 1]] += Q / ant[i].tour_length;
Map_City.Deltτ[ant[i].tour[j + 1]][ant[i].tour[j]] += Q / ant[i].tour_length;
}
Map_City.Deltτ[ant[i].tour[CityCount - 1]][ant[i].tour[0]] += Q / ant[i].tour_length;
Map_City.Deltτ[ant[i].tour[0]][ant[i].tour[CityCount - 1]] += Q / ant[i].tour_length;
}
for (int i = 0; i<CityCount; i++)
{
for (int j = 0; j<CityCount; j++)
{
Map_City.τ[i][j] = (1 - ρ)*Map_City.τ[i][j] + Map_City.Deltτ[i][j];
Map_City.Deltτ[i][j] = 0;
}
}
}
// main.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <ctime>
using namespace std;
const int CityCount = 29, AntCount = 29;//城市数量和蚂蚁数量
int besttour[CityCount];//最佳路线
const double α = 1, β = 5,ρ = 0.5, Q = 1;
double random(int low, double uper)//生成某个区间内随机数的函数
{
return (rand() / (double)RAND_MAX)*(uper - low) + low;
};
int random(int uper)//返回一个从0到最大随机数的任意整数
{
return (rand() % uper);
};
class City
{
public:
string name;
double x, y;//城市的x、y坐标
void shuchu()
{
std::cout << name << " " << x << " " << y << endl;
}
};
class Graph//图信息
{
public:
City city[CityCount];
double Distance[CityCount][CityCount];//城市间的距离矩阵
double τ[CityCount][CityCount];//信息素矩阵
double Deltτ[CityCount][CityCount];//信息素变化量矩阵
void shuchu()
{
cout << "城市名称 " << "坐标x" << " " << "坐标y" << endl;
for (int i = 0; i < CityCount; i++)
city[i].shuchu();
cout << "距离矩阵： "<< endl;
for (int i = 0; i < CityCount; i++)
{
for (int j = 0; j < CityCount; j++)
{
if (j == CityCount - 1)
std::cout << Distance[i][j] << endl;
else
std::cout << Distance[i][j] << " ";
}
}
cout << "信息素矩阵： " << endl;
for (int i = 0; i < CityCount; i++)
{
for (int j = 0; j < CityCount; j++)
{
if (j == CityCount - 1)
std::cout << τ[i][j] << endl;
else
std::cout << τ[i][j] << " ";
}
}
cout << "信息素增量矩阵： " << endl;
for (int i = 0; i < CityCount; i++)
{
for (int j = 0; j < CityCount; j++)
{
if (j == CityCount - 1)
std::cout << Deltτ[i][j] << endl;
else
std::cout << Deltτ[i][j] << " ";
}
}
}
void Readcoordinatetxt(string txtfilename);//读取城市坐标文件的函数
};
Graph Map_City;//定义全局对象图
void Graph::Readcoordinatetxt(string txtfilename)
{
ifstream myfile(txtfilename, ios::in);
double x = 0, y = 0;
int z = 0;
if (!myfile.fail())
{
int i = 0;
while (!myfile.eof() && (myfile >> z >> x >> y))
{
city[i].name = to_string(long double(z));//城市名称转化为字符串
city[i].x = x; city[i].y = y;
i++;
}
}
else
cout << "文件不存在";
myfile.close();//计算城市距离矩阵
for (int i = 0; i < CityCount; i++)
for (int j = 0; j < CityCount; j++)
{
Distance[i][j] = sqrt(pow((city[i].x - city[j].x), 2) + pow((city[i].y - city[j].y), 2));//计算城市ij之间的距离
τ[i][j] = 1;
Deltτ[i][j] = 0;
}
}
class Ant
{
public:
int tour[CityCount + 1];//蚂蚁所构建路径的CityCount+1元数组
bool can_visit[CityCount];//蚂蚁是否能够访问城市的n元布尔数组
int tour_citycount;//蚂蚁当前走过城市的数量
double tour_length, tour_length_shortest;//蚂蚁所走的路径长度tour_length
double select_probability[CityCount];//蚂蚁对各城市的选择概率数组
Ant();//蚂蚁的初始化函数
void Build_Trip();//蚂蚁构造旅行路径的函数
void Next_City();//蚂蚁选择下一个城市的函数
void GetFirstCity();//蚂蚁随机到访第一个城市的函数
void Addcity(int city);//蚂蚁路径上添加城市的函数
void UpdateTourLength();//更新旅行路径长度的函数
void Clear();//清空函数
};
Ant ant[AntCount];//蚁群用m元数组ant来表示
Ant::Ant()//蚂蚁的构造函数
{
tour_length = tour_length_shortest = 0;
tour_citycount = 0;//起初所旅行过的城市数量为0
for (int i = 0; i<CityCount; i++)
{
can_visit[i] = true;//每个城市都可以访问
select_probability[i] = 0;//选择各个城市的概率为0
}
}
void Ant::Clear()
{
tour_length = 0;
for (int i = 0; i<CityCount; i++)
{
select_probability[i] = 0;
can_visit[i] = true;
}
tour_citycount = 0;
}
void Ant::Addcity(int city)
{
//add city to tabu;
tour[tour_citycount] = city;
tour_citycount++;
can_visit[city] = false;
}
void Ant::GetFirstCity()
{
srand((unsigned)time(NULL) + rand());
Addcity(random(CityCount));
}
void Ant::Next_City()
{
int currentcity = tour[tour_citycount - 1];//计算下一步先找到上一步所到的城市
double temp = 0, sum_probability = 0;
for (int i = 0; i < CityCount; i++)
{
if (can_visit[i] == true)
temp += pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β);
}
for (int i = 0; i < CityCount; i++)
{
if (can_visit[i] == false)
select_probability[i] = 0;//已经到过的城市选择概率为0
else
{
select_probability[i] = pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β) / temp;//对于未到过的城市，则计算选择概率
sum_probability += select_probability[i];
}
}
double r = random(0, sum_probability);//取概率区间的随机浮点数
double p = 0;
int nextcity = -1;
for (int j = 0; j < CityCount; j++)
{
if (can_visit[j] == true) p += select_probability[j];
if (p >= r)
{
nextcity = j; break;
}
}
/*if (nextcity == -1)
{
temp = -1;
for (int i = 0; i<CityCount; i++)
{
if (can_visit[i] == true)
if (temp<pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β))
{
temp = pow((Map_City.τ[currentcity][i]), α)*pow(1.0 / Map_City.Distance[currentcity][i], β);
nextcity = i;
}
}
}*/
Addcity(nextcity);
}
void Ant::Build_Trip()
{
for (int i = 0; i < CityCount; i++)
{
can_visit[i] = true;
}
GetFirstCity();
while (tour_citycount < CityCount)
{
if(tour_citycount <CityCount) Next_City();//轮盘赌法选择下一个城市
else if (tour_citycount == CityCount - 1)
{
for (int i = 0; i<CityCount; i++)
if (can_visit[i] == true)
{
Addcity(i);
break;
}//如果还剩下一个城市可以访问，那么这个城市就是最后一个城市，添加到蚂蚁旅行的城市上
}
}
tour[CityCount] = tour[0];//蚂蚁旅行的最后一个城市
}
void Ant::UpdateTourLength()//更新旅行路径长度的函数
{
for (int i = 0; i<CityCount - 1; i++)
tour_length += Map_City.Distance[tour[i]][tour[i + 1]];
tour_length += Map_City.Distance[tour[CityCount - 1]][tour[0]];
}
void UpdatePheromones(Graph Map_City,Ant ant[AntCount])//更新信息素的函数
{
for (int i = 0; i<AntCount; i++)
{
for (int j = 0; j<CityCount - 1; j++)
{
Map_City.Deltτ[ant[i].tour[j]][ant[i].tour[j + 1]] += Q / ant[i].tour_length;
Map_City.Deltτ[ant[i].tour[j + 1]][ant[i].tour[j]] += Q / ant[i].tour_length;
}
Map_City.Deltτ[ant[i].tour[CityCount - 1]][ant[i].tour[0]] += Q / ant[i].tour_length;
Map_City.Deltτ[ant[i].tour[0]][ant[i].tour[CityCount - 1]] += Q / ant[i].tour_length;
}
for (int i = 0; i<CityCount; i++)
{
for (int j = 0; j<CityCount; j++)
{
Map_City.τ[i][j] = (1 - ρ)*Map_City.τ[i][j] + Map_City.Deltτ[i][j];
Map_City.Deltτ[i][j] = 0;
}
}
}
int main()
{
int MAX_GEN = 1000;
double global_tourlength = 10e9,Ljia = DBL_MAX;
int Tjia[CityCount];//表示蚁群优化算法最终发现的最短路径
//首先对城市地图进行初始化
Map_City.Readcoordinatetxt("E:\\下学期课程\\Matlab智能计算\\ACO\\ACO\\bayg29.tsp");
Map_City.shuchu();
int temptour[CityCount];
for (int iteratorcishu = 0; iteratorcishu < MAX_GEN; iteratorcishu++)
{
for (int k = 0; k < AntCount; k++)
{
ant[k].Build_Trip();
ant[k].UpdateTourLength();//计算蚂蚁k所发现路径Tk的长度Lk
if (ant[k].tour_length < Ljia)
{
for (int h = 0; h < CityCount; h++)
Tjia[h] = ant[k].tour[h];
Ljia = ant[k].tour_length;
}
}
//找到最短的路径长度，放到temp里
double temp = ant[0].tour_length;
for (int i = 0; i<CityCount; i++) temptour[i] = ant[0].tour[i];
for (int i = 0; i<AntCount; i++)
{
if (temp>ant[i].tour_length)
{
temp = ant[i].tour_length;
for (int j = 0; j< CityCount; j++)
temptour[j] = ant[i].tour[j];
}
}
if (temp<global_tourlength)
{
global_tourlength = temp;
for (int j = 0; j< CityCount; j++)
besttour[j] = temptour[j];
}
std::cout << "第" << iteratorcishu << "次迭代的最短距离：" << global_tourlength << endl;
UpdatePheromones(Map_City,ant);
for (int i = 0; i < AntCount; i++) ant[i].Clear();
}
std::cout << "最短路径为：" << endl;
for (int i = 0; i < CityCount; i++)
{
if (i == CityCount - 1)std::cout << Map_City.city[besttour[i]].name << endl;
else std::cout << Map_City.city[besttour[i]].name << "->";
}
std::cout << "最短路径长度为：" << global_tourlength << endl;
system("Pause");
return 0;
}

复制代码

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