TA的每日心情![](source/plugin/dsu_paulsign/img/emot/kx.gif) | 开心 昨天 15:13 |
---|
签到天数: 153 天 [LV.7]常住居民III
管理员
中国膜结构网www.mjgou.com
- 积分
- 2147483647
![QQ](static/image/common/qq_big.gif)
|
- 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;
- }
复制代码 |
|