当前位置: 美高梅棋牌 > 智能家电 > 正文

一.模拟退火算法概述 模拟退火算法来源于

时间:2019-10-03 06:34来源:智能家电
介绍模拟退火前,请先了解爬山算法。因为模拟退火算法是爬山算法的改进版,它在爬山算法的基础上引入了随机化。爬山算法是完完全全的贪心法,有可能只能搜索到局部的最优值。

介绍模拟退火前,请先了解爬山算法。因为模拟退火算法是爬山算法的改进版,它在爬山算法的基础上引入了随机化。爬山算法是完完全全的贪心法,有可能只能搜索到局部的最优值。模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。

一.模拟退火算法概述

模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。

模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropops准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Bptzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Coopng Schedpe)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

从描述上看退火能够使固体获得内能的最小值,这里用模拟退火算法来解决问题时,该算法通过模拟固体的退火过程,目的是期望获得问题的最小值作为最优解,如果期望获得是最大值,等价为将目标函数乘以-1后再求解最小值,得到的最小值乘以-1即为所求最大值。所以模拟退火算法和爬山算法一样都可以获得问题的最优解,而且求解问题的最大值或者最小值其实是等价的。

二.流程图

  1. 随机选择一个退火的状态作为起点S;
  2. 每次拿相邻点N与当前点S进行比对;
  3. 如果N<S,则取N作为退火的当前状态;
  4. 如果N>S,则以一定的概率P接受该状态;
  5. 重复第2、3步或者第2、4步,直至概率P随着时间推移逐渐降低,最后变为0;
  6. 重复第2、3步=0不可能进入第4步),直至该点的邻近点中不再有比其小的点;
  7. 选择该点作为退火的最终状态,认为其内能最小,作为该算法获得的最优解。

Java代码

概率P就是模拟退火算法的核心,其物理原理如下:根据热力学的原理,在温度为T时,出现能量差为dE的降温的概率为P,表示为:

//伪码描述:    
Simulated-Annealing()    
Create initial solution S    
repeat    
    for i=1 to iteration-length do    
        Generate a random transition from S to Si    
        If ( C(S) <= C(Si) ) then    
            S=Si    
        else if( exp(C(S)-C(Si))/kt > random[0,1) ) then    
            S=Si    
    Reduce Temperature t    
until ( no change in C(S) )    

C(S): Cost or Loss function of Solution S  

编辑:智能家电 本文来源:一.模拟退火算法概述 模拟退火算法来源于

关键词: