⛄一、模拟退火算法简介
1 模拟退火算法的原理
模拟退火算法（SA）是一种适用于大规模组合优化问题的有效近似算法，来源于对固体退火过程的模拟。统计力学表明，在给定初始温度的条件下，通过将温度缓慢降低，微观粒子会在各个温度达到热平衡状态，当物体冷却到常温时达到基态，内能达到最小。模拟固体退火的过程，给定一个初始温度和初始解，随着温度的下降，每一个温度状态下，通过解的变换生成新的解。如果解的目标函数值小于前一个解，接受当前解；否则，以概率接受新解。最终的解是迭代寻优的结果。模拟退火算法以概率突跳性，能够跳出局部最优陷阱，找到全局最优解。模拟退火算法依据Metropolis接收准则接受新解，而不是使用完全确定的规则。它构成了模拟退火算法退火过程的基础。当固体从状态i经过降温变化到状态j，它所具有的能量从E(i）变化到E(j）。显然，如果E(j)<E(i），接受新的状态j。否则，依据概率P接受新解。
其中，K是物理学波尔兹曼常数，T是固体的温度。
这种概率，在路径规划的问题中，就是当新解的目标函数值小于原来的解的函数值，新解仍被接受的概率。以x表示温度T下的一个解，通过退火，可以生成一个新解x′。那么，接收x′的概率为：
2 模拟退火算法模型的建立
2.1 目标函数
首先，规定解空间。对销售点B,C,U重新进行编号（2,3，…，21),A点为产业园，既是起点也是终点，将它进行两次编号，记为1号和22号，以便于程序计算。问题转化为求解从1出发，走遍所有中间点，到达22的一个最短路径。本文通过运用百度拾取坐标系统，获得产业园和商铺点的经纬度信息。由于，本文选取的点的范围在徐州都市圈，两点之间的曲线距离可以近似看作直线距离。用k1和k2分别表示经度、纬度和千米的换算系数，将经纬度转换为千米。通过改进坐标距离公式计算距离：
计算得到皮草产业园和所有销售点中，任意两点间的距离，构成一个对称矩阵D=(dij)22×22。规定z1,z2，…，z22中，z2,z3，…z21，是由2～21随机打乱得到的一组数，则dzizi+1表示所有可能路径中，第i个和第i+1个经过的点间的距离。目标函数为运输经过所有目标的路径长度最小：
2.2 模拟退火算法实现过程
Step 1初始化
通过MATLAB随机模拟数给定初始路径，计算得到初始路径长度。设定初始温度T(0)=1。
Step 2产生新解
运用变换法，任选序号a,b(a<b），交换a和b之间的顺序，得到新的路径：
Step 3判定标准
新路径与原路径长度的差可以表示为：
当路径差Δf<0时，用新路径代替原路径。否则，以概率exp（-Δf/T）接受新的路径。
Step 4重复步骤2和步骤3，进行迭代。
Step 5结束条件
选用降温系数α，令T←αT，得到新的温度。当温度降至终止温度，算法结束，输出当前状态。
⛄二、部分源代码
clc;
clearvars;
close all;
%% Problem Definition
model=CreateModel(); % Select Model of the Problem
CostFunction=@(q) MyCost(q,model); % Cost Function
alpha1=0.15; %percent of destroy customers
%% SA Parameters
MaxIt=400; % Maximum Number of Iterations
T0=10; % Initial Temperature
alpha=0.2; % Temperature Damping Rate
tour=parallel_savings_init(model); % Create initail solution by CW Saving
tour(cellfun(@(routes) any(isnan(routes)),tour)) = [];
for i=1:numel(tour)
tour{i}=[1,tour{i},1];
end
x.tour=tour;
x.Cost=DisAllRoute(model,x.tour);
% Update Best Solution Ever Found
BestSol=x;
% Array to Hold Best Cost Values
BestCost=zeros(MaxIt,3);
T=T0;
tic;
%% SA Main Loop
for it=1:MaxIt
% Create Destroy[xnew.Ldestroy,xnew.list,m]=CreateDestroy(model,x.tour,alpha1);try[xnew.Lrepair,xnew.unrouted,n]=CreateRepair(model,xnew);catchbreakendxnew.Cost=DisAllRoute(model,xnew.Lrepair);if xnew.Cost<=x.Cost% xnew is better, so it is acceptedx=xnew;x.tour=xnew.Lrepair;if rand<=px=xnew;x.tour=xnew.Lrepair;endend% Update Best Solutionif x.Cost<=BestSol.CostBestSol=x;
end
%% Results
disp([’ Time = ’ num2str(toc)]);
disp([‘GAP LNS = ’ (num2str((min(BestCost(:,3))-model.Best)/model.Best*100)) ’ %’]);
figure(1);
plot(BestCost(:,3),‘LineWidth’,2);
xlabel(‘Iteration’);
ylabel(“Cost”);
figure(2);
PlotSolution(model,BestSol.tour);
⛄三、运行结果
⛄四、matlab版本及参考文献
1 matlab版本
a
2 参考文献
[1]王旭颖,杨金云,陈哲,倪秋铭,刘朱丹.基于模拟退火算法的电商物流配送问题研究[J].中国管理信息化. ,24(07)
3 备注
简介此部分摘自互联网，仅供参考，若侵权，联系删除
