计算智能-模拟退火算法.ppt

1、4.模拟退火算法,4.1 模拟退火算法概述,模拟退火算法：基本思想是把某类优化问题的求解过程与统计热力学中的热平衡问题进行对比，试图通过模拟高温物体退火过程的方法，来找到优化问题的全局最优或近似全局最优解。,4.1 模拟退火算法概述,一个物体（例如金属）的退火过程大体上是这样的：首先对该物体加热（熔化），那么物体内的原子就可高速自由运行，处于较高的能量状态。但是作为一个实际的物理系统，原子的运行总是最低的能态。一开始温度较高时，高温使系统具有较高的内能，而随着温度的下降，原子越来越趋向于低能态，最后整个物体形成最低能量的基态。,4.1 模拟退火算法概述,模拟退火算法（ Simulated An

2、nealing；SA） 最早的想法是由N.Metropolis 等人于1953 年所提出，在当时并沒有受到重视。 直到1983 年由Kirkpatrick et al. 提出蒙特卡罗模拟（MonteCarlo Simulated）概念的随机搜寻技巧，利用此方法来求解的组合优化问题时，才使此算法受到重视。,4.1 模拟退火算法概述,SA的观念主要来自于固体加热至一定的温度后，固体间的分子结构会被打散瓦解变为液态结构， 接着再对其降温过程加以控制，当完全冷却能使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态,4.1 模拟退火算法概述,当目前状况是落于区域的最佳解时，模拟退火法会藉

3、由重新加热的动作，透过随机的过程，以几率性质来接受一个暂劣解使其演算法能跳脱目前的区域最佳解，而有机会能达到另一个最佳解,4.1 模拟退火算法概述,接受法则（Accepting Rule） 并用退火程序（Annealing Schedule）的参数演算法的进行 而Metroplis 接受法则的概念则在于能使求解时跳脱陷入区域最佳解 而模拟退火法能否成功应用在于退火程序的合理选择,4.1 模拟退火算法概述,若令i 代表在时间k 的现有解，其成本为C(i) 下一个搜寻到的解，其成本为C(j) D E = C(j) - C(i)为两个解之间的成本差 当j 的成本大于i 時，SA 会根据一几率決定是否

4、要接受j来取代i 成为时间k+1 的新解,4.1 模拟退火算法概述,因此当搜寻到的新解比现有解之成本大时，会有一个几率值来决定是否接受交换。 SA 基本上是以Metrolopis 接受法则为基楚，再配合退火程序，藉由温度逐渐的降低来调整是否接受成本较差新解的几率，当温度越低时，几率值也跟著降低,4.2 模拟退火算法流程,四个基本要素 系统状态（Configuration）：即在某一个温度下，系统产生的初始解，并当作目前的现行解 搜寻法则（Search rule）：在退火的过程中，由目前系统状态经由随机扰动而产生变化跳至另一种状态 一般而言，SA 较常用的有梯度搜寻法（ Gradient Typ

5、e） 和迭代改善法（ IterativeImprovement,4.2 模拟退火算法流程,成本函数（Cost Function）：用来衡量某一系统状态下之能量函数 退火程序（Annealing Process）：退火程序中包含的参数有初始温度、降温机制、冷却率和终止温度。在退火的过程中，在温度高的时候，虽然是较差的目标值，但有可能被接受当成目前的目标值，但随着温度慢慢的降低，接受较差目标值的概率逐渐降低。,4.2 模拟退火算法流程,4.2 模拟退火算法流程,参数设定 初始温度 为了防止落入区域极小的陷阱，在模拟退火法中初始温度的设定必须使得大部份的转移均可被接受 初始温度的设定可以是一个定值，

6、 如Kirkpatrick等学者 ( 1983 ) 将初始温度定为10 Heragu 以及 Alfa ( 1992 )将初始温度定为999 初始温度亦可由所設定接受概率的门槛值 P 0來反推求得，如Kouvelis 以及 Chiang( 1992 ) 將初始温度定为,4.2 模拟退火算法流程,終止條件 終止條件最簡單的設定方式是指定一個固定的終止溫度，一般是一個接近於零較小的數，或是限制降溫次數不超過預定值 其它方式則為檢查所求得的解是否有所改善，如在1992 年Kouvelis 與 Chiang設定若經過數次降溫後所得的解仍未改善或移轉接受比率低於一個定值，則將終止模擬退火法的運算。,4.2

7、 模拟退火算法流程,降溫時機 降溫時機是指在同一溫度下所应反复進行Metropolis 演算的次數 最直接的方式是設定一個固定長度，但此長度与問題規模有关，如在1992 年Kouvelis 与Chiang 將其設定為鄰近解個數之比率。 此外亦可設定降溫時機為移轉接受次數已達一定值，如Heragu 以及 Alfa（1992）所使用的方式便是 但此一方式當溫度降至很低時，移轉接受之機率將會很小，進而導致馬可夫鏈過長，因此必須同時限定馬可夫鏈的長度，以免造成求解時間過長,4.2 模拟退火算法流程,溫度控制參數 溫度控制參數是指在演算過程中，若達到降溫時機時，由目前溫度減少到次一溫度的下降比率 若溫度

8、控制參數愈小，則溫度下降的差距愈大，那麼會造成在次一溫度達成均衡所需的馬可夫鏈長度愈長，使得求解時間增加。 因此，為了避免在新溫度下的馬可夫鏈長度過長，溫度控制參數不應過小，Kirkpatrick 等學者（1983）將其設定為0.9，而一般則設定在0.5至0.9 之間。,4.2 模拟退火算法应用,0-1背包问题 一个旅行者有一个最多能装M公斤的背包，现在有N件物品， 它们的重量分别是W1，W2，.,Wn, 它们的价值分别为P1,P2,.,Pn.若每种物品只有一件。 求旅行者能获得的最大总价值。,4.2 模拟退火算法应用,例：已知背包的装载量为m=10,现在有n=5个物品，它们的重量和价值分别是

9、 (2,3,5,1,4)和(2,5,8,3,6)。试使用模拟退火算法求解该背包问题。,4.2 模拟退火算法应用,问题的一个可行解用0和1的序列表示，例如i=(10101)表示选择第1、第3和第5个物品，而不选择第2和第4个物品。 第一步：初始化，假设初始解为i=(11001)，初始温度为T=10，计算 f(i)=2+5+6=13,4.2 模拟退火算法应用,第二步：在T温度下局部搜索，直到“平衡”。 降温時机用在同一温度下所应反复进行Metropolis 演算的次数，假设次数为3。 搜寻法则：随机改变某一位的0,1值或交换某两位的0,1值。,4.2 模拟退火算法应用,假设产生的新解j=(11100)，f(j)=2+5+8=1513，所以接受新解。 假设产生的新解j=(11010)， f(j)=2+5+3=1013，计算接受概率 P(T)=exp(10-13)/10)0.741， 产生一个随机数random(0,1)