禁忌搜索(Tabu search,Ts)算法的思想最早由Glover在1986提出,它是对局部邻域搜索的一种扩展, LPO2506I-682LC是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法通过引入灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化,以实现全局优化。Ts算法最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环),从而保证对不同的有效搜索途径的探索。在Ts算法中,首先按照随机方法产生一个初始解作为当前解,然后在当前解的邻域中搜索若干个解,取其中的最优解作为新的当前解。为了避免陷入局部最优解,这种优化方法允许一定的下山操作(使解的质量变差)。另外,为了避免对已搜索过的局部最优解的重复,TS算法使用禁忌表记录已搜索的局部最优解的历史信息,这在一定程度上使搜索过程避开局部极值点,从而开辟新 的搜索区域。Ts算法的流程图如图3-10所示。