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

人工智能实验三实验报告
班级： 姓名： 学号：
一 实验题目
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;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=group[i].adapt;
grouptemp[i].p=group[i].p;
for(j=0;j<cities;j++)
grouptemp[i].city[j]=group[i].city[j];
}
//数据更新
for(i=0;i<num;i++)
{
temp=xuan[i];
group[i].adapt=grouptemp[temp].adapt;
group[i].p=grouptemp[temp].p;
for(j=0;j<cities;j++)
group[i].city[j]=grouptemp[temp].city[j];
}

2）交叉操作：
交叉算子就是把两个父代个体的部分结构加以替换重组而生成新个体的操作。
部分匹配交叉、顺序交叉、改进的启发式顺序交叉
//temp1号染色体和temp2染色体交配
for(i=0;i<t/2;i++)
{
point1=rand()%cities;
point2=rand()%cities;
for(j=temp1;j<num;j++)
if(jiaopeiflag[j]==1)
{
temp1=j;
break;
}
for(j=temp1+1;j<num;j++)
if(jiaopeiflag[j]==1)
{
temp2=j;
break;
}
//进行基因交配
if(point1>point2) //保证point1<=point2
{
temp=point1;
point1=point2;
point2=temp;
}
memset(map1,-1,sizeof(map1));
memset(map2,-1,sizeof(map2));
//断点之间的基因产生映射
for(k=point1;k<=point2;k++)
{
map1[group[temp1].city[k]]=group[temp2].city[k];
map2[group[temp2].city[k]]=group[temp1].city[k];
}
//断点两边的基因互换
for(k=0;k<point1;k++)
{
temp=group[temp1].city[k];
group[temp1].city[k]=group[temp2].city[k];
group[temp2].city[k]=temp;
}
for(k=point2+1;k<cities;k++)
{
temp=group[temp1].city[k];
group[temp1].city[k]=group[temp2].city[k];
group[temp2].city[k]=temp;
}
//处理产生的冲突基因
for(k=0;k<point1;k++)
{
for(kk=point1;kk<=point2;kk++)
if(group[temp1].city[k]==group[temp1].city[kk])
{
group[temp1].city[k]=map1[group[temp1].city[k]];
break;
}
}
for(k=point2+1;k<cities;k++)
{
for(kk=point1;kk<=point2;kk++)
if(group[temp1].city[k]==group[temp1].city[kk])
{
group[temp1].city[k]=map1[group[temp1].city[k]];
break;
}
}
for(k=0;k<point1;k++)
{
for(kk=point1;kk<=point2;kk++)
if(group[temp2].city[k]==group[temp2].city[kk])
{
group[temp2].city[k]=map2[group[temp2].city[k]];
break;
}
}
for(k=point2+1;k<cities;k++)
{
for(kk=point1;kk<=point2;kk++)
if(group[temp2].city[k]==group[temp2].city[kk])
{
group[temp2].city[k]=map2[group[temp2].city[k]];
break;
}
}
temp1=temp2+1;
}

3）变异操作
TSP问题中，经常采取的变异操作主要有：位点变异、逆转变异、对换变异、插入变异。
//随机产生变异概率
srand((unsigned)time(NULL));
for(i=0;i<num;i++)
{
bianyip[i]=(rand()%100);
bianyip[i]/=100;
}
//确定可以变异的染色体
t=0;
for(i=0;i<num;i++)
{
if(bianyip[i]<pm)
{
bianyiflag[i]=1;
t++;
}
}
//变异操作,即交换染色体的两个节点
srand((unsigned)time(NULL));
for(i=0;i<num;i++)
{
if(bianyiflag[i]==1)
{
temp1=rand()%10;
temp2=rand()%10;
point=group[i].city[temp1];
group[i].city[temp1]=group[i].city[temp2];
group[i].city[temp2]=point;
}
}

3 实验中采用的算法参数的最佳选择值是多少
#define cities 10/30 //城市的个数
#define MAXX 150 //迭代次数
#define pc 0.72 //交配概率
#define pm 0.02 //变异概率
#define num 20 //种群的大小
六 实验结果
1 要求有实验运行结果截图，以及必要的说明

以上部分是每次迭代的步骤结果，通过染色体群体中个体的交配、变异，从而更改染色体的具体基因组成，通过不断进行适应度计算、存活率的计算，更新已有数值；

以上部分为迭代之后的总结果，输出最终的种群评价，从染色体种群里面取出最佳的染色体，并进行输出。

2 要求说明是否搜索到了最优解，如果没有，请分析原因
本题中根据随机生成的cities个城市之间的相互距离、随机产生初试群，通过TSP算法，通过以下步骤：
(1) 初始化群体;
(2) 计算群体上每个个体的适应度值;
(3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;
(4) 按概率Pc进行交叉操作;
(5) 按概率Pm进行变异操作;
(6) 没有满足某种停止条件，则转第(2)步，否则进入(7)；
(7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。
成功找到种群中适应度值最优的染色体作为问题的满意解或最优解。
若失败，分析可得失败原因为：随机生成的cities个城市之间的相互距离、随机产生初试群有可能不存在适应度值最优的染色体

七 实验总结及体会
1. 同一问题可能有不同的几种算法相对应解决：
对于此类旅行者问题，原在数据结构和算法课中学过迪杰斯特拉算法，也可以高效快速的解决给定好初值的最短路径问题；
在本课中，有学到了新的算法：TSP算法，此算法从遗传学角度，开辟了一个新的视野。通过每次迭代求出的局部最优解和最终求出的全局最优解。
两种不同的算法可以求解同一问题，但是角度完全不一样，从目前自己实验的结果而言，对于小数据量的输入均可以快速高效的完成题目。但是遗传算法可以考虑到的问题复杂度更高，更适合应用于实际。

2. 学习时应当重视动手实践能力：
课堂上讲解的遗传算法较为简单基础，对于理论学习而言，十分适合。但一旦应用于实践时，发现虽然每个部分模块自己都可以理解并且熟悉，但是对于实际应用，并且切实地解决实际问题仍存在较大的困难。
从理论到实践，从课本的知识到解决问题，若不及时的加以消化并且切实的应用于解决问题，可以看出知识很难为现实提供帮助。因而应在学习之后及时进行上机实验，并且达到熟练掌握与运用的阶段。

THANKS !!!

致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求

欢迎您的下载，资料仅供参考