人工智能TSP旅行商问题实验报告.doc

人工智能实验三实验报告班级：姓名：学号：一实验题目TSP问题的遗传算法实现旅行商问题（TravelingSalesmanProblem,TSP），又译为旅行推销员问题、货担郎问题，简称为TSP问题，是最基本的路线问题。假设有n个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。应用遗传算法求解30/10个节点的TSP（旅行商问题）问题，求问题的最优解。二实验目的1熟悉和掌握遗传算法的基本概念和基本思想；2理解和掌握遗传算法的各个操作算子，能够用选定的编程语言设计简单的遗传优化系统；3通过实验培养学生利用遗传算法进行问题求解的基本技能。三实验要求1掌握遗传算法的基本原理、各个遗传操作和算法步骤；2要求求出问题最优解，若得不出最优解，请分析原因；3对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值；4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。四数据结构请说明染色体个体和群体的定义方法。structRanSeTi//染色体的个体的定义方法{intcity[cities];//基因的排列（即城市的顺序，路径的组织）intadapt;//记录适应度doublep;//记录其在种群中的幸存概率}RanSeTi[num],RanSeTitemp[num];//用数组来存储染色体群体方法五实验算法1说明算法中对染色体的编码方法，适应度函数定义方法1)染色体的编码方法:即为染色体个体定义过程中生成的基因排列（路径中城市的顺序）structRanSeTi//染色体的个体的定义方法{intcity[cities];//基因的排列（即城市的顺序，路径的组织）intadapt;//记录适应度doublep;//记录其在种群中的幸存概率}RanSeTi[num],RanSeTitemp[num];//用数组来存储染色体群体方法2)适应度函数定义方法：评价函数即适应度函数，在遗传算法中用来计算一个染色体优劣的函数。在进行遗传操作和种群进化的时候，每个染色体的适应值是决定它是否进入下一轮种群进化的关键因素。适应值高的函数被选作新一代个体的可能性就会大。TSP问题中适应度函数常取路径长度的倒数（或倒数的相关函数），如：其中，N是个调节参数，根据实验情况进行确定。for(i=0;i<num;i++){sumdistance=0;for(j=1;j<cities;j++){n1=RanSeTi[i].city[j-1];n2=RanSeTi[i].city[j];sumdistance+=distance[n1][n2];}RanSeTi[i].adapt=sumdistance;//每条染色体的路径总和biggestsum+=sumdistance;//种群的总路径}2采用的选择、交叉、变异操作算子的具体操作1）选择操作我们定义f(xi)为第i（i=1,2,3.....popsize）个染色体的适应度，则每个个体被选中的概率是：本题中具体使用的是期望值方法//初始化梯度概率for(i=0;i<num;i++){gradient[i]=0.0;xuanze[i]=0.0;}gradient[0]=group[0].p;for(i=1;i<num;i++)gradient[i]=gradient[i-1]+group[i].p;srand((unsigned)time(NULL));//随机产生染色体的存活概率for(i=0;i<num;i++){xuanze[i]=(rand()%100);xuanze[i]/=100;}//选择能生存的染色体for(i=0;i<num;i++){for(j=0;j<num;j++){if(xuanze[i]<gradient[j]){xuan[i]=j;//第i个位置存放第j个染色体break;}}}//拷贝种群for(i=0;i<num;i++){grouptemp[i].adapt