目錄
蟻群算法
Hopfield網(wǎng)絡(luò)
遺傳算法
免疫算法
蟻群算法
求解思路
Hopfield網(wǎng)絡(luò)
Hopfield網(wǎng)絡(luò)適合求結(jié)果的次優(yōu)解，可以保證解向能量函數(shù)最小值方向收斂，但不能確保達到全局最小點。
實現(xiàn)能量函數(shù)
網(wǎng)格能量的最小值對應(yīng)于最佳或者次最佳的路徑距離。
%%%%%%%計算能量函數(shù)%%%%%%%%%%%%
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);實現(xiàn)動態(tài)方程
?repmat - 重復(fù)數(shù)組副本
? ? 此 MATLAB 函數(shù) 返回一個數(shù)組，該數(shù)組在其行維度和列維度包含 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;優(yōu)化計算
clear all
clc
%定義全局變量
global A D
%導(dǎo)入城市位置
load location
%計算相互城市間距離
distance=dist(citys,citys');
%初始化網(wǎng)絡(luò)
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);
%尋優(yōu)迭代
for k=1:iter_num
% 動態(tài)方程計算
dU=diu(V,distance);
% 輸入神經(jīng)元狀態(tài)更新
U=U+dU*step;
% 輸出神經(jīng)元狀態(tài)更新
V=(1+tansig(U/U0))/2;
% 能量函數(shù)計算
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));
%結(jié)果顯示
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(['優(yōu)化前路徑(長度：' num2str(Length_init) ')'])
axis([0 1 0 1])
grid on
xlabel('城市位置橫坐標(biāo)')
ylabel('城市位置縱坐標(biāo)')
% 計算最優(yōu)路徑長度
[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
% 繪制最優(yōu)路徑
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(['優(yōu)化后路徑(長度：' num2str(Length_end) ')'])
axis([0 1 0 1])
grid on
xlabel('城市位置橫坐標(biāo)')
ylabel('城市位置縱坐標(biāo)')
% 繪制能量函數(shù)變化曲線
figure(3)
plot(1:iter_num,E);
ylim([0 1000])
title(['能量函數(shù)變化曲線(最優(yōu)能量：' num2str(E(end)) ')']);
xlabel('迭代次數(shù)');
ylabel('能量函數(shù)');
else
disp('尋優(yōu)路徑無效');
end
遺傳算法
?基本步驟
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%主函數(shù)%%%%%%%%%%%%%
clear;
clc;
%%%%%%%%%%%%%輸入?yún)?shù)%%%%%%%%%%%%
N=10; %%城市的個數(shù)
M=20; %%種群的個數(shù)
C=100; %%迭代次數(shù)
C_old=C;
m=2; %%適應(yīng)值歸一化淘汰加速指數(shù)
Pc=0.8; %%交叉概率
Pmutation=0.2; %%變異概率
%%%%%%%%%生成城市的坐標(biāo)%%%%%%%%%%%%%%%%
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('隨機產(chǎn)生的種群圖')
axis([-3 3 -3 3]);
subplot(2,1,2)
plot_route(pos,R);
xlabel('橫軸')
ylabel('縱軸')
title('隨機生成種群中城市路徑情況')
axis([-3 3 -3 3]);
%%%%%%%%初始化種群及其適應(yīng)函數(shù)%%%%%%%%%%%%
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
%%%%每次選擇都保存最優(yōu)的種群%%%%
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
%%%%求適應(yīng)度函數(shù)%%%%
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('優(yōu)化后的種群中城市路徑情況')
axis([-3 3 -3 3]);
% %%%%%%%%適應(yīng)度函數(shù)%%%%%%%%%%%%%%%%%%%%
% 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
%
% %%%%%%%%個體距離計算函數(shù)%%%%%%%%%%%%
% 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
%
% %%%%%%%%交叉操作函數(shù)%%%%%%%%%%%%%%%%%%%%
% 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
%
% %%%%%%%%對調(diào)函數(shù)%%%%%%%%%%%%%%%%%%%%
% function [x,y]=exchange(x,y)
% temp=x;
% x=y;
% y=temp;
% end
%
% %%%%%%%%變異函數(shù)%%%%%%%%%%%%%%%%%%%%
% 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
%
% %%%%%%%%連點畫圖函數(shù)%%%%%%%%%%%%%%%%%%%%%%%%
% 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
?randperm - 整數(shù)的隨機排列?p = randperm(n)
? ? 此 MATLAB 函數(shù) 返回行向量，其中包含從 1 到 n 沒有重復(fù)元素的整數(shù)隨機排列。?scatter - 散點圖? ? scatter(x,y)
? ? 此 MATLAB 函數(shù) 在向量 x 和 y 指定的位置創(chuàng)建一個包含圓形標(biāo)記的散點圖。該類型的圖形也稱為氣泡圖。 要繪制一組坐標(biāo)，請將 x 和 y 指定為等長向量。 要在同一組坐標(biāo)區(qū)上繪制多組坐標(biāo)，請將 x 或 y 中的至少一個指定為矩陣。?fprintf - 將數(shù)據(jù)寫入文本文件
? ? 此 MATLAB 函數(shù) 按列順序?qū)?formatSpec 應(yīng)用于數(shù)組 A1,...An 的所有元素，并將數(shù)據(jù)寫入到一個文本文件。fprintf 使用在對 fopen 的調(diào)用中指定的編碼方案。fprintf(fileID,formatSpec,A1,...,An)
fprintf(formatSpec,A1,...,An)
免疫算法
?基本流程
目標(biāo)免疫?
????????采用單點交叉和目標(biāo)免疫。
?global - 將變量聲明為全局變量? ? global var1 ... varN
文章來源：http://www.zghlxwxcb.cn/news/detail-473778.html
%清空命令窗口和內(nèi)存
clear
clc
N=10;
%城市的個數(shù)
M=N-1;
%種群的個數(shù)
pos=randn(N,2);
%%生成城市的坐標(biāo)
global D;
%城市距離數(shù)據(jù)
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
%中間結(jié)果保存
global TmpResult;
TmpResult = [];
global TmpResult1;
TmpResult1 = [];
%參數(shù)設(shè)定
[M, N] = size(D);%集群規(guī)模
pCharChange = 1;%字符換位概率
pStrChange = 0.4;%字符串移位概率
pStrReverse = 0.4;%字符串逆轉(zhuǎn)概率
pCharReCompose = 0.4;%字符重組概率
MaxIterateNum = 100;%最大迭代次數(shù)
%數(shù)據(jù)初始化
mPopulation = zeros(N-1,N);
mRandM = randperm(N-1);%最優(yōu)路徑
mRandM = mRandM + 1;
for rol = 1:N-1
mPopulation(rol,:) = randperm(N);%產(chǎn)生初始抗體
mPopulation(rol,:) = DisplaceInit(mPopulation(rol,:));%預(yù)處理
end
%迭代
count = 0;
figure(2);
while count < MaxIterateNum
%產(chǎn)生新抗體
B = Mutation(mPopulation, [pCharChange pStrChange pStrReverse pCharReCompose]);
%計算所有抗體的親和力和所有抗體和最優(yōu)抗體的排斥力
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('最佳適應(yīng)度變化趨勢')
xlabel('迭代數(shù)')
ylabel('最佳適應(yīng)度')
% mRandM
文章來源地址http://www.zghlxwxcb.cn/news/detail-473778.html
到了這里，關(guān)于旅行商問題TSP的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
