电子商务网站名称和网址,毕业设计做网站用什么软件,琴行网站开发学术论文,电子商务网站建设与管理感想和收获模拟退火算法的MATLAB实现 模拟退火算法简介模拟退火算法应用实例关于计算结果 模拟退火算法简介
1982年#xff0c;Kirkpatrick 将退火思想引入组合优化领域#xff0c;提出了一种能够有效解决大规模组合优化问题的算法#xff0c;尤其对 NP 完全问题表现出显著优势。模拟… 模拟退火算法的MATLAB实现 模拟退火算法简介模拟退火算法应用实例关于计算结果 模拟退火算法简介
1982年Kirkpatrick 将退火思想引入组合优化领域提出了一种能够有效解决大规模组合优化问题的算法尤其对 NP 完全问题表现出显著优势。模拟退火算法的灵感源自固体退火过程即先将温度升至极高然后缓慢降温即退火使系统达到能量的最低点。相较于快速降温即淬火无法达到最低能量状态退火的缓慢降温过程更有助于系统找到全局最优解。
模拟退火算法是一种适用于求解最小化问题或更新学习过程随机或确定性的随机搜索算法。在该过程中每一步的更新长度与对应的参数成正比这些参数类似于物理过程中的温度。在优化开始时为了更快地实现最小化或学习温度被设置得很高随后逐渐降温以实现系统的稳定性。
这算法将物理系统的退火过程类比于优化问题的求解过程优化的目标函数对应于金属的内能优化问题的自变量组合状态空间对应于金属的内能状态空间求解过程即是在组合状态空间中寻找目标函数值最小的组合状态。
根据 Metropolis 准则粒子在温度 T \mathrm{T} T 时趋于平衡的概率为 exp ( − △ E / ( k T ) ) \exp(-\bigtriangleup E/(k\mathrm{T})) exp(−△E/(kT)) 其中 E E E 为温度 T \mathrm{T} T 时的内能 △ E \bigtriangleup E △E 为其变化量 k k k 为 Boltzmann 常数。将固体退火过程模拟到组合优化问题中内能 E E E 对应于目标函数值 f f f温度 T \mathrm{T} T 演化为控制参数 t t t从而得出模拟退火算法从初始解 i i i 和控制参数初值 t t t 开始对当前解反复进行 “生成新解、计算目标函数差、接受或舍弃” 的迭代并逐步衰减 t t t 值。算法终止时的当前解即为近似最优解。这是基于蒙特卡罗迭代求解方法的一种启发式随机搜索过程。退火过程由冷却进度表Cooling Schedule控制包括控制参数初值 t t t 及其衰减因子 △ t \bigtriangleup t △t、每个 t t t 值时的迭代次数 L L L 和停止条件 S S S 等。
模拟退火算法应用实例
MATLAB 遗传算法和模式搜索工具箱提供了 simulannealbnd 函数用于通过模拟退火算法求解无约束或带有边界约束的多变量最小化问题。该函数的调用语法如下
x simulannealbnd(fun, x0)从初始值 x0 开始搜索目标函数 fun 的最小值 x。目标函数的输入为变量 x并在 x 处返回一个标量值。x0 可以是标量或向量。x simulannealbnd(fun, x0, lb, ub)在边界条件 lb 和 ub 的约束下优化求解目标函数 fun。x simulannealbnd(fun, x0, lb, ub, options)使用自定义的 options参数而非默认值进行优化求解。x simulannealbnd(problem)求解 problem其中 problem 是一个包含输入变量的结构体。[x, fval] simulannealbnd(...)返回点 x 处的目标函数值 fval。[x, fval, exitflag] simulannealbnd(...)返回退出标志 exitflag用于描述函数计算的退出条件。[x, fval, exitflag, output] simulannealbnd(fun, ...)返回结构体 output其中包含优化过程中的信息。 【例1】 求解 MATLAB 自带的测试函数 De Jong 第五函数的最小值。De Jong 第五函数是一个具有多个局部极小值的二维函数。在 MATLAB 命令行中输入 dejong5fcn 可查看 De Jong 第五函数的图像如图 1 所示。 dejong5fcn% 注意命令行中输入查看 De Jong 第五函数的图像。图1. De Jong 第五函数 x0 [0 0];
[x,fval] simulannealbnd(dejong5fcn,x0)% 注意.m文件名必要和simulannealbnd一样否则报错。运行结果 另外在具有上下边界条件约束的情况下也可以调用simulannealbnd数来求解:
x0 [0 0];
lb [-64 -64]; % 下边界约束
ub [64 64]; % 上边界约束
[x,fval] simulannealbnd(dejong5fcn,x0,lb,ub)运行结果 在优化过程中可以实时绘制图像显示优化信息包括当前迭代中的最优点、最优值、当前点和当前值等。可以使用以下 MATLAB 命令实现这一功能。
x0 [0 0];
options saoptimset(PlotFcns {saplotbestx, saplotbestf, saplotx, saplotf}); %绘图参数设置
simulannealbnd(dejong5fcn, x0, [ ], [ ], options)运行结果 图2. 使用模拟退火算法优化 De Jong 第5函数 在模拟退火算法的运行过程中程序实时显示了结果的图形。最终生成的图像如图2所示其中展示了最优点、最优值、当前点和当前值等优化信息。算法在点 (-31.9772, -31.9778) 处找到了函数的最小值。
关于计算结果
由于模拟退火算法是一种随机算法在优化过程中存在随机选择的因素因此每次运行相同的命令结果可能会有所不同。有时算法可能会陷入局部最优导致某些结果较大。为了获得更理想的解即更小的目标函数值通常需要多次调用优化函数并在多次计算结果中选择最优的结果作为最终输出。
在模拟退火算法的计算过程中MATLAB 使用了均匀随机数和正态随机数生成器。决定是否接受新的点时算法会使用 rand 和 randn 函数进行选择。由于每次调用 rand 和 randn 函数时其种子都会发生变化因此每次调用这些函数时都会生成不同的随机数。
如果需要精确地再现计算结果可以在调用 simulannealbnd 函数时返回 output 结构数组。output 结构数组中包含了当前随机数生成器的种子状态。在再现计算前可以将种子设置为 output 中保存的种子。例如在使用模拟退火算法计算 De Jong 第5函数的最优值时可以返回变量 output相应的 simulannealbnd 调用语法为
[x, fval, exitflag, output] simulannealbnd(dejong5fcn, [0 0]);运行结果 随机种子包含在 output.rngstate 中可以通过以下命令重新设置随机数生成器的状态。如果现在再次运行 simulannealbnd 命令就可以验证是否得到与上次相同的结果。 set(RandStream.getGlobalStream,State, output.rngstate.State);[x, fval, exitflag, output] simulannealbnd(dejong5fcn, [0 0])% 注意这两句在运行过一次退火寻优后在命令行中直接运行。运行结果 不过如果不需要重复验证结果最好不要设置随机种子。因为不设置种子可以充分利用模拟退火算法的随机性增加获得更优结果的机会。其他具有随机性的算法如遗传算法等也具有类似的特性此处不再赘述。 END 2024年9月7日
