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