禁忌搜索算法

出自 MBA智库百科(https://wiki.mbalib.com/)

禁忌搜索算法（Tabu Search/Taboo Search，简称TS算法）

　　禁忌搜索算法（Tabu Search或Taboo Search，简称TS算法）是一种全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征。它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过破禁水平来释放一些被禁忌的优良状态，进而保证多样化的有效探索，以最终实现全局优化。

　　禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Fred Glover(美国工程院院士，科罗拉多大学教授)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的 meta-heuristic算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。本章将主要介绍禁忌搜索的优化流程、原理、算法收敛理论与实现技术等内容。

考虑最优化问题，对于X中每一个解x，定义一个邻域N(x)，禁忌搜索算法首先确定一个初始可行解x，初始可行解x可以从一个启发式算法获得或者在可行解集合X中任意选择，确定完初始可行解后，定义可行解x的邻域移动集s(x)，然后从邻域移动中挑选一个能改进当前解x的移动，s(x)，再从新解x’开始，重复搜索。如果邻域移动中只接受比当前解x好的解，搜索就可能陷入循环的危险。为避免陷入循环和局部最优，构造一个短期循环记忆表——禁忌表(TabuList)，禁忌表中存放刚刚进行过的(称为禁忌表长度)个邻域移动，这些移动称作为禁忌移动(Tabu Move)。对于当前的移动，在以后的T次循环内是禁止的，以避免回到原先的解，次以后释放该移动。禁忌表是一个循环表，搜索过程中被循环的修改，使禁忌表始终保存着个移动。即使引入了一个禁忌表，禁忌搜索算法仍有可能出现循环。因此必须给定停止准则以避免算法出现循环。当迭代内所发现的最好解无法改进或无法离开它时，则算法停止。

　　组合优化是TS算法应用最多的领域。置换问题，如TSP、调度问题等，是一大批组合优化问题的典型代表，在此用它来解释简单的禁忌搜索算法的思想和操作。对于 n元素的置换问题，其所有排列状态数为n!，当n较大时搜索空间的大小将是天文数字，而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。

　　首先，我们对置换问题定义一种邻域搜索结构，如互换操作（SWAP），即随机交换两个点的位置，则每个状态的邻域解有Cn2=n（n一1）/2个。称从一个状态转移到其邻域中的另一个状态为一次移动（move），显然每次移动将导致适配值（反比于目标函数值）的变化。其次，我们采用一个存储结构来区分移动的属性，即是否为禁忌“对象”在以下示例中：考虑7元素的置换问题，并用每一状态的相应21个邻域解中最优的5次移动（对应最佳的5个适配值）作为候选解；为一定程度上防止迂回搜索，每个被采纳的移动在禁忌表中将滞留3步（即禁忌长度），即将移动在以下连续3步搜索中将被视为禁忌对象；需要指出的是，由于当前的禁忌对象对应状态的适配值可能很好，因此在算法中设置判断，若禁忌对象对应的适配值优于“ best so far”状态，则无视其禁忌属性而仍采纳其为当前选择，也就是通常所说的藐视准则（或称特赦准则）。

　　可见，简单的禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中领域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。需要指出的是：

　　（1）首先，由于TS是局部领域搜索的一种扩充，因此领域结构的设计很关键，它决定了当前解的领域解的产生形式和数目，以及各个解之间的关系。

　　（2）其次，出于改善算法的优化时间性能的考虑，若领域结构决定了大量的领域解（尤其对大规模问题，如TSP的SWAP操作将产生Cn2个领域解），则可以仅尝试部分互换的结果，而候选解也仅取其中的少量最佳状态。

　　（3）禁忌长度是一个很重要的关键参数，它决定禁忌对象的任期，其大小直接进而影响整个算法的搜索进程和行为。同时，以上示例中，禁忌表中禁忌对象的替换是采用FIFO方式（不考虑藐视准则的作用），当然也可以采用其他方式，甚至是动态自适应的方式。

　　（4）藐视准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。

　　（5）对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种确定性策略）。

　　（6）为了使算法具有优良的优化性能或时间性能，必须设置一个合理的终止准则来结束整个搜索过程。

　　此外，在许多场合禁忌对象的被禁次数（frequency）也被用于指导搜索，以取得更大的搜索空间。禁忌次数越高，通常可认为出现循环搜索的概率越大。

　　通过上述示例的介绍，基本上了解了禁忌搜索的机制和步骤。简单TS算法的基本思想是：给定一个当前解（初始解）和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。

　　条理化些，则简单禁忌搜索的算法步骤可描述如下：

　　（1）给定算法参数，随机产生初始解x，置禁忌表为空。

　　（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。

　　（3）利用当前解工的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。

　　（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤。

　　（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。

　　（6）转步骤（2）。

　　与传统的优化算法相比，TS算法的主要特点是：

　　（1）在搜索过程中可以接受劣解，因此具有较强的“爬山”能力；

　　（2）新解不是在当前解的邻域中随机产生，而或是优于“best so far”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。由于TS算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增强获得更好的全局最优解的概率，所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。

　　禁忌搜索算法是一种由多种策略组成的混合启发式算法。每种策略均是一个启发式过程，它们对整个禁忌搜索起着关键的作用。禁忌搜索算法一般由以下几种策略组成:

　　(1)邻域移动:邻域移动是从一个解产生另一个解的途径。它是保证产生好的解和算法搜索速度的最重要因素之一。邻域移动定义的方法很多，对于不同的问题应采用不同的定义方法。通过移动，目标函数值将产生变化，移动前后的目标函数值之差，称之为移动值。如果移动值是非负的，则称此移动为改进移动;否则称作非改进移动。最好的移动不一定是改进移动，也可能是非改进移动，这一点就保证搜索陷入局部最优时，禁忌搜索算法能自动把它跳出局部最优。

　　(2)禁忌表:不允许恢复即被禁止的性质称作Tabu。禁忌表的主要目的是阻止搜索过程中出现循环和避免陷入局部最优，它通常记录前若干次的移动，禁止这些移动在近期内返回。在迭代固定次数后，禁忌表释放这些移动，重新参加运算，因此它是一个循环表，每迭代一次，将最近的一次移动放在禁忌表的末端，而它的最早的一个移动就从禁忌表中释放出来。为了节省记忆时间，禁忌表并不记录所有的移动，只记录那些有特殊性质的移动，如记载能引起目标函数发生变化的移动。禁忌表记载移动的方式主要有三种:*记录目标值；*移动前的状态；*移禁忌搜索算法在冷藏供应链配送网络中的应用研究动本身。

　　禁忌表是禁忌搜索算法的核心，禁忌表的大小在很大程度上影响着搜素速度和解的质量。如果选择的好，可有助于识别出曾搜索过的区域。实验表明，如果禁忌表长度过小，那么搜索过程就可能进入死循环，整个搜索将围绕着相同的几个解徘徊;相反，如果禁忌表长度过大，那它将在相当大的程度上限制了搜索区域，好的解就有可能被跳过，同时，不会改进解的效果而增加算法运算时间。因此一个好的禁忌表长度应该是尽可能小却又能避免算法进入循环。禁忌表的这种特性非常类似于“短期记忆”，因而人们把禁忌表称作短期记忆函数。

　　禁忌表另一个作用是通过调整禁忌表的大小使搜索发散或收敛。初始搜索时，为提高解的分散性，扩大搜索区域，使搜索路径多样化，经常希望禁忌表长度小。

　　相反当搜索过程接近最优解时，为提离解的集中性，减少分散，缩小搜索区域，这时通常希望禁忌表长度大。为达到这样的目的，最近越来越多的人们允许禁忌表的大小和结构随搜索过程发生改变，即使用动态禁忌表，实验结果表明了动态禁忌表往往比固定禁忌表获得更好的解。

　　(3)选择策略:选择策略即择优规则，是对当前的邻域移动选择一个移动而采用的准则。择优规则可以采用多种策略，不同的策略对算法的性能影响不同。一个好的选择策略应该是既保证解的质量又保证计算速度。当前采用最广泛的两类策略是最好解优先策略(Bestlmprovedstrategy)和第一个改进解优先策略(FirstImProvedstrategy)。最好改进解优先策略就是对当前邻域中选择移动值最好的移动产生的解，作为下一次迭代的开始。而第一个改进解优先策略是搜索邻域移动时选择第一改进当前解的邻域移动产生的解作为下一次迭代的开始。最好改进解优先策略相当于寻找最陡的下降，这种择优规则效果比较好，但是它需要更多的计算时间;而最快的下降对应寻找第一个改进解的移动，由于它无需搜索整个一次邻域移动，所以它所花计算时间较少，对于比较大的邻域，往往比较适合。

　　(4)破禁策略:破禁策略通常指渴望水平(Aspiration)函数选择，当一个禁忌移动在随后}T}次的迭代内再度出现时，如果它能把搜索带到一个从未搜索过的区域，则应该接受该移动即破禁，不受禁忌表的限制。衡量标准就是定义一个渴望水平函数，渴望水平函数通常选取当前迭代之前所获得的最好解的目标值或此移动禁忌时的目标值作为渴望水平函数。

　　(5)停止规则:在禁忌搜索中停止规则通常有两种，一种是把最大迭代数作为停止算法的标准，而不以局优为停止规则;另一种是在给定数目的迭代内所发现的最好解无法改进或无法离开它时，算法停止。

　　(6)长期表:短期记忆用来避免最近所作的一些移动被重复，但是在很多的情况下短期记忆并不足以把算法搜索带到能够改进解的区域。因此在实际应用中常常短期记忆与长期记忆相结合使用，以保持局部的强化和全局多样化之间的平衡，即在加强与好解有关性质的同时还能把搜索带到未搜索过的区域。

　　(7)在长期记忆中，频率起着非常重要的作用，使用频率的目的就是通过了解同样的选择在过去做了多少次来重新指导局部选择。当在非禁忌移动中找不到可以改进的解时用长期记忆更有效。

　　目前长期记忆函数主要有两种形式，一种通过惩罚的形式，即用一些评价函数来惩罚在过去的搜索中用得最多或最少的那些选择，并用一些启发方法来产生新的初始点。用这种方式获得的多样性可以通过保持惩罚一段时间来得到加强，然后取消惩罚，禁忌搜索继续按照正常的评价规则进行。另一种形式采用频率矩阵，使用两种长期记忆，一种是基于最小频率的长期记忆，另一种是基于最大频率的长期记忆。通过使用基于最小频率的长期记忆，可以在未搜索的区域产生新的序列;而使用基于最大频率的长期记忆，可以在过去的搜索中认为是好的可行区域内产生不同的序列。在整个搜索过程中频率矩阵被不断的修改。^[3]