机器人最优路径模拟退火算法+源程序(3)
时间:2021-08-23 20:38 来源:毕业论文 作者:毕业论文 点击:次
|
模拟退火算法是通过赋予搜索过程一种随时间变化的且最终趋于零的概率突跳性，从而可以有效的避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。 3.3 模拟退火算法的原理 模拟退火算法来源于固体退火原理，具体是将固体加温至充分高，再让其慢慢冷却下来，加温时，固体内部的粒子随温度上升开始变为无序状，内能逐渐增大，而慢慢冷却时粒子逐渐趋于有序，在每个温度都将达到平衡状态，最后在常温状态下达到基态，内能减为最小。根据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.4模拟退火算法的基本思想来,自|优;尔`论^文/网www.youerw.com (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) 如果满足终止条件就输出当前解作为最优解，结束程序（终止条件通常情况下取为连续若干个新解都没有被接受，即终止算法）； (责任编辑：qin) |