该算法是⼀种新的随机搜索⽅法，它是近年来提出的⼀种适合于解决⼤规模组合优化问题的通⽤⽽有效的近似算法。与以往的近似算法相⽐，模拟退⽕算法具有描述简单、使⽤灵活、运⽤⼴泛、运⾏效率⾼和较少受到初始条件约束等优点
模拟退⽕算法来源于固体退⽕原理，将固体加温⾄充分⾼，再让其徐徐冷却，加温时，固体内部粒⼦随温升变为⽆序状，内能增⼤，⽽徐徐冷却时粒⼦渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最⼩。根据Metropolis准则，粒⼦在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。⽤固体退⽕模拟组合优化问题，将内能E模拟为⽬标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退⽕算法：由初始解i和控制参数初值t开始，对当前解重复“产⽣新解→计算⽬标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终⽌时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的⼀种启发式随机搜索过程。退⽕过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因⼦Δt、每个t值时的迭代次数L和停⽌条件S。 3.5.1 模拟退⽕算法的模型
考德威尔模拟退⽕算法可以分解为解空间、⽬标函数和初始解三部分。
河南坠子偷石榴
模拟退⽕的基本思想:
(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步。
净然法师
算法对应动态演⽰图：
模拟退⽕算法新解的产⽣和接受可分为如下四个步骤：
第⼀步是由⼀个产⽣函数从当前解产⽣⼀个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产⽣新解的⽅法，如对构成新解的全部或部分元素进⾏置换、互换等，注意到产⽣新解的变换⽅法决定了当前新解的邻域结构，因⽽对冷却进度表的选取有⼀定的影响。
有毒胶囊第⼆步是计算与新解所对应的⽬标函数差。因为⽬标函数差仅由变换部分产⽣，所以⽬标函数差的计算最好按增量计算。事实表明，对⼤多数应⽤⽽⾔，这是计算⽬标函数差的最快⽅法。
第三步是判断新解是否被接受，判断的依据是⼀
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议