人工智能实验一：利用遗传算法求解 TSP（旅行商）问题 |
您所在的位置：网站首页 › tsp问题求解最小生成树 › 人工智能实验一：利用遗传算法求解 TSP（旅行商）问题 |
人工智能实验一：利用遗传算法求解 TSP（旅行商）问题
|
1.任务描述
本关任务：利用遗传算法求解 TSP 问题。 2.相关知识为了完成本关任务，你需要掌握：1. 遗传算法；2. TSP问题。 遗传算法一个后继状态由两个父状态决定，以k个随机产生的状态开始（population），一个状态表示成一个字符串。 定义一个健康度量函数用来评价状态的好坏程度，通过选择，交叉，突变的操作产生下一轮状态。
旅行商问题，即 TSP 问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。 假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。 3.编程要求在右侧编辑器中补充void select()和void cross()函数，解决 TSP 问题，求所有路径中的最小路径路程。 4.测试说明平台会对你编写的代码进行测试： 预期输出：18 5.实验过程下面是关于非补充部分的代码解释： 1.宏定义一些常量，用来简化代码，提高效率 #define cityNum 10 //城市数量 #define popSize 10 //种群大小 #define croRate 0.85 //交叉概率 #define mutRate 0.1 //变异概率 #define MAX 999 //最大距离2.定义“染色体”结构体，一个染色体用于标识一个个体 struct Chrom { int cityArr[cityNum]; //城市编号 char name; //染色体名称 float adapt; //个体适应度 int dis; //个体距离 };3.定义种群和新种群以及临时变量 struct Chrom genes[popSize]; //种群 struct Chrom genesNew[popSize]; //新种群 struct Chrom temp;4.定义十个城市名以及其之间的距离，用邻接矩阵表示 char names[cityNum] = { 'A','B','C','D','E','F','G','H','I','J' }; //城市名 int distance[cityNum][cityNum] = { { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, { 1, 0, 1, 2, 3, 4, 5, 6, 7, 8 }, { 2, 1, 0, 1, 2, 3, 4, 5, 6, 7 }, { 3, 2, 1, 0, 1, 2, 3, 4, 5, 6 }, { 4, 3, 2, 1, 0, 1, 2, 3, 4, 5 }, { 5, 4, 3, 2, 1, 0, 1, 2, 3, 4 }, { 6, 5, 4, 3, 2, 1, 0, 1, 2, 3 }, { 7, 6, 5, 4, 3, 2, 1, 0, 1, 2 }, { 8, 7, 6, 5, 4, 3, 2, 1, 0, 1 }, { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 } }; //距离邻接矩阵5.void initGroup()函数：用于初始化群体，生成一组随机的染色体 void initGroup() { int i, j, k; int t = 0; int flag = 0; srand(time(NULL)); //用于初始化随机数种子，time(NULL)返回当前系统时间 for (i = 0; i t = rand() % cityNum; //每次在城市列表中随机选取一个城市编号 flag = 1; for (k = 0; k flag = 0; break; } } if (flag) //选取的城市没有被选中 { temp.cityArr[j] = t; //存入数组中 genes[i] = temp; //生成一个完整的染色体 j++; //j自增1 } } } }6.void popFitness()函数：用于计算种群中每个个体的适应度值 void popFitness() //计算种群中每个个体的适应度值 { int i, n1, n2; for (i = 0; i n1 = genes[i].cityArr[j - 1]; //获取前一个城市的编号 n2 = genes[i].cityArr[j]; //获取当前城市的编号 genes[i].dis += distance[n1][n2]; //将前一个城市到当前城市的距离累加到路径长度中 } //将最后一个城市到第一个城市的距离加到路径长度中，得到该个体的总路径长度 genes[i].dis += distance[genes[i].cityArr[0]][genes[i].cityArr[cityNum - 1]]; //计算当前个体的适应度值，并保存到genes数组中 genes[i].adapt = (float)1 / genes[i].dis; } }7.int chooseBest()函数：从种群中选择适应度最高的个体 int chooseBest() { int choose = 0; //适应度最高的个体的索引 float best = 0.0f; //当前适应度最高的值 best = genes[0].adapt; //初始化当前适应度最高的值 for (int i = 0; i best = genes[i].adapt; //更新当前适应度最高的值 choose = i; //更新适应度最高的个体的索引 } } return choose; //返回适应度最高的个体的索引 }下面需要对代码进行补充 1.补充select()函数选择操作是遗传算法中的一个重要步骤，它的作用是从当前种群中选出一些适应度较高的个体，作为下一代个体的双亲，从而保留优良的基因 常用的实现方法有: 适应度比例法，随机遍历抽样法，局部选择法，锦标赛选择法和 序选择法（轮盘赌方法） 这里我们使用轮盘赌方法： 计算每个个体的适应度值和总适应度值计算每个个体被选中的概率生成一个0到1之间的随机数从第一个个体开始累加选择概率，直到大于或等于随机数为止返回当前累加到的个体作为选中结果下面是具体代码实现： void select() { float biggestSum = 0.0f; //定义适应度总和 float adapt_pro[popSize]; float pick = 0.0f; int i; for (i = 0; i adapt_pro[i] = genes[i].adapt / biggestSum; } for (i = 0; i sum += adapt_pro[j]; //累加适应度比例 if (sum > pick) //当累加值超过pick时，选择对应的个体 { genesNew[i] = genes[j]; break; } } /********** End **********/ } for (i = 0; i float pick; int choice1, choice2; //交叉的两个父代 int pos1, pos2; //记录交叉点位置 int temp; int conflict1[popSize]; //记录父代1的冲突基因位置 int conflict2[popSize]; //记录父代2的冲突基因位置 int num1; //num用来记录冲突基因个数，且两个父代冲突基因数相同 int num2; int index1, index2; //交换基因时使用 int move = 0; //控制交叉操作的次数和对象 while (move move += 2; continue; } choice1 = move; choice2 = move + 1; // 随机选择两个交叉点 pos1 = rand() % popSize; pos2 = rand() % popSize; while (pos1 > popSize - 2 || pos1 pos2 = rand() % popSize; } //保证pos1比pos2小 if (pos1 > pos2) { temp = pos1; pos1 = pos2; pos2 = temp; } //交换pos1到pos2之间的基因片段 for (int j = pos1; j /********** Begin **********/ for (int j = 0; j if (genes[choice1].cityArr[j] == genes[choice1].cityArr[k]) { conflict1[num1++] = j; } if (genes[choice2].cityArr[j] == genes[choice2].cityArr[k]) { conflict2[num2++] = j; } } } /********** End **********/ for (int j = pos2 + 1; j /********** Begin **********/ if (genes[choice1].cityArr[j] == genes[choice1].cityArr[k]) { conflict1[num1++] = j; } if (genes[choice2].cityArr[j] == genes[choice2].cityArr[k]) { conflict2[num2++] = j; } /********** End **********/ } } } if ((num1 == num2) && num1 > 0)//将两个冲突子代的冲突基因进行交换 { for (int j = 0; j double pick; //随机数 int pos1, pos2, temp; //交换位置和临时变量 for (int i = 0; i continue; } pos1 = rand() % popSize; // 随机生成第一个交换位置 pos2 = rand() % popSize; // 随机生成第二个交换位置 while (pos1 > popSize - 1) // 如果第一个位置超出范围，则重新生成 { pos1 = rand() % popSize; } while (pos2 > popSize - 1) // 如果第二个位置超出范围，则重新生成 { pos2 = rand() % popSize; } int a = genes[i].dis; // 记录原来的总距离 temp = genes[i].cityArr[pos1]; // 交换两个城市的顺序 genes[i].cityArr[pos1] = genes[i].cityArr[pos2]; genes[i].cityArr[pos2] = temp; popFitness(); // 计算新的适应度函数值 if (genes[i].dis > a) // 如果新的总距离大于原来的，则恢复原来的顺序（贪心策略） { temp = genes[i].cityArr[pos1]; genes[i].cityArr[pos1] = genes[i].cityArr[pos2]; genes[i].cityArr[pos2] = temp; } } } 6.完整代码 #include "stdio.h" #include "stdlib.h" #include "time.h" #define cityNum 10 //城市数量 #define popSize 10 //种群大小 #define croRate 0.85 //交叉概率 #define mutRate 0.1 //变异概率 #define MAX 999 //最大距离 //定义染色体的结构 struct Chrom { int cityArr[cityNum]; //城市编号 char name; //染色体名称 float adapt; //个体适应度 int dis; //个体距离 }; struct Chrom genes[popSize]; //种群 struct Chrom genesNew[popSize]; //新种群 struct Chrom temp; char names[cityNum] = { 'A','B','C','D','E','F','G','H','I','J' }; //城市名 int distance[cityNum][cityNum] = { { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, { 1, 0, 1, 2, 3, 4, 5, 6, 7, 8 }, { 2, 1, 0, 1, 2, 3, 4, 5, 6, 7 }, { 3, 2, 1, 0, 1, 2, 3, 4, 5, 6 }, { 4, 3, 2, 1, 0, 1, 2, 3, 4, 5 }, { 5, 4, 3, 2, 1, 0, 1, 2, 3, 4 }, { 6, 5, 4, 3, 2, 1, 0, 1, 2, 3 }, { 7, 6, 5, 4, 3, 2, 1, 0, 1, 2 }, { 8, 7, 6, 5, 4, 3, 2, 1, 0, 1 }, { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 } }; //距离邻接矩阵 //初始化群体，生成一组随机的染色体 void initGroup() { int i, j, k; int t = 0; int flag = 0; srand(time(NULL)); //用于初始化随机数种子，time(NULL)返回当前系统时间 for (i = 0; i t = rand() % cityNum; //每次在城市列表中随机选取一个城市编号 flag = 1; for (k = 0; k flag = 0; break; } } if (flag) //选取的城市没有被选中 { temp.cityArr[j] = t; //存入数组中 genes[i] = temp; //生成一个完整的染色体 j++; //j自增1 } } } } void popFitness() //计算种群中每个个体的适应度值 { int i, n1, n2; for (i = 0; i n1 = genes[i].cityArr[j - 1]; //获取前一个城市的编号 n2 = genes[i].cityArr[j]; //获取当前城市的编号 genes[i].dis += distance[n1][n2]; //将前一个城市到当前城市的距离累加到路径长度中 } //将最后一个城市到第一个城市的距离加到路径长度中，得到该个体的总路径长度 genes[i].dis += distance[genes[i].cityArr[0]][genes[i].cityArr[cityNum - 1]]; //计算当前个体的适应度值，并保存到genes数组中 genes[i].adapt = (float)1 / genes[i].dis; } } //从种群中选择适应度最高的个体 int chooseBest() { int choose = 0; //适应度最高的个体的索引 float best = 0.0f; //当前适应度最高的值 best = genes[0].adapt; //初始化当前适应度最高的值 for (int i = 0; i best = genes[i].adapt; //更新当前适应度最高的值 choose = i; //更新适应度最高的个体的索引 } } return choose; //返回适应度最高的个体的索引 } void select() { float biggestSum = 0.0f; //定义适应度总和 float adapt_pro[popSize]; float pick = 0.0f; int i; for (i = 0; i adapt_pro[i] = genes[i].adapt / biggestSum; } for (i = 0; i sum += adapt_pro[j]; //累加适应度比例 if (sum > pick) //当累加值超过pick时，选择对应的个体 { genesNew[i] = genes[j]; break; } } /********** End **********/ } for (i = 0; i float pick; int choice1, choice2; //交叉的两个父代 int pos1, pos2; //记录交叉点位置 int temp; int conflict1[popSize]; //记录父代1的冲突基因位置 int conflict2[popSize]; //记录父代2的冲突基因位置 int num1; //num用来记录冲突基因个数，且两个父代冲突基因数相同 int num2; int index1, index2; //交换基因时使用 int move = 0; //控制交叉操作的次数和对象 while (move move += 2; continue; } choice1 = move; choice2 = move + 1; // 随机选择两个交叉点 pos1 = rand() % popSize; pos2 = rand() % popSize; while (pos1 > popSize - 2 || pos1 pos2 = rand() % popSize; } //保证pos1比pos2小 if (pos1 > pos2) { temp = pos1; pos1 = pos2; pos2 = temp; } //交换pos1到pos2之间的基因片段 for (int j = pos1; j /********** Begin **********/ for (int j = 0; j if (genes[choice1].cityArr[j] == genes[choice1].cityArr[k]) { conflict1[num1++] = j; } if (genes[choice2].cityArr[j] == genes[choice2].cityArr[k]) { conflict2[num2++] = j; } } } /********** End **********/ for (int j = pos2 + 1; j /********** Begin **********/ if (genes[choice1].cityArr[j] == genes[choice1].cityArr[k]) { conflict1[num1++] = j; } if (genes[choice2].cityArr[j] == genes[choice2].cityArr[k]) { conflict2[num2++] = j; } /********** End **********/ } } } if ((num1 == num2) && num1 > 0)//将两个冲突子代的冲突基因进行交换 { for (int j = 0; j double pick; //随机数 int pos1, pos2, temp; //交换位置和临时变量 for (int i = 0; i continue; } pos1 = rand() % popSize; // 随机生成第一个交换位置 pos2 = rand() % popSize; // 随机生成第二个交换位置 while (pos1 > popSize - 1) // 如果第一个位置超出范围，则重新生成 { pos1 = rand() % popSize; } while (pos2 > popSize - 1) // 如果第二个位置超出范围，则重新生成 { pos2 = rand() % popSize; } int a = genes[i].dis; // 记录原来的总距离 temp = genes[i].cityArr[pos1]; // 交换两个城市的顺序 genes[i].cityArr[pos1] = genes[i].cityArr[pos2]; genes[i].cityArr[pos2] = temp; popFitness(); // 计算新的适应度函数值 if (genes[i].dis > a) // 如果新的总距离大于原来的，则恢复原来的顺序（贪心策略） { temp = genes[i].cityArr[pos1]; genes[i].cityArr[pos1] = genes[i].cityArr[pos2]; genes[i].cityArr[pos2] = temp; } } } int main() { char c = 0; //printf("\n\t\t******************************** ÒÅ´«Ëã·¨Çó½âTSP(ÂÃÐÐÉÌ)ÎÊÌâ *********************************\n"); initGroup(); //³õʼ»¯ popFitness(); //¸üÐÂÊý¾Ý //Êä³öÅäÖÃÐÅÏ¢ /*printf("\n\t\t»ùÒò³¤¶È:%d",cityNum); printf("\tÖÖȺ´óС:%d",popSize); printf("\t½»²æ¸ÅÂÊ:%.2f",croRate); printf("\t±äÒì¸ÅÂÊ:%.2f",mutRate); printf("\t½ø»¯´úÊý:%d",MAX); printf("\tÔ¤Éè×îÓŽ⣺18"); printf("\n\n\t\t**********************************************************************************************\n");*/ int i, j; //Êä³ö¾àÀë¾ØÕó /*printf("\n\t\t--------- ³ÇÊоàÀë¾ØÕó ---------\n"); printf("\t\t"); int i,j; for(i = 0; i < cityNum; i ++) { for(j = 0;j < cityNum; j ++) { printf(" %d",distance[i][j]); } printf("\n\t\t"); } printf("--------------------------------");*/ //Êä³ö·¾¶ÐÅÏ¢ /*printf("\n\t\t-------- ³õʼÖÖȺ»ùÒò¿â --------\n"); printf("\t\t "); for(i = 0; i < cityNum; i ++) { printf(" %c",genes[i].name); } printf("\n\t\t"); for(i = 0;i < cityNum; i ++) { printf("%c",genes[i].name); for(j = 0; j < cityNum; j ++) { printf(" %d",genes[i].cityArr[j]); } printf("\n\t\t"); } printf("--------------------------------\n");*/ //printf("\n\t\tÑ°Çó×îÓŽâÖУº"); //ͨ¹ý²»¶Ï½ø»¯£¬Ö±µ½´ïµ½¶¨ÒåµÄ½ø»¯´úÊý for (i = 0; i ",genes[chooseBest()].cityArr[i]); } printf("%d",genes[chooseBest()].cityArr[0]);*/ printf("%d", genes[chooseBest()].dis); //printf("\n\n\t\tÊÇ·ñÔÙÊÔÒ»´Î?(Y/y) ÊÇ/(N/n) ·ñ£º"); fflush(stdin); /* c = getchar(); fflush(stdin); if(c=='N'||c=='n') { break; }*/ //printf("\n\t\t"); return 0; }运行结果：
|
【本文地址】