模式识别：禁忌搜索与模拟退火算法20151019..pptx

2018/5/23
1
模式识别:模拟退火算法&禁忌搜索算法
Pattern Recognition
主讲人:胡雪梅
导师:黄岚
指导老师:王岩
时间:2015/10/19
模拟退火算法&禁忌搜索算法
模拟退火算法
禁忌搜索算法
模拟退火算法&禁忌搜索算法
模拟退火算法
源自于物理学锻造技术和退火现象,在1953 年由Metropolis 所提出来的。
固体物质退火过程与一般组合优化问题相似。
算法起源
之中,开始状态下物体的分子状态是无序的,然后进行高温处理,物体分子变得活跃并分散开来,到达最高温时内能最大,逐渐冷却时各个物体分子渐渐变得有序并开始寻找一个最佳平衡点,如果温度降得足够慢,那么到达最终态时内能将最小,分子将排列的最为有序。
退火过程
模拟退火算法就是模仿锻造技术的退火方法来找到整个解空间下的最终收敛状态以达到寻找最优解的目的。
算法基本思想
由初始解和控制参数的初值开始,对当前解重复“产生新解计算目标函数差判断是否接受接受或舍弃”的迭代,并逐渐衰减t值,算法终止时的当前解即为近似最优解。
算法步骤
(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′作为新的当前解,否则以Metropolis 准则接受S′作为新的当前解;(6) 如果满足终止条件则输出当前解作为最优解,结束程序; (7) T逐渐减少,且T->0,然后转第2步;
模拟退火算法&禁忌搜索算法
算法特点
与初始值无关,算法求得的解与初始解状态S无关;
以概率 l 收敛于全局最优解的全局优化算法;
模拟退火算法具有并行性;
模拟退火算法&禁忌搜索算法
算法应用实例
兔子醉酒
兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。
旅行商问题( TSP , Traveling Salesman Problem )
有N个城市,要求从其中某个问题出发,唯一遍历所有城市,再回到出发的城市,求最短的路线。
旅行商问题属于所谓的NP完全问题,精确的解决TSP只能通过穷举所有的路径组合,其时间复杂度是O(N!) 。
使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。模拟退火解决TSP的流程图如右所示:
模拟退火算法&禁忌搜索算法
基于模拟退火思想改进的K均值算法
K均值算法的局限性
聚类结果依赖于初始划分;
需事先指定聚类数目;
对“噪音”和孤立点敏感;
容易陷入局部最优;
改进K均值算法思想
将内能模拟为目标函数值,将K均值的聚类结果作为初始解,初始目标函数值作为初始温度,对当前解重复“产生新解计算目标函数差接受或舍弃新解”的迭代过程,并逐步降低温度值,算法终止时的当前解为近似最优解。
优点
采用了Metropolis准则,中间解以一点的概率跳出了局部极小,避免落入局部极小的可能,然后在退火温度的控制下找到最优解。
模拟退火算法&禁忌搜索算法
算法步骤与流程
模拟退火算法&禁忌搜索算法
禁忌搜索算法
概述
禁忌搜索(Tabu Search或Taboo Search,简称TS)的思想最早Glover(1986)提出,它是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。
为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目,不见泰山。禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。
关键术语
禁忌表、禁忌长度、适配值、邻域函数、候选解、禁忌准则、藐视准则
算法特点
优点:可以接受劣解,具有“爬山”能力;能够跳出局部最优解;。
缺点:对初始解依赖性比较强;迭代是串行的。
算法应用
置换问题,如TSP、调度问题
模拟退火算法&禁忌搜索算法
兔子找最高峰
兔子们找到了泰山,它们之中的一只就会留守在这里,其他的再去别的地方寻找。就这样,一大圈后,把找到的几个山峰一比较,珠穆朗玛峰脱颖而出。
当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表(tabu list)”的含义。
那只留在泰