人工智能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问题中适应度函数常取路径长度的倒数（或倒数的相关函数），如：

)(),(),,,(111121x x d x x d N x x x f n n i i i

n ++=∑-=+Λ

其中，N 是个调节参数，根据实验情况进行确定。

for(i=0;i

{

sumdistance=0;

for(j=1;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(x i )为第i （i=1,2,3.....popsize ）个染色体的适应度，则每个个体被选中的概率

是： ∑==popsize j j i i x f x f x P 1)()

()( 本题中具体使用的是期望值方法

//初始化梯度概率

for(i=0;i

{

gradient[i]=0.0;

xuanze[i]=0.0;

}

gradient[0]=group[0].p;

for(i=1;i

gradient[i]=gradient[i-1]+group[i].p;

srand((unsigned)time(NULL));

//随机产生染色体的存活概率

for(i=0;i

{

xuanze[i]=(rand()%100);

xuanze[i]/=100;

}

//选择能生存的染色体

for(i=0;i

{

for(j=0;j

{

if(xuanze[i]

{

xuan[i]=j; //第i个位置存放第j个染色体

break;

}

}

}

//拷贝种群

for(i=0;i

{

grouptemp[i].adapt=group[i].adapt;

grouptemp[i].p=group[i].p;

for(j=0;j

grouptemp[i].city[j]=group[i].city[j];

}

//数据更新

for(i=0;i

{

temp=xuan[i];

group[i].adapt=grouptemp[temp].adapt;

group[i].p=grouptemp[temp].p;

for(j=0;j

group[i].city[j]=grouptemp[temp].city[j];