智能算法解决tsp问题及源代码.docVIP

智 能 算 法 作 业 方震 PAGE 1 遗传算法解决10个城市TSP问题 姓名：方震 学号：一﹑问题描述 10个城市的坐标如下： 号 1 2 3 4 5 6 7 8 9 10 X 0.6683 0.6195 0.4000 0.2439 0.1707 0.2293 0.5171 0.8732 0.6878 0.8488 Y 0.2536 0.2634 0.4439 0.1463 0.2293 0.7610 0.9414 0.6536 0.5219 0.3609 该问题的理论解为2.6907. 二﹑方案设计 1.编码及初始化种群 以城市号编码，随机产生得到初始种群，利用randperm（城市数）函数产生，例如： 6 7 4 9 5 3 2 8 10 1 2.计算适应度 直接计算每条染色体（路径）的长度，取倒数为适应度。 3.轮盘赌选择 4.交叉——常规交配法（CM） 设有父代1和父代2，随机选择一个交配位，子代1交配位之前的基因为父代1交配位之前的基因，交配位之后的基因，从父代2中按顺序选择那些没有出现过的基因，子代2也做类似的处理，例如（|为交配位）： 父代1: 1 2 3 4|5 6 7 8 父代2: 5 2 1 7|3 8 4 6 子代1: 1 2 3 4|5 7 8 6 子代2: 5 2 1 7|3 4 6 8 5.变异 随机选择一条染色体中两个基因进行交换，例如，随机选择两个位置如3和7则： 6 7 4 9 5 3 2 8 10 1 →6 7 2 9 5 3 4 8 10 1 6.更新种群 将本代中初始种群s和变异后得到的种群s3合并为A，更新的种群s’中一半来自A中最优秀的，其余一半来自A中除了被选走的最优秀的，其他基因的随机。 三﹑结果输出与统计 程序输出结果如下： 》myGA 近似最近路径为： 5 4 2 1 10 9 8 7 6 3 近似最小路程为： 2.6907 运行几次后输出表格： 附录：源代码 distance.m function [distan] = distance(coord) m=length(coord); distan=zeros(m); for i=1:m for j=i:m distan(i,j)=(sum((coord(:,i)-coord(:,j)).^2))^0.5; distan(j,i)=distan(i,j); end end fit.m function [ f,g,p ] = fit(s,distan) [inn,m]=size(s); f=zeros(1,inn); g=zeros(1,inn); p=zeros(1,inn); fsum=0; for i=1:inn; for j=2:m; g(i)=g(i)+distan(s(i,j-1),s(i,j)); end g(i)=g(i)+distan(s(i,m),s(i,1)); f(i)=1/g(i); end fsum=sum(f); for i=1:inn; p(i)=f(i)/fsum; end end select.m function[s1]=select(s,p) pl=length(p); sel=zeros(1,pl); pr=rand(1,pl); for i=1:pl sump=0; j=ceil(pl*rand); while sumppr(i); sump=sump+p(mod(j-1,pl)+1); j=j+1; end sel(i)=mod(j-2,pl)+1; s1(i,:)=s(sel(i),:); end cross.m function [s2] = cross(s1,pcross) [inn,m]=size(s1); s11=zeros(inn,m); s12=zeros(inn,m); l=zeros(1,m); for i=1:inn; if rand=pcross s11(i,:)=s1(i,:); l(i)=1; else s12(i,:)=s1(