Simulated Annealing Algorithm，SAA

Presentation on theme: "Simulated Annealing Algorithm，SAA"— Presentation transcript:

1 Simulated Annealing Algorithm，SAA
第四章 模拟退火算法 (II) Simulated Annealing Algorithm，SAA by 谢广明 ， ~2006学年度第一学期

2 内 容 SAA求解TSP SAA求解函数优化问题 SAA策略 SAA改进 SM-SA混合策略 GA-SA混合策略
内 容 SAA求解TSP SAA求解函数优化问题 SAA策略 SAA改进 SM-SA混合策略 GA-SA混合策略 by 谢广明 ， ~2006学年度第一学期

3 SAA求解TSP 具体实现相当简单 设定初始温度、终止温度，采用等比降温策略 能量函数直接取为目标函数 设定变异算子 设定热平衡迭代次数
设定相关参数 by 谢广明 ， ~2006学年度第一学期

4 SAA求解TSP 关键问题是变异算子 方式很多 理论已经证明上述所有方式都收敛 实际验证收敛性能差异很大 如何由旧的解产生新的解
相邻两位置对换——变动最小 任意两位置对换 单点位置移动 子排列位置移动 子排列反序 子排列位置移动且反序——变动最大 理论已经证明上述所有方式都收敛 实际验证收敛性能差异很大 by 谢广明 ， ~2006学年度第一学期

5 SAA求解TSP by 谢广明 ， ~2006学年度第一学期

6 SAA求解函数优化问题 具体实现相似，主要注意 能量函数根据具体目标函数需要调整 设定变异算子 设定热平衡迭代次数
by 谢广明 ， ~2006学年度第一学期

7 SAA策略 初温 变异算子 选择算子 降温策略 等温过程平衡准则 算法终止准则 by 谢广明 ， ~2006学年度第一学期

8 初温 初温 要足够高 实验表明，初温越高，获得高质量解的几率越大，但花费的计算时间将同时增加。 初温的确定应折衷考虑优化质量和优化效率。
by 谢广明 ， ~2006学年度第一学期

9 变异算子 一般叫做状态产生函数 设计状态产生函数(邻域函数)的出发点应该是尽可能保证产生的候选解遍布全部解空间。
状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。前者决定由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概率。候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生，而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、正态分布、指数分布、柯西分布等。 by 谢广明 ， ~2006学年度第一学期

10 选择算子 一般叫做状态接受函数 状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则： (1)在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率； (2)随温度的下降，接受使目标函数值上升的解的概率要逐渐减小； (3)当温度趋于零时，只能接受目标函数值下降的解。 by 谢广明 ， ~2006学年度第一学期

11 降温策略 实验表明降温速度越慢，获得高质量解的几率越大，但花费的计算时间将同时增加。
常用的等比策略：Tk+1=a ·Tk, a 为(0,1)中常数 温度高时下降的慢些，温度低时下降的快些 by 谢广明 ， ~2006学年度第一学期

12 等温过程平衡准则 一般叫做抽样稳定准则 常用的抽样稳定准则包括： 应与问题规模成比例
用于决定在各温度下产生候选解的数目。 常用的抽样稳定准则包括： (a)检验目标函数的均值是否稳定； (b)连续若干步的目标值变化较小； (c)按一定的步数抽样。 应与问题规模成比例 实验表明高温时迭代次数越多越好，低温时迭代次数可以适当减少 by 谢广明 ， ~2006学年度第一学期

13 终止条件 算法终止准则， SA算法的收敛性理论中，要求温度终值趋于零，这显然是不实际的。通常的做法包括： 用于决定算法何时结束
(b)设置外循环迭代次数 (c)算法搜索到的最优值连续若干步保持不变； (d)检验系统熵是否稳定。 by 谢广明 ， ~2006学年度第一学期

14 算法改进 改进各个环节： (1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。
(2)设计高效的退火历程。 (3)避免状态的迂回搜索。 (4)采用并行搜索结构。 (5)为避免陷入局部极小，改进对温度的控制方式。 (6)选择合适的初始状态。 (7)设计合适的算法终止准则。 by 谢广明 ， ~2006学年度第一学期

15 算法改进 增加新的环节： (1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，以激活各状态的接受概率，调整搜索进程中的当前状态，避免算法在局部极小解停滞不前。 (2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可增加存储环节，将“Best So Far”的状态记忆下来。 (3)增加补充搜索过程。在退火过程结束后，以搜索到的最优解为初始状态，再次执行SA过程或局部趋化性搜索。 (4)对每一当前状态，采用多种搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。 (5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。 (6)上述各方法的综合应用。 by 谢广明 ， ~2006学年度第一学期

16 TINA Time-invariant noise algorithm
变异算子中扰动强度不随时间改变，而是和能量大小相关，能量大的扰动大，能量小的扰动小，能量为零，扰动也为零，算法停止。 by 谢广明 ， ~2006学年度第一学期

17 MTRSA 单调升温(Monotonic temperature rising) SA
在算法退火后期，温度很低且陷入局部极小解的时，算法很难跳出。因此，可以适当重新提高温度，促使算法跳出。 by 谢广明 ， ~2006学年度第一学期

18 并行SA 并行SA 操作并行：各个环节同时处理 进程并行：同时多个算法运行 空间并行：解空间分解分别处理，最终组合
by 谢广明 ， ~2006学年度第一学期

19 FSA 快速SA 采用半全局的Cauchy-Lorentz跃迁分布代替原来局部性的Guass分布，使得新的状态可以有更大距离的跃迁
by 谢广明 ， ~2006学年度第一学期

20 SAMG 记忆指导SA(Simulated Annealing with Memmory Guidance ,简记为SAMG)
增加一个记忆装置，存储算法计算过程产生的最好的解，以这个解为最终解。 by 谢广明 ， ~2006学年度第一学期

21 自适应SA 自适应SA 算法, 特点： 根据邻域搜索进展的反馈信息, 自适应确定温度变化和邻域搜索强度
1) 退火过程中温度参数变化符合幅值递减的下降总趋势, 但不排除局部升温的可能, 以保证寻求到合适的温度序列, 避免陷入局部最优; 2) 算法的终止条件依据退火温度和邻域搜索进展状态设计; 3) 每一温度下算法的迭代次数随温度下降而递增, 邻域搜索强度依其对目标函数的贡献动态分配; 4) 温度变化、邻域搜索和终止条件的控制机制由算法过程自动触发。 by 谢广明 ， ~2006学年度第一学期

22 SMSA 单纯形算法(Simplex Method)-SA混合 SM 出发点 流程 总结 把传统的单纯形算法和SA结合起来
by 谢广明 ， ~2006学年度第一学期

23 SM 单纯形法(Simplex method，SM) 也称可变多面体搜索法，是一种传统的处理无约束最优化问题的直接算法.
算法首先在n欧氏空间中构造一个包含n+1个顶点的凸多面体，求出各顶点的函数值，并确定其中的最大值、次大值和最小值，然后通过反射、扩张、内缩、缩边等策略求出一个较好解，用之取代最大(差)点，从而构成新的多面体，如此多次迭代则可逼近一个性能较好的极小点。 by 谢广明 ， ~2006学年度第一学期

24 SM 单纯形法(Simplex method，SM)
Lagarias(1998)研究了SM方法求解低维函数时的收敛特性，但结论难以推广到高维问题，也即单一SM难以保证对高维复杂函数具有较好的优化效果。 by 谢广明 ， ~2006学年度第一学期

25 SMSA构造出发点 SMSA基本思想 任一给定初始解X0, 首先用单纯形法快速求得一个极小值点,
然后改用模拟退火法随机搜索, 跳离该局部极小值, 一旦找到一个比该极小值点更小的点时, 立即以该点为初始值调用单纯形法直接搜索该点附近的另一个极小值点, 如此交叉进行, 直到满足精度条件, 算法结束, 得到的结果必为目标函数的全局最小值。 by 谢广明 ， ~2006学年度第一学期

26 SMSA构造出发点 机制的融合：SM是确定性下降法，SA是基于随机分布的算法。
选择机制上存在如此差异的两种算法进行混合，有利于丰富优化中的搜索行为，增强全局和局部意义下的搜索能力和效率。 结构互补：SM始终由多个点进行搜索，SA则是串行单链的，两者混合可使SA成为并行算法。 by 谢广明 ， ~2006学年度第一学期

27 SMSA构造出发点 行为互补： 基于可变多面体结构的确定性SM收敛速度快，但易陷入局部极小点。
by 谢广明 ， ~2006学年度第一学期

28 SMSA构造出发点 削弱参数选择的苛刻性： 两者混合使算法各方面的搜索能力均有提高，因而对参数的选择不必过严。
SA对参数具有很强的依赖性，参数不合适将严重影响优化性能。SA的收敛条件导致参数选择较为苛刻，甚至不实用，设计时要通过大量试验和经验来确定。 两者混合使算法各方面的搜索能力均有提高，因而对参数的选择不必过严。 研究表明，混合算法采用单一算法相同参数时优化性能和鲁棒性均有大幅度提高，尤其对较大规模的复杂问题。 by 谢广明 ， ~2006学年度第一学期

29 SMSA流程 状态初始化，确定初温 确定最大点，次大点，最小点 Y 算法收敛准则满足否？ 输出结果 N 使用单纯形法求局部极小点
以概率接受新个体 SA抽样稳定否？ 退温操作 Y N SMSA流程 by 谢广明 ， ~2006学年度第一学期

30 SMSA总结 SM法对高维复杂函数的优化性能与初值鲁棒性均很差，它虽然是一种确定性方法，而且利用了可变多面体的空间结构，但对初始解和问题的依赖性较强，优化高维复杂函数很容易陷入局部极小。 单一SA尽管搜索行为概率可控，但在缺乏SM的定向搜索能力配合时，在极小点附近的趋化性搜索效果不好，初值鲁棒性也不理想。虽然性能较SM法有所改善，但仍不适于高维复杂函数的优化。 by 谢广明 ， ~2006学年度第一学期

31 SMSA总结 SMSA融合SM和SA两者的优点，包含了随机性搜索和确定性搜索，既有SA退火历程对搜索行为的控制，又有单纯形法可变多面体结构的几何指导，对高维复杂函数的优化表现出高精度的优化性能和很好的初值鲁棒性，是一种很有潜力的函数优化算法。 基于问题维数对算法性能影响的研究表明，SM和SA的优化质量和初值鲁棒性随问题维数的增加明显下降，而SMSA的优化性能对问题维数的增加具有较强的适应性。因此，对于低维函数，由于各类算法均能取得较满意的优化性能，建议采用SA或SM求解，以节省优化时间；但对高维复杂函数，建议采纳SMSA混合策略，以实现高精度和强初值鲁棒性的优化性能。 by 谢广明 ， ~2006学年度第一学期

32 GASA混合策略 构造出发点 流程 特点 效率分析 by 谢广明 ， ~2006学年度第一学期

33 GASA构造出发点 优化机制的融合 理论上，GA和SA两种算法均属于基于概率分布机制的优化算法。
对选择优化机制上如此差异的两种算法进行混合，有利于丰富优化过程中的搜索行为，增强全局和局部意义下的搜索能力和效率。 by 谢广明 ， ~2006学年度第一学期

34 GASA构造出发点 优化结构的互补 SA算法采用串行优化结构， GA采用群体并行搜索。
两者相结合，能够使SA成为并行SA算法，提高其优化性能；同时SA作为一种自适应变概率的变异操作，增强和补充了GA的进化能力。 by 谢广明 ， ~2006学年度第一学期

35 GASA构造出发点 优化操作的结合 SA算法的状态产生和接受操作每一时刻仅保留一个解，缺乏冗余和历史搜索信息；
这些不同作用优化操作的相结合，丰富了优化过程中的邻域搜索结构，增强了全空间的搜索能力。 by 谢广明 ， ~2006学年度第一学期

36 GASA构造出发点 优化行为的互补 由于复制对当前种群外的解空间无探索能力，种群中各个体分布“畸形”时交叉的进化能力有限，小概率变异很难增加种群的多样性。所以，若算法收敛准则设计不好，GA经常会出现进化缓慢或“早熟”收敛的现象。 SA的优化行为对退温历程具有很强的依赖性，而理论上的全局收敛对退温历程的限制条件很苛刻，因此SA优化时间性能较差。 两种算法结合，SA的两准则可控制算法收敛性以避免出现“早熟”收敛现象，并行化的抽样过程可提高算法的优化时间性能。 by 谢广明 ， ~2006学年度第一学期

37 GASA构造出发点 削弱参数选择的苛刻性 SA和GA对算法参数具有很强的依赖性，参数选择不合适将严重影响优化性能。
研究表明，混合算法在采用单一算法参数时，优化性能和鲁棒性均有大幅度提高，尤其对较大规模的复杂问题。 by 谢广明 ， ~2006学年度第一学期

38 得到SA的初始种群，对种群中各个体i=1~Pop_size进行SA搜索
给定算法参数 初始化种群，确定初温 评价当前种群中各个体 算法收敛准则满足否？ 执行GA的选择复制操作 执行GA的交叉操作(附带保优操作) 执行GA的变异操作(附带保优操作) 得到SA的初始种群，对种群中各个体i=1~Pop_size进行SA搜索 输出优化结果 由SA状态产生函数产生新个体 以概率接受新个体 SA抽样 稳定否？ 退温操作 Y N GASA流程 by 谢广明 ， ~2006学年度第一学期

39 GASA特点 是标准GA、SA以及并行SA算法的统一结构
若在GASA混合策略中移去有关SA的操作，则混合策略转化为GA算法；若移去GA的进化操作，则转化为并行SA算法；进一步，若置种群数为1，则转化为标准SA算法。 by 谢广明 ， ~2006学年度第一学期

40 GASA特点 GASA混合策略是一个两层并行搜索结构
进程层次上，混合算法在各温度下串行地依次进行GA和SA搜索，是一种两层串行结构。其中，SA的初始解来自GA的进化结果，SA经Metropolis抽样过程得到的解又成为GA进一步进化的初始种群。 空间层次上，GA提供了并行搜索结构，使SA转化成为并行SA算法，因此混合算法始终进行群体并行优化。 by 谢广明 ， ~2006学年度第一学期

41 GASA特点 GASA混合策略利用了不同的邻域搜索结构
复制有利于优化过程中产生优良模态的冗余信息，交叉有利于后代继承父代的优良模式，高温下的SA操作有利于优化过程中状态的全局大范围迁移，变异和低温下的SA操作有利于优化过程中状态的局部小范围趋化性移动，从而增强了算法在解空间中的探索能力和效率。 by 谢广明 ， ~2006学年度第一学期

42 GASA特点 GASA混合策略的搜索行为是可控的 混合策略的搜索行为，可通过退温历程(即初温、退温函数、抽样次数)加以控制。
控制初温，可控制算法的初始搜索行为；控制温度的高低，可控制算法突跳能力的强弱，高温下的强突跳性有利于避免陷入局部极小，低温下的趋化性寻优有利于提高局部搜索能力； 控制温度的下降速率，可控制突跳能力的下降幅度，影响搜索过程的平滑性；控制抽样次数，可控制各温度下搜索能力，影响搜索过程对应的齐次马氏链的平稳概率分布。这种可控性增强了克服GA易“早熟”收敛的能力。算法实施时，退温历程还可引入可变抽样次数、“重升温”等高级技术。 by 谢广明 ， ~2006学年度第一学期

43 GASA特点 GASA混合策略利用了双重终止准则
by 谢广明 ， ~2006学年度第一学期

44 GASA特点 取长补短 在优化机制、结构和行为上，GASA混合优化策略均结合了GA和SA的特点，使两种算法的搜索能力得到相互补充，弥补了各自的弱点，它是一种优化能力、效率和可靠性较高的优化方法。对于存在多极小的复杂优化问题，混合策略的优化性能将体现出更明显的优越性。 by 谢广明 ， ~2006学年度第一学期

45 GASA效率分析 优化性能(避免陷入局部极小的能力)提高
此外，进化计算方法中为提高全局收敛效率，复制操作时自然希望适配值高的状态得以较大的生存概率。但是，不难理解，过强的复制操作将使种群过分地吸引到局部极小解。 by 谢广明 ， ~2006学年度第一学期

46 GASA效率分析 优化性能(避免陷入局部极小的能力)提高
混合算法中SA的嵌入是对GA变异的一种有效补充，赋予优化过程在各状态具有可控的概率突跳特性，尤其在高温时使得算法具有较大的突跳性，是避免局部极小的有力手段，加大了打破上述僵局的可能，也减弱了GA对算法参数的过分依赖性。 在温度较低时SA算法演变为几乎是概率1的保优变异操作，Metropolis抽样过程将实现很强的趋化性局部搜索。而相对SA而言，混合策略又实行群体并行优化。所以，混合策略的优化性能，尤其是避免陷入局部极小的能力，必然提高。 by 谢广明 ， ~2006学年度第一学期

47 GASA效率分析 优化效率提高 混合策略中引入GA，使得SA串行搜索转化为多点并行搜索。而GA和SA各自不同的邻域搜索结构相结合，使得算法在解空间中的探索能力和范围均有所提高，因此优化效率必然比SA高。 by 谢广明 ， ~2006学年度第一学期

48 GASA效率分析 鲁棒性提高 相对SA而言，GASA混合策略的多点搜索必然削弱算法对初值的依赖性；相对GA而言，混合策略的搜索行为可通过控制温度参数而加以控制，且理论上GA并不影响平稳分布，因此鲁棒性也将提高。 但是，初值对算法效率有一定的影响，同时考虑到通用GA和SA算法对问题信息的无依赖性，虽然随机选取初值的方法比较简单且很常用，但在处理不同问题时建议不妨利用问题信息或启发式方法构造一些解作为混合策略的初始种群，以取得良好的搜索效率。 by 谢广明 ， ~2006学年度第一学期

49 GASA总结 GASA混合策略可描述为：GA利用SA得到的解作为初始种群，通过并行化遗传操作使种群得以进化；SA对GA得到的进化种群进行进一步优化，温度较高时表现出较强的概率突跳性，体现为对种群的“粗搜索”，温度较低时演化为趋化性局部搜索算法，体现为对种群的“细搜索”。这种混合不仅是算法结构上的，而且是搜索机制和进化思想上的相互补充，为较好解决复杂优化问题提供了有力的途径。 类似可以有EP-SAA, ES-SAA混合 by 谢广明 ， ~2006学年度第一学期