模拟退火算法及其Matlab 实现
模拟退火算法（Simulated Annealing algorithm ，简称SA ）是柯克帕垂克（S. Kirkpatrick ）于1982年受热力学中的固体退火过程与组合优化问题求解之间的某种“相似性”所启发而提出的，用于求解大规模组合优化问题的一种具有全局搜索功能的随机性近似算法。与求解线性规划的单纯形法、Karmarkar 投影尺度法，求解非线性规划的最速下降法、Newton 法、共轭梯度法，求解整数规划的分支定界法、割平面法等经典的优化算法相比，模拟退火算法在很大程度上不受制于优化问题的具体形式和结构，具有很强的适应性和鲁棒性，因而也具有广泛的应用价值。
模拟退火算法源于对固体退火过程的模拟；采用Metropolis 接受准则；并用一组称为冷却进度表的参数来控制算法进程，使得算法在多项式时间里给出一个近似最优解。固体退火过程的物理现象和统计性质是模拟退火算法的物理背景；Metropolis 接受准则使算法能够跳离局部最优的“陷阱”，是模拟退火算法能够获得整体最优解的关键；而冷却进度表的合理选择是算法应用的关键。
1 物理退火过程
物理中的固体退火是先将固体加热至熔化，再徐徐冷却，使之凝固成规整晶体的热力学过程。在加热固体时，固体粒子的热运动不断增加，随着温度的升高，粒子与其平衡位置的偏离越来越大，当温度升至溶解温度后，固体的规则性被彻底破坏，固体溶解为液体，粒子排列从较有序的结晶态转变为无序的液态，这个过程称为溶解。溶解过程的目的是消除系统中原先可能存在的非均匀状态，使随后进行的冷却过程以某一平衡态为始点。溶解过程与系统的熵增过程相联系，系统能量也随温度的升高而增大。
冷却时，液体粒子的热运动渐渐减弱，随着温度的徐徐降低，粒子运动渐趋有序。当温度降至结晶温度后，粒子运动变为围绕晶体格点的微小振动，液体凝固成固体的晶态，这个过程称为退火。退火过程之所以必须“徐徐”进行，是为了使系统在每一温度下都达到平衡态，最终达到固体的基态（图1-1）。退火过程中系统的熵值（衡量不能利用的热能数量）不断减少，系统能量也随温度降低趋于最小值。冷却时，若急剧降低温度，则将引起淬火效应，即固体只能冷凝为非均匀的亚稳态，系统能量也不会达到最小值。
退火过程中系统在每一温度下达到平衡态的过程，可以用封闭系统的等温过程来描述。根据玻尔兹曼（Boltzmann ）有序性原理，退火过程遵循应用于热平衡封闭系统的热力学定律——自由能减少定律：
“对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡态”。
系统的自由能F E TS =-，其中E 是系统的内能，T 是系统温度，S 是系统的熵。设 i 和j 是恒温系统的两个状态，即i i i F E TS =-和j j j F E TS =-，而
()()j i j i j i F F F E E T S S E T S ?=-=---=?-?
若系统状态由i 自发变化到j ，则应有0F ?<。显然，能量减少（0E ?<）与熵增加
（0S ?>）有利于自发变化。因此任一恒定温度下，系统状态从非平衡自发变化到平衡态，都是能量和熵竞争的结果，温度决定着这两个因素的相对权重。在高温下，熵占统治地位，有利于变化的方向就是熵增加的方向，因而显出粒子的无序状态，而低温对应于低熵，低温下能量占优势，能量减少的方向有利于自发变化，因而得到有序（低熵）和低能的晶体结构。 2 Metropolis 算法
固体在恒定温度下达到热平衡的过程可以蒙特卡罗（Monte Carlo ）方法进行模拟。Monte Carlo 方法的特点是算法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。
从物理系统倾向于能量较低的状态，而热运动又妨碍它准确落入最低态的物理图像出发，采样时着重取那些有重要贡献的状态，则可以较快地得到较好的结果。
1953年，Metropolis 等提出了固体在恒定温度下达到热平衡的重要性采样法。他们用下述方法产生固体的状态序列：
先给定以粒子相对位置表征的初始状态i ，作为固体的当前状态，该状态的能量是i E 。然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新状态j ，新状态的能量是j E 。如果j i E E <，则该新状态就作为“重要”状态。如果j i E E >，则考虑到热运动的影响，该新状态是否是“重要”状态，要根据固体处于该状态的概率来判断。固体处于状态j 和状态i 的概率的比值等于相应Boltzmann 因子1的比值，即
exp()i j
E E r kT -= (1.1)
则1r <。用随机数发生器产生区间[0,1)上服从均匀分布的随机数ξ，若r ξ>，则新状态j 作为重要状态，并以j 取代i 成为当前状态；否则舍去状态j ，仍以i 为当前状态。
重复以上新状态的产生过程。在大量迁移（固体状态的变换称为迁移）后，系统趋于能量较低的平衡状态，固体状态的概率分布趋于(1.1)式的Gibbs 正则分布。
由(1.1)式可知，高温下可接受与当前状态能差较大的新状态为重要状态，而在低温下只 能接受与当前状态能差较小的新状态为重要状态。这与不同温度下热运动的影响完全一致，在温度趋于零时，就不能接受任何成立j i E E >时的新状态j 了。上述接受新状态的准则称为Metropolis 准则，相应的算法被称为Metropolis 算法。
.3 模拟退火算法
对固体退火过程的研究给人们以新的启示。1982年，Kirkpatrick 等首先意识到固体退火过程与组合优化问题之间存在的类似性，Metropolis 等对固体在恒定温度下达到热平衡过程的模拟也给他们以启迪：应该把 Metropolis 准则引入到优化过程中来。最终他们得
1由统计物理的知识，温度为T 的固体处于能量为E i 的微观态i 的概率为()exp i C E kT -，其中()
exp i E -称为玻尔兹曼（Boltzmann ）因子,k 为Boltzmann 常数，T 为绝对温度，C 是与E i 无关的常数，上述概率分布也称为吉布斯（Gibbs ）正则分布。容易知道，当固体处于能量较低的微观态的概率较大；在温度降低时，那些能量相比最低的微观态最有可能出现；当温度趋于零时，固体只能处于能量为最小值的基态上。
到一种对Metropolis 算法进行迭代的组合优化算法，因这种算法模拟固体退火过程，故称之为“模拟退火算法”。
在模拟退火算法中，设优化问题的控制参数为t 时的一个解t i x 及其非负目标函数()t i f x 分别与固体的在某一温度下的一个微观状态i 及其能量i E 等价，设随着算法进程递减其值的控制参数t 相当固体退火过程中的温度的角色，则对于控制参数t 的每一取值，算法持续进行“产生新解—判断—接受/舍弃”的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程，也就是执行了一次Metropolis 算法。与Metropolis 算法从某一初始状态出发，通过计算系统的时间演化过程，求出系统最终达到的状态相似，模拟退火算法从某个初始解出
发，经过大量解的变换后，可以求得给定控制参数值t 时组合优化问题的相对最优解t opt x 。
然后减少控制参数t 的值，重复执行Metropolis 算法，就可以在控制参数t 趋于零时，最终求得组合优化问题的整体最优解。由于固体退火必须“徐徐”降温，才能使固体在每一温度下都达到热平衡，最终趋于能量最小的基态，控制参数的值也必须缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集。
模拟退火算法用Metropolis 算法产生组合优化问题解的序列，并由与Metropolis 准则对应的转移概率P ：
1,()()()()()exp(),()()
t t j i t t
t t
t i j i j t t j i f x f x P x x f x f x f x f x t ??≤?=?->?? (1.2) 确定是否接受从当前解t i x 到新解t
j x 的转移。式(1.2)中的t R +∈表示控制参数。开始让t 取
较大的值(与固体的熔解温度相对应)，在进行足够多的转移后，缓慢减少t 的值(与“徐徐”降温相对应)，如此重复，直至满足某个停止准则是算法终止。因此，模拟退火算法可视为递减控制参数值时Metropolis 算法的迭代。图1.1和图1.2描述了固体退火过程与模拟退火算法之间的相似性。
设1()k k t T t -=表示Metropolis 算法第k 次迭代时控制参数t 的值，()T t 表示控制参数更新函数，f t 表示终止温度。k L 表示Metropolis 算法第k 次迭代时产生的变换个数。下面最小化目标函数()f x 为例，给出模拟退火算法的具体操作步骤：
图1-1 固体退火过程示意图 图1-2 模拟退火算法流程示意图
(1) 设置初始温度0t 、终止温度f t 及控制参数更新函数()T t ；
(2) 随机产生初始解0x ，以此作为当前最优点0opt x x =，计算目标函数值()opt f x ；
(3) 对当前最优点作一随机变动，产生一新解k x ，计算新解的目标函数值()f x ，并计算目标函数值增量()()opt f f x f x ?=-；
(4) 若0?<，则接受该新解为当前最优点,opt x x =；若0?≥，则以概率p 的方式接受该新解为当前最优点；
(5) 若k k L <，则1k k ←+，转(4)；
()1k k t T t -=。设置k L ，令循环计数器初值0k =；
(6) 若f t T ≥，则转(3)；
若f t T <，则输出当前最优点，算法结束。
模拟退火算法依据Metropolis 准则接受新解，因此除接受优化解外，还在一个限定范围内接受恶化解，这正是模拟退火算法与其他局部搜索算法的本质区别所在。开始时t 值大，可能接受较差的恶化解；随着t 值的减少，只能接受较好的恶化解；最后在t 值趋于零时，就不再接受任何恶化解了。这就使模拟退火算法既可以从局部最优的“陷阱”中跳出，更有可能求得组合优化问题的整体最优解，又不失简单性和通用性。
实验用例： 用模拟退火算法解决如下10个城市的TSP 问题，该问题最优解为691.2 opt f 。 表1 10个城市的坐标 城市 X 坐标 Y 坐标 城市 X 坐标 Y 坐标 3 0.4000 0.4439 8 0.8732 0.6536 编程实现 用MATLAB 实现模拟退火算法时，共编制了5个m 文件，分别如下 1、swap.m function [ newpath , position ] = swap( oldpath , number ) % 对 oldpath 进 行 互 换 操 作 % number 为 产 生 的 新 路 径 的 个 数 % position 为 对 应 newpath 互 换 的 位 置 m = length( oldpath ) ; % 城 市 的 个 数 newpath = zeros( number , m ) ; position = sort( randi( m , number , 2 ) , 2 ); % 随 机 产 生 交 换 的 位 置 for i = 1 : number newpath( i , : ) = oldpath ; % 交 换 路 径 中 选 中 的 城 市 newpath( i , position( i , 1 ) ) = oldpath( position( i , 2 ) ) ; newpath( i , position( i , 2 ) ) = oldpath( position( i , 1 ) ) ; end 2、pathfare.m function [ objval ] = pathfare( fare , path ) % 计 算 路 径 path 的 代 价 objval % path 为 1 到 n 的 排 列 ，代 表 城 市 的 访 问 顺 序 ； % fare 为 代 价 矩 阵 ， 且 为 方 阵 。 [ m , n ] = size( path ) ; objval = zeros( 1 , m ) ; for i = 1 : m for j = 2 : n objval( i ) = objval( i ) + fare( path( i , j - 1 ) , path( i , j ) ) ; end objval( i ) = objval( i ) + fare( path( i , n ) , path( i , 1 ) ) ; end
MCM战备历程3（模拟退火算法Matlab源程序）For glory 2007-02-03 11:20:04| 分类：数学建模 | 标签：学习|字号订阅 %模拟退火算法程序 T_max=input('please input the start temprature'); T_min=input('please input the end temprature'); iter_max=input('please input the most interp steps on the fit temp'); s_max=input('please input the most steady steps ont the fit temp'); T=T_max; load d:\address.txt; order1=randperm(size(address,1))';%生成初始解。 plot(address(order1,1),address(order1,2),'*r-') totaldis1=distance(address,order1); while T>=T_min iter_num=1; s_num=1; plot(T,totaldis1) hold on while iter_num
模拟退火算法模拟退火算法是一种通用的随机搜索算法，是局部搜索算法的扩展。它的思想是再1953 年由metropolis 提出来的，到1983 年由kirkpatrick 等人成功地应用在组合优化问题中。 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis 准则，粒子在温度T 时趋于平衡的概率为e- △ E/(kT)，其中E为温度T时的内能，AE为其改变量，k 为Boltzmann 常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f ,温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解-计算目标函数差T接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooli ng Schedule)控制，包括控制参数的初值t 及其衰减因子△ t、每个t值时的迭代次数L和停止条件S。 模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则：若厶t‘ <0 则接受S'作为新的当前解S,否则以概率exp(- △ t‘ /T) 接受S'作为新的当前解S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。 可在此基础上开始下一轮试验。而当新解被判定为舍弃时，
Matlab数理统计工具箱应用简介 1．概述 Matlab的数理统计工具箱是Matlab工具箱中较为简单的一个，其牵扯的数学知识是大家都很熟悉的数理统计，因此在本文中，我们将不再对数理统计的知识进行重复，仅仅列出数理统计工具箱的一些函数，这些函数的意义都很明确，使用也很简单，为了进一步简明，本文也仅仅给出了函数的名称，没有列出函数的参数以及使用方法，大家只需简单的在Matlab工作空间中输入“help 函数名”，便可以得到这些函数详细的使用方法。 2．参数估计 betafit 区间 3．累积分布函数 betacdf β累积分布函数 binocdf 二项累积分布函数 cdf 计算选定的累积分布函数 chi2cdf 累积分布函数2χ expcdf 指数累积分布函数 fcdf F累积分布函数 gamcdf γ累积分布函数 geocdf 几何累积分布函数 hygecdf 超几何累积分布函数 logncdf 对数正态累积分布函数 nbincdf 负二项累积分布函数 ncfcdf 偏F累积分布函数 nctcdf 偏t累积分布函数 ncx2cdf 偏累积分布函数2χ normcdf 正态累积分布函数 poisscdf 泊松累积分布函数 raylcdf Reyleigh累积分布函数 tcdf t 累积分布函数 unidcdf 离散均匀分布累积分布函数 unifcdf 连续均匀分布累积分布函数 weibcdf Weibull累积分布函数 4．概率密度函数 betapdf β概率密度函数 binopdf 二项概率密度函数 chi2pdf 概率密度函数2χ
exppdf 指数概率密度函数 fpdf F概率密度函数 gampdf γ概率密度函数 geopdf 几何概率密度函数 hygepdf 超几何概率密度函数 lognpdf 对数正态概率密度函数 nbinpdf 负二项概率密度函数 ncfpdf 偏F概率密度函数 nctpdf 偏t概率密度函数 ncx2pdf 偏概率密度函数2χ normpdf 正态分布概率密度函数 pdf 指定分布的概率密度函数 poisspdf 泊松分布的概率密度函数 raylpdf Rayleigh概率密度函数 tpdf t概率密度函数 unidpdf 离散均匀分布概率密度函数unifpdf 连续均匀分布概率密度函数weibpdf Weibull概率密度函数5．逆累积分布函数 Betainv 逆β累积分布函数 binoinv 逆二项累积分布函数 chi2inv 逆累积分布函数2χ expinv 逆指数累积分布函数 finv 逆F累积分布函数 gaminv 逆γ累积分布函数 geoinv 逆几何累积分布函数 hygeinv 逆超几何累积分布函数 logninv 逆对数正态累积分布函数 nbininv 逆负二项累积分布函数 ncfinv 逆偏F累积分布函数 nctinv 逆偏t累积分布函数 ncx2inv 逆偏累积分布函数2χ norminv 逆正态累积分布函数 possinv 逆正态累积分布函数 raylinv 逆Rayleigh累积分布函数 tinv 逆t累积分布函数 unidinv 逆离散均匀累积分布函数 unifinv 逆连续均匀累积分布函数 weibinv 逆Weibull累积分布函数
/* * 使用模拟退火算法(SA)求解TSP问题(以中国TSP问题为例) * 参考自《Matlab 智能算法30个案例分析》 * 模拟退火的原理这里略去，可以参考上书或者相关论文 * update: 16/12/11 * author:lyrichu * email:919987476@https://www.doczj.com/doc/966421151.html, */ #include
模拟退火算法 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 模拟退火算法的模型 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想: (1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起 点)，每个T值的迭代次数L (2) 对k=1，……，L做第(3)至第6步： (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 (5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)
接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。 (7) T逐渐减少，且T->0，然后转第2步。 算法对应动态演示图： 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则
表Ⅰ-11 线性模型函数 函数描述 anova1 单因子方差分析 anova2 双因子方差分析 anovan 多因子方差分析 aoctool 协方差分析交互工具 dummyvar 拟变量编码 friedman Friedman检验 glmfit 一般线性模型拟合 kruskalwallis Kruskalwallis检验 leverage 中心化杠杆值 lscov 已知协方差矩阵的最小二乘估计manova1 单因素多元方差分析manovacluster 多元聚类并用冰柱图表示multcompare 多元比较 多项式评价及误差区间估计 polyfit 最小二乘多项式拟合 polyval 多项式函数的预测值 polyconf 残差个案次序图 regress 多元线性回归 regstats 回归统计量诊断 续表 函数描述 Ridge 岭回归 rstool 多维响应面可视化 robustfit 稳健回归模型拟合 stepwise 逐步回归 x2fx 用于设计矩阵的因子设置矩阵 表Ⅰ-12 非线性回归函数 函数描述 nlinfit 非线性最小二乘数据拟合（牛顿法）nlintool 非线性模型拟合的交互式图形工具nlparci 参数的置信区间 nlpredci 预测值的置信区间 nnls 非负最小二乘 表Ⅰ-13 试验设计函数 函数描述 cordexch D-优化设计（列交换算法）daugment 递增D-优化设计 dcovary 固定协方差的D-优化设计ff2n 二水平完全析因设计 fracfact 二水平部分析因设计 fullfact 混合水平的完全析因设计hadamard Hadamard矩阵（正交数组）rowexch D-优化设计（行交换算法） 表Ⅰ-14 主成分分析函数 函数描述 barttest Barttest检验 pcacov 源于协方差矩阵的主成分pcares 源于主成分的方差 princomp 根据原始数据进行主成分分析 表Ⅰ-15 多元统计函数 函数描述 classify 聚类分析 mahal 马氏距离 manova1 单因素多元方差分析manovacluster 多元聚类分析 表Ⅰ-16 假设检验函数 函数描述 ranksum 秩和检验 signrank 符号秩检验 signtest 符号检验 ttest 单样本t检验 ttest2 双样本t检验 ztest z检验 表Ⅰ-17 分布检验函数 函数描述 jbtest 正态性的Jarque-Bera检验kstest 单样本Kolmogorov-Smirnov检验kstest2 双样本Kolmogorov-Smirnov检验lillietest 正态性的Lilliefors检验 表Ⅰ-18 非参数函数 函数描述 friedman Friedman检验 kruskalwallis Kruskalwallis检验ranksum 秩和检验 signrank 符号秩检验 signtest 符号检验
模拟退火算法及其Matlab 实现 模拟退火算法(Simulated Annealing algorithm ,简称SA )是柯克帕垂克(S. Kirkpatrick )于1982年受热力学中的固体退火过程与组合优化问题求解之间的某种“相似性”所启发而提出的,用于求解大规模组合优化问题的一种具有全局搜索 功能的随机性近似算法。与求解线性规划的单纯形法、Karmarkar 投影尺度法,求 解非线性规划的最速下降法、Newton 法、共轭梯度法,求解整数规划的分支定界法、割平面法等经典的优化算法相比,模拟退火算法在很大程度上不受制于优化问 题的具体形式和结构,具有很强的适应性和鲁棒性,因而也具有广泛的应用价值。 模拟退火算法源于对固体退火过程的模拟;采用Metropolis 接受准则;并用 一组称为冷却进度表的参数来控制算法进程,使得算法在多项式时间里给出一个近 似最优解。固体退火过程的物理现象和统计性质是模拟退火算法的物理背 景;Metropolis 接受准则使算法能够跳离局部最优的“陷阱”,是模拟退火算法能 够获得整体最优解的关键;而冷却进度表的合理选择是算法应用的关键。 1 物理退火过程 物理中的固体退火是先将固体加热至熔化,再徐徐冷却,使之凝固成规整晶体 的热力学过程。在加热固体时,固体粒子的热运动不断增加,随着温度的升高,粒子 与其平衡位置的偏离越来越大,当温度升至溶解温度后,固体的规则性被彻底破坏, 固体溶解为液体,粒子排列从较有序的结晶态转变为无序的液态,这个过程称为溶解。溶解过程的目的是消除系统中原先可能存在的非均匀状态,使随后进行的冷却 过程以某一平衡态为始点。溶解过程与系统的熵增过程相联系,系统能量也随温度 的升高而增大。 冷却时,液体粒子的热运动渐渐减弱,随着温度的徐徐降低,粒子运动渐趋有 序。当温度降至结晶温度后,粒子运动变为围绕晶体格点的微小振动,液体凝固成固体的晶态,这个过程称为退火。退火过程之所以必须“徐徐”进行,是为了使系统在每一温度下都达到平衡态,最终达到固体的基态(图1-1)。退火过程中系统的熵值
%%% 模拟退火算法源程序 % 此题以中国31省会城市的最短旅行路径为例： % clear;clc; function [MinD,BestPath]=MainAneal(pn) % CityPosition存储的为每个城市的二维坐标x和y； CityPosition=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;... 4196 1044;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;... 1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;... 4263 2931;3429 1908;3507 2376;3394 2643;3439 3201;2935 3240;3140 3550;... 2545 2357;2778 2826;2370 2975]; figure(1); plot(CityPosition(:,1),CityPosition(:,2),'o') m=size(CityPosition,1);%城市的数目 % D = sqrt((CityPosition(:,ones(1,m)) - CityPosition(:,ones(1,m))').^2 + ... (CityPosition(:,2*ones(1,m)) - CityPosition(:,2*ones(1,m))').^2); path=zeros(pn,m); for i=1:pn path(i,:)=randperm(m); end iter_max=100;%i m_max=5;% Len1=zeros(1,pn);Len2=zeros(1,pn);path2=zeros(pn,m); t=zeros(1,pn); T=1e5; tau=1e-5; N=1; while T>=tau iter_num=1; m_num=1; while m_num Matlab常用工具箱 MATLAB包括拥有数百个内部函数的主包和三十几种工具包.工具包又可以分为功能性工具包和学科工具包.功能工具包用来扩充MATLAB的符号计算,可视化建模仿真,文字处理及实时控制等功能.学科工具包是专业性比较强的工具包,控制工具包,信号处理工具包,通信工具包等都属于此类. 开放性使MATLAB广受用户欢迎.除内部函数外,所有MATLAB主包文件和各种工具包都是可读可修改的文件,用户通过对源程序的修改或加入自己编写程序构造新的专用工具包. Matlab Main Toolbox——matlab主工具箱 Control System Toolbox——控制系统工具箱 Communication Toolbox——通讯工具箱 Financial Toolbox——财政金融工具箱 System Identification Toolbox——系统辨识工具箱 Fuzzy Logic Toolbox——模糊逻辑工具箱 Higher-Order Spectral Analysis Toolbox——高阶谱分析工具箱 Image Processing Toolbox——图象处理工具箱 LMI Control Toolbox——线性矩阵不等式工具箱 Model predictive Control Toolbox——模型预测控制工具箱 μ-Analysis and Synthesis Toolbox——μ分析工具箱 Neural Network Toolbox——神经网络工具箱 Optimization Toolbox——优化工具箱 Partial Differential Toolbox——偏微分方程工具箱 Robust Control Toolbox——鲁棒控制工具箱 Signal Processing Toolbox——信号处理工具箱 Spline Toolbox——样条工具箱 Statistics Toolbox——统计工具箱 Symbolic Math Toolbox——符号数学工具箱 Simulink Toolbox——动态仿真工具箱 Wavele Toolbox——小波工具箱 常用函数Matlab内部常数[3] eps：浮点相对精度 exp：自然对数的底数e i或j：基本虚数单位 inf或Inf：无限大, 例如1/0 nan或NaN：非数值（Not a number）,例如0/0 pi：圆周率p（= 3.1415926...） realmax：系统所能表示的最大数值 realmin：系统所能表示的最小数值 nargin: 函数的输入引数个数 nargout: 函数的输出引数个数 lasterr：存放最新的错误信息 lastwarn：存放最新的警告信息 MATLAB常用基本数学函数 abs(x)：纯量的绝对值或向量的长度 angle(z)：复数z的相角(Phase angle) 模拟退火算法 摘要：阐述了模拟退火算法的基本原理及实现过程,运用MATLAB语言实现了该算法。并将其运用到解决旅行商问题的优化之中。数值仿真的结果表明了该方法能够对函数进行全局寻优,有效克服了基于导数的优化算法容易陷入局部最优的问题。该方法既可以增加对MATLAB 语言的了解又可以加深对模拟退火过程的认识,并达到以此来设计智能系统的目的。 关键词：模拟退火算法，全局寻优，搜索策略 simulatedannealing algorithm Abstract：This paper describes the basic principles and processes simulatedannealing algorithm, using MATLAB language implementation of the algorithm. And use it to solve the traveling salesman problem among optimization. Simulation results show that the method can be a function of global optimization, effectively overcome the derivative-based optimization algorithm is easy to fall into local optimum. This method not only can increase the MATLAB language can deepen understanding and awareness of the simulated annealing process, and in order to achieve the purpose of the design of intelligent systems. Keywords:simulatedannealing algorithm,Global optimization,strategy function [f,T]=TSPSA(d,t0,tf) %TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度 [m,n]=size(d); L=100*n; t=t0; pi0=1:n; min_f=0; for k=1：n-1 min_f=min_f+d(pi0(k),pi0(k+1)); end min_f=min_f+d(pi0(n),pi0(1)); p_min=pi0; while t>tf for k=1:L; kk=rand; [d_f,pi_1]=exchange_2(pi0,d); r_r=rand; if d_f<0 pi0=pi_1; elseif exp(d_f/t)>r_r pi0=pi_1; else pi0=pi0; end end f_temp=0; for k=1：n-1 f_temp=f_temp+d(pi0(k),pi0(k+1)); end f_temp=f_temp+d(pi0(n),pi0(1)); if min_f>f_temp min_f=f_temp; p_min=pi0; end t=0.87*t; end f=min_f; T=p_min; %aiwa要调用的子程序,用于产生新解 function [d_f,pi_r]=exchange_2(pi0,d) [m,n]=size(d); clear m; u=rand; u=u*(n-2); u=round(u); if u<2 u=2; end if u>n-2 u=n-2; end v=rand; v=v*(n-u+1); v=round(v); if v<1 v=1; end v=u+v; if v>n v=n; end pi_1(u)=pi0(v); pi_1(v)=pi0(u); if u>1 for k=1：u-1 pi_1(k)=pi0(k); end end if v>(u+1) for k=1：v-u-1 pi_1(u+k)=pi0(v-k); end end if v Matlab 并行计算工具箱的使用 Matlab并行工具箱的产生一方面给大规模的数据分析带来了巨大的效益，另一方面且引入了分布式计算，借助matlab自身携带的MDCE，可以实现单机多核并行运行或者是同一个局域网络中的多台处理器组成的机群的并行运行。 个人以为后者是前者的拓展，并行计算的最初目的是为了解决串行计算速度不能满足某些复杂运算而产生的技术，能够借助较低配置的处理，协同工作处理同一个程序，但是他们之间是并不会交互的，仅仅是有核心主机—client进行大任务的分解，而后将它们分配给各个处理器，由处理器共同完成。所以说并行计算的实质还是主从结构的分布式计算。这里体现了数量的优势，同一个程序串行运行可能需要40个小时，但是若是由10台处理器同时跑，则有望将计算时间降低到接近4个小时的水平。而且这十台处理器可以是一个多个多核CPU组成，例如一个8核心CPU和1个2核心CPU。也可以是由5个2核心CPU组成，形式灵活。 而分布式计算在并行计算的基础上有功能上的扩展，一个很重要的方面就体现在，上述的十个处理器之间可以进行交互式通讯这是基于MPI(message passing interface)实现的，这对于大规模的分布式控制系统是很有需要的，也就是说，各个处理器之间要实现数据的实时传递，有时是共享某些信息，有时是lab1需要lab2的某些信息。相对于单纯的并行计算来说，后者将交互式通讯扩展到了labs之间，而不仅仅是lab和client之间。 Matlab 并行计算工具箱中的函数有： 1.Parfor (FOR循环的并行计算)； 函数1：matlabpool 其作用是开启matlab并行计算池，单独的命令会以默认的配置开启并行计算环境。 函数2：parfor For循环的并行计算替代关键词，需要注意的是，parfor不能像for一样嵌套。 但是外部的parfor内部可以嵌套for循环。 函数3：batch 用于在worker上运行matlab脚本或者是matlab函数。 例如：batch(‘script.m’) 语句会根据默认并行配置文件定义的集群将script脚本文件运行在worker上。 2.批处理 函数1：batch，其语法有： j = batch('aScript') j = batch(myCluster,'aScript') j = batch(fcn,N,{x1, ..., xn}) j = batch(myCluster,fcn,N,{x1,...,xn}) j = batch(...,'p1',v1,'p2',v2,...) 其中的变量： J The batch job object. 'aScript'The script of MATLAB code to be evaluated by the MATLAB pool job. myClusterCluster object representing cluster compute resources. fcnFunction handle or string of function name to be evaluated by the MATLAB pool job. 模拟退火算法 基于模拟退火算法的TSP问题求解具体步骤如下： 1）随机产生一个初始解path（作为当前最优路径），计算目标函数值pathfare(fare,path)=e0，并设置初始温度t0，内循环终止方差istd，外循环终止方差ostd降温系数lam，温度更新函数tk=lam*tk-1，并令k=1，输入各城市坐标coord，计算城市间的距离fare。 2）根据控制参数更新函数来控制温度的下降过程，给定最大循环步数iLK，设置循环计数器的初始值in=1。 3）对当前的最优路径作随机变动，产生一个新路径newpath，计算新路径的目标函数值pathfare(fare,newpath)=e1和目标函数值的增量e1-e04）根据Metropolis准则，如果增量（e1-e0）<0，则接受新产生的路径newpath作为当前最优路径；如果（e1-e0）>=0，则以公式（1）来决定新路径newpath是否代替path。rand()随机产生一个在[0,1]之间的随机数。exp[-(e1-e0)/t]>rand() 4）如果目标函数值小于istd，则直接跳出内循环。 5）如果in 1. distance.m function [fare]=distance(coord) %coord为各城市的坐标 %fare为城市间的距离矩阵 [~,m]=size(coord);%m为城市的个数 fare=zeros(m); for i=1:m%外层为行 for j=1:m%内层为列 fare(i,j)=(sum((coord(:,i)-coord(:,j)).^2))^0.5; fare(j,i)=fare(i,j);%距离矩阵对称 end end 2. myplot.m function []=myplot(path,coord,pathfar) %做出路径的图形 %path为要做图的路径,coord为各个城市的坐标 %pathfar为路径path对应的费用 len=length(path); clf; hold on; Matlab如何添加新的工具箱-经验总结 最近在学习遗传算法与免疫算法，所以涉及到matlab的工具箱的应用，尤其gads 工具箱，所以在网上下载了一些工具箱，但是不会用，在网上找了点资料，留着以后也可以用。 1，我是单独下载的工具箱，把新的工具箱拷贝到某个目录（我的是C:\Program Files\MATLAB\R2010\toolbox）。 注意：你要是添加的很多个m文件，那就把这些m文件直接拷到再下一层你想要的工具箱的文件夹里 例如，我要添加的是遗传工具箱，在刚才的文件夹下我已经有gads（遗传工具箱）文件夹了，但有的m文件还没有，我就把新的m文件统统拷到C:\Program Files\MATLAB\R2010\toolbox\gads目录下了 如果你连某工具箱（你打算添加的）的文件夹都没有，那就把文件夹和文件一起拷到C:\Program Files\MATLAB\R2010\toolbox下。 先把工具箱保存到MATLAB安装目录的根目录下面，然后运行 matlab---->file---->set path---->add folder 然后把你的工具箱文件夹添加进去就可以了 2 在matlab的菜单file下面的set path把它（C:\Program Files\MATLAB\R2010\toolbox\gads）加上。 3 把路径加进去后在file→Preferences→General的Toolbox Path Caching 里点击update Toolbox Path Cache更新一下。 记得一定要更新！我就是没更新，所以添加了路径，一运行还是不行。 后来更新了才行。 4 用which newtoolbox_command.m来检验是否可以访问。如果能够显示新设置的路径，则表明该工具箱可以使用了。 这个我也不知道怎么用。怎么检验？在命令窗口输入which newtoolbox_command.m？还是打开which newtoolbox_command.m文件（我搜索了，没找到这个文件啊）我一直没搞懂。 我的matlab小经验 我前几天刚刚接触matlab 由于要用MATLAB遗传算法工具箱编程，我直接在安装好的ｍａｔｌａｂ命令栏输入程序结果提示找不到函数后来我才了解到MATLAB自带的工具箱是GADS，在此环境下运行程序会出现函数未定义等问题， 基于matlab的模拟退火法 编写一个matlab的程序用模拟退火法求函数最优解 function [xo,fo] = Opt_Simu(f,x0,l,u,kmax,q,TolFun) % 模拟退火算法求函数f(x)的最小值点，且l <= x <= u % f为待求函数，x0为初值点，l，u分别为搜索区间的上下限，kmax为最大迭代次数 % q为退火因子，TolFun为函数容许误差 %%%%算法第一步根据输入变量数，将某些量设为缺省值 if nargin < 7 TolFun = 1e-8; end if nargin < 6 q = 1; end if nargin < 5 kmax = 100; end %%%%算法第二步，求解一些基本变量 N = length(x0); %自变量维数 x = x0; fx = feval(f,x); %函数在初始点x0处的函数值 xo = x; fo = fx; %%%%%算法第三步，进行迭代计算，找出近似全局最小点 for k =0:kmax Ti = (k/kmax)^q; mu = 10^(Ti*100); % 计算mu dx = Mu_Inv(2*rand(size(x))-1,mu).*(u - l);%步长dx x1 = x + dx; %下一个估计点 x1 = (x1 < l).*l +(l <= x1).*(x1 <= u).*x1 +(u < x1).*u; %将x1限定在区间[l,u]上 fx1 = feval(f,x1); df = fx1- fx; if df < 0||rand < exp(-Ti*df/(abs(fx) + eps)/TolFun) %如果fx1 % maxpop给定群体规模% pop群体 % newpop种群 %t0初始温度 function [codmin,finmin]=fc0(cc,v0,t0) N=length(cc(1,:)); %定群体规模 if N>50 maxpop=2*N-20; end if N<=40 maxpop=2*N; end %产生初始群体 pop=zeros(maxpop,N); pop(:,1)=v0; finmin=inf; codmin=0; for i=1:maxpop Ra=randperm(N); Ra(find(Ra==v0))=Ra(1); pop(i,:)=Ra; end t=t0; while t>0 %用模拟退火产生新的群体pop=fc1(maxpop,pop,N,cc,v0,t); %转轮赌选择种群 f=zeros(1,maxpop); for i=1:maxpop for j=1:N-1 x=pop(i,j); y=pop(i,j+1); fo1=cc(pop(i,j),pop(i,j+1)); f(i)=f(i)+fo1; end f(i)=f(i)+cc(pop(i,1),pop(i,N)); end fmin=min(f); for i=1:maxpop if fmin==inf&f(i)==inf end if fmin~=inf|f(i)~=inf dd=fmin-f(i); end ftk(i)=exp(dd/t); end [fin1,cod]=sort(-ftk); fin=abs(fin1); %f(cod(1)) if f(cod(1)) 说明：函数首字母皆为小写！ 1 线性代数 1.1 矩阵分析 Norm 矩阵或向量的范数Null 零空间 Normest 估计矩阵的2范数Orth 正交化 Rank 矩阵的秩Rref 简化矩阵为梯形形式 Det 矩阵行列式的值Subspace 两个子空间的夹角 1.2 线性方程 \和/ 线性方程求解Lu LU分解 Inv 矩阵的逆Ilu 不完全的LU分解Cond 矩阵条件数Luinc 不完全的LU分解Condest 1范条件数估计Qr QR分解 Lsqnonneg 非负线性最小二乘Chol Cholesky分解 Cholinc 不完全cholesky分解Pinv 伪逆 Linsolve 带特殊控制的线性方程求解Lscov 已知协方差的最小二乘1.3 特征值和奇异值 Eig 特征值和特征向量Polyeig 多项式特征值问题 Svd 奇异值分解Condeig 已知特征值求条件数 Eigs 稀疏矩阵的特征值Hess Hessenberg型 Svds 稀疏矩阵的奇异值和向量Qz 广义特征值的QZ分解 Poly 特征多项式Schur Schur分解 1.4 矩阵函数 Expm 矩阵指数Sqrtm 矩阵平方根 Logm 矩阵对数Funm 计算一般矩阵函数 2 曲线拟合工具箱函数 2.1 拟合数据预处理 Cftool 打开GUI形式的工具箱Smooth 对数据点做平滑处理 Excludedata 去除异常数据点 2.2 数据拟合 Cftool 打开GUI形式工具箱Fittype构造一个曲线拟合对象 Fit用指定的拟合模型对数据 进行拟合Get 获取拟合选项结构体的某个字段名及其值 Fitoptions 创建或修改拟合选项结构 体 Set 设置拟合选项某字段值2.3 拟合类型和方法 Argnames 曲线拟合类型（或函数）对 象的输入参量名Indepnames 曲线拟合类型（或函数）的 自变量 Category 曲线拟合类型（或函数）的 拟合类型Islinear 判断曲线拟合类型（或函数） 是否为线性 Coeffnames 曲线拟合类型（或函数）的 系数名称Numargs 曲线拟合类型（或函数）的 输入参数个数 Dependnames 曲线拟合类型（或函数）的 因变量Numcoeffs 曲线拟合类型（或函数）的 拟合系数个数 Feval 计算曲线拟合类型（或函 数）Probnames 曲线拟合类型（或函数）的 问题相关参数名称 Fittype创建一个曲线拟合类型（或 函数）Type 曲线拟合类型（或函数）的 名称 Formula 曲线拟合类型（或函数）的 公式 2.4 曲线拟合的方法（和2.3相同的没再写） Cfit 创建一个曲线拟合 函数对象 Confint 拟合系数的值的置信区间 Coeffvalues 通过拟合得到的拟 合函数的系数值Predint 在任意点处用拟合函数计算得到 的函数值的95%置信区间 Differentiate 求取拟合函数的导 数 Integrate 拟合函数的积分 Plot 绘制拟合曲线图Probvalues 拟合函数中的与问题相关的参数 值 还包括除去表2.3中fittype外所有函数，解释同上。 2.5 拟合数据后处理Matlab常用工具箱及常用函数
智能计算-模拟退火算法(matlab实现)
模拟退火算法求解TSP问题Matlab源码
Matlab-并行计算工具箱函数基本情况介绍
M模拟退火最短距离问题 Matlab代码 亲测完美运行
Matlab如何添加新的工具箱经验总结
基于matlab的模拟退火法
遗传模拟退火算法matlab通用源程序
matlab常用工具箱函数注释
相关主题
文本预览