禁忌搜索算法优化技巧

禁忌搜索算法（Tabu Search，TS）最早由Glover在1986年提出，它是一种智能随机算法，是对局部邻域搜索的一种拓展。该算法在搜索过程中可以克服易于早熟收敛的缺陷，从而达到全局最优化。它的主要思想是在搜索过程中可以接受劣解，使得搜索过程能跳出局部最优解进而转向其他区域进行搜索，具有较强的爬山能力，从而避免了迂回搜索。同时通过特赦准则来释放一些被禁忌的优良状态，以达到提高优化效率，保证搜索过程的多样性和有效性的目的，特赦准则的引入显著提高了获得更好解或全局最优解的概率［147，148］。

禁忌搜索算法的计算过程是先给定一个初始解和一种邻域结构，然后在初始解的邻域结构中确定出若干候选解；当最佳候选解对应的目标函数与已保留的最好解对应的目标函数相比较好时，忽视最佳候选解的禁忌特性，并用其替换当前解和最好解，修改禁忌表；当上述候选解不存在时，选取候选解中非禁忌的最好解，无视它与当前解的优劣，使其成为新的当前解，修改禁忌表。如此反复执行搜索操作，直至满足停止准则。影响禁忌搜索算法性能的关键环节包括邻域结构、禁忌长度、禁忌对象、特赦准则和终止准则，其各自功能见表4－3。

表4-3　TS算法组成及功能

4.4.1.1　邻域结构

邻域结构与局部最优和全局最优密切相关，若邻域结构选择不当将使算法陷入局部最小，而无法实现全局最优，进而影响算法性能。

本章中将邻域结构的表示形式设置为　[－ξx，＋ξx ]，其中ξ为一个数值很小的常数，通常根据经验选定，优化问题特性的不同将导致ξ形式的不同。

由于优化变量为一个同时包含厚度和张力的八维向量，因此针对厚度和张力设置不同的ξ适应厚度和张力数量级上的差异。同时，针对不同的钢种、规格也要设置不同的ξ以满足搜索过程的需要。

邻域中候选解的产生流程如下。

（1）根据案例推理技术获得初始解 x0＝（h10，h20，h30，h40，T10，T20，T30，T40）T，选定 ξh和 ξT。(www.xing528.com)

（2）将－1，0，1三个数随机组合成一个八维向量φ，则候选解可以表示为 x′＝x0＋ξx0φ。

假设生成的八维向量 φ＝（0，－1，1，1，－1，0，0，1），则根据上述流程计算得到的候选解 x′＝（h10，h20－ ξhh20，h30＋ξhh30，h40＋ξhh40，T10－ ξTT10，T20，T30，T40＋ξTT40）T。重复以上过程则可以得到需要数目的候选解，这一方法简单实用，编程易于实现，并且保证了候选解在邻域中的覆盖面。

4.4.1.2　禁忌表

禁忌表实现了算法禁止重复前面动作的特点，使邻域搜索可以尽可能避开已搜索到的局部最优解。禁忌表包含两个主要指标，即禁忌对象和禁忌长度。

本章中选取最近搜索过的解作为禁忌对象，当候选解满足禁忌表但不满足特赦准则时将不能替代当前解，进而使搜索转向更大的区域。同时设置动态禁忌长度，初始搜索时给定一个较小的值，而后根据实际情况动态增加禁忌长度。当某一个解对应的最佳目标值出现的频率很高，超过一个给定值时，可终止计算，将其作为最终获得的最优解。

4.4.1.3　特赦准则

在搜索过程中，有可能存在当前解的邻域内所有元素都被禁忌或者一个被禁忌的候选解优于当前最优解的情况，此时需要建立特赦准则来保证这些优良状态不被遗漏。本章中将特赦准则设置为选取目标值优于当前最优解的禁忌候选解成为新的当前最优解。