禁忌搜索算法

禁忌搜索算法TABUSEARCH(TS)汇报人：张翠芝小组成员：张翠芝蒋培祥田木易目录•1引言•2算法概述（案例导入）•2.1什么是禁忌算法•2.2禁忌算法基本步骤•2.3禁忌算法主要构成要素•2.4案例分析-旅行商问题•2.5禁忌搜索算法流程•3禁忌算法搜索总结•3.1局部邻域搜索及优劣性•3.2禁忌搜索算法特点•3.3禁忌搜索算法的改进方向•优化问题相关算法01引言1.引言一个问题的求解过程就是搜索，它是人工智能的一个基本问题，而人工智能在各应用领域中被广泛的使用。搜索技术渗透在各种人工智能系统，可以说没有哪一种人工智能的应用不用搜索方法。1.引言●TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。●相对于遗传算法，TS是另一种搜索特点不同的算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。所谓禁忌，就是禁止重复前面的操作。为改进局部邻域搜索容易陷入局部最优的不足，禁忌搜索算法引入一个禁忌表，记录已搜索过的局部最优点，在下一次搜索中，对禁忌表中的信息不再搜索或有选择的搜索，以跳出局部最优点，实现全局最优化。禁忌搜索算法是一种全局邻域搜索、逐步寻优的算法。禁忌搜索算法是一种迭代搜索算法，其显著特点是利用记忆来引导算法的搜索过程，是对人类智力过程的一种模拟，是人工智能的一种体现。02算法概述启发式算法蕴含的人生哲学:兔子寻找世界上最高的山•■兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法，它不能保证局部最优值就是全局最优值。•■兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火。•■兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略，这就是禁忌搜索。禁忌搜索算法:兔子寻找世界上最高的山•兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。当兔子们再寻找时，一般地会有意识地避开泰山，因为他们知道，这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表(tabulist)”的含义。•那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度(tabulength)”;•如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“bestsofar”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“藐视准则(aspirationcriterion)”。•这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。爬山算法（第一天）•今天的任务是去给山顶的人家化斋，在爬山算法的帮助下，终于顺利爬到了最高点！阿弥陀佛~~图中小人0为当前所在位置（算法初始解）；在二维空间中，他可选择向左一步或向右一步（小红人1、2，PS：邻域），因为2的高度大于1，故他选择向右挪动（邻域选择）；持续该过程（算法迭代），他将到达小人3的位置，此时向左或向右，都无法进一步变高，故认定已到最高点，停止攀登（算法最优解）。爬山算法（第二天）•化斋任务第一阶段结束~继续前行，下一个任务是去给隔壁山顶的人家化斋。可是，我在半山坡的地方使用爬山算法，怎么每次都会回到原先那户人家啊，阿弥陀佛，谁可以告诉我是哪里出了错吗？由于他一直遵循Hill-climbing算法，故这次登顶的结果会和第一次（小人1）一样（算法陷入局部最优）；但站在上帝视角的我们看来，如果小和尚先下山，再上山，爬到另一座山的山顶（小人2），会到达一个更好的位置。爬山算法（第三天）•使用禁忌搜索算法后，妈妈再也不用担心我找不到人家了，阿弥陀佛~上帝这次创建小和尚时，倒了一点禁忌搜索（TabuSearch）算法。小和尚在半山腰时想再次尝试爬山，他发现之前走的路被自己标记了“禁止通行”的路标（禁忌策略），故成功的完成了先下后上的爬山过程，达到了更高的山峰。禁忌搜索（第四天）•阿弥陀佛，还好有破禁准则在...不然禁忌策略用不好，一辈子别想登顶了...设置路标的方式多种多样（禁忌策略的设置对算法效率影响很大），这里小和尚设置的标准为方向。当小和尚从当前山顶下到半山腰（小人0），他设置了禁止左行的标记。但在半山腰向左抬头看，他发现当前山峰的左侧有一座更高的，故忽略标记（藐视准则），向左爬行，到达最高点。此外，禁止标记也不应无限存在，以防对解空间的限制过大。一般情况下是其过一段时间（禁忌长度）后自动消失。2.1什么是禁忌搜索算法？•禁忌搜索算法（TabuSearchAlgorithm，简称TS）起源于对于人类记忆功能的模仿，是一种元启发式算法(meta-heuristics)。它从一个初始可行解(initialfeasiblesolution)出发，试探一系列的特定搜索方向(移动)，选择让特定的目标函数值提升最多的移动。为了避免陷入局部最优解，禁忌搜索对已经经历过的搜索过程信息进行记录，从而指导下一步的搜索方向。•禁忌搜索是人工智能的一种体现，是局部搜索的一种扩展。禁忌搜索是在邻域搜索(localsearch)的基础上，通过设置禁忌表（tabulist）来禁忌一些曾经执行过的操作，并利用藐视准则来解禁一些优质解。2.2禁忌搜索算法基本步骤•①初始化•利用贪婪算法等局部搜索算法生成一个初始解，清空禁忌表，设置禁忌长度。•②邻域搜索产生候选解•根据步骤①产生初始解，通过搜索算子（searchoperators），如relocation、exchange、2-opt等，产生候选解(candidatesolution)，并计算各个候选解的适应值（即解对应的目标函数值）。•③选择最好的候选解•从步骤②产生的所有候选解中选出适应值最好的候选解，将其与当前最好解(即搜索算法开始到现在找到的最好解)进行比较，如果优于当前最好解，那么就不考虑其是否被禁忌，用这个最好的候选解来更新当前最好解，并且作为下一个迭代的当前解，然后将对应的操作加入禁忌表；如果不优于当前最好解，就从所有候选解中选出不在禁忌状态下的最好解作为新的当前解，然后将对应操作加入禁忌表。•④判断终止条件•若满足终止条件，则立即停止并输出当前最好解；否则继续搜索。一般终止条件为是否到达一定的迭代次数或者达到了一个时间限制。算法流程2.3TS主要构成要素（1）适配值函数（EvaluationFunction）：适配值函数是用来评价邻域中的邻居、判断其优劣的衡量指标。大多数情况下，适配值函数为目标函数。如果目标函数的计算比较困难或耗时较多，可以以反应问题目标的某些特征值作为适配值，选择何种特征值要视具体问题而定，但必须保定特征值的最佳性与目标函数的最佳性一致。（2）邻域移动（MoveOperator）：邻域移动是进行解转移的关键，又称“算子”，影响整个算法的搜索速度。邻域移动需要根据不同的问题特点来自定义，而整个邻近解空间是由当前解通过定义的移动操作构筑的所有邻域解构成的集合。（3）禁忌表（TabuTable）：禁忌表记录被禁止的变化，以防出现搜索循环、陷入局部最优。对其的设计中最关键的因素是禁忌对象（禁忌表限定的对象）和禁忌步长（对象的禁忌在多少次迭代后失效）。禁忌表是禁忌搜索算法的核心，禁忌表的对象、步长及更新策略在很大程度上影响着搜索速度和解的质量。若禁忌对象不准确或者步长过小，算法避免陷入局部最优的能力会大打折扣；若禁忌表步长过大，搜索区域将会限制，好的解就可能被跳过。2.4TS主要构成要素•（4）邻居选择策略（NeighborSelectionStrategy）：选择最佳邻域移动的规则。目前最广泛采用的是“最好解优先策略”及“第一个改进解优先策略”。前者需比较所有邻域，耗时较久，但解的收敛更有效；后者在发现第一个改进解就进行转移，耗时较少，但收敛效率弱于前者，对于邻域解空间较大的问题往往比较适合。•（5）禁忌准则（AspirationCriterion）：标记对应已搜索的局部最优解的一些对象，将这些已经搜索过的对象设定为禁忌状态，在进一步的迭代搜索中不考虑处于禁忌状态的解，尽量避开这些对象（而不是绝对禁止循环），避免迂回搜索，从而保证对不同的有效搜索途径的探索，是一种局部极小突跳的全局逐步寻优算法。•（6）藐视准则：藐视准则是对优良状态的奖励，它是对禁忌策略的一种放松。在禁忌搜索算法中，如果存在优于「bestsofar」状态的禁忌候选解，则将最优禁忌候选解从禁忌表中解禁；或者可能出现候选解全部被禁忌的情况，此时藐视准则将使最优禁忌候选解从禁忌表中解禁，以实现更高效的优化性能。•（7）停止规则（StopCriterion）：禁忌搜索中停止规则的设计多种多样，如最大迭代数、算法运行时间、给定数目的迭代内不能改进解或组合策略等等。•例题1旅行商问题（TSP）下面我们以TSP问题为例说明介绍这些组成部分：如下图所示，有5个城市，任何两个城市之间的距离都是确定的，现要求一个旅行商从某城市出发必须经过每个城市一次且仅有一次，最后回到出发的城市，问如何确定一条最短的线路(每条边的长度已在图中标出)？•1.构造初始解如下图所示2.初始解对应的适应值为•3.搜索算子：(邻域搜索产生候选解)•（1）Relocation算子•该算子在当前解中选择并移除一个节点(node)，然后再选择一个位置将选中的节点插入。如图所示，当前解中选择节点2，再选择插入位置节点3（之后），执行后得到候选解，此时适应值变化量为•（2）Swap算子•该算子在当前解中同时选择两个不同的节点，然后对这两个节点的位置交换。如图所示，当前解中选择节点2和4，再对这两个节点交换位置，执行后得到候选解2，此时适应值变化量为•（3）Neighborhood算子：从当前解对一系列的搜索方向进行一次试探（通过算子搜索一次）能得到的所有解的集合，即仅经过一次操作能得到的所有解如上图所示，通过3中搜索算子搜索一次得到的候选解的集合即为当前邻域。如果x=(1,2,3,4)，则C42=6，N(x)={(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}•4.禁忌表（TabuList）：记录当前所选择操作的状态变化，一般包括禁忌对象和禁忌长度。在初始解的邻域中，候选解10为所有候选解中改进最大的解（即|ΔF|最大，ΔF=-2）。因此，候选解10被选中作为下一个迭代的当前解，则禁忌对象如上图所示。5.禁忌长度（TabuTenure）：禁止在之后的k次迭代中对禁忌表中所记录的状态进行改变，这里的k即称为禁忌长度。6.候选解（CandidateSolution）：当前邻域中的解。7.藐视准则（AspirationCriterion）：从候选解集合中挑选出最好的候选解，将其与当前最好解进行比较，若其是被禁止的解但是优于当前最好解，那么就将其解禁，用来作为下一迭代的当前解并替代当前最好解。藐视准则防止了因为禁忌表的存在，而错过优质解的情况出现。例：4城市非对称TSP问题初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市，禁忌长度选取3。邻域映射为2－opt，即x中的两个元素进行对换禁忌搜索案例2禁忌搜索案例2局部邻域搜索第1步解的形式禁忌对象及长度候选解f(x0)=4ABCDBCDABC对换评价值CD4