禁忌搜索算法

汇报人：禁忌搜索算法禁忌搜索算法概述禁忌搜索算法原理0102目录CONTENTS禁忌搜索算法概述01优化算法的分类优化算法的分类精确算法(绝对最优解)精确算法包括线性规划、动态规划、整数规划和分支定界法等运筹学中的传统算法，其算法计算复杂性一般很大，只适合于求解小规模问题，在工程中往往不实用。启发式算法（近似算法）启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。爬山算法算法思想：从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。背景介绍禁忌搜索（tabusearch，TS）中的Tabu一词最早来源于汤加语，它的本意是指不能触摸的东西。禁忌也就是禁止重复前面的操作.禁忌搜索由美国科罗拉多大学系统科学家Glover教授于1986年在一篇论文中首次提出。之后不久，Glover教授分别在1986年和1990年发表了两篇著名的标题为Tabusearch的论文，提出了现在大家所熟知的禁忌搜索的大部分原理。禁忌搜索的流行应归功于瑞士联邦理工学院Werra教授所带领的团队在20世纪80年代后期的开创性工作。因为在当时Glover的文章在没有”超启发式文化”的情况下并没有被很好地理解。正是由于Werra团队所发表的系列论文在学术界发挥的重要作用，才使禁忌搜索技术广为人知。1990年，随着介绍禁忌搜索的第一本专著的出版，禁忌搜索的研究达到了一个高峰。1997年，Glover与Laguna合著的第一本禁忌搜索专著正式出版，标志着禁忌搜素的相关研究日趋完善，并得到了同行的认可。相关概念禁忌算法(TabuSearch，TS)基本思想：基于爬山算法的改进，标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而获得更多的搜索区域。算法举例为了找出地球上最高的山，一群有志的兔子们开始想办法。算法举例兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表”（tabulist）的含义。那只留在秦山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，秦山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度”（tabulength）；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“bestsofar”的状态，就可以不顾及有没有兔子留守，就把这个地方考虑进来，这就叫“特赦准则”（aspirationcriterion）构成要素（1）评价函数（EvaluationFunction）：评价函数是用来评价邻域中的邻居、判断其优劣的衡量指标。大多数情况下，评价函数为目标函数。但自定义的形式也可存在，算法也可使用多个评价函数，以提高解的分散性（区分度）。（2）邻域移动（MoveOperator）：邻域移动是进行解转移的关键，又称“算子”，影响整个算法的搜索速度。邻域移动需要根据不同的问题特点来自定义，而整个邻近解空间是由当前解通过定义的移动操作构筑的所有邻域解构成的集合。（3）禁忌表（TabuTable）：禁忌表记录被禁止的变化，以防出现搜索循环、陷入局部最优。对其的设计中最关键的因素是禁忌对象（禁忌表限定的对象）和禁忌步长（对象的禁忌在多少次迭代后失效）禁忌表是禁忌搜索算法的核心，禁忌表的对象、步长及更新策略在很大程度上影响着搜索速度和解的质量。若禁忌对象不准确或者步长过小，算法避免陷入局部最优的能力会大打折扣；若禁忌表步长过大，搜索区域将会限制，好的解就可能被跳过。构成要素禁忌长度：禁忌表中所能接受的最多禁忌对象的数量禁忌步长：对象的禁忌在多少次迭代后失效（4）邻居选择策略（NeighborSelectionStrategy）：选择最佳邻域移动的规则。目前最广泛采用的是“最好解优先策略”及“第一个改进解优先策略”。前者需比较所有邻域，耗时较久，但解的收敛更有效；后者在发现第一个改进解就进行转移，耗时较少，但收敛效率弱于前者，对于邻域解空间较大的问题往往比较适合。构成要素（5）特赦准则（AspirationCriterion），又称藐视准则：通俗定义：对于在禁忌的对象，如果出现以下情况，不论现在对象的禁忌长度如何，均设为01.基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特救；2.基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；3.基于影响力的规则，可以特赦对目标值影响大的对象。（6）终止规则（StopCriterion）：禁忌算法是一个启发式算法，我们不可能让搜索过程无穷进行，所以一些直观的终止规则就出现了1.确定步数终止，无法保证解的效果，应记录当前最优解；2.频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；3.目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。拓展(1)兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法。(2)兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处,也可能踏入平地。但是,他渐渐清醒了并朝他踏过的最方向跳去。这就是模拟退火算法。(3)兔子们吃了失忆药片，并被发射到太空,然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是,如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。(4)一群兔子朝着各处跳去，去了最高处山的兔子发出信号影响周围的兔子朝它跳去。慢慢最高的山去了越来越多的兔子，直到所有兔子全都集中在最高峰。这就是蚁群算法。禁忌搜索算法原理02算法流程算法实例四城市非对称TSP问题初始解x0=（ABCD），f（x0）=4，邻域映射为两个城市顺序对换的2-opt，始、终点都是A城市。算法实例禁忌长度为3禁忌对象以及长度H=[]四城市非对称TSP问题第一步：初解：ABCDA，f=4采用2-opt算法产生候选解集变换CD→ABDCA4.5最优解BC→ACBDA7.5BD→ADCBA8算法实例四城市非对称TSP问题第二步：最优解：ABDCA，f=4.5采用2-opt算法产生候选解集禁忌对象以及长度H=[（CD，3）]变换CD→ABCDA4禁忌解BC→ACDBA3.5最优解BD→ADBCA4.5算法实例四城市非对称TSP问题第三步：最优解：ACDBA，f=3.5采用2-opt算法产生候选解集禁忌对象以及长度H=[（CD，2）（BC，3）]变换CD→ADCBA8禁忌解BC→ABDCA4.5禁忌解BD→ACBDA7.5最优解算法实例四城市非对称TSP问题第四步：最优解：ACBDA，f=7.5采用2-opt算法产生候选解集禁忌对象以及长度H=[(CD,1)(BC,2)(BD,3)]变换CD→ADBCA4.5禁忌解BC→ABCDA4禁忌解BD→ACDBA3.5禁忌解达到禁忌长度，禁忌长度为3时解为min（4，4.5，3.5，7.5}算法实例四城市非对称TSP问题第四步：最优解：ACBDA，f=7.5采用2-opt算法产生候选解集禁忌对象以及长度H=[(CD,0)(BC,1)(BD,2)]CD解禁变换CD→ADBCA4.5最优解BC→ABCDA4禁忌解BD→ACDBA3.5禁忌解当禁忌对象及长度为2时算法实例四城市非对称TSP问题第五步：最优解：ADBCA，f=4.5采用2-opt算法产生候选解集禁忌对象以及长度H=[(CD,2)(BC,0)(BD,1)]BC解禁变换CD→ACBDA7.5禁忌解BC→ADCBA8最优解BD→ABDCA4.5禁忌解当禁忌对象及长度为2时回到了步骤1的候选集，结束迭代，至此搜索完毕，禁忌长度为2的解为min（4，4.5，3.5，7.5，4.5，8）谢谢观看