智能优化算法--模拟退火算法

1、智能优化算法与应用湖南大学电气学院自动化系3模拟退火算法及其应用Simulated Annealing，SA5尼古拉梅特罗波利斯尼古拉梅特罗波利斯(NicholasConstantineMetropolis)1915年6月11日生于美国芝加哥。1936年他在芝加哥大学取得学士学位，1941年取得实验物理学博士学位，之后留校在冶金学实验室(MetallurgicalLaboratory)工作，其间他在1942年曾参与哥伦比亚大学的原子弹计划。1943年他进入洛斯阿拉莫斯实验室，参加著名的“曼哈顿计划”，与“原子弹之父”费米(EnricoFermi)和泰勒(EdwardTeller)一起工作，其任

2、务是为高温、高压、高密度下的物质建立状态方程，从此他的研究工作从物理学转入了数学领域。在曼哈顿计划中他是课题组组长。67组合优化，作为应用数学中最年轻而又至关重要的领域之一，整合了组合数学、线性规划以及算法理论的方法和技巧。由于它在解决从远程通讯到超大规模集成电路、从产品运销到航班机组排班等领域内困难问题方面的成功，这一领域在过去的十年里取得了巨大的、超乎寻常的发展。8910在FBI，人脸识别终于要真正发挥在电影中一样的作用了。作为国家的指纹数据库的更新的一部分，美国联邦调查局已经开始推出了面部识别，识别罪犯，反恐。而这些高富帅们的手笔也不是一般的大：$1billion。1112爬山算法爬山算

3、法 ( Hill Climbing )介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。1314模拟退火模拟退火(SA, Simulated Annealing)思想思想爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是

4、其搜索过程引入了随机因素。模拟退火算法以一定的概以一定的概率率接受一个比当前解要差的解，因此有可能有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。15模拟退火算法描述：若J(Y(i+1)=J(Y(i)(即移动后得到更优解)，则总是接受该移动若J(Y(i+1)J(Y(i)(即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）逐渐降低

5、（逐渐降低才能趋向稳定）这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。16作为模拟退火算法应用，讨论货郎担问题(TravellingSalesmanProblem，简记为TSP)：设有n个城市，用数码1,n代表。城市i和城市j之间的距离为d(i，j)i,j=1,nTSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短。旅行商旅行商问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是O(N!)。使用模拟退火用模拟退火算法可以比较快的求出TSP的一条近似最优路径。17P问题：可以在以多项式表达的时间内求出确切解的问

6、题，也就是说它的计算复杂度是一个多项式。我们通常用的O(n),O(logn),O(n2)等等类似的都是这类问题。18什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。19NP问题：英文是non-deterministicpolynomial,是多项式时间可以验证的问题。最初是在非确定图灵机上，如果一个问题存在一个解，那么就先猜它，一定可以在多项式时间内猜到这个解。（关键

7、是就是不判定这个问题到底有没有解）p？=NP目前还没有被证实。也就是还不知道P和NP的关系，但是可以确定的是P属于NP。2021欧洲地中海之滨、法国的东南方，有一个世界上版图最小的国家摩纳哥公国，世人称之为“赌博之国”、“袖珍之国”、“邮票小国”。22蒙特卡洛模拟为方便的解决困难而复杂的实际问题开启了一扇大门。估计蒙特卡罗模拟最著名的早期使用是诺贝尔奖物理学家EnricoFermi（原子弹之父）在1930年的应用，那时他用一种随机方法来计算刚发现的中子的性质。23专著专著薛定谔方薛定谔方程程统计物理学统计物理学典论典论24蒙特卡罗模拟是曼哈顿计划所用到的模拟的核心部分，在20世纪50年代蒙特卡

8、罗模拟就用在LosAlamos国家实验室发展氢弹的早期工作中，并流行于物理学和运筹学研究领域。兰德公司和美国空军是这个时期主要的两个负责资助和传播蒙特卡罗方法的组织，今天蒙特卡罗模拟也被广泛应用于不同的领域，包括工程，物理学，研发，商业和金融。25中文名称：退火英文名称：annealing将金属加热到一定温度，保持足够时间，然后以适宜速度冷却(通常是缓慢冷却，有时是控制冷却)的一种金属热处理工艺。12627(1)降低硬度，改善切削加工性.(2)消除残余应力，稳定尺寸，减少变形与裂纹倾向；(3)细化晶粒，调整组织，消除组织缺陷。(4)均匀材料组织和成分，改善材料性能或为以后热处理做组织准备。在生

9、产中，退火工艺应用很广泛。根据工件要求退火的目的不同，退火的工艺规范有多种，常用的有完全退火、球化退火、和去应力退火等。28物质自动趋向的最低能态与函数最小值之间物质自动趋向的最低能态与函数最小值之间有相有相似性似性！函数最小值，就像最低能态？降温图像离散函数图像相似性?最小值最低能态退火俗称退火俗称先把固体加热至足够高温先把固体加热至足够高温，使固体中所有粒子处于，使固体中所有粒子处于无序的状态（最高的熵值无序的状态（最高的熵值），然后将温度缓慢下降），然后将温度缓慢下降，粒子渐渐有序（熵值下，粒子渐渐有序（熵值下降），这样只要温度上升降），这样只要温度上升得足够高，冷却过程足够得足够高，冷

10、却过程足够慢，则所有粒子最终会处慢，则所有粒子最终会处于最低能态（最低的熵值于最低能态（最低的熵值）。）。t07a0.187H5T t ( )Ht0H()eat t0()0102030051015T t ( )t最低能态时间温度EKTe34353637SA 算法的计算过程可视为重复递减控制参数值（温度）并算法的计算过程可视为重复递减控制参数值（温度）并进行进行Metropolis 算法的迭代过程。一次算法的迭代过程。一次Metropolis 算法是算法是指，对于控制参数指，对于控制参数t的每一取值，算法在的每一取值，算法在Markov 链长度内链长度内持续进行持续进行“产生新解产生新解判断判断

11、接受接受/舍弃舍弃”的迭代过程，对的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。算法终止应着固体在某一恒定温度下趋于热平衡的过程。算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。求解法的一种启发式随机搜索过程。一类随机过程。它的原始模型马尔可夫链，由俄国数学家A.A.马尔可夫于1907年提出。该过程具有如下特性：在已知目前状态（现在）的条件下，它未来的演变（将来）不依赖于它以往的演变(过去)。例如森林中动物头数的变化构成马尔可夫过程。在现实世界中，有很多过程都是马尔可夫过程，如液体中微粒所作的

12、布朗运动、传染病受感染的人数、车站的候车人数等，都可视为马尔可夫过程。关于该过程的研究，1931年A.H.柯尔莫哥洛夫在概率论的解析方法一文中首先将微分方程等分析的方法用于这类过程，奠定了马尔可夫过程的理论基础。394041 sin 102.01,2fxxxx 4243 ?exp, kikiikikkikiCPTPETECTPiTEinS如何确定则有如下关系：的概率为：这时处于状态平衡，下，经一段时间达到热在温度的能量为，状态有限个，离散的个状态中有设热力学系统44iknikiikkikikkiinikikikiEETTPETETEiTPTTPETETETP ,1expexp11下的平均能量：

13、最小的那一个代表可见：45kTkiTPkT0kiTEnTPki1kiTP46kiTP0kTkiTEiEjEkjTPiEjE47kT367. 0406. 0367. 0406. 010010010090kkkkkjkiCCueCeCTPTP48200001072.310194.84440kkkjkiCCTPTPkinikiTPTP1kT0kT4950515253221( )afa，- 21( )exp22f，- 1 , ( )0baa bfelse545556575859606162 内循环热平衡的达到外循环算法的特点冷却控制搜索：随机的邻域移动移动同要素：状态表达和邻域代表状态是离散有限状态空

14、间， , , minSATSiSSiif63Si0TfT0, 0TTkk 的邻域表示iiNiNj, ifjff0T0kiTE64 kTnjiTfUk, exp, 1 , 0则令若, 0jif令kTkT651 kkfkTT kTkTTTTrrTTkkkk112.99. 095. 0 . 1优点：简单易行。其中较好的方法660,0TTkkSikTn0n ifjff iNj 1 nn1 kkkT0f1 , 0expUTfkji kTnn fkTT 6715, 5,18, 84321PPPP41miniiF68 43214321321211PPPPFPPPFPPFPF 92181152835412344321PPPPF691000T60fT3020kkkTnTTTT 118if704.是随机产生的是随机产生的100kT ji