禁忌搜索算法

1.禁忌搜索算法预备知识

1.1 预备知识1—解空间

  对于一个组合优化问题来说，解空间定义为：任一可能（可行）解可以访问的搜索空间。
  举个例子:对于n个城市的旅行商问题来说，一个解可以用自然数序列{1,2,…,n}的某种排列来表达，于是解空间则是由该自然数序列的所有排列组合构成。
  假如有是基于四个城市的Tsp问题，那么{1,2,3,4}、{2,3,1,4}都是该问题的TSP的解。

1.2.预备知识2—邻域

  令S表示组合优化问题的一个解，则其邻域N(S)可以定义为：S执行一次邻域移动可以访问的所有解的集合。
  举例：对于4个城市的旅行商问题来说，采用上述的基于排列的解表达方法，邻域移动定义为 2-opt，即对S中2个元素进行对换S=(1,2,3,4)，则领域N(S)={(2,1,3,4), (3,2,1,4), (4,2,3,1), (1,3,2,4),(1,4,3,2), (1,2,4,3)}

2.禁忌搜索算法实现过程

2.1.禁忌搜索算法思想

  人类在选择过程中具有记忆功能，比如走迷宫时，当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性，这样就可以确定性的避开迂回搜索，所以禁忌搜索的一个比较重要的思想就是能够通过接受劣解来逃离局优，这样就不容易陷入局部最优的困境。

2.2.禁忌搜索构成要素

2.2.1.搜索结果表达

  ① 采用恰当的数据结构来表示问题的解。
  ② 初始解的产生：随机产生或者采用启发式方法产生一个初始解。
  ③ 适值函数的构造：往往直接将目标函数作为适值函数。

2.2.2.邻域移动策略

  ① 组合优化问题中邻域移动可以定义为某种排列置换
  ② 邻域移动定义是灵活的，目的是便于搜索
  $\bullet$局部搜索：当前解附近区域搜索
  $\bullet$全局搜索：远离当前解区域搜索

2.2.3.禁忌表引入

  禁忌表(T表)的引入就是为了防止搜索出现循环，如果出现循环算法可能就陷入了一定的"困境"，根据TS算法的核心思想，宁可选择劣解也不进入循环或局部最优的情况。
  禁忌表(T)的使用规则如下所示:
  ① 将移动作为禁忌对象
  ② 表的长度称为Tabu-Size，可以用来控制局域搜索和广域搜索。
  ③ 表是动态更新的：把最新的解记入，最老的解从表中释放(解禁)。

2.2.4.禁忌搜索选择策略

  选择策略需要满足以下两个要求:
  ① 当前解S每一步总是移动到邻域N(S)中未被禁忌的最优。
  ② 为了保证算法具有跳出局优的能力。

2.2.5.禁忌搜索渴望水平

  渴望水平就是破禁的临界值，如果当前的解达到(大于/小于看题目要求)当前渴望水平，则当前的邻域移动不受T表的限制，主要是为了实现的破禁的目的。
  ① 若被禁忌的邻域移动会使当前解达到超出渴望水平的要求，则这种邻域移动将不受T表限制
  ② 渴望水平一般选取为历史上所能达到的最优函数值，其主要目的是为了破禁。

2.2.6.禁忌搜索停止准则

  任何优化方法都有自己的停止准则，一般来说就涉及以下三种情况:
  ① 设定最大迭代次数(最大迭代次数之后不再迭代)
  ② 得到满意解(获得最优解之后停止)
  ③ 若干次迭代未获得更好的解(在一定迭代次数内最优解的值没有变化则选择停止)

2.3.禁忌搜索伪代码

2.3.1.定义禁忌搜索

  %%参数定义
  $S:$当前解
  $S^{\ast }$: 当前最优解
   $f^{\ast }$: 当前最优函数值
  $N(S):S$的邻域
  $\tilde{N}(S):N(S)$的可行子集 (未被禁忌以及突破渴望水平的邻域解)
  $T:$ 禁忌表

2.3.2.初始化与迭代过程

   %%初始化
  产生(或构造)一个初始解$S_0$; 令$S\leftarrow S_0,f^{\ast }\leftarrow f(S_0),S^{\ast }\leftarrow S_0,T\leftarrow \varnothing ;$

  %%送代过程
  While 停止条件不被满足 do
  令$S\leftarrow {\mathrm{argmin}}_{S^{\prime }\in \tilde{N}(S)}[f(S^{\prime })];$
  若$f(S)<f^{\ast }$,则令$f^{\ast }\leftarrow f(S),S^{\ast }\leftarrow S;$
  更新禁忌表$T;$
  Endwhile.

3.禁忌搜索算法应用

  先给定全国31个省会城市的坐标，请你基于禁忌搜索方法方法求解遍历31个省会坐标的最短路径长度，并且给出搜索的过程图片，设矩阵C是31行2列的矩阵，其中每行包含一个省会城市坐标，矩阵C如下所示:

  C = [1304 2312; 3639 1315; 4177 2244; 3712 1399; 3488 1535; 3326 1556;3238 1229; 4196 1044; 4312 790; 4386 570; 3007 1970; 2562 1756;2788 1491; 2381 1676; 1332 695; 3715 1678; 3918 2179; 4061 2370;3780 2212; 3676 2578; 4029 2838; 4263 2931; 3429 1908; 3507 2376;3394 2643; 3439 3201; 2935 3240; 3140 3550; 2545 2357; 2778 2826;2370 2975]
  基于禁忌算法求解出的结果如下所示:

  总的来说，禁忌搜索的结果还是比较不错的，相关的应用过程与代码详情请见下一篇文章。