1 简介

SA( Simulated annea ling)算法是一种求解组合优化问 题的随机搜索方法。它在最优解搜索策略中引入了适当的 随机因素 ,对目标函数一般不需要特殊的限制条件 ,具有 比较广泛的适应性。它是一种通用的算法 ,目前已在工程、 经济等领域得到了广泛的应用 ,诸如生产调度、控制工程、机器学习、神经网络、图像处理等领域。虽然由于采用随机搜索策略 , SA算法只能在概率的 意义上为求得全局最优解提供保证 ,但是可以证明 , SA算法最终能以概率为 1收敛于全局最优解。下面先介绍 SA算法的主要内容。 归纳而言 , SA算法是一种基于 Monte Carlo迭代求解策略的随机搜索算法 ,其出发点是基于物质的物理退火 过程与组合优化之间的相似性 ,算法由某一较高的初始温 度开始 ,利用具有概率突变特性的 Metropolis抽样策略在 解空间中进行随机搜索 ,伴随温度的不断下降 ,反复进行 该抽样过程 ,最终以概率 1收敛于全局最优解。​SA算法的 实验性具有质量高、初始解鲁棒性强、通用性好以及算法 易实现等优点。

2 部分代码

%% 基于模拟退火算法位置规划问题 clc clear tic %% 数据导入与初始化 %% 用户集群点、选址个数导入及创建 uc.look = importdata('.\eil51.txt'); uc.index = 1:length(uc.look); uc.count=8; % 选址个数 uc.xy=[uc.look(:,2) uc.look(:,3)]; % 用户集群点坐标 %% 计算用户集群之间的距离 uc.num=size(uc.xy,1); uc.dist=zeros(uc.num,uc.num); for i=1:uc.num for j=1:uc.num if i~=j uc.dist(i,j)=((uc.xy(i,1)-uc.xy(j,1)).^2+... (uc.xy(i,2)-uc.xy(j,2)).^2).^0.5; end uc.dist(i,j)=uc.dist(i,j); end end % 模拟退火算法参数初始化 maxOuterIter = 2000; % 外层迭代次数 maxInnerIter = 900; % 内层迭代次数（马尔科夫链长度） T0 = 1000; % 初始温度 alpha = 0.99; % 温度衰减系数 T = T0; % 温度 %% 多目标归一化处理 参数 w1=0.5; w2=0.5; %% 初始解构建 [allocate]=createInitSolution(uc); [totaldist]=distFunc(allocate,uc); [d]=saved(allocate,uc); [dmax]=maxnian(d,uc); [dmean]=meanmax(d,uc); [fit]=intiger(totaldist,dmax,w1,w2); bestAllocate=allocate; bestdist=totaldist; Bestdist=zeros(maxOuterIter,1); bestdmax=dmax; Bestdmax=zeros(maxOuterIter,1); bestd=d; bestfit=fit; Bestdfit=zeros(maxOuterIter,1); %% 模拟退火 for outIter=1:maxOuterIter for inIter=1:maxInnerIter % 新解和原来的解进行比较 [newAllocate]=createNeighborSolution(uc,allocate); [newTotaldist]=distFunc(newAllocate,uc); [newd]=saved(newAllocate,uc); [newdmax]=maxnian(newd,uc); [newdmean]=meanmax(newd,uc); [newfit]=intiger(newTotaldist,newdmax,w1,w2); if newfit<=fit allocate=newAllocate; fit=newfit; dmax=newdmax; totaldist=newTotaldist; d=newd; else delta=(newfit-fit)/fit; P=exp(-delta/T); if rand <= P allocate=newAllocate; fit=newfit; dmax=newdmax; totaldist=newTotaldist; d=newd; end end if fit<=bestfit bestAllocate=allocate; bestfit=fit; bestdmax=dmax; bestdist=totaldist; bestd=d; end end % 如果新解比当前解更好，则更新当前解，以及当前解的总距离 %if newTotaldist <= totaldist % allocate=newAllocate; % totaldist=newTotaldist; %else % 以一定的概率接受非优解 % delta=(newTotaldist-totaldist)/totaldist; % P=exp(-delta/T); % if rand <= P % allocate=newAllocate; % totaldist=newTotaldist; % end %end % 更新全局最优解，以及全局最优解总距离 %if totaldist<=bestdist % bestAllocate=allocate; % bestdist=totaldist; % end %% bestAllocate % 记录每次迭代的最优解 Bestdist(outIter)=bestdist; % 全局最优解 %disp(['第',num2str(outIter),'代全局最优解: ',num2str(bestdist)]) % 降温操作 %T=alpha*T; Bestfit(outIter)=bestfit; disp(['第',num2str(outIter),'代全局最优解: ',num2str(bestfit)]) %Bestdmax(outIter)=bestdmax; T=alpha*T; end %% draw(uc,bestAllocate,Bestfit) %% toc

3 仿真结果

4 参考文献

[1]辛星. "基于模拟退火法的桥梁监测传感优化布置的MATLAB实现方法." 江西建材 11(2016):2.