智能网站优化算法之禁忌搜索算法
禁忌搜索算法因在后文中将使用禁忌搜索作为求解算法，为此首先对此算法作一概述。禁忌搜索(Tabu Search;TS)是模仿人类记忆功能，根据避免犯重复性错误的特点设计出来的一生智能优化算法。它是20世纪80年代由Glover等等人针对组合优化问题提出的（Glover 1989，1990，1998; Glover etd 1993），随后在调度、优化等领域取得了广泛应用（Armentano and Suich 2000,Annen～and Yamashita 2OOO;Ben-Daya and Al-Fawzan 1998;Chelouah and Siarry 2000: Landr/eu etd 2001)。
TS定义了邻域空间的概念：当前解x的邻域空间N(x)是指从当前解出发的所有可行移动s(x)产生的解的集合。
通过一系列移动，TS可以从解空间中的某个解移向邻域中的最优解，并试图找到全局最优解。TS记录曾经找到的最好解作为算法求得的最优解。禁忌表防止了这种“移动”陷入循环和局优。
首先对解空间x中的每一个解s定义它的郐域N(s)，禁忌搜索作从一个解到邻域中另一个解的重复移动。显然，如果不加限制，这样的移动非常可能形成循环。为了防止TS陷入局部最优点，有必要在，f（s’)>f(s)时也移向邻域点s’（以极小化目标为例）。因此TS引入了一个循环表——禁忌表T。此表采用“先进先出”的结构，其中记录了搜索过程中最近T次的移动。当执行一个移动时，新的移动社记录到T表的顶部，同时最底部的移动被取消。
当某移动被包含在T表中时，此移动处于“禁忌”状态。在某些条件下，可能需要解除被“禁忌”的移动，由此引入了吸收水平函数A(z)的概念：如果f(s’)<A，则从s’到s的禁忌移动是合法的。这里的吸收水甲一般定义为历史上的最好解。禁忌搜索的停止准则一般是某个最大的迭代次数，或者是经过一定的迭代次数后当前解仍没有得到改善。
下面分别介绍上述概念：
(1)邻域移动
邻域移动是从当前解产生新解的途径，可以针对问题特点采用不同的定义方法。领域移动前后的目标函数值之差称为移动值，若移动值为负，则称此移动为改进移动；否则称作非改进移动。最好的移动可能是改进移动，也可能是非改进移动，这使禁忌搜索算法具有跳出局优的能力。
(2)选择策略
选择策略即择优规则，一个好的选择策略应既能保证解的质量又保证计算速度。当前应用最广泛的选择策略是最好解优先策略(Best Improved Strategy)和第一改进解优先策略(First Imp,o.ed St.ategy)。最好解优先策略就是从当前邻域中选择导致最小目标值的移动产生的解，并作为下一次选代的开始。第一改进解优先荒略是从邻域中选择第一个可以改进当前解的移动产生的解，并作为下一次迭代的开始。最好解优先策略相当于搜索最陡的下降，效果较好但需更多的计算时间。第一改进解优先策略无需搜索整个邻域，所以所花计算时间较少，适合于较大的邻域。
(3)禁忌表
禁忌表是禁忌搜索的核心，主要目的足阻止搜索过程中出现循环或陷入局部最优。它通常记录此前的若干次移动，井禁止这些移动在近期内返回。在迭代固定次数后，禁忌表释放这些移动，重新参加运算。禁忌表的长度在很大程度上影响着搜索速度和解的质量禁忌表的长度太短，搜索容易陷入死循环；禁忌表太长时，搜索容易跳过最优解。因此适当的禁忌表长度应该是尽可能小同时义能避免算法进入循环。由于禁忌表的这种特性类似于人的“短期记忆”，因而禁忌表义称短期记忆函数。
(4)吸收水平函数
为防止由于某些移动被禁止而使搜索跳过好的解，TS算法引A了吸收水平函数，亦称为破禁水平。在某移动对应邻域解的目标值超过一定的破禁水平时，即使此移动在禁忌表中，仍可向这一邻域进行移动。吸收水平函数的设置因根据问题而异，它可以是一组判断依据，若其中任一条件i满足，即有ai(s，x) <Ai(s，x)，则邻域s的禁忌状态可被取消。其中ai(·)是吸收水平函数，Ai(·)是阈值。
(5)长期表
短期记忆用来避免重复进行相同的移动，但是它并不能把搜索带到新的搜索区域，因此在实际应用中短期表经常与长期表结合使用，以保持局部搜索与全局搜索之间的平衡。通过使用长期表，相当于每次搜索都从不同且相距较远的初始状态出发，这样各次搜索的过程便不会互相重复。
(6)停止规则
TS算法常用的停止规则有两种。一种是把最大选代次
数作为停止算法的标准；另一种是在给定数目的选代次数内
得到的最好解没有改进时算法终止。wc;gpisngjxc
页:
[1]