优化算法_模拟退火算法_案例_Matlab
模拟退火算法(Simulate Anneal Arithmetic,SAA)是一种通用概率演算法,用来在一个大的搜寻空间内找寻命题的最优解。具体定义可以参考百度百科资料:模拟退火算法_百度百科。
此案例主要是使用matlab进行进行简单TSP问题(旅行商问题)的求解,具体问题如图所示:
首先编写此案例中所使用到的6个函数,具体代码如下:
function1:Distance,用于计算两两城市之间的距离
function D = Distance(citys)
% 计算两两城市之间的距离
n = size(citys,1);
D = zeros(n,n);
for i = 1:n
for j = i+1:n
D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));
D(j,i) = D(i,j);
end
end
endfunction2:DrawPath,用于画出行走路径
function DrawPath(Route,citys)
% 画出行走路径
figure
plot(,...
,'o-');
grid on
for i = 1:size(citys,1)
text(citys(i,1),citys(i,2),[' ' num2str(i)]);
end
text(citys(Route(1),1),citys(Route(1),2),' 起点');
text(citys(Route(end),1),citys(Route(end),2),' 终点');
endfunction3:OutputPath,用于打印出行走路径
function p = OutputPath(R)
% 打印出行走路径路径函数
R = ;
N = length(R);
p = num2str(R(1));
for i = 2:N
p = ;
end
disp(p)
endfunction4:PathLength,用于计算路径总长度
function Length = PathLength(D,Route)
% 用于计算路径路径长度
Length = 0;
n = size(Route,2);
for i = 1:(n - 1)
Length = Length + D(Route(i),Route(i + 1));
end
Length = Length + D(Route(n),Route(1));
endfunction5:NewPath,用于输出该次迭代所得出的新解
function S2 = NewPath(S1)
% 输出该次迭代所得出的新解
N = length(S1);
S2 = S1;
a = round(rand(1,2)*(N-1)+1); %产生两个随机位置 用来交换
W = S2(a(1));
S2(a(1)) = S2(a(2));
S2(a(2)) = W; %得到一个新路线
endfunction6:UseNewPath,用于判断是否接受新解
function = UseNewPath(S1,S2,D,T)
% 判断是否接受新解
R1 = PathLength(D,S1);%计算路线长度
N = length(S1); %得到城市的个数
R2 = PathLength(D,S2);%计算路线长度
dC = R2 - R1; %计算能力之差
if dC < 0 %如果能力降低 接受新路线
S = S2;
R = R2;
elseif exp(-dC/T) >= rand %以exp(-dC/T)概率接受新路线
S = S2;
R = R2;
else %不接受新路线
S = S1;
R = R1;
end
end以上即为主程序所用到的函数,下面来编写主程序main.m:
step1:清空环境变量
clear all;
clc;step2:导入城市位置数据
X = [18.4700 95.1000
16.4700 94.6400
20.0900 94.5400
14.3900 93.3700
25.2300 97.2400
22.0000 93.0500
23.4700 92.0200
16.2000 96.2900
17.3000 97.3800
13.0500 98.1200
15.5300 97.3800
24.5200 95.5900
16.4100 97.1300
15.0900 92.5500];导入成功后生成矩阵X如图所示:
step3:计算距离
D = Distance(X);%计算距离矩阵
N = size(D,1); %城市的个数计算成功后生成距离数据矩阵D如图所示,其中对角线上数据为0:
step4:初始化参数
T0 = 1e10; % 初始温度
Tend = 1e-30;% 终止温度
q = 0.9; %降温速率
Time = ceil(double(solve()));% 计算迭代的次数
% Time = 875;
count = 0; %迭代计数
Obj = zeros(Time,1); %目标值矩阵初始化
track = zeros(Time,N); %每代的最优路线矩阵初始化step5:随机产生一个初始路线
S1 = randperm(N);
DrawPath(S1,X)
disp(&#39;初始路径:&#39;)
OutputPath(S1);
Rlength = PathLength(D,S1);
disp([&#39;总距离:&#39;,num2str(Rlength)]);产生随机路径后使用DrawPath函数所画图像如图所示:
使用OutputPath函数,打印出的行走路径如图所示:
step6:迭代优化
while T0 > Tend
count = count + 1; %更新迭代次数
temp = zeros(L,N+1)
% 产生新解
S2 = NewPath(S1);
= UseNewPath(S1,S2,D,T0);
% 记录每次迭代过程的最优路线
if count == 1 || R < Obj(count-1)
Obj(count) = R; %若当前温度下最优路程小于上一路程,则记录当前路程
else
Obj(count) = Obj(count-1);%若当前温度下最优路程大于上一路程,则记录上一路程
end
track(count,:) = S1;
T0 = q * T0; %降温
endstep7:画出优化过程图
figure
plot(1:count,Obj)
xlabel(&#39;迭代次数&#39;)
ylabel(&#39;距离&#39;)
title(&#39;优化过程&#39;)优化过程图像如图所示:
step8:画出最优路径图
DrawPath(track(end,:),X)使用DrawPath函数所画图像如图所示:
step9:输出最优路径路线与距离
disp(&#39;最优解:&#39;)
S = track(end,:);
p = OutputPath(S);
disp([&#39;总距离:&#39;,num2str(PathLength(D,S))]);使用OutputPath函数,打印出的最优路径如图所示:
页:
[1]