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

智能优化算法与应用湖南大学电气学院自动化系自我介绍刘敏，电气学院自动化系副教授2007-2012年美国加州大学博士，博士后2000-2007年北京大学本科,硕士研究方向：计算机视觉，图像处理联系方式liu_min@3参考教材：王耀南,《智能信息处理技术》,高等教育出版社,2003年8月第1版.王凌,《智能优化算法及其应用》,清华大学出版社,施普林格出版社,2004.模拟退火算法及其应用SimulatedAnnealing，SA5导言模拟退火算法（SimulatedAnnealing，SA)是一种通用的优化算法。目前，已在：生产调度、控制工程、计算机视觉、神经网络、图像处理等工程领域中得到了广泛应用。

1953年，Metropolis等提出SA思想；1983年，Kirkpatrick等将其用于组合优化，目的在于：为具有NP复杂性的问题提供有效的近似求解算法；克服优化过程陷入局部极小；克服初值依赖性。尼古拉·梅特罗波利斯尼古拉·梅特罗波利斯(Nicholas

Constantine

Metropolis)1915年6月11日生于美国芝加哥。1936年他在芝加哥大学取得学士学位，1941年取得实验物理学博士学位，之后留校在冶金学实验室(MetallurgicalLaboratory)工作，其间他在1942年曾参与哥伦比亚大学的原子弹计划。1943年他进入洛斯阿拉莫斯实验室，参加著名的“曼哈顿计划”，与“原子弹之父”费米(EnricoFermi)和泰勒(EdwardTeller)一起工作，其任务是为高温、高压、高密度下的物质建立状态方程，从此他的研究工作从物理学转入了数学领域。在曼哈顿计划中他是课题组组长。67组合优化组合优化，作为应用数学中最年轻而又至关重要的领域之一，整合了组合数学、线性规划以及算法理论的方法和技巧。由于它在解决从远程通讯到超大规模集成电路、从产品运销到航班机组排班等领域内困难问题方面的成功，这一领域在过去的十年里取得了巨大的、超乎寻常的发展。8计算机视觉ComputerVision计算机视觉是一门研究如何使机器“看”的科学，更进一步的说，就是是指用摄影机和电脑代替人眼对目标进行识别、跟踪和测量等，并进一步做图形处理，用电脑处理成为更适合人眼观察或传送给仪器检测的图像。9计算机视觉制造业、检验识别、文档分析、医疗诊断、军事、智能电网等领域中各种智能系统中不可分割的一部分。美国把对计算机视觉的研究列为对经济和科学有广泛影响的科学和工程中的重大基本问题，即所谓的重大挑战（grandchallenge）。为计算机和机器人开发具有与人类水平相当的视觉能力。10人脸识别在FBI，人脸识别终于要真正发挥在电影中一样的作用了。作为国家的指纹数据库的更新的一部分，美国联邦调查局已经开始推出了面部识别，识别罪犯，反恐。而这些高富帅们的手笔也不是一般的大：$1billion。11机器视觉其他应用：湖南大学电气院指纹打卡

美国加州大学实验室红膜识别计算机视觉又叫做机器视觉，扫地机器人http://ipd.pps.tv/play_373X1J.html12爬山算法(HillClimbing)介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。13爬山算法14模拟退火(SA,SimulatedAnnealing)思想爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是其搜索过程引入了随机因素。模拟退火算法以一定的概率接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。15模拟退火算法思想模拟退火算法描述：

若J(Y(i+1))>=J(Y(i))

(即移动后得到更优解)，则总是接受该移动

若J(Y(i+1))<J(Y(i))

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

for(j=0;j<100;j++)18非确定性问题什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。19NP问题NP问题：英文是non-deterministicpolynomial,是多项式时间可以验证的问题。最初是在非确定图灵机上，如果一个问题存在一个解，那么就先猜它，一定可以在多项式时间内猜到这个解。（关键是就是不判定这个问题到底有没有解）

p？=NP目前还没有被证实。也就是还不知道P和NP的关系，但是可以确定的是P属于NP。2021模拟退火算法及其应用SA算法是基于MonteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。MonteCarlo蒙特卡洛欧洲地中海之滨、法国的东南方，有一个世界上版图最小的国家摩纳哥公国，世人称之为“赌博之国”、“袖珍之国”、“邮票小国”。22蒙特卡洛模拟蒙特卡洛模拟为方便的解决困难而复杂的实际问题开启了一扇大门。估计蒙特卡罗模拟最著名的早期使用是诺贝尔奖物理学家EnricoFermi（原子弹之父）在1930年的应用，那时他用一种随机方法来计算刚发现的中子的性质。23蒙特卡罗有关MonteCarlo方法历史背景的最精确描述来自JunLiu的专著，他指出一批物理学家在二战期间为估算薛定谔方程的本征值而发明了一种基于统计抽样的数值计算法，其最初想法归功于Ulam。后来Ulam的同事Metropolis将该方法命名为MonteCarlo。1950年代Metropolis和几名统计物理学同事发表了一篇经典论文，提出了MarkovChainMonteCarlo(MCMC)算法。而MCMC法后来是Bayesian统计学能够不断前进的主要动力。24蒙特卡罗蒙特卡罗模拟是曼哈顿计划所用到的模拟的核心部分，在20世纪50年代蒙特卡罗模拟就用在LosAlamos国家实验室发展氢弹的早期工作中，并流行于物理学和运筹学研究领域。兰德公司和美国空军是这个时期主要的两个负责资助和传播蒙特卡罗方法的组织，今天蒙特卡罗模拟也被广泛应用于不同的领域，包括工程，物理学，研发，商业和金融。25退火中文名称：退火英文名称：annealing将金属加热到一定温度，保持足够时间，然后以适宜速度冷却(通常是缓慢冷却，有时是控制冷却)的一种金属热处理工艺。[1]2627

什么是退火退火淬火物理退火过程高温低温缓慢下降高能状态低能状态高温低温快速下降高能状态高能状态退火的作用(1)降低硬度，改善切削加工性.(2)消除残余应力，稳定尺寸，减少变形与裂纹倾向；(3)细化晶粒，调整组织，消除组织缺陷。(4)均匀材料组织和成分，改善材料性能或为以后热处理做组织准备。在生产中，退火工艺应用很广泛。根据工件要求退火的目的不同，退火的工艺规范有多种，常用的有完全退火、球化退火、和去应力退火等。28模拟退火算法的基本思想启发注意到一个自然规则：物质总是趋于最低的能态。水总是向低处流。电子总是向最低能级的轨道排布。最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。模拟退火算法的设计与原理猜想物质自动趋向的最低能态与函数最小值之间有相似性！！！我们能不能设计一种算法求函数最小值，就像物质”自动”地趋向最低能态？降温图像离散函数图像相似性?最小值最低能态物理模型——固体退火退火俗称固体降温先把固体加热至足够高温，使固体中所有粒子处于无序的状态（最高的熵值），然后将温度缓慢下降，粒子渐渐有序（熵值下降），这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态（最低的熵值）。最低能态时间温度模拟退火算法的设计与原理类比根据Metropolis准则，粒子在温度T时趋于热平衡的概率为

其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。可以设计算法：将系统熵值类比为函数值F，来模拟这个退火过程。Metropolis准则（1953）——以概率接受新状态

p=exp[-(Ej-Ei)/kBT]

在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。342.3模拟退火算法及其应用物理退火过程由以下三部分组成：加温过程增强粒子热运动，使其偏离平衡位置。当温度足够高时，固体熔解为液体，消除系统可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。等温过程对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。冷却过程使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。352.3模拟退火算法及其应用为了模拟固体在恒定温度下达到热平衡的过程，可采用MonteCarlo方法，该方法简单，但必须大量采样才能得到较精确结果，计算量很大。考虑到物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低态的图像，采样时着重取那些有重要贡献的状态则可较快达到较好的结果。

1953年，Metropolis等据此提出了重要性采样法（也称为Metropolis准则），即以概率接受新状态。362.3模拟退火算法及其应用Metropolis准则：在温度t，由当前状态i产生新状态j，两者的能量分别为Ci和Cj，若Cj<Ci

，则接受新状态j为当前状态；否则，若概率pr=exp[-(Cj-Ci)/(kt)大于[0,1)区间内的随机数，仍接受新状态j为当前状态;若不成立，则保留状态i为当前状态。其中，k为Boltzmann常数。372.3模拟退火算法及其应用SA算法的基本思路：由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。

模拟退火算法的实现思想SA算法的计算过程可视为重复递减控制参数值（温度）并进行Metropolis算法的迭代过程。一次Metropolis算法是指，对于控制参数t的每一取值，算法在Markov链长度内持续进行“产生新解—判断—接受/舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。

马尔科夫过程一类随机过程。它的原始模型马尔可夫链，由俄国数学家A.A.马尔可夫于1907年提出。该过程具有如下特性：在已知目前状态（现在）的条件下，它未来的演变（将来）不依赖于它以往的演变(过去)。例如森林中动物头数的变化构成——马尔可夫过程。在现实世界中，有很多过程都是马尔可夫过程，如液体中微粒所作的布朗运动、传染病受感染的人数、车站的候车人数等，都可视为马尔可夫过程。关于该过程的研究，1931年A.H.柯尔莫哥洛夫在《概率论的解析方法》一文中首先将微分方程等分析的方法用于这类过程，奠定了马尔可夫过程的理论基础。39MarkovProcess马尔科夫过程(MarKovProcess)是一个典型的随机过程。设X(t)是一随机过程，当过程在时刻t0所处的状态为已知时，时刻t(t>t0)所处的状态与过程在t0时刻之前的状态无关，这个特性成为无后效性。无后效的随机过程称为马尔科夫过程。马尔科夫过程中的时同和状态既可以是连续的，又可以是离散的。我们称时间离散、状态离散的马尔科夫过程为马尔科夫链。马尔科夫链中，各个时刻的状态的转变由一个状态转移的概率矩阵控制。40412.3模拟退火算法及其应用例：考虑一元函数求最大值的优化问题422.2模拟退火算法及其应用SA在局部极小解处有机会跳出，并最终趋于全局最优的根本原因：算法通过概率判断来接受新状态。理论上，初温充分高、降温足够慢、每一温度下抽样足够长、最终温度趋于零时，算法以概率1收敛到全局最优解。由于SA的某些收敛条件无法严格实现，或即使某些收敛条件可以实现，但常因为实际应用的效果不理想而不被采用。迄今为止，SA的参数选择依然是一个难题，通常只能依据一定的启发式准则或大量的实验加以选取。43二.退火过程和Bolzman方程（2）44Bolzman方程二.退火过程和Bolzman方程（3）45温度对的影响当很大时， ，各状态的概率几乎相等SA开始做广域搜索，随着温度的下降 差别扩大二.退火过程和Bolzman方程（4）46当 时，与的小差别带来和的巨大差别例如：=90， =100，二.退火过程和Bolzman方程（5）47当 =100时二.退火过程和Bolzman方程（6）48当=1时此时结论:

时，以概率1趋于最小能量状态二.退火过程和Bolzman方程（7）492.3模拟退火算法及其应用步骤1：确定编码方式和能量函数（目标函数）最常用的编码方案：实数编码，以实数来表示求解状态。

s=1.8函数优化问题中，能量函数由待优化函数变换而成。若目标函数为最大化问题：C(s)=-f(s)若目标函数为最小化问题：C(s)=f(s)502.3模拟退火算法及其应用步骤2：确定初温实