MATLAB智能算法三十个案例分析_精品.doc

1、案例背景 模拟退火算法（Simulated Annealing，简称SA）的思想最早是由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成： （1）加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。 （2）等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行的，当自由能达到最小时，系统达到平衡状态。 （3）冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。 其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，我们要得到的最优解就是能量最低态。其中Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。 2、案例目录： 第19章 基于模拟退火算法的TSP算法 19.1理论基础 ??19.1.1 模拟退火算法基本原理 ??19.1.2 TSP问题介绍 19.2 案例背景 ??19.2.1 问题描述 ??19.2.2 解决思路及步骤 ? ? 算法流程 ? ? 模拟退火算法实现 ? ?? ?1. 控制参数的设置 ? ?? ?2. 初始解 ? ?? ?3. 解变换生成新解 ? ?? ?4. Metropolis 准则 ? ?? ?5. 降温 19.3 MATLAB程序实现 ??19.3.1 计算距离矩阵 ??19.3.2 初始解 ??19.3.3 生成新解 ??19.3.4 Metropolis准则函数 ??19.3.5 画路线轨迹图 ??19.3.6 输出路径函数 ??19.3.7 可行解路线长度函数 ??19.3.8 模拟退火算法主函数 ??19.3.9 结果分析 19.4 延伸阅读 ??19.4.1 模拟退火算法的改进 ??19.4.2 算法的局限性 19.5 参考文献 clc; clear; close all; %% tic T0=1000; % 初始温度 Tend=1e-3; % 终止温度 L=200; % 各温度下的迭代次数（链长） q=0.9; %降温速率 load CityPosition1; %加载数据 %% D=Distanse(X); %计算距离矩阵 N=size(D,1); %城市的个数 %% 初始解 S1=randperm(N); %随机产生一个初始路线 %% 画出随机解的路径图 DrawPath(S1,X) pause(0.0001) %% 输出随机解的路径和总距离 disp(初始种群中的一个随机值:) OutputPath(S1); Rlength=PathLength(D,S1); disp([总距离：,num2str(Rlength)]); %% 计算迭代的次数Time Time=ceil(double(solve([1000*(0.9)^x=,num2str(Tend)]))); count=0; %迭代计数 Obj=zeros(Time,1); %目标值矩阵初始化 track=zeros(Time,N); %每代的最优路线矩阵初始化 %% 迭代 while T0Tend count=count+1; %更新迭代次数 temp=zeros(L,N+1); for k=1:L %% 产生新解 S2=NewAnswer(S1); %% Metropolis法则判断是否接受新解 [S1,R]=Metropolis(S1,S2,D,T0); %Metropolis 抽样算法 temp(k,:)=[S1 R]; %记录下一路线的及其路程 end %% 记录每次迭代过程的最优路线 [d0,index]=min(temp(:,end)); %找出当前温度下最优路线 if count==1 || d0Obj(count-1) Obj(count)=d0; %如果当前温度下最优路程小于上一路程则记录当前路程 else Obj(count)=Obj(count-1);%如果当前温度下最优路程大于上一路程则记录上一路程 end track(count,:)=temp(index,1:end-1); %记录当前温度的最优路线 T0=q*T0; %降温 fprintf(1,%d\n,count) %输出当前迭代次数 end %% 优化过程迭代图 figure plot(1:count,Obj) xlabel(迭代次数) ylabel(距离) title(优化过程) %% 最优解的路径图 DrawPath(track(