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)
|
- #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;
- }
复制代码 |
|