禁忌搜索算法

启发式搜索算法与传统的方法

Tabu Search是由美国科罗拉多州大学的Fred Glover教授在1977年左右提出来的,是一个用来跳出局部最优的搜寻方法。在解决最优问题上,一般区分为两种方式,一种是传统的方法,就是穷举法、贪婪法、分治法、动态规划等等;而另一种方法则是一些启发式搜索算法。
而这两种方法最大的不同点就在于使用传统的方法,我们必须对每一个问题都去设计一套算法,一旦我们遇到一个新的问题,整个算法就得重新设计,所以相当不方便,也缺乏广泛性。可是相对的好处就是一旦我们可以证明算法的正确性,那么我们就可以保证找到的答案一定是最优的。而对于启发式算法,针对不同的问题,我们可以套用同一个架构来寻找答案,在这个过程中,我们只需要设计评价函数以及如何找到下一个可能解的函数等等,所以启发式算法的广泛性比较高,但相对在准确度上就不一定能够达到最优。因为启发式算法的架构使得它可以很快接近最优解,但却不能保证找到的解一定是最优解。不过在现实中,我们所遇到的问题越来越复杂,一个问题牵涉的量也很多,如果根据传统的方法来设计算法,往往都必须要将问题简化了才有办法达成目标,然而,简化后的模型求出的最优解往往比对完整问题求出的近似解更不合事实。

禁忌搜索与局部邻域搜索

禁忌搜索是对局部邻域搜索的一种扩展,是一种全局逐步寻求最优算法。禁忌搜索算法中充分体现了集中和扩散两个策略,它的集中策略体现在局部搜索,即从一点出发,在这点的邻域内寻求更好的解,以达到局部最优解而结束,为了跳出局部最优解,扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息,算法通过对禁忌表中点的禁忌,而达到一些没有搜索的点,从而实现更大区域的搜索。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索,虽然算法通用易实现,且容易理解,但搜索性能完全依赖于邻域结构和初解,尤其会陷入局部极小而无法保证全局优化型。针对局部邻域搜索,为了实现全局优化,可尝试的路径有:以可控性概率接受劣解来跳出局部极小,如模拟退火算法;扩大邻域搜索结构,如TSP的2-opt扩展到k-opt,还有就是TS的禁忌策略尽量避免迂回搜索,它是一种确定性的局部极小跳出策略。

禁忌搜索的影响因素

简单的禁忌搜索是在局部邻域搜索的基础上,通过设置禁忌表来禁忌一些已经历的操作,并利用特赦准则来奖励一些优良状态,其中邻域结构、候选解、禁忌长度、禁忌对象、特赦准则、终止准则等是影响禁忌搜索算法性能的关键。

  1. 首先,由于TS是局部邻域搜索的一种扩充,因此邻域结构设计很关键,它决定了当前解的邻域解的产生形式和数目以及各个解之间的关系。
  2. 其次,出于改善算法的优化时间性能考虑,如果邻域结构决定了大量的邻域解,则可仅尝试部分解互换的结构,而候选解也仅去其中的少量最佳状态(如TSP中可能会产生 个邻域解)。
  3. 禁忌长度是一个很重要的关键参数,它决定禁忌对象的禁忌时间,其大小直接影响整个算法的搜索进程和行为。禁忌对象的替换可以采用FIFO方式,即先进先出,也可以采用其他方式甚至是动态自适应的方式。
  4. 特赦准则的设置是算法避免遗失优良状态,激励对优良状态的局部搜索,进而实现全局优化的关键步骤。
  5. 对非禁忌候选状态,算法无视它与当前状态的适配值的优劣关系,仅考虑它们中间的最佳状态为下一步决策,如此可实现对局部极小的跳出。
  6. 为了使算法具有优良的性能或时间性能,必须设置一个合理的终止准则来结束整个搜索过程。
    此外,在许多场合禁忌对象的被禁次数越多也被用于搜索,以取得更大的搜索空间。禁忌次数越高,通常可认为出现循环搜索的概率越大。

    TS的特点

  7. 从移动规则看,每次只与最优点比较,而不与经过点比较,故可以爬出局部最优。
  8. 选优规则始终保持曾经达到的最优点,所以即使离开了全局最优点也不会失去全局最优性。
  9. 终止规则不以达到局部最优为终止规则,而以最大迭代次数、出现频率限制或者目标值偏离成都为终止规则。

    解读

    禁忌——禁止重复前面的工作。
    跳出局部最优点