利用遗传算法解决TSP问题.docx

课程实验报告

1.实验目的
利用遗传算法获得TSP问题的近似解。
2.实验要求
要求学生了解遗传算法解决问题的基本流程。对TSP问题有所了解,知道TSP问题的难点在什么地方,如何使用遗传算法来获得一个较好的近似解。
3.实验内容
已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
4.实验软硬件环境
基本Windows系统基本运行环境，VS2012
实验方案
（1）遗传算法
是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法
遗传算法的基本运算过程如下：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。
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，则旅行商问题的数学模型为：
minl=σ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将所选的父代两两组队，随机产生一个位置进行交叉，如：
81421386325734324221
6123568563185633211
交叉后为：
81421386325185633211
6123568563734324221

（6）变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使