禁忌搜索（TS）

禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法。禁忌搜索就是对于找到的一部*部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间，避免陷入局部极小。


通俗的解释TS算法：
一群兔子寻找海拔最高的山，假如兔子们找到了泰山，它们之中的一只就会留守在这里(即泰山加入禁忌表中，在其他兔子搜索过程中不再考虑泰山，以便获得更多搜索空间)，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。
当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表”的含义。那只留在泰山的兔子一般不会就一直停留在泰山，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度”；如果在搜索的过程中，留守泰山的兔子还没有归队(即泰山这个解仍在禁忌表中)，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

增强连续禁忌搜索算法（ECTS）

下面介绍一种增强连续禁忌搜索算法（ECTS），算法尤其强调集中化搜索和分散化搜索的重要性。分为五部分：
1.参数设置
2.分散搜索
3.最佳有希望区域的搜索
4.集中搜索
5.算法终止、结果输出
（重点介绍2、3、4部分）





分散化搜索：
1、分散搜索从一个初始解出发，在其邻域中产生规定数目的邻域解，在搜索过程中，禁忌表记录中心点位置，通过检验每个新产生的邻域解的中心是否已被记录在禁忌表中来判断其禁忌属性，并规定只有不属于禁忌表的邻域解才可接受，然后接受非禁忌的最佳邻域解为新的当前解。
2、在目标函数出现不可接受的恶化时就进行新的有希望区域的检测，而相应的中心位置将被存储在希望表中。当得到一个新的有希望解，如果该解不属于希望球则用之定义一个新的有希望区域，如果接受该新希望区域，则把希望表中最差区域替换掉。
注：
希望表和禁忌表为同一性质，希望表里也记录了若干个的邻域解的中心。
注：
希望表条件：所有相关目标函数值的恶化超过设定阈值时，在这个邻域球中，因为性能下降较快故选择球的中心点作为当前解，并被存储在希望表中，以便后续的集中化搜索。
注：
（此处的函数值恶化本人理解为“更优解”，记录到希望表才能在更优的区域集中化搜索，使得容易得到更优解）
（结合组合优化的“特赦原则”，更好理解）
3、当新的有希望区域在规定连续步数内未检测到，则终止分散搜索，并确定最佳的有希望区域。
注：
分散化搜索只从一个初始解出发，在其邻域中得到邻域解。但在算法执行的过程中，希望表的元素个数会越来越多，以便接下来最佳有希望区域的搜索，即择优操作。


最佳有希望区域的搜索：
step1：计算希望表中所有解的目标函数值的平均值。
step2：将目标值高于平均值的解消去。
step3：将禁忌球半径和超方体邻域大小缩半，对余留的有希望解执行“产生邻域解、选取最佳解”的搜索过程，在邻域解优于有希望解时，将邻域解替换为有希望解，而当整个希望表被扫描过后，算法将移去最不重要的有希望区域。
重复上述操作，直到只有一个有希望区域存在。
注：
举个栗子，当前希望表中有5个解[x1,x2,x3,x4,x5]，通过对比平均值消去得到[x1,x3,x4]，禁忌球半径和超方体邻域大小缩半，对[x1,x3,x4]以新的邻域结构执行TS搜索过程，此时希望表中解为[x1’,x3’,x4’]。重复求平均消去操作，直到希望表仅有一个解[x1’’’]。


集中化操作：
step1：首先重新设置禁忌表，并将上一进程得到的有希望区域定义为搜索域，该区域的中心(即x1’’’)作为当前解。
step2：再次执行TS搜索过程，直到目标函数值在规定连续迭代步数内保持不变。
step3：将禁忌球半径和超方体邻域大小缩半，重新设置禁忌表，并以最佳解为起点重复上述操作，直到达到最大迭代步数或目标值连续若干步保持不变。