本文共 8885 字，大约阅读时间需要 29 分钟。
#include #include #include #include #include #include #include #include #include #include using namespace std;class GA{private: struct City{ //城市（名、坐标）结构 string name; //名称(编号） int x, y; //二维坐标 City(){} }; struct Edge{ //城市间距离 int pos; //下标 int length; //距离大小，表示第pos个城市和第pos+1个城市间的距离 }; string datafile; //测试数据文件名 string resultfile; //测试结果文件名 int cityn; //城市数目 int popsize; //种群规模 double pc; //交叉概率 double pm; //变异概率 int maxgen; //最大进化代数 int bestgen; //最忧解最早出现代数 int bestlength; //最短路径长度(最优解) int *bestpath; //最优路径 City *city; //记录城市信息的数组 int **distance; //cityn X cityn 距离矩阵，记录城市之间距离 double *fitness; //种群适应度，记录种群中各个体的适应度 double *p; //种群总个个体适应度累积概率 int **father; //父代 int **child; //子代 int gen; //当前代数 clock_t start, end; //用于计算程序运行时间的参数public: GA(string df, int n, int p, double p1, double p2, int g,string rf){ /* *df ---- 测试数据文件 *n ---- 城市数目 *p ---- 种群规模 *p1 ---- 交叉概率 *p2 ---- 变异概率 *g ---- 进化代数 *rf ---- 测试结果文件 */ datafile = df; cityn = n; popsize = p; pc = p1; pm = p2; maxgen = g; resultfile = rf; } ~GA(){ //析构函数，释放数组空间 delete[]bestpath; delete[]city; for (int i = 0; i < cityn; ++i){ delete[]distance; } delete[]distance; for (int i = 0; i < popsize; ++i){ delete[]father; delete[]child; } delete[]father; delete[]child; } void initdata(){ //初始化数据 //读取测试数据 fstream file(datafile, ios::in); if (file.bad()){ cout << "Fail to open the txt file !\n"; exit(-1); } city = new City[cityn]; for (int i = 0; i < cityn; ++i){ file >> city[i].name >> city[i].x >> city[i].y; } file.close(); //初始化距离矩阵 distance = new int*[cityn]; for (int i = 0; i < cityn; ++i){ distance[i] = new int[cityn]; } for (int i = 0; i < cityn; i++){ distance[i][i] = 0; for (int j = i + 1; j < cityn; ++j){ int xd = city[i].x - city[j].x; int yd = city[i].y - city[j].y; double rij = sqrt((xd*xd + yd*yd) / 10.0); int tij = (int)round(rij + 0.5); if (tij < rij){ distance[i][j] = distance[j][i] = tij + 1; } else{ distance[i][j] = distance[j][i] = tij; } } } } void initpop(){ //初始化种群 father = new int*[popsize]; child = new int*[popsize]; for (int i = 0; i < popsize; ++i){ father[i] = new int[cityn]; child[i] = new int[cityn]; } /* *贪心算法思想优化初始种群 *for(a==0...size-1){ * 以城市a为起点 * 在剩下的cityn-1个城市中找出距离a最近的城市b * 在剩下的cityn-2个城市中找出距离b最近的城市c * ... * 以此类推直到所有城市都遍历完 * } *其中0<=a = cityn); //算法默认要求种群的规模大于城市数目 int size = popsize*0.2; int best, minlength; int *vis = new int[cityn]; //辅助数组，0表示该城市未访问，1表示已访问 for (int i = 0; i < size; ++i){ //初始化cityn个具有贪婪性质的初始染色体 memset(vis, 0, cityn*sizeof(vis)); vis[i] = 1; father[i][0] = i; for (int j = 1; j < cityn; ++j){ //贪心算法找出余下cityn-1个城市的序列 minlength = numeric_limits ::max(); for (int k = 0; k < cityn; ++k){ if (vis[k] == 0 && minlength > distance[i][k]){ //father[i][j-1] minlength = distance[i][k]; best = k; } } father[i][j] = best; vis[best] = 1; } } delete[]vis; /*for (int i = 0; i < cityn; ++i){ cout << countlength(father[i]) << endl; }*/ vector randomseq; //利用vector里的random_shuffle()函数随机生成剩余popsize for (int i = 0; i < cityn; ++i){ randomseq.push_back(i); } for (int i = size; i < popsize; ++i){ random_shuffle(randomseq.begin(), randomseq.end()); for (int j = 0; j < cityn; ++j){ father[i][j] = randomseq[j]; } } //初始化最佳长度、最优解出现代数、当前代数 bestlength = numeric_limits ::max(); bestgen = gen = 0; bestpath = new int[cityn]; //计算初始种群的最短路径 int length; for (int i = 0; i < popsize; ++i){ length = countlength(father[i]); if (bestlength > length){ bestlength = length; for (int j = 0; j < cityn; ++j){ bestpath[j] = father[i][j]; } } } } void evolution(){ srand(unsigned(time(NULL))); start = clock(); //算法开始 initdata(); initpop(); while (gen++ < maxgen){ //算法实现的主体部分（以进化代数为算法结束判断条件） countfitness(); //计算适应度 select(); //选择 crossover(); //交叉 mutation(); //变异 copy(); //子代替代父代成为新的父代并继续繁衍下去 } end = clock(); //算法结束 showresult(); } void countfitness(){ //计算适应度和适应度累积概率（轮盘赌算法需要） int sum = 0; int *d = new int[popsize]; for (int i = 0; i < popsize; ++i){ d[i] = countlength(father[i]); sum += d[i]; } fitness = new double[popsize]; p = new double[popsize]; fitness[0] = 1.0*d[0] / sum; p[0] = (1 - fitness[0]) / (cityn - 1); for (int i = 1; i < popsize; ++i){ fitness[i] = 1.0*d[i] / sum; p[i] = p[i - 1] + (1 - fitness[i]) / (cityn - 1); } } void select(){ //轮盘赌选择算法剩下popsize-1个染色体 int k; for (int i = 0; i < popsize; ++i){ k = 0; double r = static_cast (rand()) / RAND_MAX; while (r > p[k]){ k++; } for (int j = 0; j < cityn; ++j){ //把父代第k个个体复制到子代 child[i][j] = father[k][j]; } } //最优保存策略，用父代中的最优个体代替子代中的最劣个体 int best = 0; int minlength = countlength(father[0]); for (int i = 1; i < popsize; ++i){ int length = countlength(father[i]); if (minlength < length){ minlength = length; best = i; } } int worst = 0; int maxlength = countlength(child[0]); for (int i = 1; i < popsize; ++i){ int length = countlength(child[i]); if (maxlength > length){ maxlength = length; worst = i; } } for (int i = 0; i < cityn; ++i){ child[worst][i] = father[best][i]; } delete[]fitness; delete[]p; } void crossover(){ //交叉 double r; //随机数 int n = 0; int *flag = new int[popsize]; //是否已进行过交叉的标记 memset(flag, 0, sizeof(flag)); while (n < popsize){ r = static_cast (rand()) / RAND_MAX; if (r < pm){ /* *交叉操作 *(1)随机选取两个染色体n1和n2，同时随机产生两个交叉点left和right（left right){ //使得left length){ bestlength = length; bestgen = gen; for (int i = 0; i < cityn; ++i){ bestpath[i] = child[n1][i]; } } length = countlength(child[n2]); if (bestlength > length){ bestlength = length; bestgen = gen; for (int i = 0; i < cityn; ++i){ bestpath[i] = child[n2][i]; } } } n += 2; } delete[]flag; } void mutation(){ //变异 double r; //随机数 int n = 0; int mut; //变异方式 while (n < popsize){ r = static_cast (rand()) / RAND_MAX; if (r < pm){ /* *变异操作（共有两种变异方式） *（一） *（1）将城市序列转换成城市间距离的数组并按照距离从大到小进行排序 *（2）选择最长距离和次长的两段城市间距离 *（3）根据两段城市间距离在染色体中的相对位置进行消除 *（二） *（1）随机选取染色体上的两个城市left和right *（2）以left为起点，将left与right之间的城市重新排列，排列方式如下： * 【i】假设left位置上为城市a,在余下的right-left-1个城市中找出距离a最近的城市,设为b * 【ii】接着在剩下的right-left-2个城市中找出距离b最近的城市，设为c * 【iii】以此类推，直到所有城市都已重排列 */ mut = rand() % 2; //0为第一种变异方式，1为第二种变异方式 int left, right; if (mut == 0){ Edge *edge = new Edge[cityn]; for (int i = 0; i < cityn - 1; ++i){ edge[i].pos = i; edge[i].length = distance[child[n][i]][child[n][i + 1]]; } edge[cityn - 1].pos = cityn - 1; edge[cityn - 1].length = distance[child[n][0]][child[n][cityn - 1]]; qsort(edge, cityn, sizeof(edge[0]), cmp); //按距离从大到小排序 left = edge[0].pos; //最长距离 right = edge[1].pos; //次长距离 if (left > right){ int temp = left; left = right; right = temp; } if (left == right - 1 || left == right - cityn + 1){ //最长的两个距离相邻 int r, temp; r = rand() % cityn; temp = child[n][right]; child[n][right] = child[n][r]; child[n][r] = temp; } else{ for (int i = left + 1; i <= (right + left) / 2; ++i){ int temp = child[n][i]; child[n][i] = child[n][right + left + 1 - i]; child[n][right + left + 1 - i] = temp; } } } else{ int m = (cityn / 4 - 2) * (gen / (maxgen / 4)); left = rand() % (cityn - m); right = left + m; int best, minlength; int *vis = new int[cityn]; //辅助数组，0表示该城市未访问，1表示已访问 memset(vis, 0, cityn*sizeof(vis)); //vis[father[n1][left]] = 1; for (int i = left + 1; i <= right; ++i){ //找出余下城市的序列 minlength = numeric_limits ::max(); for (int j = left + 1; j <= right; ++j){ if (vis[child[n][j]] == 0 && minlength > distance[child[n][i - 1]][child[n][j]]){ minlength = distance[child[n][i - 1]][child[n][j]]; best = j; } } vis[child[n][best]] = 1; int temp = child[n][i]; child[n][i] = child[n][best]; child[n][best] = temp; } delete[]vis; } //计算变异操作是否获得比当前最优解更好的解 int length = countlength(child[n]); if (bestlength > length){ bestlength = length; bestgen = gen; for (int i = 0; i < cityn; ++i){ bestpath[i] = child[n][i]; } } } ++n; } } void copy(){ //子代复制为父代，继续繁衍 double sum = 0; for (int i = 0; i < popsize; ++i){ sum += countlength(child[i]); for (int j = 0; j < cityn; ++j){ father[i][j] = child[i][j]; } } //cout << sum/cityn <<" "< <<" "< << endl; //system("pause"); } void showresult(){ //输出结果 fstream result(resultfile, ios::out); if (result.bad()){ cout << "Fail to open the txt file !\n"; exit(-1); } result << "最短路径长度:" << bestlength << '\n'; result << "最短路径出现代数:" << bestgen << '\n'; result << "算法运行时间(ms):" << (end - start) << "\n"; result << "最优路径:" << endl; for (int i = 0; i < cityn; ++i){ result << " "; result << bestpath[i] << '\t'; if ((i + 1) % 12 == 0){ result << '\n'; } } result.close(); cout << "最优解为:" << bestlength << ",已生成" << resultfile << "记录实验结果。\n"; } int countlength(int *seq){ //计算城市序列seq的路径长度 int length = 0; for (int i = 0; i < cityn - 1; ++i){ length += distance[seq[i]][seq[i + 1]]; } length += distance[seq[0]][seq[cityn - 1]]; return length; } static int cmp(const void *a,const void *b){ return ((Edge*)b)->length < ((Edge*)a)->length; }};int main(){ /* *实验测试样例 *测试数据:att48.txt，其实际最优解为10628 *城市数目：48 *种群规模：100 *交叉概率：0.5 *变异概率：0.1 *进化代数：1000 */ (new GA("att48.txt", 48, 100, 0.5, 0.1, 1000,"result.txt"))->evolution();}
附件：
转载地址：http://krebi.baihongyu.com/