TSP问题求解.doc

TSP问题的遗传算法实验报告 一、实验题目 TSP问题的遗传算法实现 二 、实验目的 1 熟悉和掌握遗传算法的基本概念和基本思想； 2 加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子； 3 理解和掌握利用遗传算法进行问题求解的基本技能。 三 、实验要求 1 以10/个城市结点的TSP问题为例,用遗传算法加以求解； 2 掌握遗传算法的基本原理、各个遗传操作和算法步骤； 3能求出问题最优解，若得不出最优解，请分析原因； 4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。 四 、实验代码 Main函数 %% 连续Hopfield神经网络的优化—旅行商问题优化计算 % function main %% 清空环境变量、定义全局变量 clear all clc global A D %% 导入城市位置 load city_location %% 计算相互城市间距离 distance=dist(citys,citys); %% 初始化网络 N=size(citys,1); A=200; D=100; U0=0.1; step=0.0001; delta=2*rand(N,N)-1; U=U0*log(N-1)+delta; V=(1+tansig(U/U0))/2; iter_num=10000; E=zeros(1,iter_num); %% 寻优迭代 for k=1:iter_num % 动态方程计算 dU=diff_u(V,distance); % 输入神经元状态更新 U=U+dU*step; % 输出神经元状态更新 V=(1+tansig(U/U0))/2; % 能量函数计算 e=energy(V,distance); E(k)=e; end %% 判断路径有效性 [rows,cols]=size(V); V1=zeros(rows,cols); [V_max,V_ind]=max(V); for j=1:cols V1(V_ind(j),j)=1; end C=sum(V1,1); R=sum(V1,2); flag=isequal(C,ones(1,N)) isequal(R,ones(1,N)); %% 结果显示 if flag==1 % 计算初始路径长度 sort_rand=randperm(N); citys_rand=citys(sort_rand,:); Length_init=dist(citys_rand(1,:),citys_rand(end,:)); for i=2:size(citys_rand,1) Length_init=Length_init+dist(citys_rand(i-1,:),citys_rand(i,:)); end % 绘制初始路径 figure(1) plot([citys_rand(:,1);citys_rand(1,1)],[citys_rand(:,2);citys_rand(1,2)],o-) for i=1:length(citys) text(citys(i,1),citys(i,2),[ num2str(i)]) end text(citys_rand(1,1),citys_rand(1,2),[ 起点 ]) text(citys_rand(end,1),citys_rand(end,2),[ 终点 ]) title([优化前路径(长度： num2str(Length_init) )]) axis([0 1 0 1]) grid on xlabel(城市位置横坐标) ylabel(城市位置纵坐标) % 计算最优路径长度 [V1_max,V1_ind]=max(V1); citys_end=citys(V1_ind,:); Length_end=dist(citys_end(1,:),citys_end(end,:)); for i=2:size(citys_end,1) Length_end=Length_end+dist(citys_end(i-1,:),citys_end(i,:)); end disp(最优路径矩阵);V1 % 绘制最优路径 figure(2) plot([citys_end(:,1);citys_end(1,1)],... [citys_end(:,2);cit