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);citys_end(1,2)],'o-')

   for i=1:length(citys)

       text(citys(i,1),citys(i,2),['  ' num2str(i)])

   end

   text(citys_end(1,1),citys_end(1,2),['       起点' ])

   text(citys_end(end,1),citys_end(end,2),['       终点' ])

   title(['优化后路径(长度：' num2str(Length_end) ')'])

   axis([0 1 0 1])

   grid on

   xlabel('城市位置横坐标')

   ylabel('城市位置纵坐标')

   % 绘制能量函数变化曲线

   figure(3)

   plot(1:iter_num,E);

   ylim([0 2000])

   title(['能量函数变化曲线(最优能量：' num2str(E(end)) ')']);

   xlabel('迭代次数');

   ylabel('能量函数');

else

   disp('寻优路径无效');

end

% %===========================================

% function du=diff_u(V,d)

% global A D

% n=size(V,1);

% sum_x=repmat(sum(V,2)-1,1,n);

% sum_i=repmat(sum(V,1)-1,n,1);

% V_temp=V(:,2:n);

% V_temp=[V_temp V(:,1)];

% sum_d=d*V_temp;

% du=-A*sum_x-A*sum_i-D*sum_d;

% %==========================================

% function E=energy(V,d)

% global A D

% n=size(V,1);

% sum_x=sumsqr(sum(V,2)-1);

% sum_i=sumsqr(sum(V,1)-1);

% V_temp=V(:,2:n);

% V_temp=[V_temp V(:,1)];

% sum_d=d*V_temp;

% sum_d=sum(sum(V.*sum_d));

% E=0.5*(A*sum_x+A*sum_i+D*sum_d);

diff_u函数

% % % % 计算du

function du=diff_u(V,d)

global A D

n=size(V,1);

sum_x=repmat(sum(V,2)-1,1,n);

sum_i=repmat(sum(V,1)-1,n,1);

V_temp=V(:,2:n);

V_temp=[V_temp V(:,1)];

sum_d=d*V_temp;

du=-A*sum_x-A*sum_i-D*sum_d;

Energy函数

% % % % % 计算能量函数

function E=energy(V,d)

global A D

n=size(V,1);

sum_x=sumsqr(sum(V,2)-1);

sum_i=sumsqr(sum(V,1)-1);

V_temp=V(:,2:n);

V_temp=[V_temp V(:,1)];

sum_d=d*V_temp;

sum_d=sum(sum(V.*sum_d));

E=0.5*(A*sum_x+A*sum_i+D*sum_d);

五 、实验结果

（图一、最优路径矩阵）

（图二、优化前路线）

（图三、优化后路线）

（图三、能量函数）