第10章 模拟退火与禁忌搜索.ppt

文档介绍：模拟退火算法思想模拟退火算法思想模拟退火算法是什么?是怎样提出来的?模拟退火算法(Simulated Annealing,SA)是一种模拟物理退火的过程而设计的优化算法。它的基本思想最早在1953年就被Metropolis提出,但直到1983年Kirkpatrick等人才设计出真正意义上的模拟退火算法并进行应用。模拟退火算法的基本思想是怎样的?模拟退火算法采用类似于物理退火的过程,先在一个高温状态下(相当于算法随机搜索),然后逐渐退火,在每个温度下(相当于算法的每一次状态转移)徐徐冷却(相当于算法局部搜索),最终达到物理基态(相当于算法找到最优解)。 模拟退火算法思想模拟退火算法思想物理退火过程?物体内部的状态?状态的能量?温度?熔解过程?退火冷却过程?状态的转移?能量最低状态模拟退火算法?问题的解空间?解的质量?控制参数?设定初始温度?控制参数的修改?解在邻域中的变化?最优解物理退火过程模拟退火算法类比关系1010..2 2 =8,现有n=5个物品,它们的重量和价值分别是(2, 3, 5, 1, 4)和(2, 5, 8, 3, 6)。试使用模拟退火算法求解该背包问题,写出关键的步骤。求解:假设问题的一个可行解用0和1的序列表示,例如i=(1010)表示选择第1和第3个物品,而不选择第2和第4个物品。: 禁忌搜索算法思想禁忌搜索算法思想禁忌搜索算法是什么?禁忌搜索算法(Tabu Search,TS)是Glover于1986年提出的一种全局搜索算法。禁忌搜索算法的基本思想是怎样的?禁忌搜索是属于模拟人类智能的一种优化算法,它模仿了人类的记忆功能,在求解问题的过程中,采用了禁忌技术,对已经搜索过的局部最优解进行标记,并且在迭代中尽量避免重复相同的搜索(但不是完全隔绝),从而获得更广的搜索区间,有利于寻找到全局最优解。 禁忌搜索相关概念禁忌搜索相关概念禁忌表(Tabu List,TL)?是用来存放(记忆)禁忌对象的表。它是禁忌搜索得以进行的基本前提。禁忌表本身是有容量限制的,它的大小对存放禁忌对象的个数有影响,会影响算法的性能。禁忌对象(Tabu Object,TO)?是指禁忌表中被禁的那些变化元素。禁忌对象的选择可以根据具体问题而制定。例如在旅行商问题(Traveling Salesman Problem,TSP)中可以将交换的城市对作为禁忌对象,也可以将总路径长度作为禁忌对象。