MATLAB之模拟退⽕算法（旅⾏商问题）
这⾥写⽬录标题
视频学习
代码来源于清风⽼师授课时，使⽤代码，数据来源于⼩⽯⽼师授课资料
简介
模拟退⽕算法，和遗传算法⼀样，是⼀种启发性算法，利⽤之前的数据与现在的数据作⽐较。
旅⾏商问题（TSP），是典型的优化问题，在物流配送，计算机⽹络，电⼦地图，交通疏导，电⽓分布等⽅⾯都有重要的⼯程和理论价值。
TSP可以简单的描述为，⼀个⼈需要到n个城市⾛⼀遍，并且最后回到最初的城市，计算该过程，应该如何选择路径，使得所⾛的路程最短，或者费⽤最低。 TSP算法设计步骤
（1）设计解空间
TSP解空间，可以理解为遍历城市的顺序，S (i)={1,2,3,4,5,6,7…}（各个城市
边编号为123456789…），每⼀个S(i)都表⽰⼀个遍历所有城市的⼀次路径。
最优解与初始路径没有多⼤的联系，所以初始路径可以随机⽣成。
（2）⽬标函数
在TSP中，⽬标函数就是回路路径长度最短
（3）新解产⽣
这⼀步骤很重要，，新解可以通过，交替法，移位法，倒置法等产⽣新的
解。
（4）Metropolis接受准则
以新解与旧解的差值，以及此时的温度为准则，判断是否接受新解， 这个概率会随着温度T的降低⽽不断减⼩，所以接受新解的概率会随着迭代次
数的累加，不断减⼩，后⾯⼏乎不接受新解，会⼀直到那个最优，这也是
防⽌获得的是局部最优的结果，⽽不是全局最优。
源代码
主函数
%%模拟退⽕解决TSP问题
clear;clc
coord =[66.8325.36;61.9526.34;4044.39;24.3914.63;17.0722.93;22.9376.1;51.7194.14;87.3265.36;68.7852.19;84.8836.09;5030;4020;2526];
n =size(coord,1);%城市的数⽬
figure(1)%新建⼀个编号为1的图形窗⼝
plot(coord(:,1),coord(:,2),'o');%画出城市的分布散点图
hold on %等⼀下要接着在这个图形上画图的
d =zeros(n);%初始化两个城市的距离矩阵全为0
for i =2:n
for j =1:i
coord_i =coord(i,:); x_i =coord_i(1); y_i =coord_i(2);%城市i的横坐标为x_i，纵坐标为y_i
coord_j =coord(j,:); x_j =coord_j(1); y_j =coord_j(2);%城市j的横坐标为x_j，纵坐标为y_j d(i,j)=sqrt((x_i-x_j)^2+(y_i-y_j)^2);%计算城市i和j的距离
end
end
d = d+d';%⽣成距离矩阵的对称的⼀⾯
%%参数初始化
T0 =1000;%初始温度
T = T0;%迭代中温度会发⽣改变，第⼀次迭代时温度就是T0
maxgen =1000;%最⼤迭代次数
Lk =500;%每个温度下的迭代次数
alfa =0.95;%温度衰减系数
%%随机⽣成⼀个初始解
path0 =randperm(n);%⽣成⼀个1-n的随机打乱的序列作为初始的路径
%%初始化⽤来保存中间结果的⾏⾛路径和距离的取值
iter_path = path0;
iter_result =calculate_tsp_d(path0,d);%调⽤我们⾃⼰写的calculate_tsp_d函数计算当前路径的距离
%%模拟退⽕过程
for iter =1: maxgen %外循环，我这⾥采⽤的是指定最⼤迭代次数
for i =1: Lk %内循环，在每个温度下开始迭代
result0 =calculate_tsp_d(path0,d);%调⽤我们⾃⼰写的calculate_tsp_d函数计算当前路径的距离
path1 =gen_new_path(path0);%调⽤我们⾃⼰写的gen_new_path函数⽣成新的路径
result1 =calculate_tsp_d(path1,d);%计算新路径的距离
if result1 < result0 %如果新路径的距离⼩于当前路径的距离皮黔生
path0 = path1;%更新当前路径为新路径
iter_path =[iter_path; path1];%将新到的path1添加到中间结果中
iter_result =[iter_result; result1];%将新到的result1添加到中间结果中
else
p =exp(-(result1 - result0)/T);%根据Metropolis准则计算⼀个概率
if rand(1)< p %⽣成⼀个随机数和这个概率⽐较，如果该随机数⼩于这个概率
path0 = path1;%更新当前路径为新路径
end
end
end
T = alfa*T;%温度下降
end
[best_result, ind]=min(iter_result);%到最⼩的距离的值，以及其在向量中的下标
min_path =iter_path(ind,:);%根据下标到此时路径
disp('最佳的⽅案是：');disp(min_path)
disp('此时最优值是：');disp(best_result)
min_path =[min_path,min_path(1)];%在最短路径的最后⾯加上⼀个元素，即第⼀个点（我们要⽣成⼀个封闭的图形）n = n+1;%城市的个数加⼀个（紧随着上⼀步）
for i =1:n-1
j = i+1;
coord_i =coord(min_path(i),:); x_i =coord_i(1); y_i =coord_i(2);
coord_j =coord(min_path(j),:); x_j =coord_j(1); y_j =coord_j(2);
pm0.5plot([x_i,x_j],[y_i,y_j],'-')%每两个点就作出⼀条线段，直到所有的城市都⾛完
pause(0.2)%暂停0.02s再画下⼀条线段
hold on
end
新解⽣成函数：gen_new_path.m
function path1 =gen_new_path(path0)
% path0：原来的路径
n =length(path0);
%随机选择两种产⽣新路径的⽅法
p1 =0.33;%使⽤交换法产⽣新路径的概率
p2 =0.33;%使⽤移位法产⽣新路径的概率
r =rand(1);%随机⽣成⼀个[01]间均匀分布的随机数
if r< p1 %使⽤交换法产⽣新路径
c1 =randi(n);%⽣成1-n中的⼀个随机整数
c2 =randi(n);%⽣成1-n中的⼀个随机整数
path1 = path0;%将path0的值赋给path1帝京景物略
path1(c1)=path0(c2);%改变path1第c1个位置的元素为path0第c2个位置的元素
path1(c2)=path0(c1);%改变path1第c2个位置的元素为path0第c1个位置的元素
elseif r < p1+p2 %使⽤移位法产⽣新路径
c1 =randi(n);%⽣成1-n中的⼀个随机整数
c2 =randi(n);%⽣成1-n中的⼀个随机整数
c3 =randi(n);%⽣成1-n中的⼀个随机整数
sort_c =sort([c1 c2 c3]);%对c1 c2 c3从⼩到⼤排序
c1 =sort_c(1); c2 =sort_c(2); c3 =sort_c(3);% c1 <= c2 <= c3
tem1 =path0(1:c1-1);
tem2 =path0(c1:c2);公民社会理论
tem3 =path0(c2+1:c3);
tem4 =path0(c3+1:end);
path1 =[tem1 tem3 tem2 tem4];
else%使⽤倒置法产⽣新路径
c1 =randi(n);%⽣成1-n中的⼀个随机整数
c2 =randi(n);%⽣成1-n中的⼀个随机整数
if c1>c2 %如果c1⽐c2⼤，就交换c1和c2的值
tem = c2;
c2 = c1;
c1 = tem;
end
tem1 =path0(1:c1-1);
tem2 =path0(c1:c2);
tem3 =path0(c2+1:end);
path1 =[tem1 fliplr(tem2) tem3];%矩阵的左右对称翻转 fliplr，上下对称翻转 flipud
end
动力学模型
end
⽬标函数：calculate_tsp_d.m
function result =calculate_tsp_d(path,d)
%输⼊：path：路径（1⾄n的⼀个序列），d：距离矩阵
n =length(path);
result =0;%初始化该路径⾛的距离为0
for i =1:n-1
result =d(path(i),path(i+1))+ result;%按照这个序列不断的更新⾛过的路程这个值
end
result =d(path(1),path(n))+ result;%别忘了加上从最后⼀个城市返回到最开始那个城市的距离end
促销策略分析程序结果
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议