退火算法什么意思

⑴ 退火算法的定义

Simulate Anneal Arithmetic (SAA,模拟退火算法)
根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中e为温度T时的内能，ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schele)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 模拟退火算法起源于物理退火。
􀂄物理退火过程：
⑴ 加温过程
⑵ 等温过程
⑶ 冷却过程 模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想：
⑴ 初始化：初始温度T（充分大），初始解状态S（是算法迭代的起点）， 每个T值的迭代次数L
⑵ 对k=1,……,L做第⑶至第6步：
⑶ 产生新解S′
⑷ 计算增量Δt′=C(S′）-C(S)，其中C(S)为评价函数
⑸ 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
⑹ 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
⑺ T逐渐减少，且T->0,然后转第2步。 模拟退火算法新解的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则： 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

⑵ 退火算法的应用领域及示例

作为模拟退火算法应用，讨论旅行商问题(Travelling Salesman Problem,简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i,j) i,j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。
求解TSP的模拟退火算法模型可描述如下：
解空间 解空间S是遍访每个城市恰好一次的所有回路，是{1,……,n}的所有循环排列的集合,S中的成员记为(w1,w2,……,wn)，并记wn+1= w1。初始解可选为(1,……,n)
目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数：
我们要求此代价函数的最小值。
新解的产生 随机产生1和n之间的两相异数k和m,
若k<m,则将
(w1,w2,…,wk,wk+1,…,wm,…,wn)
变为：
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k>m,则将
(w1,w2,…,wm,wm+1,…,wk,…,wn)
变为：
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述变换方法可简单说成是“逆转中间或者逆转两端”。
也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。
代价函数差 设将(w1,w2,……,wn)变换为(u1,u2,……,un)，则代价函数差为：
根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
Procere TSPSA:
begin
init-of-T; { T为初始温度}
S={1,……,n}; {S为初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 从当前回路S产生新回路S′}
Δt:=f(S′））-f(S);{f(S)为路径总长}
IF（Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheling Problem)等等。 模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
⑴ 温度T的初始值设置问题。
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。
⑵ 退火速度问题。
模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
⑶ 温度管理问题。
温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：
T(t+1)=k×T(t)
式中k为正的略小于1.00的常数,t为降温的次数 优点：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。
缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。
经典模拟退火算法的缺点：
⑴如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢；
⑵如果降温过程过快，很可能得不到全局最优解。
􀂄 模拟退火算法的改进
⑴ 设计合适的状态产生函数，使其根据搜索进程的需要
表现出状态的全空间分散性或局部区域性。
⑵ 设计高效的退火策略。
⑶ 避免状态的迂回搜索。
⑷ 采用并行搜索结构。
⑸ 为避免陷入局部极小，改进对温度的控制方式
⑹ 选择合适的初始状态。
⑺ 设计合适的算法终止准则。
也可通过增加某些环节而实现对模拟退火算法的改进。
主要的改进方式包括：
⑴ 增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。
⑵ 增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。
⑶ 增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。
⑷ 对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。
⑸ 结合其他搜索机制的算法，如遗传算法、混沌搜索等。
⑹上述各方法的综合应用。

⑶ 模拟退火算法的介绍

模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

⑷ 什么是退火算法

模拟退火的基本思想:
(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) 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
(7) T逐渐减少，且T->0，然后转第2步。

⑸ 模拟退火算法的简介

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。
模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

⑹ 退火算法的介绍

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

⑺ 均场退火算法

均场退火方法既可以看作是一种新的神经网络计算模型,又可视为是对模拟退火的重大改进.该文把具有相邻约束的多层通孔最小化问题转换为更具广泛意义的k-着色问题,并提出了k-着色问题的均场退火求解算法.算法在线段相交图模型的基础上,提出了相邻矩阵和交叠矩阵等概念,并利用换位矩阵,将问题映射为相应的神经网络,再构造了该问题的能量函数.能量函数中的目标项、违背交叠约束的惩罚项、违背相邻约束的惩罚项和神经元归一化处理保证了网络能够求解到一个合法解.实验结果表明,这是一个有效的算法.

⑻ 非数值算法的模拟退火算法

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体
内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平
衡态，最后在常温时达到基态，内能减为最小。根据Metropolis 准则，粒子在温度T 时趋于
平衡的概率为e-ΔE/(kT)，其中E 为温度T 时的内能，ΔE 为其改变量，k 为Boltzmann 常
数。用固体退火模拟组合优化问题，将内能E 模拟为目标函数值f，温度T 演化成控制参数
t，即得到解组合优化问题的模拟退火算法：由初始解i 和控制参数初值t 开始，对当前解重
复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t 值，算法终止时的当
前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火
过程由冷却进度表(Cooling Schele)控制，包括控制参数的初值t 及其衰减因子Δt、每个t
值时的迭代次数L 和停止条件S。
1、模拟退火算法可以分解为解空间、目标函数和初始解三部分 。 它为问题的所有可能(可行的或包括不可行的)解的集合，它限定了初始解选取和新解产
生时的范围。对无约束的优化问题，任一可能解(possible solution)即为一可行解(feasible
solution)，因此解空间就是所有可行解的集合；而在许多组合优化问题中，一个解除满足目
标函数最优的要求外，还必须满足一组约束(constraint)，因此在解集中可能包含一些不可行
解(infeasible so1ution)。为此，可以限定解空间仅为所有可行解的集合，即在构造解时就考
虑到对解的约束；也可允许解空间包含不可行解，而在目标函数中加上所谓罚函数(penalty
function)以“惩罚”不可行解的出现。 它是对问题的优化目标的数学描述，通常表述为若干优化目标的一个和式。目标函数的
选取必须正确体现对问题的整体优化要求。例如，如上所述，当解空间包含不可行解时，目
标函数中应包含对不可行解的罚函数项，借此将一个有约束的优化问题转化为无约束的优化
问题。一般地，目标函数值不一定就是问题的优化目标值，但其对应关系应是显明的。此外，
目标函数式应当是易于计算的，这将有利于在优化过程中简化目标函数差的计算以提高算法
的效率。 是算法迭代的起点，试验表明，模拟退火算法是鲁棒的(Robust)，即最终解的求得几乎
不依赖于初始解的选取。
2、基本思想：
(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) 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
(7) T 逐渐减少，且T->0，然后转第2 步。
二、遗传算法
遗传算法的基本思想是基于Darwin 进化论和Mendel 的遗传学说的。
Darwin 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种
每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，
只有那些能适应环境的个体特征方能保留下来。
Mendel 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因
形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的
个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去
劣的自然淘汰，适应性高的基因结构得以保存下来。
遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。
1、遗传算法的原理
遗传算法GA 把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在
执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的
“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过
交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会
收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
长度为L 的n 个二进制串bi(i=1，2，，n)组成了遗传算法的初解群，也称为初始群体。
在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三
种：
（1）．选择(Selection)
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一
操作为再生(Reproction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适
应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproction)。
（2）．交叉(Crossover)
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而
产生新的个体。
（3）．变异(Mutation)
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi 中，如果某位基因为1，
产生变异时就是把它变成0；反亦反之。
2、遗传算法的特点
（1）．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；
容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。
（2）．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。
遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
（3）．遗传算法有极强的容错能力
遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅
速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，
遗传算法有很高的容错能力。
（4）．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最
优解的产生，变异体现了全局最优解的覆盖。
三、神经网络算法
“人工神经网络”(ARTIFICIAL NEURAL NETWORK，简称A.N.N.)是在对人脑组织结构和
运行机智的认识理解基础之上模拟其结构和智能行为的一种工程系统。早在本世纪40 年代
初期，心理学家McCulloch、数学家Pitts 就提出了人工神经网络的第一个数学模型，从此开
创了神经科学理论的研究时代。其后，F.Rosenblatt、Widrow 和Hopf、J.J.Hopfield 等学者又
先后提出了感知模型，使得人工神经网络技术得以蓬勃发展。
神经系统的基本构造是神经元(神经细胞)，它是处理人体内各部分之间相互信息传递的基本
单元。据神经生物学家研究的结果表明，人的一个大脑一般有10 10 ～10 11
个神经元。每个神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的其它
较短分支——树突组成。轴突的功能是将本神经元的输出信号(兴奋)传递给别的神经元。其
末端的许多神经末梢使得兴奋可以同时传送给多个神经元。树突的功能是接受来自其它神经
元的兴奋。神经元细胞体将接受到的所有信号进行简单地处理(如：加权求和，即对所有的
输入信号都加以考虑且对每个信号的重视程度——体现在权值上——有所不同)后由轴突输
出。神经元的树突与另外的神经元的神经末梢相连的部分称为突触。
1、神经网络的工作原理
人工神经网络首先要以一定的学习准则进行学习，然后才能工作。现以人工神经网络对手写
“A”、“B”两个字母的识别为例进行说明，规定当“A”输入网络时，应该输出“1”，而
当输入为“B”时，输出为“0”。所以网络学习的准则应该是：如果网络作出错误的的判决，
则通过网络的学习，应使得网络减少下次犯同样错误的可能性。首先，给网络的各连接权值
赋予(0，1)区间内的随机值，将“A”所对应的图象模式输入给网络，网络将输入模式加权
求和、与门限比较、再进行非线性运算，得到网络的输出。在此情况下，网络输出为“1”
和“0”的概率各为50%，也就是说是完全随机的。这时如果输出为“1”(结果正确)，则使
连接权值增大，以便使网络再次遇到“A”模式输入时，仍然能作出正确的判断。如果输出
为“0”(即结果错误)，则把网络连接权值朝着减小综合输入加权值的方向调整，其目的在
于使网络下次再遇到“A”模式输入时，减小犯同样错误的可能性。如此操作调整，当给网
络轮番输入若干个手写字母“A”、“B”后，经过网络按以上学习方法进行若干次学习后，
网络判断的正确率将大大提高。这说明网络对这两个模式的学习已经获得了成功，它已将这
两个模式分布地记忆在网络的各个连接权值上。当网络再次遇到其中任何一个模式时，能够
作出迅速、准确的判断和识别。一般说来，网络中所含的神经元个数越多，则它能记忆、识
别的模式也就越多。
2、人工神经网络的特点
人工神经网络是由大量的神经元广泛互连而成的系统，它的这一结构特点决定着人工神经网
络具有高速信息处理的能力。人脑的每个神经元大约有10 3～10 4 个树突及相应的突
触，一个人的大脑总计约形成10 14 ～10 15 个突触。用神经网络的术语来说，
即是人脑具有10 14 ～10 15 个互相连接的存储潜力。虽然每个神经元的运算
功能十分简单，且信号传输速率也较低(大约100 次/秒)，但由于各神经元之间的极度并行互
连功能，最终使得一个普通人的大脑在约1 秒内就能完成现行计算机至少需要数10 亿次处
理步骤才能完成的任务。
人工神经网络的知识存储容量很大。在神经网络中，知识与信息的存储表现为神经元之间分
布式的物理联系。它分散地表示和存储于整个网络内的各神经元及其连线上。每个神经元及
其连线只表示一部分信息，而不是一个完整具体概念。只有通过各神经元的分布式综合效果
才能表达出特定的概念和知识。
由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大，使得它具有很强的
不确定性信息处理能力。即使输入信息不完全、不准确或模糊不清，神经网络仍然能够联想
思维存在于记忆中的事物的完整图象。只要输入的模式接近于训练样本，系统就能给出正确
的推理结论。
正是因为人工神经网络的结构特点和其信息存储的分布式特点，使得它相对于其它的判断识
别系统，如：专家系统等，具有另一个显着的优点：健壮性。生物神经网络不会因为个别神
经元的损失而失去对原有模式的记忆。最有力的证明是，当一个人的大脑因意外事故受轻微
损伤之后，并不会失去原有事物的全部记忆。人工神经网络也有类似的情况。因某些原因，
无论是网络的硬件实现还是软件实现中的某个或某些神经元失效，整个网络仍然能继续工
作。
人工神经网络是一种非线性的处理单元。只有当神经元对所有的输入信号的综合处理结果超
过某一门限值后才输出一个信号。因此神经网络是一种具有高度非线性的超大规模连续时间
动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局限，标志着人们智能
信息处理能力和模拟人脑智能行为能力的一大飞跃。

⑼ 模拟退火算法是什么

从代码角度来说，就是2个循环，一个总温度外循环（足够大，并逐渐减小），另一个内部循环（使其达到该特定温度下的平衡，怎么算平衡自己定义的）。很多书都说外部的总温度外循环，却忽略了内部循环，内部循环值应该多大，我也很模糊。