旅行商问题TSP-Toy模板网

这篇具有很好参考价值的文章主要介绍了旅行商问题TSP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

蚁群算法

Hopfield网络

遗传算法

免疫算法

蚁群算法

求解思路

Hopfield网络

Hopfield网络适合求结果的次优解，可以保证解向能量函数最小值方向收敛，但不能确保达到全局最小点。

实现能量函数

网格能量的最小值对应于最佳或者次最佳的路径距离。

%%%%%%%计算能量函数%%%%%%%%%%%%
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);

实现动态方程

repmat - 重复数组副本
此 MATLAB 函数返回一个数组，该数组在其行维度和列维度包含 A 的 n 个副本。A 为矩阵时，B 大小为 size(A)*n。

%%%%%%%%%%计算du%%%%%%%%%%%
function du=diu(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;

优化计算

clear all
clc 
%定义全局变量
global A D
%导入城市位置
load location
%计算相互城市间距离
distance=dist(citys,citys');
%初始化网络
N=size(citys,1);
A=500;
D=200;
U0=0.2;
step=0.00005;
delta=2*rand(N,N)-1;
U=U0*log(N-1)+delta;
V=(1+tansig(U/U0))/2;
iter_num=5000;
E=zeros(1,iter_num);
%寻优迭代
for k=1:iter_num  
    % 动态方程计算
    dU=diu(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
  
   % 绘制最优路径
   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 1000])
   title(['能量函数变化曲线(最优能量：' num2str(E(end)) ')']);
   xlabel('迭代次数');
   ylabel('能量函数');
else
   disp('寻优路径无效');
end

旅行商问题TSP

遗传算法

基本步骤

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%主函数%%%%%%%%%%%%%
clear;
clc;
%%%%%%%%%%%%%输入参数%%%%%%%%%%%%
N=10;               %%城市的个数
M=20;               %%种群的个数
C=100;               %%迭代次数
C_old=C;
m=2;                %%适应值归一化淘汰加速指数
Pc=0.8;             %%交叉概率
Pmutation=0.2;       %%变异概率

%%%%%%%%%生成城市的坐标%%%%%%%%%%%%%%%%
pos=randn(N,2);

%%%%%%%%生成城市之间距离矩阵%%%%%%%%%%%%
D=zeros(N,N);
for i=1:N
    for j=i+1:N
        dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;
        D(i,j)=dis^(0.5);
        D(j,i)=D(i,j);
    end
end

%%%%%%%%生成初始群体%%%%%%%%%%%%%%%%%%%%
popm=zeros(M,N);
for i=1:M
    popm(i,:)=randperm(N);
end

%%%%%%%%随机选择一个种群%%%%%%%%%%%%%%%%
R=popm(1,:);
figure(1);
subplot(2,1,1)
scatter(pos(:,1),pos(:,2),'k.');
xlabel('横轴')
ylabel('纵轴')
title('随机产生的种群图')
axis([-3 3 -3 3]);
subplot(2,1,2)
plot_route(pos,R);      
xlabel('横轴')
ylabel('纵轴')
title('随机生成种群中城市路径情况')
axis([-3 3 -3 3]);

%%%%%%%%初始化种群及其适应函数%%%%%%%%%%%%
fitness=zeros(M,1);
len=zeros(M,1);
for i=1:M
    len(i,1)=myLength(D,popm(i,:));
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
R=popm(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
fitness=fitness/sum(fitness); 
distance_min=zeros(C+1,1);  %%各次迭代的最小的种群的距离
while C>=0
fprintf('迭代第%d次\n',C);
%%%%选择操作%%%%
nn=0;
for i=1:size(popm,1)
    len_1(i,1)=myLength(D,popm(i,:));
    jc=rand*0.3;
    for j=1:size(popm,1)
        if fitness(j,1)>=jc
        nn=nn+1;
        popm_sel(nn,:)=popm(j,:);
        break;
        end
    end
end
%%%%每次选择都保存最优的种群%%%%
popm_sel=popm_sel(1:nn,:);
[len_m len_index]=min(len_1);
popm_sel=[popm_sel;popm(len_index,:)]; 
%%%%交叉操作%%%%
nnper=randperm(nn);
A=popm_sel(nnper(1),:);
B=popm_sel(nnper(2),:);
for i=1:nn*Pc
[A,B]=cross(A,B);
popm_sel(nnper(1),:)=A;
popm_sel(nnper(2),:)=B;
end
%%%%变异操作%%%%
for i=1:nn
    pick=rand;
    while pick==0
         pick=rand;
    end
    if pick<=Pmutation
       popm_sel(i,:)=Mutation(popm_sel(i,:));
    end
end
%%%%求适应度函数%%%%
NN=size(popm_sel,1);
len=zeros(NN,1);
for i=1:NN
    len(i,1)=myLength(D,popm_sel(i,:));
end
maxlen=max(len);
minlen=min(len);
distance_min(C+1,1)=minlen;
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
fprintf('minlen=%d\n',minlen);
R=popm_sel(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
popm=[];
popm=popm_sel;
C=C-1;
%pause(1);
end
figure(2)
plot_route(pos,R);
xlabel('横轴')
ylabel('纵轴')
title('优化后的种群中城市路径情况')
axis([-3 3 -3 3]);

% %%%%%%%%适应度函数%%%%%%%%%%%%%%%%%%%%
% function fitness=fit(len,m,maxlen,minlen)
%     fitness=len;
%     for i=1:length(len)
%         fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001)).^m;
%     end
% end
% 
% %%%%%%%%个体距离计算函数%%%%%%%%%%%%
% 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
% end
% 
% %%%%%%%%交叉操作函数%%%%%%%%%%%%%%%%%%%%
% function [A,B]=cross(A,B)
%     L=length(A);
%     if L<10
%         W=L;
%     elseif ((L/10)-floor(L/10))>=rand&&L>10
%         W=ceil(L/10)+8;
%     else
%         W=floor(L/10)+8;
%     end
%     p=unidrnd(L-W+1);
%     fprintf('p=%d ',p);
%     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
% end
% 
% %%%%%%%%对调函数%%%%%%%%%%%%%%%%%%%%
% function [x,y]=exchange(x,y)
%     temp=x;
%     x=y;
%     y=temp;
% end
% 
% %%%%%%%%变异函数%%%%%%%%%%%%%%%%%%%%
% function a=Mutation(A)
%     index1=0;index2=0;
%     nnper=randperm(size(A,2));
%     index1=nnper(1);
%     index2=nnper(2);
%     %fprintf('index1=%d ',index1);
%     %fprintf('index2=%d ',index2);
%     temp=0;
%     temp=A(index1);
%     A(index1)=A(index2);
%     A(index2)=temp;
%     a=A;
% end
% 
% %%%%%%%%连点画图函数%%%%%%%%%%%%%%%%%%%%%%%%
% function plot_route(a,R)
%     scatter(a(:,1),a(:,2),'rx');
%     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)
%         x0=a(R(i-1),1);
%         y0=a(R(i-1),2);
%         x1=a(R(i),1);
%         y1=a(R(i),2);
%         xx=[x0,x1];
%         yy=[y0,y1];
%         plot(xx,yy);
%         hold on;
%     end
% end

旅行商问题TSP

randperm - 整数的随机排列 p = randperm(n)
此 MATLAB 函数返回行向量，其中包含从 1 到 n 没有重复元素的整数随机排列。

scatter - 散点图 scatter(x,y)
此 MATLAB 函数在向量 x 和 y 指定的位置创建一个包含圆形标记的散点图。该类型的图形也称为气泡图。要绘制一组坐标，请将 x 和 y 指定为等长向量。要在同一组坐标区上绘制多组坐标，请将 x 或 y 中的至少一个指定为矩阵。

fprintf - 将数据写入文本文件
此 MATLAB 函数按列顺序将 formatSpec 应用于数组 A1,...An 的所有元素，并将数据写入到一个文本文件。fprintf 使用在对 fopen 的调用中指定的编码方案。

fprintf(fileID,formatSpec,A1,...,An)
fprintf(formatSpec,A1,...,An)

免疫算法

基本流程

旅行商问题TSP

目标免疫

采用单点交叉和目标免疫。

global - 将变量声明为全局变量 global var1 ... varN

旅行商问题TSP

%清空命令窗口和内存
clear
clc 
N=10;               
%城市的个数
M=N-1;               
%种群的个数
pos=randn(N,2);
%%生成城市的坐标
global D;
%城市距离数据
D=zeros(N,N);
for i=1:N
    for j=i+1:N
        dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;
        D(i,j)=dis^(0.5);
        D(j,i)=D(i,j);
    end
end

%中间结果保存
global TmpResult;
TmpResult = [];
global TmpResult1;
TmpResult1 = [];

%参数设定
[M, N] = size(D);%集群规模
pCharChange = 1;%字符换位概率
pStrChange = 0.4;%字符串移位概率
pStrReverse = 0.4;%字符串逆转概率
pCharReCompose = 0.4;%字符重组概率
MaxIterateNum = 100;%最大迭代次数

%数据初始化
mPopulation = zeros(N-1,N);
mRandM = randperm(N-1);%最优路径
mRandM = mRandM + 1;
for rol = 1:N-1
    mPopulation(rol,:) = randperm(N);%产生初始抗体
    mPopulation(rol,:) = DisplaceInit(mPopulation(rol,:));%预处理
end

%迭代
count = 0;
figure(2);
while count < MaxIterateNum
    %产生新抗体
    B = Mutation(mPopulation, [pCharChange pStrChange pStrReverse pCharReCompose]);
    %计算所有抗体的亲和力和所有抗体和最优抗体的排斥力
    mPopulation = SelectAntigen(mPopulation,B);
    hold on
    plot(count,TmpResult(end),'o');
    drawnow
display(TmpResult(end));
display(TmpResult1(end));
    count = count + 1;
end

hold on
plot(TmpResult,'-r');
title('最佳适应度变化趋势')
xlabel('迭代数')
ylabel('最佳适应度')
% mRandM

旅行商问题TSP 文章来源地址https://www.toymoban.com/news/detail-473778.html