Hao Chen

cighao@gmail.com

  • About ME
  • Archives
  • Exploring World
Search

Hao Chen

cighao@gmail.com

  • About ME
  • Archives
  • Exploring World

模拟退火算法简介

2015-12-03

目录 [+]

  1. 1. 简介
  2. 2. 相关概念
    1. 退火
    2. Boltzman 概率分布
    3. Metropolis 准则
  3. 3. 原理
  4. 4.算法步骤
    1. step1
    2. step2
    3. step3
    4. step4
  5. 5.源码

1. 简介

模拟退火算法 (Simulated Annealing,SA) 最早的思想是由 N. Metropolis 等人于1953年提出。1983年, S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于 Monte-Carlo 迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。

2. 相关概念

退火

退火:将固体加热到足够高的温度,使分子呈随即排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。

退火过程:

  • 加温过程:增强粒子运动,消除系统原先可能存在的非均匀态。
  • 等温过程:对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡。
  • 冷却过程:使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。

Boltzman 概率分布

Boltzman 概率分布告诉我们:

  • 同一个温度,分子停留在能量小状态的概率大于停留在能量大状态的概率
  • 温度越高,不同能量状态对应的概率相差越小,温度足够高时,各状态对应概率基本相同。
  • 随着温度的下降,能量最低状态对应概率越来越大,温度趋于0时,其状态趋于1

Metropolis 准则

固体在恒定温度下达到热平衡的过程可以用 Metropolis 方法加以模拟。

温度恒定时:若在温度T,当前状态i –> 新状态j,若Ej<Ei,则接受j为当前状态;否则,若概率 p=e−(Ej−Ei)/(kB∗T) 大于[0,1)区间的随机数,则仍接受状态j为当前状态;若不成立则保留状态i为当前状态。

温度变化时:p=e−(Ej−Ei)/(kB∗T) ,在高温下,可接受当前状态能量差较大的新状态;在低温下,只接受与当前状态能量差较小的新状态。

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。

4.算法步骤

step1

由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。

step2

计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。

step3

判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是 Metropolis 准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。

step4

当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。

5.源码

MATLAB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function [xo,fo] = Opt_Simu(f,x0,u,l,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<fx或者概率大于随机数z
x = x1;
fx = fx1;
end
if fx < fo
xo = x;
fo = fx1;
end
end
function x = Mu_Inv(y,mu)
x = (((1+mu).^abs(y)- 1)/mu).*sign(y);

  • 算法
  • 模拟退火算法

扫一扫,分享到微信

微信分享二维码
利用模拟退火算法求解TSP问题
粒子群优化算法简介
  1. 1. 1. 简介
  2. 2. 2. 相关概念
    1. 2.1. 退火
    2. 2.2. Boltzman 概率分布
    3. 2.3. Metropolis 准则
  3. 3. 3. 原理
  4. 4. 4.算法步骤
    1. 4.1. step1
    2. 4.2. step2
    3. 4.3. step3
    4. 4.4. step4
  5. 5. 5.源码

Related Issues not found

Please contact @cighao to initialize the comment

© 2025 Hao Chen
Hexo Theme Yilia by Litten
  • Search

tag:

  • Javascript
  • Web 前端
  • Matlab
  • 遗传算法
  • 算法
  • Hexo
  • 计算机
  • Linux IO
  • Cassandra
  • 数论
  • SSD
  • NVMe
  • Database
  • 论文阅读
  • Disksim
  • flashsim
  • Ubuntu
  • 画图
  • 信号处理
  • 黑客
  • Mysql
  • Python
  • 爬虫
  • 粒子群算法
  • 模拟退火算法
  • Neo4j
  • Ngrok
  • SPDK
  • RocksDB
  • Java
  • Matplotlib
  • openstack swift
  • 分布式存储
  • 对象存储
  • 学术
  • Tool
  • C语言
  • 正则表达式
  • 端口扫描
  • 二层规划
  • 排序
  • 随笔
  • Nodejs
  • Tools
  • 数据库

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 数据库中的热点行优化 (SIGMOD'21 Paper 解读)

    2022-02-28

    #Database#论文阅读

  • NVMe SSD中namespace的介绍和创建

    2020-04-12

    #SSD#NVMe

  • 快速搭建 L2TP VPN 服务器

    2019-11-20

    #计算机#Tool

  • SPDK 介绍(二):SPDK 相关博客

    2019-10-25

    #SPDK

  • SPDK 介绍(一):使用 FIO 测试 SPDK

    2019-10-23

    #SPDK

  • RocksDB 介绍(一):相关博客

    2019-10-22

    #RocksDB

  • Linux IO 相关资料

    2019-09-29

    #计算机#Linux IO

  • Cassandra 介绍(三):Commitlog 介绍(1)

    2019-09-26

    #Cassandra

  • Cassandra 介绍(二):Blogs

    2019-09-22

    #Cassandra

  • Cassandra 介绍(一):Install and test with YCSB

    2019-09-19

    #Cassandra

  • 阿里数据库内核月报(汇总)

    2019-09-03

    #数据库

  • Neo4j 介绍(五):使用 java 访问 neo4j

    2019-04-24

    #Neo4j

  • Neo4j 介绍(四):关于 neo4j 的一些博客

    2019-04-21

    #Neo4j

  • Neo4j 介绍(三):使用 python 访问 neo4j

    2019-04-21

    #Neo4j

  • Neo4j 介绍(二):main 函数

    2019-04-13

    #Neo4j

  • 日常遇到的一些小问题的解决方案

    2019-03-29

    #计算机#Tool

  • Neo4j 介绍(一):安装

    2019-03-21

    #Neo4j

  • matlab 画图(十): 分组和堆叠的条形图

    2019-01-13

    #Matlab#画图

  • 论文写作常用工具

    2018-11-20

    #Tools

  • Openstack Swift学习(八):配置ntp

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(七):ssbench 使用

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(六):服务启动源码分析

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(五):debug 总结

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(四):中间件

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(三):log 配置

    2018-09-22

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(二):相关文档

    2018-07-20

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(一):安装

    2018-07-12

    #openstack swift#分布式存储#对象存储

  • 在 linux 上首次使用 SSD

    2017-03-20

    #SSD

  • disksim-3.0 with flashsim 源码分析(六):垃圾回收

    2017-02-27

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(五):写操作

    2017-02-27

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(四):初始化

    2017-02-27

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(三):callFsim()函数介绍

    2017-02-21

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(二):DFTL 中的 cache

    2016-12-10

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(一):disksim-3.0 和 flashsim 的安装

    2016-12-06

    #SSD#Disksim#flashsim

  • flashsim 源码分析(五): flashsim 的初始化

    2016-11-22

    #SSD#flashsim

  • flashsim 源码分析(四): 总线上锁机制的实现

    2016-11-13

    #SSD#flashsim

  • flashsim 源码分析(三): 总线通道中的交叉

    2016-11-11

    #SSD#flashsim

  • flashsim 源码分析(二): flashsim 中的面向对象设计

    2016-11-09

    #SSD#flashsim

  • flashsim 源码分析(一):安装 flashsim

    2016-11-08

    #SSD#flashsim

  • 利用概率算法求解八皇后问题

    2016-10-20

    #算法

  • 回溯法求解八皇后问题

    2016-10-20

    #算法

  • 利用概率算法估算集合大小

    2016-10-17

    #算法

  • 神奇的卡特兰数

    2016-10-07

    #算法#数论

  • 论文阅读:基于闪存的缓冲区管理算法

    2016-08-23

    #SSD#论文阅读#学术

  • 论文阅读:针对闪存的成本感知的缓冲区管理策略(DASFAA 2015)

    2016-08-19

    #SSD#论文阅读#学术

  • 暴力破解 wifi 密码

    2016-08-04

    #黑客

  • 论文阅读:SSD内部多级并行性的探索和利用(TOC 2013)

    2016-07-20

    #SSD#论文阅读#学术

  • 论文阅读:SSD中基于PSO的缓冲区管理算法(ICITCS 2015)

    2016-07-19

    #SSD#论文阅读#学术

  • 利用二级指针删除链表节点

    2016-07-09

    #算法

  • 抓包获取简书的登录密码

    2016-07-07

    #黑客

  • disksim with ssdmodel 源码解析(二十二):读写和擦除时间的计算

    2016-06-28

    #SSD#Disksim

  • 求离散采样信号的波峰和波谷

    2016-05-31

    #信号处理

  • matlab 画图(九): 横坐标标签倾斜设置

    2016-05-13

    #Matlab#画图

  • matlab 画图(八): 双坐标绘图

    2016-04-29

    #Matlab#画图

  • matlab 画图(七): 扇形图

    2016-04-24

    #Matlab#画图

  • matlab 画图(六): 横向柱状图

    2016-04-20

    #Matlab#画图

  • matlab 画图(五): 垂直柱状图

    2016-04-17

    #Matlab#画图

  • matlab 画图(四): 句柄作图示例

    2016-04-16

    #Matlab#画图

  • disksim with ssdmodel 源码解析(二十一):warm up ssd

    2016-04-15

    #SSD#Disksim

  • matlab 画图(三): 图形句柄

    2016-04-14

    #Matlab#画图

  • matlab 画图(二): 基本作图技巧

    2016-04-13

    #Matlab#画图

  • disksim with ssdmodel 源码解析(二十):统计结果的提取

    2016-04-12

    #SSD#Disksim

  • matlab 画图(一): 线条样式设计

    2016-04-11

    #Matlab#画图

  • disksim with ssdmodel 源码解析(十九):ssd 的初始化

    2016-03-31

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十八):GC 分析(五)

    2016-03-30

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十七):GC 分析(四)

    2016-03-30

    #SSD#Disksim

  • SSD 编程学习笔记(一)

    2016-03-29

    #SSD

  • disksim with ssdmodel 源码解析(十六):GC 分析(三)

    2016-03-29

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十五):GC 分析(二)

    2016-03-27

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十四):ssd_activate_elem函数分析

    2016-03-24

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十三):如何兼容64位系统

    2016-03-23

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十二):写操作分析

    2016-03-23

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十一):地址映射

    2016-03-23

    #SSD#Disksim

  • matplotlib 画图(四):text 和 label 的设置

    2016-03-22

    #画图#Matplotlib

  • disksim with ssdmodel 源码解析(十):GC分析(一)

    2016-03-19

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(九):syssim_driver 系统级接口(二)

    2016-03-19

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(八):syssim_driver 系统级接口(一)

    2016-03-19

    #SSD#Disksim

  • matplotlib 画图(三):线的连续与间断

    2016-03-19

    #画图#Matplotlib

  • disksim with ssdmodel 源码解析(七):block的组织形式

    2016-03-18

    #SSD#Disksim

  • matplotlib 画图(二):图形填充

    2016-03-17

    #画图#Matplotlib

  • disksim with ssdmodel 源码解析(六):disksim_setup_disksim

    2016-03-16

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(五):程序流程介绍

    2016-03-16

    #SSD#Disksim

  • matplotlib 画图(一):横向柱状图

    2016-03-16

    #画图#Matplotlib

  • 一种时间复杂度为 O(N) 整数排序算法

    2016-03-15

    #算法#排序

  • disksim with ssdmodel 源码解析(四):ssd_event_arrive 函数的介绍

    2016-03-13

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(三):初次使用介绍

    2016-03-12

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(二):输入参数的介绍

    2016-03-06

    #SSD#Disksim

  • 在 Hexo 中给文章添加版权信息

    2016-03-01

    #Hexo

  • python中的爬虫神器 XPath 介绍

    2016-03-01

    #Python#爬虫

  • 程序员得长多高

    2016-02-26

    #Python#爬虫#随笔

  • Hexo 博客添加打赏功能

    2016-02-23

    #Hexo

  • Hexo 主题优化

    2016-02-14

    #Hexo

  • 利用 HttpClient 刷 CSDN 博客文章浏览量

    2016-02-04

    #Java

  • nodejs 中模块使用的介绍

    2016-01-10

    #Nodejs

  • 利用 javascript 实现回到顶部效果

    2016-01-09

    #Javascript#Web 前端

  • Ngrok: 一个提供内网到外网映射的工具

    2015-12-18

    #Ngrok

  • 如何给数百万考生的成绩排序

    2015-12-17

    #算法#排序

  • 在 Hexo 中给文章添加目录

    2015-12-13

    #Hexo

  • Java 动态加载类

    2015-12-06

    #Java

  • python 中安装 requests 模块

    2015-12-05

    #Python#爬虫

  • 利用模拟退火算法求解TSP问题

    2015-12-04

    #算法#模拟退火算法

  • 模拟退火算法简介

    2015-12-03

    #算法#模拟退火算法

  • 粒子群优化算法简介

    2015-11-30

    #算法#粒子群算法

  • Hexo yilia主题添加网站访客人数统计

    2015-11-30

    #Hexo

  • 利用粒子群算法求解非线性二层规划问题

    2015-11-07

    #算法#粒子群算法#二层规划

  • 遗传算法的 matlab 实现

    2015-11-03

    #Matlab#遗传算法#算法

  • 基于javascript实现的2048小游戏

    2015-11-02

    #Javascript#Web 前端

  • 随机生成正整数 1-n 的一个排列

    2015-10-11

    #算法#C语言

  • disksim with ssdmodel 源码解析(一):disksim及ssdmodel模块扩展的安装

    2015-09-09

    #SSD#Disksim#Ubuntu

  • 固态硬盘(SSD)原理及相关介绍

    2015-08-31

    #SSD

  • windows7下安装ubuntu及相关问题的解决方案

    2015-08-27

    #Ubuntu

  • python 正则表达式的使用

    2015-08-22

    #Python#爬虫#正则表达式

  • 基于 python socket 的端口扫描程序

    2015-03-29

    #Python#端口扫描

  • mysql windows 下zip安装

    2015-03-29

    #Mysql