- 1、本文档共8页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
人工智能TSP旅行商问题实验报告剖析
人工智能实验三实验报告
班级: 姓名: 学号:
一 实验题目
TSP问题的遗传算法实现
旅行商问题(Traveling Salesman Problem, TSP),又译为旅行推销员问题、货担郎问题,简称为TSP问题,是最基本的路线问题。假设有n个可直达的城市,一销售商从其中的某一城市出发,不重复地走完其余n-1个城市并回到原出发点,在所有可能的路径中求出路径长度最短的一条。
应用遗传算法求解30/10个节点的TSP(旅行商问题)问题,求问题的最优解。
二 实验目的
1 熟悉和掌握遗传算法的基本概念和基本思想;
2 理解和掌握遗传算法的各个操作算子,能够用选定的编程语言设计简单的遗传优化系统;
3 通过实验培养学生利用遗传算法进行问题求解的基本技能。
三 实验要求
1 掌握遗传算法的基本原理、各个遗传操作和算法步骤;
2 要求求出问题最优解,若得不出最优解,请分析原因;
3 对实验中的几个算法控制参数进行仔细定义,并能通过实验选择参数的最佳值;
4 要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。
四 数据结构
请说明染色体个体和群体的定义方法。
struct RanSeTi //染色体的个体的定义方法
{
int city[cities]; //基因的排列(即城市的顺序,路径的组织)
int adapt; //记录适应度
double p; //记录其在种群中的幸存概率
} RanSeTi [num], RanSeTi temp[num]; //用数组来存储染色体群体方法
五 实验算法
1 说明算法中对染色体的编码方法,适应度函数定义方法
1) 染色体的编码方法:
即为染色体个体定义过程中生成的基因排列(路径中城市的顺序)
struct RanSeTi //染色体的个体的定义方法
{
int city[cities]; //基因的排列(即城市的顺序,路径的组织)
int adapt; //记录适应度
double p; //记录其在种群中的幸存概率
} RanSeTi [num], RanSeTi temp[num]; //用数组来存储染色体群体方法
2) 适应度函数定义方法:
评价函数即适应度函数,在遗传算法中用来计算一个染色体优劣的函数。在进行遗传操作和种群进化的时候,每个染色体的适应值是决定它是否进入下一轮种群进化的关键因素。适应值高的函数被选作新一代个体的可能性就会大。
TSP问题中适应度函数常取路径长度的倒数(或倒数的相关函数),如:
其中,N是个调节参数,根据实验情况进行确定。
for(i=0;inum;i++)
{
sumdistance=0;
for(j=1;jcities;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;inum;i++)
{
gradient[i]=0.0;
xuanze[i]=0.0;
}
gradient[0]=group[0].p;
for(i=1;inum;i++)
gradient[i]=gradient[i-1]+group[i].p;
srand((unsigned)time(NULL));
//随机产生染色体的存活概率
for(i=0;inum;i++)
{
xuanze[i]=(rand()%100);
xuanze[i]/=100;
}
//选择能生存的染色体
for(i=0;inum;i++)
{
for(j=0;jnum;j++)
{
if(xuanze[i]gradient[j])
{
xuan[i]=j; //第i个位置存放第j个染色体
break;
}
}
}
//拷贝种群
for(i=0;inum;i++)
{
grouptemp[i].adapt=group[i].adap
文档评论(0)