禁忌搜索算法-详解.docx

禁忌搜索算法-详解
 
   
 
 
 
 
 
 
 
     
 
 
 
 
 
禁忌搜索算法（Tabu Search/Taboo Search，简称TS算法）
目录
1 什么是禁忌搜索域解），则可以仅尝试部分互换的结果，而候选解也仅取其中的少量最佳状态。
　　（3）禁忌长度是一个很重要的关键参数，它决定禁忌对象的任期，其大小直接进而影响整个算法的搜索进程和行为。同时，以上示例中，禁忌表中禁忌对象的替换是采用FIFO方式（不考虑藐视准则的作用），当然也可以采用其他方式，甚至是动态自适应的方式。
　　（4）藐视准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。
　　（5）对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种确定性策略）。
　　（6）为了使算法具有优良的优化性能或时间性能，必须设置一个合理的终止准则来结束整个搜索过程。
　　此外，在许多场合禁忌对象的被禁次数（frequency）也被用于指导搜索，以取得更大的搜索空间。禁忌次数越高，通常可认为出现循环搜索的概率越大。
禁忌搜索算法的流程[1]
　　通过上述示例的介绍，基本上了解了禁忌搜索的机制和步骤。简单TS算法的基本思想是：给定一个当前解（初始解）和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优
劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。
　　条理化些，则简单禁忌搜索的算法步骤可描述如下：
　　（1）给定算法参数，随机产生初始解x，置禁忌表为空。
　　（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。
　　（3）利用当前解工的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。
　　（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤。
　　（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。
　　（6）转步骤（2）。
禁忌搜索算法流程的特点[1]
　　与传统的优化算法相比，TS算法的主要特点是：
　　（1）在搜索过程中可以接受劣解，因此具有较强的“爬山”能力；
　　（2）新解不是在当前解的邻域中随机产生，而或是优于“best so far”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。由于TS算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他