利用遗传算法解决TSP问题
- 格式：doc
- 大小：141.50 KB
- 文档页数：15
课程实验报告
1. 实验目的
利用遗传算法获得TSP问题的近似解。
2.实验要求
要求学生了解遗传算法解决问题的根本流程。对TSP问题有所了解,知道TSP问题的难点在什么地方,如何使用遗传算法来获得一个较好的近似解。
3.实验内容
n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
4.实验软硬件环境
根本Windows系统根本运行环境，VS2021
5.实验方案
〔1〕遗传算法
是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法
遗传算法的根本运算过程如下：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对穿插产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估根底上的。
d)穿插运算：将穿插算子作用于群体。所谓穿插是指把两个父代个体的局部构造加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是穿插算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、穿插、变异运算之后得到下一代群体P(t 1)。
f)终止条件判断:假设t=T,那么以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
〔2〕用遗传算法模拟TSP问题
TSP问题及旅行商问题,假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值
这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商
问题(dij≠dji,,任意i,j=1,2,3，…,n)。
假设对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中
ti∈v(i=1,2,3,…,n)，且记tn+1= t1，那么旅行商问题的数学模型为：
min l=σd(t(i),t(i+1)) 〔i=1,…,n〕
旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目
与城市数目n是成指数型增长的，所以一般很难准确地求出其最优解，本文采用遗传算法求其近似解。
6.实验步骤：
〔1〕初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。
〔2〕适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1))。
〔3〕评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的时机要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=al
pha*(1-alpha).^(i-1) 。
〔4〕选择过程：选择过程是以旋转赌轮pop-size次为根底，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进展选择染色体的。
step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj)
j=1,…,i;i=1,…,pop-size.
step2、从区间(0,pop-size)中产生一个随机数r；
step3、假设qi-1
step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。
〔5〕穿插过程：本文采用常规单点穿插。为确定穿插操作的父代，从 到pop-size重复以下过程：从[0，1]中产生一个随机数r，如果r 将所选的父代两两组队，随机产生一个位置进展穿插，如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1
穿插后为：
8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1
6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
〔6〕变异过程：本文采用均匀多点变异。类似穿插操作中选择父代的过程，在r选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置按均匀变异〔该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点变异为x'k=ukmin+r(ukmax-ukmin)〕操作。如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
变异后：
8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
〔7〕循环操作：判断是否满足设定的代数xzome，否，那么跳入适应度f的计算；是，完毕遗传操作，跳出。
实验代码：
#include
#include
#include
#include
#include
#define cities 10 //城市的个数
#define MAXX 100//迭代次数
#define pc 0.8 //交配概率
#define pm 0.05 //变异概率
#define num 10//种群的大小
int bestsolution;//最优染色体
int distance[cities][cities];//城市之间的距离
struct group //染色体的构造
{
int city[cities];//城市的顺序
int adapt;//适应度
double p;//在种群中的幸存概率
}group[num],grouptemp[num];
//随机产生cities个城市之间的相互距离
void init()
{
int i,j;
memset(distance,0,sizeof(distance));
srand((unsigned)time(NULL));
for(i=0;i
{
for(j=i+1;j
{
distance[i][j]=rand()%100;
distance[j][i]=distance[i][j];
}
}
//打印距离矩阵
printf("城市的距离矩阵如下\n");
for(i=0;i
{
for(j=0;j
printf("%4d",distance[i][j]);
printf("\n");
}
}
//随机产生初试群
void groupproduce()
{
int i,j,t,k,flag;
for(i=0;i
for(j=0;j
group[i].city[j]=-1;
srand((unsigned)time(NULL));
for(i=0;i
{
//产生10个不一样的数字
for(j=0;j
{
t=rand()%cities;
flag=1;
for(k=0;k
{
if(group[i].city[k]==t)
{
flag=0;
break;
}
}
if(flag)
{
group[i].city[j]=t;
j++;
}
}
}
//打印种群基因
printf("初始的种群\n");
for(i=0;i
{
for(j=0;j
printf("%4d",group[i].city[j]);
printf("\n");
}
}
//评价函数,找出最优染色体
void pingjia()
{
int i,j;
int n1,n2;
int sumdistance,biggestsum=0;
double biggestp=0;
for(i=0;i
{
sumdistance=0;
for(j=1;j
{
n1=group[i].city[j-1];
n2=group[i].city[j];
sumdistance+=distance[n1][n2];
}
group[i].adapt=sumdistance; //每条染色体的路径总和
biggestsum+=sumdistance; //种群的总路径
}
//计算染色体的幸存能力,路劲越短生存概率越大
for(i=0;i
{
group[i].p=1-(double)group[i].adapt/(double)biggestsum;
biggestp+=group[i].p;
}
for(i=0;i
