《基于遗传算法的TSP问题》由会员分享，可在线阅读，更多相关《基于遗传算法的TSP问题（7页珍藏版）》请在金锄头文库上搜索。
1、第?章 基于遗传算法的 TSP 问题?.1 案例背景？.1.1 城市垃圾收运最短路线问题城市垃圾自其产生到最终被送到处置场处理，需要环卫部门对其进行收集与运输，这一过程称为城 市垃圾的收运。某城市垃圾收运过程简化如下： 该城市有有 276 处垃圾收集点，和 1 个中转站，垃圾车从垃圾中转站出发，经过每个垃圾点清理垃 圾，针对表？-1 中给出的垃圾中转站和收集点的坐标信息数据，求垃圾车收运的最短路线。表？-1 案例数据表Stop_IDX(feet)Y(feet)Stop_Typ e 0-481779641320622 1-484089041810691 2-484826042015451 3-4
2、84639542012271 4-484632842012351 5-485475441986491 273-486752441995041 274-487412041988401 275-487862042041901 276-487648441976611 注： Stop_ID：收集点编号，X，Y 分别为该点的坐标，单位为 feet；Stop_Type：收集点类型（1：垃圾收 集点，2：垃圾中转站）；由于垃圾收集点位于城市街道中，故本问题中两点之间距离考虑采用 Manhattan 距离：( )。11221212( , ) ( ,),(,)distance x yxyxyxx xyy y通过
3、分析，我们知道属于 TSP 问题（Traveling Salesman Problem 即旅行商问题），是指已知 n 个城 市之间的相互距离，现有一个推销员必须遍访这 n 个城市，并且每个城市只能访问一次，最后又必须返 回出发城市，如何安排访问次序使旅行路线的总长度最短。TSP 问题是一个典型的组合优化问题，其最 优解的求解代价是指数级的。已经证明 TSP 问题是一个 NP 难问题，其可能的路径数目与城市数目 n 是 成指数型增长的，所以一般很难精确地求出其最优解。 在本章中，我们希望能找到解决 TSP 问题的有效算法，参考中国邮递员问题，对遗传算法进行改进 以适应本模型约束的要求来进行建模和
4、求解。？.1.2 遗传算法简述遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法，是由美国的 J.Holland 教授 1975 年首先提出，在组合优化、机器学习、信号处理、自适应控制和人工生命等领域有广泛的应用。其做法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法对于解决 TSP 问题等组合优化问题具有较好的寻优性能。遗传算法的主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定，具有内在的隐2数学建模 30
5、个案例分析并行性和更好的全局寻优能力，采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。 遗传算法的一般流程如图？-1 所示。图？-1 BP 遗传算法一般流程图遗传算法的基本运算过程如下：（1）初始化 设置进化代数计数器 t=0，设置最大进化代数 T，随机生成 M 个个体作为初始群体P(0)。（2）个体评价 计算群体 P(t)中各个个体的适应度。 （3）选择运算 将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。（4）交叉运算 将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组
6、而生成新个体的操作。 （5）变异运算 将变异算子作用于群体。即是对群体中的个体串的某些基因值作变动。群体 P(t)经过选择、交叉、变异运算之后得到下一代群体 P(t1)。 （6）终止判断 若 t T，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。？.2.模型建立采用遗传算法解决该问题的过程如下： （1）编码 常用的编码方式有二进制编码、浮点数编码和混合编码等等。此处使用十进制编码。 （2）初始化 种群大小为 n，初始化产生 n277 路径矩阵（MATLAB 中利用 randperm(m)产生 m 个不重复 1m 的 数）。 （3）适应值函数 实际问题参数集编码群体t计算适应
7、度运算：复制交叉变异群体t+1满足要求？解码改善或解决实际问题群体t+1 群体tYN第 6 章3常用的适应值函数有 f(x)、-f(x)、max- f(x)、f(x)-min 等等。本案例采用以下适应值函数：（？-1）( )min(1)max min 0.0001mf xFitness 其中 Fitness 为适应值；f (x)为路径长度；max、min 分别为目前为止最大和最小路径长度；m 为适应 值归一化加速指数。 （4）选择 遗传操作包括选择、交叉和变异三种基本形式。选择是从当前群体中选出优良个体，参与后续的遗 传操作。常用方法有轮盘赌选择法、随机遍历抽样法、局部选择法等等。本案例采用若
8、 fitness=alpharand，则选择该个体，alpha 为保护指数，rand 为随机数。 （5）交叉 交叉是把两个父个体的部分结构加以替换重组而生产新个体的操作，将优良基因遗传给下一代，达 到种群进化目的。常用的交叉方法单点交叉、多点交叉、均匀交叉、部分匹配交叉等等。本案例采用部 分匹配交叉。 对于下面两个父个体的表示，随机地选择两个交叉点“|”。 p1：（1 2 3 | 4 5 6 7 | 8 9） p2：（4 5 2 | 1 8 7 6 | 9 3） 首先两个交叉点之间的中间段交换，得到： o1：（x x x | 1 8 7 6 | x x） o2：（x x x | 4 5 6 7
9、 | x x） 其中，x 表示暂未定义码，得到中间段的映射关系有：1 4，8 5，76，67。 对子个体 1，子个体 2 中的 x 部分，分别保留从其父个体中继承未选定的 2，3，9，得到： o1：（x 2 3 | 1 8 7 6 | x 9) o2：（x x 2 | 4 5 6 7 | 9 3) 最后根据中间段映射关系，对于子个体 1 的第一个 x，使用最初父码 1，由 14 交换得到第一个 x 为 4，类似第一个子个体的第二个 x，使用最初父码 8，由 85 交换得到子个体 1 的第二个 x 为 5。如 果映射关系中存在传递关系，即备选交换有多个码，则选择此前未确定的一个码作为交换。最终得
10、到的 个体为： o1：（4 2 3 | 1 8 7 6 | 5 9） o2：（1 8 2 | 4 5 6 7 | 9 3) （6）变异 变异是对群体中个体串的基因值作变动。就字符集为0,1的二进制码串来说，变异操作就是把某些 基因值取反，即 10 或 01。一般变异操作的基本步骤如下：在群体中所有个体的码串范围内随机确 定变异基因；以事先确定的变异概率对这些基因值进行变异。？.3 MATLAB 实现根据上一节建立的模型，用 MATLAB 软件仿真求解 TSP 问题。？.3.1 遗传算法求解 TSP 问题本案例用遗传算法求解 TSP 问题，其中模型中的 277 个点坐标为本案例所提供，存放在本地
11、磁盘 E 下的 coordinate.txt 文件中，具体的 MATLAB 实现主程序代码如下所示。程序一：主程序 Clear a=load(E:coordinate.txt); %277 个点坐标读取 D=ff01(a); %生成无向图的赋权邻接矩阵 D，a 为读入的各点坐标 R,Rlength=geneticTSP(D,a,1000,500000,2,0.8)%这里的计算参数可以更改4数学建模 30 个案例分析程序二：计算路径的遗传算法函数 %R 为最小距离的路径，Rlength 为最小路径长度，D 为距离矩阵通过 ff01 函数计算； %a 为各点坐标，n 为种群大小，C 为迭代次数，达
12、到 C 时停止迭代； %m 为适应值归一化淘汰保护加速指数，就是加速种群的更换，alpha 为淘汰保护系数。 function R,Rlength=geneticTSP(D,a,n,C,m,alpha) N,NN=size(D); farm=zeros(n,N);%用于存储种群 for i=1:nfarm(i,:)=randperm(N);%随机生成初始种群 end R=farm(1,:); subplot(1,2,1) scatter(a(:,1),a(:,2),.) pause(1) farm(1,:)=R; len=zeros(n,1);%存储路径长度 fitness=zeros(n,1
13、);%存储归一化适应值 counter=0; while counter =alpha*randnn=nn+1;FARM(nn,:)=farm(i,:);endendFARM=FARM(1:nn,:); aa,bb=size(FARM);%交叉和变异while aanFARM=FARM(1:n,:);%保持种群规模为 nend 第 6 章5farm=FARM;clear FARMcounter=counter+1 end Rlength=myLength(D,R) counter; subplot(1,2,2) plotaiwa(a,R) R 程序三：无向图的赋权邻接矩阵 D 的计算函数 %输
14、入参数 a 是各点的坐标 %输出参数 D 是无向图的赋权邻接矩阵 function D=ff01(a) c,d=size(a); D=zeros(c,c); for i=1:cfor j=i:cbb=(a(i,1)-a(j,1).2+(a(i,2)-a(j,2).2;D(i,j)=bb(0.5);D(j,i)=D(i,j);end end 程序四：适应值计算函数 %计算归一化适应值 function fitness=fit(len,m,maxlen,minlen) fitness=len; for i=1:length(len)fitness(i,1)=(1-(len(i,1)-minlen)
15、/(maxlen-minlen+0.0001).m; end 程序五：交叉函数 function a,b=intercross(a,b) L=length(a); if L=rand elseW=floor(L/10)+8; end p=unidrnd(L-W+1);%随机选择交叉范围，从 p 到 p+W for i=1:W%交叉x=find(a=b(1,p+i-1);y=find(b=a(1,p+i-1);a(1,p+i-1),b(1,p+i-1)=exchange(a(1,p+i-1),b(1,p+i-1);a(1,x),b(1,y)=exchange(a(1,x),b(1,y); end
16、 程序六: 变异函数 function x,y=exchange(x,y) temp=x; x=y; y=temp; 程序七: 计算路径的长度函数 %该路径长度是一个闭合的路径的长度6数学建模 30 个案例分析function len=myLength(D,p) N,NN=size(D); len=D(p(1,N),p(1,1); for i=1:(N-1)len=len+D(p(1,i),p(1,i+1); end 程序八：绘制路径示意图函数 function plotaiwa(a,R) scatter(a(:,1),a(:,2),.) hold on plot(a(R(1),1),a(R(length(R),1),a(R(1),2),a(R(length(R),2) hold on for i=2:length(R
