禁忌搜索

2024-12-08

禁忌搜索（精选7篇）

禁忌搜索篇1

1 引言

工程领域内存在大量的优化问题, 对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识, 属于局部优化算法。智能随机算法不依赖问题的性质, 按一定规则搜索解空间, 直到搜索到近似优解或最优解, 属于全局优化算法, 其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法 (Tabu Search, TS) 最早是由Glover在1986年提出, 它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制, 采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦 (破禁) 准则来释放一些被禁忌的优良状态, 以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法, 可以克服搜索过程易于早熟收敛的缺陷而达到全局优化[1]。

迄今为止, TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域, 并显示出极好的研究前景[2,3,4,5,6,7,8,9,11,12,13,14,15]。目前关于TS的研究主要分为对TS算法过程和关键步骤的改进, 用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。

禁忌搜索提出了一种基于智能记忆的框架, 在实际实现过程中可以根据问题的性质做有针对性的设计, 本文在给出禁忌搜索基本流程的基础上, 对如何设计算法中的关键步骤进行了有益的总结和分析。

2 禁忌搜索算法的基本流程

TS算法一般流程描述[1]:

(1) 设定算法参数, 产生初始解x, 置空禁忌表。

(2) 判断是否满足终止条件?若是, 则结束, 并输出结果;否则, 继续以下步骤。

(3) 利用当前解x的邻域结构产生邻域解, 并从中确定若干候选解。

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

(5) 判断候选解对应的各对象的禁忌情况, 选择候选解集中非禁忌对象对应的最佳状态为新的当前解, 同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。

(6) 转步骤 (2) 。

算法可用图1所示的流程图更为直观的描述。

3 禁忌搜索算法中的关键设计

3.1 编码及初始解的构造

禁忌搜索算法首先要对待求解的问题进行抽象, 分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略, 主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示[2], 十进制编码将问题的解用一个十进制串来表示[3], 实数编码将问题的解用一个实数来表示[4], 在某些组合优化问题中, 还经常使用混合编码[5]、0-1矩阵编码等。

禁忌搜索对初始解的依赖较大, 好的初始解往往会提高最终的优化效果。初始解的构造可以随机产生, 但效果往往不够理想, 通常是基于问题特征信息, 借助一些启发式方法产生, 以保证初始解的性能。

3.2 邻域移动、邻域解及邻域解规模

邻域移动, 相关文献也称作邻域操作、邻域结构、邻域变换等。禁忌搜索要想不断进行就要依赖邻域移动来不断拓展搜索空间, 邻域移动是在当前解的基础上, 按照特定的移动策略产生一定数目的新解, 这些新解被称为邻域解, 新解的数目称为邻域解规模。邻域移动的设计通常与问题有关, 如排列置换类组合优化问题, 常用的邻域移动方法是交换、插入、逆序等[3,6,7,8]。不同的移动将导致邻域解个数及其变化情况的不同, 进而影响搜索的质量和效率。在一些应用中为了取得好的搜索效果, 会根据搜索的进展情况动态改变邻域移动策略, 即变邻域移动[9]。邻域移动的设计策略既要保证变化的有效性还要保证变化的平滑性, 即产生的邻域解和当前解既有不同, 又不能差异太大。不同使搜索过程向前进行, 不能差异太大保证搜索是有序而非随机的搜索。邻域解的规模, 也并不总是取可产生邻域解个数的上限, 可以根据需要和经验设定成小于上限的值, 以提高搜索的运行效率。

3.3 解的评价函数

解的评价函数, 相关文献又称其为适应值函数、适配值函数或适应度函数。对于禁忌搜索空间中的解, 通过评价函数来计算其对应的评价函数值, 评价函数值的大小代表了解的优劣程度。根据问题的特性, 可能评价函数值越大越好, 反之也可能越小越好。依据数学方法, 两种目标可以等价转换。直接把优化目标作为评价函数是一种简单、直观的方法, 同时任何与优化目标等价的变换函数也可以作为评价函数。有时, 目标函数的计算困难或是耗时较多, 则可以取体现问题目标的特征值来替代计算, 但必须要保证特征值与问题目标有一致的最优性。

与遗传算法的评价函数类似, 在求解带有约束的优化问题时, 可以将解违反约束的情况作为惩罚因子加入评价函数, 从而规避传统启发式方法中对于约束的复杂处理。基本形式如公式 (1) 。

其中, P (Rj, x) 为第j个约束的惩罚值, 当解满足约束时, 惩罚值为0。关于评价函数的设计详见文献[10]。

3.4 禁忌表、禁忌对象、禁忌长度、候选解及禁忌频率

禁忌表是用来存放禁忌对象的一个容器, 被放入禁忌表中的禁忌对象在解禁之前不能被再次搜索, 可见禁忌表模拟了人的记忆机制, 防止搜索陷入局部最优, 进而探索更多的搜索空间。禁忌表可以使用数组、队列、栈、链表等顺序结构实现, 每个顺序结构的元素定义根据具体问题确定。

禁忌对象就是放入禁忌表中的元素, 归纳而言, 禁忌对象通常可选取状态 (解的编码) 本身或状态分量或适配值的变化等, 禁忌范围依次扩大[1]。其中选取状态本身易于理解, 也最为常用, 禁忌范围最小。

禁忌长度就是每个禁忌对象在禁忌表中的生存时间, 也称为禁忌对象的任期。当一个禁忌对象加入禁忌表时, 设置其任期为禁忌长度值, 搜索过程每迭代一次, 禁忌表中的各禁忌对象的任期自动减1, 当某一禁忌对象任期为0时, 将其从禁忌表中删除。任期不为0的禁忌对象处于禁忌状态, 不能被搜索过程选为新解。

候选解是当前解邻域解集的一个子集。搜索中为了减少搜索的代价 (包括空间和时间) , 要求禁忌长度和候选解集尽量小, 但禁忌长度过小将使搜索无法跳出局部最小, 候选解集过小将使搜索早熟收敛。候选解集的大小常根据问题特性和对算法的要求确定, 禁忌长度的选取则主要有静态和动态两种方法。静态方法是指在搜索过程中, 禁忌长度是一个固定值, 比如, 其中n为问题维数或规模。动态方法是指在搜索过程中, 禁忌长度也是动态变化的, 当算法搜索能力较强时, 可以增大禁忌长度从而延续当前的搜索能力, 并避免搜索陷入局部优解, 反之亦然。

禁忌频率记录每个禁忌对象出现在禁忌表中的次数, 以此作为搜索过程的重要参考, 如若某个对象出现频繁, 则可以增加禁忌长度来避免循环。此外可以把某对象的禁忌频率作为评价解的因素加入评价函数来指导搜索过程。

3.5 特赦准则

特赦准则, 相关文献也称为藐视准则、破禁准则[11]、释放准则等。特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解 (或状态) 被禁时, 能够释放特定解 (或状态) , 从而实现高效的全局优化搜索。

3.6 终止准则

终止准则也称停止准则, 即算法在何条件下停止搜索过程。实际应用中无法使用在禁忌长度充分大的条件下实现状态空间的遍历这一理论收敛条件, 往往使用如下近似终止 (收敛) 准则。

(1) 算法迭代次数达到指定最大次数停止[8,11]。

(2) 最优解的目标函数值小于指定误差。

(3) 最优解的禁忌频率达到指定值。

4 总结和展望

本文简述了禁忌搜索算法的发展、特点及应用, 给出了基本禁忌搜索算法实现的流程, 对禁忌搜索设计过程中的关键步骤进行了分析和总结, 为推广禁忌搜索算法在优化领域的应用有一定意义。

今后关于禁忌搜索算法的研究热点主要有以下几个方面。

(1) 与其他优化算法结合, 如与传统启发式算法、遗传算法、模拟退火算法、粒子群算法、神经网络算法、蚁群算法、混沌算法等结合, 构成更新型的混合优化算法[2,4,5,12,13,14,15]。

(2) 为推广禁忌搜索算法在超大规模优化领域中的应用, 突破禁忌搜索的串行性限制, 研究并行禁忌搜索算法。包括基于问题空间分解的并行策略和基于多禁忌搜索任务的并行策略[1]。

(3) 对禁忌搜索算法本身的关键步骤进行改良设计。如根据禁忌频率信息在算法中增加集中搜索和分散搜索, 分别实现优良区域的重点搜索和搜索范围的扩展。

(4) 探索禁忌搜索算法适于应用的新的优化领域。

进一步研究禁忌搜索算法中相关参数及操作对算法性能影响的相关理论, 开发更加高效的禁忌搜索算法。

禁忌搜索求解TSP问题篇2

禁忌搜索是一种新的优化方法, 其框架灵活, 通用性强, 应用领域较广。TSP是一类典型的组合优化问题, 它在交通运输、电路板线路以及物流配送等领域都有广泛的应用。本文采用改进的禁忌搜索算法求解TSP问题。

1、禁忌搜索算法

1.1 算法思想

禁忌搜索是对局部邻域搜索的一种扩展, 是一种全局逐步寻优算法, 禁忌就是禁止重复前面的工作, 有效克服局部邻域搜索易陷入局部最优的不足。该算法是通过引入一个灵活的存储结构和相应的禁忌准则来保证对不同的有效搜索途径的搜索, 并通过藐视准则来赦免一些被禁忌的优良状态, 最终实现全局优化。

1.2 邻域和候选解

定义1:令 (D, f) 为一个组合优化问题, 其中D为决策变量的可行域, f为目标函数, 设决策变量为x, 则一个邻域函数可定义为D上的一个映射, 即:N:D→2D。其中2D表示D的所有子集组成的集合。即对每个x∈D, N (x) ∈2D。N (x) 称为x的邻域, x′∈N (x) 称为x的一个邻居。

定义2若坌x∈N (x′) , 均满足f (x′) ≤f (x) 。则称x′为f在D上的局部极小解;若∀x∈D, 均满足f (x′) ≤f (x) , 则称x′为为f在D上的全局最小解。

邻域结构的设计通常与问题有关。它影响了当前解的邻域解的产生形式和数目, 以及各个解之间的关系, 对搜索质量和效率有较大的影响。

候选解通常在当前状态的邻域中择优选取, 但选取过多将造成较大的计算量, 而选取较小则容易早熟收敛。为了节省时间, 算法要有选择性取少量的优良解来改善算法的时间效率。

1.3 初始解、适应函数、禁忌准则和藐视准则

禁忌搜索对初始解有较强的依赖性, 好的初始解可以使禁忌搜索在解空间中搜索到好的解, 而较差的初始解则会降低禁忌搜索的收敛速度。在求解某个具体问题时, 如何选择高质量的初始解来提高算法搜索的质量和效率是很重要的。

禁忌搜索的适应函数是对搜索的评价, 结合禁忌准则和藐视准则来选取新的当前状态。禁忌的目的则是为了尽量避免迂回搜索。禁忌长度就是即禁忌对象不允许被选取的最大次数。禁忌对象只有当其任期为0时才能被解禁。禁忌长度与问题相关, 它可以是固定值也可以是某种规律变化的。

在藐视准则的设置时, 算法应避免遗失优良状态, 激励对优良状态的局部邻域搜索, 实现全局优化的关键步骤。

在禁忌搜索算法中, 藐视准则是将某些状态解禁, 以实现更高效的优化性能。禁忌对象上次被禁忌时使得适应函数有所改善, 并且当前该禁忌对象对应的候选解的适应函数优于当前解, 则对该禁忌对象解禁。该准则保证有效的搜索。

禁忌搜索是动态搜索邻域的算法, 流程图如下:

2、禁忌算法求解TSP

TSP是一个易于描述问题却难以大规模处理的NP问题。TSP问题定义如下:

TSP设C={≤c1, c2, …, cn}≤是n个城市的集合,

L={lij≤ci, cj∈C}是集合C中城市两两相连的集合, dij (i, j=1, 2, …, n) 是lij的距离, 即。TSP是一条对C={c1, c2, …, cn}中n个城市访问且只访问一次的最短封闭曲线。TSP是一个组合最优化问题, 即有限集上的最优化。因此, TSP的一个最优解就是对应于结点标号为{1, 2, …, n}的一个排列π, 并使得长度f (π最小。其中f (π) 的定义为

本文提出的禁忌搜索算法如下:

(1) 随机解初始解x。

(2) 建立禁忌表, 设置最大迭代次数和禁忌长度。

(3) 判断是否满足终止条件

(4) 是结束搜索, 输出优化结果。

(5) 否生成x的邻域N (x) , 产生候选集。

(6) 判断是否有候选解满足藐视准则

(7) 是, 将满足藐视准则的解作为当前解。更新禁忌表。转 (3)

(8) 否, 将非禁忌最佳解作为当前解。更新禁忌表。转 (3)

3、仿真结果

本文以10个城市和30个城市为例, 城市坐标和实验结果如下

从实验寻优过程可以看出, 数据能多次逃离局部最优解, 最终在一个区域震荡, 该区域的最优不一定是全局最优。上面的两个例子就说明这个问题。10城市的最优是2.6907, 30城市的最优是423.7406。但禁忌算法的收敛深度快, 计算效率高, 稳定性好。

4、结束语

从仿真结果图中可以看出, 禁忌搜索算法的寻优下降过程非常快, 在短时间收敛于“次优解或最优解”。禁忌搜索算法在求解小规模的优化问题上显示出超强能力, 但在大规模的优化问题时表现差强人意, 如迭代次数增多, 搜索性能下降等等。这是禁忌搜索算法需再改进之处。

参考文献

[1]GareyM R, Johnson D S.A guide to the Theory ofNP-Com-pleteness[J].Computers and Intractability, 1979, 3 (5) .

[2]贺一, 刘光远.变异操作对禁忌搜索性能的影响研究[J].计算机科学, 2002, 29 (5) .

[3]张辉赵正德杨立朝赵郁亮.TSP问题的算法与应用的研究[J].计算机应用与软件, 2009, 26 (4) .

禁忌搜索篇3

禁忌搜索算法(TS)由Glover教授于1986年正式提出。禁忌搜索算法与模拟退火、进化计算、蚁群算法、粒子群优化、人工免疫系统等一样,都属于自然计算的研究范畴。禁忌搜索算法是智能优化算法中的一种,是人工智能的一种体现。是对人类智力过程的一种模拟[1-2]。迄今为止,TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功,近年来又在函数全局优化方面得到较多的研究,并大有发展的趋势。

在TS算法中,不同的参数设定将会影响算法求解的效率和最优解的精度,因此本文以多极值一维函数为例,对TS算法参数设定进行实验,以找出算法求解参数的较佳组合[3,4]。在MATLAB工具开发环境下,讨论算法的参数选择,通过在以上三种终止准则下的比较和研究,总结了它们的差异和优缺点。

2 禁忌搜索算法

禁忌搜索算法是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化[5]。

2.1 禁忌搜索算法的局部邻域搜索

局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索,虽然算法通用易实现,且容易理解,但其搜索性能完全依赖于邻域结构和初始解,尤其容易陷入局部极小而无法保证全局优化性。针对局部邻域搜索,为了实现全局优化,可尝试的途径有:以可控性概率接受劣解来逃逸局部极小;扩大邻域搜索结构;多点并行搜索;变结构邻域搜索;另外,就是采用TS的禁忌策略尽量避免迂回搜索,是一种确定性的局部极小突跳策略。

2.2 禁忌搜索算法的相关参数

禁忌搜索是人工智能的一种体现。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象,而不是绝对禁止循环,从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域(neighborhood)、禁忌表(tabu list)、禁忌长度(tabu 1ength)、候选解(candidates)、藐视准则(aspiration criterion)等概念[6]。简单的禁忌搜索是在邻域搜索的基础上,通过设置禁忌表来禁忌一些已经历的操作,并利用藐视准则来奖励一些优良状态,其中邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。

2.3 禁忌搜索算法流程

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

算法具体步骤可描述如下:

(1)给定算法参数,随机产生初始解x,置禁忌表为空。

(2)判断算法终止条件是否满足?若是,则结束算法并输出优化结果;否则,继续以下步骤。

(3)利用当前解的邻域函数产生其所有(或若干)邻域解,并从中确定若干候选解。

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

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

(6)转步骤(2)。

3 禁忌搜索算法优化函数设计方案

3.1 适配函数的定义

以适配值或其变化为禁忌对象则将处于同一适配值的状态视为相同状态,这在函数优化中经常采用。由于一个值的变化隐含着多个状态的变化,因此这种情况下的禁忌范围相对于状态的变化将有所扩大。目标函数的任何变形都可以作为适配值函数。因为通信系统中传输信号多为一维多极值余弦函数的变形,故本文的目标函数多极值一维函数,其图像如图2.1:

本文目标函数为一个有具有普遍性的信号形式,有研究意义,故无需任何变形,故直接用目标函数作为适配值函数,对适配值函数的优化即是寻找最大值的过程。

3.2 禁忌对象的设计

禁忌对象是被置入禁忌表中的那些变化元素,其主要目的是为了尽量避免迂回搜索而多搜索一些有效的搜索途径。通常可选取状态本身、状态分量、适配值的变化作为禁忌对象。本文将适配值的变化作为禁忌对象。

3.3 邻域结构的设计

本文的邻域结构是以当前产生的最优解X为中心,随机产生满足在0

3.4 禁忌表及禁忌长度

禁忌长度大小是影响TS算法性能的关键参数。禁忌长度是禁忌对象在不考虑藐视准则情况下不允许被选取得最大次数,对象只有当其任期为0时才被解禁。在算法的构造和计算过程中,一方面要求计算量和存储量尽量小,这就要求禁忌长度尽量小;但是禁忌长度过短将造成搜索循环。

本文的禁忌表包括的元素有禁忌长度,与状态信息相应的适配值[8]。本文的禁忌长度是定长不变的,它的选取是通过实验仿真讨论确定的,对于不同的禁忌长度,画出禁忌长度和当前最优解的曲线。通过曲线,便可以恰当的选择禁忌长度,使禁忌搜索算法具有最佳的优化性能。本文将讨论禁忌长度对算法优化性能的影响,并采用最佳的禁忌长度。

3.5 候选解的选择

候选解的选择首先要确定候选解的数量,然后确定最佳候选解的选取方案。原则上应该做到对当前解的邻域解的遍历,但考虑到邻域搜索的效率,通常仅取当前解的邻域解的一个子集作为候选解集。最佳候选解通常是候选解集中满足藐视准则或非禁忌的最佳状态[9]。候选解集的大小是影响TS算法性能的一个关键参数,本文将通过对不同解集大小下算法的实验仿真,选取能使函数优化性能最好的候选解集大小来进行仿真。

3.6 藐视准则

本文应用的是基于适配值准则中的全局形式,这也是最常用的一种方式。它的具体操作是:若某个候选禁忌解的适配值优于“best so far”状态,则无视其禁忌属性,解禁此候选解为当前状态和新的“best so far”状态。该准则可理解为算法搜索到了一个更好的解。

3.7 终止准则

禁忌搜索需要一个终止准则来结束算法的搜索进程,而严格的实现理论上的收敛条件,即在禁忌长度充分大的条件下实现状态空间的遍历,是不切合实际的因此实际设计算法时通常采用近似的终止准则[10]。常用的方法如下:

(1)给定最大迭代步数。迭代步数即是每次运行后总共搜索循环的次数,用它来控制算法的收敛。

(2)设定某个对象的最大禁忌频率。即,若某个状态、适配值或对换等对象的禁忌频率超过某一阈值,则终止算法,其中也包括最佳适配值连续若干步保持不变的状况。本文应用的第二种终止准则采用的禁忌对象是当前最优解连续若干步保持不变的状况。

(3)设定适配值的偏离幅度。即,首先有估界算法估计问题的下界,一旦算法中最佳适配值与下界的偏离值小于某规定幅度时,则终止搜索。

4 实验及结果分析

在以不同终止准则收敛的情况下,讨论禁忌搜索算法两个关键参数——禁忌表长度和邻域候选解个数对算法优化性能的影响,并找出最优的参数。并在每种终止收敛准则参数最优时比较三种终止准则优化本文所定义的函数时哪一种的性能更好。在MATLAB环境下对禁忌搜索算法过程用MATLAB语言编译仿真,优化本文目标函数,输出最优解。

4.1 以最大迭代步数为终止条件

在以限定最大迭代步数为终止准则情况下,邻域解集个数选为500,终止迭代步数为3000,记录找到最优解时的迭代步数,并求平均值,以此来考验算法优化性能表1是禁忌表长度与对应迭代步数的图表。

从表中可以看出,在禁忌长度等于7和9时收敛较快,但在9时收敛更好,且比较稳定,所以认为禁忌长度H=9时收敛性最好,故选择9作为禁忌长度,在以下讨论邻域解集大小时,也选此为禁忌长度。

禁忌表长度选择9,迭代次数仍然选择3000,记录找到最优解时的迭代步数,并求平均值,如表4.2是邻域解集个数与达到最优时对应迭代步数的图表。

由表2可见在邻域解集数为600时,达到最优解时迭代次数最小,但当邻域解选择大于6 0 0时,运算量增大,运行速度减慢,所以,综合考虑,选择邻域个数解为6 0 0作为最佳优化参数,并认为,在此种终止准则下,对于本文需优化函数,邻域解集个数600可以是寻到最优解的最好参数。

选择禁忌长度H=9,邻域解集数选择600,变化最终迭代步长,讨论迭代步数对优化性能的影响。同一最大迭代次数情况下,仿真运行5次,看终止最大迭代步数对最优解的影响。

在保证算法计算量和速度的前提下,应尽量减少迭代次数,如表3可见,当终止时最大迭代次数K小于1500时,无法保证每次都优化出最优解,说明迭代步数越大,结果越优,在最大迭代次数K选择1500时,每次优化出的解都是正确解7.8567,所以在此种收敛准则下,主要参数选择为禁忌长度H=9、邻域解集个数600、最大迭代步数为1500,可认为在此终止准则下此参数的选择是对本文需优化函数最佳的情况。

4.2 以某对象的最大禁忌频率为终止条件

本文应用的第二种终止准则采用的禁忌对象是当前最优解连续若干步保持不变的状况。

与4.1中仿真过程类似,可以得出以限制最优解禁忌频率为终止准则情况下最优的参数禁忌表长度和邻域候选解个数,具体图表省略。

在保证算法计算量和速度的前提下,应尽量减少候选解的禁忌频率,如表4可见,当终止时候选解的禁忌频率小于12时,无法保证每次都优化出最优解,说明候选解的禁忌频率越大,结果越优,在候选解的禁忌频率选择12时,每次优化出的解都是正确解7.8567,所以在此种收敛准则下,主要参数选择为禁忌长度H=9、邻域解集个数500、候选解的禁忌频率为12,可认为在此终止准则下此参数的选择是对本文需优化函数最优的情况。

4.3 以适配值的偏离幅度为终止准则

首先有估界算法估计问题的下界,一旦算法中最佳适配值与下界的偏离值小于某规定幅度时,则终止搜索。算法收敛时其适配值之间的差值必须连续多次小于一个较小的范围,经多次实验仿真,规定连续次数为3 0,在此参数下,进行以下研究讨论,找出最优的参数。

与4.1和4.2中仿真过程类似,可以得出以限制适配值为终止准则情况下最优的参数禁忌表长度和邻域候选解个数,具体图表省略。

在保证算法计算量和速度的前提下,应尽量增大适配值的偏离幅度,如表4可见,当终止时适配值的偏离幅度大于0.0001时,无法保证每次都优化出最优解,说明适配值偏离幅度越小,结果越优,在适配值偏离幅度选择0.0001时,每次优化出的解都是正确解7.8567,所以在此种收敛准则下,主要参数选择为禁忌长度H等于9、邻域解集个数600、适配值的偏离幅度为0.0001,可认为在此终止准则下此参数的选择是对本文需优化函数最优的情况。

4.3 三种终止准则的收敛特性比较

在上文讨论的最优参数下,把三种终止准则横向比较,在各自选择对本准则最优性能的参数基础上优化本文设定函数,并用MATLAB仿真,观察结果。

多次仿真试验后,得出结论基本相同,选出代表性曲线,如图4.1。

通过曲线可以看出,在三种终止准则下优化本文所设定的函数的时,在上文所讨论的参数下,都可以准确的优化出本函数的最优解,只是达到最优解时的迭代步数不同,由图可见,在以候选解的禁忌频率为终止准则的情况明显优于其它两种终止准则,在这种终止准则下,算法最快寻到最优解,而且曲线相对更平稳。

以适配值的偏离幅度为终止准则的情况下,算法终止时迭代步数最小,但不是最快寻到最优解,且相对于以禁忌频率为收敛准则的情况找到最优解附近邻域更慢,且没有其平稳。

以最大迭代步数为终止准则的情况下,相对于其他两种收敛准则算法找到最优解附近邻域最慢,但最后在最优解附近邻域搜索时曲线较平稳,且迭代步数足够长,可以保证算法全解空间精细搜索。

所以,对于本文优化的多极值函数:

在用禁忌搜索算法的思想进行优化时,选择终止准则不同时,其优化性能也不同,经本文讨论研究并且仿真,认为在以候选解的禁忌频率为终止准则时,其收敛性最好。

5 结束语

本文论述了禁忌搜索算法的产生背景、原理及算法框架,并就禁忌搜索算法的三种终止准则的收敛性进行了研究探讨,做了大量的仿真试验,验证了本文所提出的各种终止准则的有效性。通过这些研究工作,我们对禁忌搜索算法可得到以下结论:

禁忌搜索的最大优点在于具有记忆功能,由于“禁忌表”的作用,使得搜索可以确定性地跳出局部最优,这也是禁忌搜索算法区别于其它启发式算法的地方,与SA、G A比较而言,禁忌搜索往往能得到更好的解的质量。初始解的选取和邻域范围的确定很重要,若按简单的禁忌搜索流程来优化本函数,则陷入局部最优,所以本文提出变邻域搜索策略,使得算法可以在整个解空间遍历,验证了算法的有效性和可发展性。禁忌搜索有三种准则,对于本文所优化的函数来说,用三种收敛准则都可达到最优解。在三种终止准则下,以候选解的禁忌频率为终止准则的情况下,本文函数可以更快更稳地被优化。

摘要：禁忌搜索(Tabu Search,TS)是一种新的智能优化算法.TS以其灵活的存储结构和相应的禁忌准则来避免迂回搜索,在组合优化和函数优化领域中得到了广泛应用。本文重点研究了禁忌搜索算法的参数选择和其收敛特性的关系,侧重研究了禁忌搜索算法的两个关键参数——禁忌表长度和邻域候选解集个数对算法优化性能的影响,最后比较了本文定义的函数在三种终止准则下的优化性能。

关键词：禁忌搜索算法,终止准则,收敛特性

参考文献

[1]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001:62-82.

[2]ZHAO CHUNHUI,CUI YING.Optimal Stack Fil-ters Based on Tabu Search Algorithm[A].Proceedings of the6th international symposium on advanced intelligent systems[C].Korea:Korea University Lishui,2005:1085-1089.

[3]贺一,刘光远.禁忌搜索算法求解旅行商问题的研究[J].西南师范大学学报(自然科学版),2002,27(3):34l-345.

[4]贺一,刘光远.变异操作对禁忌搜索性能的影响研究[J].计算机科学,2002,29(5):115-116.

[5]刑文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:62-82.

[6]GLOVER F,HANAFI S.Tabu Search and Finite -e s..Convergence[J].Discrete Applied Mathematics,2002,229(4):3-36.

[7]CHELOUAH R,SIARRY P.Tabu search applied to global optimization[J].European Journal of Operational Research,2000,123(43):256-270.

[8]孙云凯,刘民,吴澄.变邻域结构Tabu搜索算法及其在Jop shop调度问题上的应用[J].电子学报,2001,29(5):622-625.

[9]柯珂,张世英.禁忌—阶梯遗传算法研究[J].控制与决策,2001,16(4):480-483.

禁忌搜索篇4

关键词：禁忌搜索算法,最短路径优化算法,智能路由,Dijkstra算法

0 引言

计算机网络的运行质量与路由的选择方法密切相关。不同的信息传输要求可以选择和采用不同的路由选择方法。目前的网络已经十分庞大, 并且以后发展的趋势会越来越大, 传统的互联网络路由协议会显得有些力不从心, 因此使用禁忌搜索算法对路由 (链路-状态路由选择算法 (Link-State Routing, L-S) ) 进行优化, 有着十分重要的作用。禁忌搜索算法是人工智能的一种体现, 是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象, 并在进一步的迭代搜索中尽量避开这些对象, 从而保证对不同的有效搜索途径的探索。该算法优化最短路径算法不仅能够优化路由的选路方式和选路速度, 还能对路径上Qos进行优化, 使网络发挥到最大的性能。

1 禁忌搜索算法求解最短路径优化问题的数学模型框架

假设:已知整个网络的拓扑结构和各链路的长度, 求网络中任意2个给定节点之间的最短通路。若将已知的各链路的长度改为路由时延或其他参数, 例如, 带宽, 经过的节点数, 平均通信量, 平均队列长度等因素及其给组合, 就相当于求任意2个节点之间且有最小时延或最小代价的通路。因此, 求最短通路的算法且有普遍意义。

输入:图G= (B (G) , E (G) ) 有一个源顶点s和一个汇顶点t, 以及对所有的边ij∈E (G) 的非负边长Cij。

输出:G中从S到T的最短路径的长度。

第0步:从对每个顶点做临时标记L开始, 做法如下:L (S) =0, 且对除S外所有的顶点L (I) =∞。

第1步:找带有最小临时标记的顶点 (如果有结, 随机地取一个) 。使该标记变成永久标记, 即该标记不再改变。

第2步:对每个没有永久标记但是又带有永久标记的顶点相邻的顶点j, 按如下方计算一个新的临时标记:L (j) =Min{L (i) +Cij}, 求最小是对所有带有永久标记的顶点i做的。

第3步:判断最新永久顶点y与最新临时顶点x是否相等, 如果相等则标记此路径为冗余路径:H=Dis{L (y) -L (x) }。再判断顶点y, x延伸节点集合里是否分别存在x, y顶点.如果是则将之删除。重复第2步和第3步, 直到所有的顶点都打上了永久标记为止。

2 禁忌搜索算法的基本框架

2.1 初始化阶段

步骤1:加载问题相关数据, 初始化变量, 生成初始解x0∈X (X为可行解空间) , 清空禁忌表, 设计数器为0。

2.2 搜索阶段

步骤1:搜索不在禁忌表内或满足藐视法则的邻域移动x*∈N (x0) 奂X, 其中f (x*) ≤f (x) , 坌x∈N (x0) , 而N (x0) 是x0的所有邻域解。

步骤2:更新禁忌表T及目前最优解的记录, 执行邻域移动x0←x*。

步骤3:判断是否已达到终止条件。如过达到, 则终止搜索并输出最优解;否则, 计数器记录累加1并返回此阶段步骤1继续执行。

3 算法验证

在此验证测试中, 通过设置不同的算法参数, 分别对10个例题重复进行求解, 将得出的结果进行统计分析, 以获得算法最优参数设置的方法。

4 禁忌表的大小

禁忌表的长度过小会导致搜索迂回进行, 从而陷入局部最优的状态;而禁忌表长度过长, 则会对搜索进行过度的限制, 从而导致可能会错过获得最优解的机会。将禁忌表的长度设置为0.5n至3n之间, 并且将该区域平均分为5个区间, 区间的界限为 (0.5+2.5/4 x) n, (x∈[0, 4]) 取整的结果, 其中n为顶点数目, x为禁忌表长度系数。

5 算法最大迭代次数

在此参数的测试中, 我会先给一个较大的迭代次数作为迭代上限, 如顶点数目在50个以下的实例中设置为2000, 顶点数目大于50的时候设置为4000。然后在算法执行的时候记录各个实例达到最优解的时候经历的迭代次数, 这个迭代次数称为最优迭代值, 以所有例题中最大的最优迭代值作为推荐使用的算法最大迭代次数值。这个方法能够精确地测出各个实例达到最优解时所需的迭代次数。

6 测试方法

本次测试中, 使用10个例题进行, 每一个实例均使用上述5种禁忌长度及3种初始解构建方法进行测试。同时为了获得更加准确的数据, 上述测试会重复5次。因此, 在本次测试中会产生10×5×3×5=750组数据。

利用测试所获得的数据制作了“禁忌表长度与初始解生成算法的相互作用下对各个例题的影响程度图” (图1) 。横轴代表了禁忌长度系数;纵轴则表示了与例题已知最优解偏离百分比。偏离百分比的计算公式是ε= (C-C*) /C*×100%。其中, C为算法计算出的路径总距离, C*为问题已知的最优解的总距离。

根据图1制作了“禁忌表长度系数及初始解生成算法的相互作用下对最终解的影响图” (图2) 。我把横轴设为各个初始解生成算法, 而纵轴依然表示了与例题已知最优解偏离百分比, 图表中的各条折线, 表示了在各个禁忌表长度系数下不同的初始解生成算法的变化。

图2可以总结出, 当禁忌表长度系数为3 (即禁忌表长度为顶点数目的2.375倍) 时, 并且使用任意内接法作为初始解生成方法, 所获得的最终解与目前已知最优解之间的平均偏离百分比是最低的 (0.67%) 。

当两个参数的组合达到较低的偏离百分比时, 我们希望能通过最少的迭代次数来获得较低的偏离百分比, 所以, 平均最低的最优迭代值是各个例题的最优参数的组合。

至于算法最大迭代次数的测试方法, 我先对表1中的十个最短路径问题按顶点数量分成两组, 分别为“顶点数目不大于50”及“顶点数目在50以上”。然后分别对两组中各例题的最优迭代值进行比较, 从中选出最大的最优迭代值作为该组的算法最大迭代次数。测试的数据和各组的最优迭代值在表1中。

注:表中的数据是在禁忌表长度为3、使用任意内接法生成初始解的情况下获得的.

从表1中可以获悉当顶点数目不大于50时, 用任意内接法生成初始解, 且禁忌表长度系数为3时, 若要获得质量较佳的解算法所需的最大迭代次数至少为1306次;同样道理, 当顶点数目大于50时, 若要获得质量较佳的解算法所需的最大迭代次数至少为3590次。由此, 我建议当顶点数目不大于50时, 算法最大迭代次数应设为2000次;当顶点数目大于50时, 算法最大迭代次数应设为4000次。

编译环境及所描述的测试环境, 均在同一台机器上执行。机器的硬件如下, 处理器为Intel Core i7-2610UE Processor (1.5 GHz) 、内存4GB。值得一提的是, 此程序在运行时, 中央处理器并不是满负载运行, 故处理器的时钟频率不能用来计算程序执行的时间及效率。

7 测试小结

虽然课题并未通过大规模的测试来获得算法参数的精确设定方法, 但通过前面几个小节的测试和分析, 可以总结出以下结论:

(1) 参数的设置会因问题的实例不同而有所差异;

(2) 总的来说, 初始解的生成算法对最终解的质量并无明显的影响, 但建议使用任意内接法;

(3) 禁忌表长度对最终解的质量有明显的影响, 当禁忌表长度系数为3 (即禁忌表长度为顶点数目的2.375倍) 时, 所获得的最终解的偏离值是最低的;

(4) 当顶点数目不大于50时, 最大迭代次数设为2000;当顶点数目大于50时, 最大迭代次数应设为4000。

8 总结

在实际应用中, 没有一种算法对任何问题都是有效的, 不同的算法有不同的适用领域, 也有它不适合求解的问题类型。因此, 算法的混合就成为了扩展算法的适用范围、提高算法的效率的有效途径。针对本文的研究结果, 以下几点是在未来我研究的主要方向:

(1) 在本文中的禁忌搜索算法主要使用了全邻域搜索, 所以当顶点数目增加时, 算法的搜索速度会变得较慢, 在未来的研究, 我会尝试使用各种算法缩小邻域的搜索范围, 以增加搜索速度。

(2) 对算法加入多样性和集中性策略, 以加快跳出局部最优的能力。

(3) 将禁忌搜索算法与算法进行混合, 拓展算法的适用域, 提高算法的性能。

禁忌搜索篇5

禁忌搜索算法由美国科罗拉多大学教授 Fred Glover 在 1986 年左右提出, 至90年代初才形成一套完整的算法[1], 是局部邻域搜索算法的推广。所谓禁忌就是禁忌重复前面的工作, 为了回避局部邻域搜索陷入局部最优的主要不足, 禁忌搜索算法用一个禁忌表来记录已经到达过的局部最优点, 在下一次搜索中, 利用禁忌表中的信息不再或者有选择的搜索这些点, 以此来跳出局部最优点, 最终达到全局优化的目的[2]。它的基本思想非常简单, 就是基于“记忆装置”记住一些最近检查过的局部最优解, 它们将成为选取下一个解的禁忌点。禁忌搜索在智能算法中独树一帜, 成为一个新的研究热点, 受到了国内外学者的广泛关注[3]。近年来禁忌搜索算法广泛应用于车间调度、神经网络、网络优化等领域, 但也有其不足之处[4]:①对初始解的依赖性较强;②多样性与集中性搜索并重的情况下, 多样性不足;③确定性的搜索制约了它的灵活性。

在禁忌搜索中, 集中性搜索和多样性搜索是它的两个重要策略。其中多样性搜索尤为重要, 通常的算法都是使用基于频率记忆或改变其参数来实现多样性搜索策略。在问题规模较大时, 单纯应用频率记忆或改变参数来实现多样性搜索往往得不到理想的效果[5]。近年来许多学者对禁忌搜索的改进做了大量的研究工作[6,7]。另外, 禁忌搜索通常使用局部抖动的方法来构造邻域, 每次只能产生一个当前解, 所以尽管禁忌搜索有很强的局部搜索能力, 但当其陷入较深的谷中时, 它很难跳出该谷。文献[7]提出了一种基于插入法的禁忌搜索算法TIS, 摆脱了单一利用基于频率的记忆来实现多样性搜索, 使搜索程序能够很快跳出以前的搜索路径, 从不同的方向继续进行搜索本文针对禁忌搜索算法中集中性与多样性搜索并重的情况下多样性不足的缺点, 引入小生境技术对其进行改进, 小生境技术通过海明距离定义的排挤策略能够保证种群的多样性, 拓宽搜索领域, 加强多样性搜索。同时加快收敛速度, 抑制早熟现象, 避免过早收敛到局部最优, 对比实验结果表明, 该算法能很好地抑制早熟收敛, 同时在计算速度和计算结果方面都有所改进。

2基于排挤机制的小生境技术

一般的进化算法对于一个优化问题只能发现一个最优解。当面临一个多模优化问题需要发现多个最优解时, 一般的进化计算技术这时将无能为力[8]。即使将一般进化算法多次使用, 也不能保证所发现的最优解互不相同。小生境技术能使一般进化算法具有发现多个最优解的能力。小生境技术源于遗传算法 (GA) , 因此在遗传算法中, 发现多模问题中多个最优解的能力被称为小生境技术。尽管目前很多进化计算技术, 如PSO、微分进化都己经提出了自己的小生境技术, 但目前遗传算法在小生境技术中仍然占据着突出的地位, 对基于其他进化算法的小生境技术仍具有指导作用。其中比较典型的就是基于排挤机制的小生境技术。在生物学中, 小生境 (Niche) 是指特定环境下的一种生存环境。在生物进化过程中, 相同的物种一般生活在一起, 共同繁衍后代, 它们往往生活在特定的区域, 如热带动物很难在北极生存, 而北极的动物很难在赤道存活。受大自然的物竞天择, 优胜劣汰的思想启发, DeJong[9]提出了基于排挤机制 (Crowding) 的小生境方法。排挤的思想源于在一个有限的空间中, 各种不同的生物为了能够延续生存, 它们之间必须相互竞争有限的资源。最先也是作为一种预防遗传算法早熟收敛而提高其种群差异性的技术, 是作为对预选择技术的一种改进[10]。目前该方法已经成功地用于解决多峰函数的极限问题。

3改进的禁忌搜索算法

在禁忌搜索中, 多样性搜索策略用于拓宽搜索区域尤其是未知区域, 特别是当搜索陷于局部最优时, 多样性搜索可改变搜索的方向, 跳出局部最优, 从而实现全局优化。集中性搜索策略是为了加强对当前搜索到的优良解的邻域做进一步的搜索, 以便能找到全局最优解。为了使搜索更有效, 在分析集中性搜索与多样性搜索后, 针对禁忌搜索算法中集中性与多样性搜索并重的情况下, 多样性不足的缺点, 本文引入小生境技术对其进行改进, 选择进一步的搜索方向, 加强搜索以快速实现全局优化, 这就是本文改进的基本思想。

本文以原禁忌搜索框架为基础, 重点加强其多样性搜索, 增加灵活性。首先, 在使用c-w节约算法得到高质量初始解的基础上开始搜索, 在搜索过程中, 不只利用禁忌表禁忌最近的搜索, 还要记录这些移动是否有所改进, 并记录下改进的信息, 在搜索决策中并入这些信息, 使得搜索往利于改进的方向进行即可。其次, 在禁忌搜索原则确定的基础上, 增加概率性因素, 把确定性选择过程变为概率性的, 在评价函数中加入概率值, 从而改进搜索方向, 使得更好的解有更大的被选中的机会。其具体改进步骤如下。

3.1选择合理的小生镜排挤因子

该方法具体步骤为:

(1) 初始化, 确定遗传参数, 设定排挤因子, 建立初始群体p (0) ;

(2) 计算个体适应度;

(3) 遗传操作:选择、交叉和变异操作;

(4) 从当前群体中p (t) 随机选排挤因子个体组成排挤因子成员;

(5) 选择相似性测度, 比较新产生的个体与排挤因子团体间的个体的相似性:

(6) 用新产生的个体去替换排挤因子团体中最相似的个体, 以形成新的当前群体;

(7) 判断终止条件是否满足, 不满足转回 (2) ;满足条件, 则结束。

上述算法在优化的初始阶段, 由于群体中个体间的相似性相差不大, 个体的更新替换呈现一定的随机选择特性。但随着优化的进展, 群体中的个体会逐步形成若干小生境, 此时基于个体相似性的替换技术可在一定程度上维持群体的分布特性, 能更进一步地形成小生境。但上述算法的主要缺点在于对排挤因子的选取上, 过大的排挤因子将影响算法的效率, 过小的排挤因子则会导致在探索过程部分峰值的丢失。

3.2并入移动方向的相关信息

想要记录移动方向的改进与否, 就需要给禁忌表中每一项增加两个变量, 即禁忌表中每一项都变成 (a, b, c) , 其中a代表禁忌值, 即在随后的a次迭代中, 不允许此项被禁忌;b代表优质解的出现次数, 即此项有b次反位或交换是优于当前解的评估值的;c代表劣质解出现的次数, 即此项有c次反位或交换是劣于当前解的评估值的。显然, b越小, c越大说明此项的反位或交换越有可能不利于搜索更优解;b越大, c越小说明此项的反位或交换越有可能有利于搜索更优解。所以可以在搜索决策中并入这些信息, 搜索就会往有利于搜索的方向进行。

改进的遗传禁忌算法描述具体步骤如下:

Step1:确定初始参数, 包括种群规模N、交叉概率Pc和变异概率Pm、最大迭代次数T等, 编码方式确定。

Step2:随机产生初始种群p (t) ={a1, a2, …, ai, …, aN}, 并求出各个个体的适应度Fai (i=1, 2, …, N) , 记录最好的个体。

Step3:依据各个个体的适应度进行降序排列, 并计算每个个体被选择的概率。选择过程中使用保优原则, 产生种群p (1) (t) 。

Step4:根据交叉概率Pc, 对群体中的个体进行交叉运算, 得到p (2) (t) 。

Step5:根据变异概率Pm, 对群体中的个体进行变异运算, 得到p (3) (t) 。

Step6:选择合理的小生镜排挤因子。按照下式求出p (3) (t) 中每两个个体bi和bj之间的海明距离:

式中:i=1, …, N-1;j=i+1, …, N;Chromlen———染色体长度。

当‖bi-bj‖

Step7:判断是否满足遗传算法终止规则, 即在规定连续代数Q内都满足:

式中:ε———一适当小的正数;eval (Utmax) ———t代的最大适应度值。则遗传算法终止, 继续下一步迭代。否则转Step3。

Step8:把遗传算法得到的最优解作为禁忌搜索的初始解, 进行禁忌搜索算法。

Step9:如果t

4实验结果与分析

旅行商问题属于中大规模的组合优化问题, 国内外学者对该问题进行了大量的研究工作, 都用该问题的解的情况来分析说明自己所提出的组合优化方法的有效性。本文也采用该问题来验证改进算法的有效性。为了验证本文算法的有效性选择有代表性的旅行商问题 (TravelingSalesmanProblem, TSP) 进行分析。TSP问题是一个著名的组合优化问题, 也是NP难题。本文选取10个城市的TSP问题, 分别用标准GA、标准TS和本文算法对n=10的TSP进行计算。参数设置为禁忌长度TL=20, 领域大小NL=40, 候选集大小CL=10。实验运行100次, 取其平均值, 结果如图1所示。

从图1可以看出, 本文算法很快得到了最优解368, GA和TS计算收敛到近似最优解分别为371和373。本文得到的解最好, TS解最差。这是因为TS采用随机的方式生成初始解, 较差的初始解搜索到的解也相对较差。本文算法收敛速度也最快, TS次之, 收敛最慢的是GA。因为GA是一个渐进的收敛过程, 可以很快地达到最优解的附近, 但要真正达到最优解却要花很长时间。本文算法在GA陷入“停滞”前, 及时把最好的解作为TS的初始解, 进行TS运算, 加快了收敛速度。为了测试本文算法的早熟控制策略是否有效, 本实验结果如表1所示。

从表1可以看出, 本文提出算法能够有效地克服标准禁忌搜索的“早熟”收敛。这是因为小生境技术的引入, 增加了种群的多样性, 使算法在更大的范围内搜索, 降低了收敛到局部最优解的可能性, 同时, 禁忌搜索算法较强的“爬山”能力, 一定程度上也可以让算法跳出局部最优解。这样, 双重抗“早熟”机制, 使算法的有效性达到99%。

5结论

针对禁忌搜索算法中集中性与多样性搜索并重的情况下多样性不足的缺点, 本文引入小生境技术对其进行改进, 小生境技术通过海明距离定义的排挤策略能够保证种群的多样性, 拓宽搜索领域, 加强多样性搜索。同时加快收敛速度, 抑制早熟现象, 避免过早收敛到局部最优, 对比实验结果表明, 该算法能很好地抑制早熟收敛, 同时在计算速度和计算结果方面都有所改进。

参考文献

[1]GLOVER F.Tabu Search:Part I[J].ORSA J on Computing, 1989, 1 (3) :190-206.

[2]ICHELG, GILBERTL, FREDERIC S.ATabu Search Heuristicfor the Undirected Selective Traveling Salesman Problem[J].European J of Operational, 1998, 106 (1) :539-545.

[3]LAUMANNS M, THIELE L, DEB K, et al.Combining Conver-gence and Diversity in Evolutionary Multi-objective Optimiza-tion[J].Evolutionary Computation, 2002, 10 (3) :263-282.

[4]SALAMI M, HENDTLASS T.A Fast Evaluation Strategy ForEvolutionary Algorithms[J].Applied Soft Computing, 2003, 2 (3) :156-173.

[5]贺一, 刘光远, 邱玉辉.Tabu Search中集中性和多样性的自适应搜索策略[J].计算机研究与发展, 2004, 41 (1) :162-166.

[6]雷开友, 王芳, 贺一, 等.Tabu Search集中性和多样性自动平衡下的增强搜索策略[J].计算机科学, 2005, 32 (1) :161-163.

[7]赵佩清, 林文才, 颜学峰.基于蚂蚁智能体调度的混沌搜索算法及化工应用[J].化工自动化及仪表, 2009, 36 (4) :21-25.

[8]高海昌, 冯博琴, 朱利.智能优化算法求解TSP问题[J].控制与决策, 2006, 21 (3) :241-247, 252.

[9]De Jong K A.An Analysis of the Behavior of Class of GeneticAdaptive Systems[D].University of Michigan, 1975:76-9381.

禁忌搜索篇6

禁忌搜索 (Tabu Search或Taboo Search, 简称TS) 最早由Glove r (1986) 提出, 它是对局部邻域搜索的一种扩展, 并且是一种全局逐步寻优算法。禁忌搜索算法通过引入一个灵活的存储结构, 并且配备一个相应的禁忌准则来避免搜索的重复, 并通过设置一个相应的藐视准则来赦免一些被禁忌的但是还有可能是优于当前解的状态, 从而保证多样化的探索并且最终实现全局优化。相对于模拟退火和遗传算法, 禁忌搜索算法是又一种搜索特点不同的meta-heuristic算法[1]。迄今为止, 禁忌搜索算法在机器学习和组合优化, 甚至包括生产调度、和神经网络等领域取得了非常大的成功, 并且引起越来越多的学者的关注, 得到了进一步的发展。

1 TSP问题的描述

旅行商问题 (TSP问题) 是一个比较经典的数学问题, 就是一个销售商从多个城市中的某一城市出发, 不重复地走完其它的城市并且回到原点, 在所有可行的路径中找出路径长度最短的一条。

将TSP用数学语言可以表述为:假设V1, V2, V3…Vn是给定的n个城市, 从某个城市Vi (1≤i≤n) 出发, 走遍每个城市一次且只一次, 然后返回到出发点, 求出一条使得总路径最短的路径。aij表示城市Vi到城市Vj的两地路径的长度[2]。

2 禁忌搜索算法

禁忌搜索算法的基本思想是:给定一个初始解 (随机的) , 并且给定这个初始解的一个邻域, 然后在此初始解的邻域中确定某些解作为算法的候选解;给定一个状态, “best so far” (既当前最优解) ;若最佳候选解所对应的目标值优于“best so far”状态, 则忽视它的禁忌特性, 并且用这个最佳候选解替代当前解和“best so far”状态, 并将相应的解加入到禁忌表中, 同时修改禁忌表中各个解的任期;若找不到上述候选解, 则在候选解里面选择非禁忌的最佳状态做为新的当前解, 并且不管它与当前解的优劣, 并且将相应的解加入到禁忌表中, 同时修改禁忌表中各对象的任期;最后, 重复上述搜索过程, 直至我们得到的解满足停止准则。

禁忌搜索的算法步骤可描述如下: (1) 给定相应算法的参数, 并且随机产生初始解x, 同时把禁忌表置为空。 (2) 判断算法是不是满足搜索终止的条件?若是, 则结束算法并且输出结果;否则, 继续执行以下步骤。 (3) 利用当前解x的邻域函数产生它的邻域解, 并且从中确定一些解作为候选解。 (4) 对与所选择的候选解判断是否满足藐视准则?若成立, 则用满足藐视准则的最佳状态y替代x成为新的当前解, 即x=y, 并用与y对应的禁忌对象替换出最早进入禁忌表的禁忌对象, 同时用y替换“best so far”状态, 然后转步骤 (6) ;否则, 执行以下步骤。 (5) 判断候选解所对应的各个对象的禁忌属性, 选择候选解集中非禁忌对象对应的最佳状态作为新的当前解, 同时用与之对应的禁忌对象来替换最早进入禁忌表中被禁忌对象元素。 (6) 转步骤 (2) 。

从上述算法步骤中我们可以看出, 禁忌对象、邻域函数、禁忌表和藐视准则, 构成了禁忌搜索算法的关键。其中, 邻域函数沿用局部邻域搜索的思想, 实现邻域搜索;禁忌表和禁忌对象, 体现了算法避免迂回搜索的特点;藐视准则, 则是对优良状态的鼓励, 它是对禁忌策略的一种解放[3,4]。

3 禁忌搜索算法用于求解TSP

用于求解旅行商问题的禁忌搜索算法各个参数的设置如下: (1) 解的领域映射为2-opt, 也就是固定起点城市, 后面的城市中每两个城市进行对换, 邻域中的元素个数为C2n+1; (2) 目标函数定义为走过所有城市之间的路径距离之和, 目标函数同时也作为评价函数; (3) 禁忌对象定义为目标函数所对应求得的目标值; (4) 禁忌长度 (tabu_le ngth) 我们可以根据具体问题来制定; (5) 从邻域中选则最好的tabu_length+1个元素作为我们下一步搜索的候选集; (6) 为了提高我们所寻求的解的质量, 并且为了防止出现循环, 我们设置了藐视准则。藐视准则定义为:当当前最优解未下降到指定的次数时, 则赦免禁忌表中的次优解, 并且将其作为下一次迭代的初始解; (7) 终止规则为:程序运行超过给定的最大迭代次数, 或者赦免次数超过给定的最大赦免次数; (8) 为了增强搜索空间的多样性, 寻求到更优的解, 可以分别以每一个城市作为初始点进行搜索。

4 讨论

和传统的算法相比, 禁忌搜索算法的主要特点是: (1) 在搜索过程中可以出现一些劣解, 因此具有比较强的“爬山”能力; (2) 新解不是在当前解的邻域中随机产生, 而或是优于“best so far”状态的解, 或是非禁忌的最佳解, 因此选取优良解的概率就会远远大于其他解。

由于禁忌搜索算法具有灵活的存储结构和藐视准则, 并且在搜索过程中可以接受某些劣解, 所以具有较强的“爬山”能力, 搜索时能够跳出局部最优解, 转向解空间的其他区域, 从而增加我们获得更好的全局最优解的概率, 所以禁忌搜索算法是一种局部搜索能力很强的全局迭代寻优算法。但是, 禁忌搜索也有明显的不足, 表现在: (1) 对初始解有较强的依赖性, 好的初始解可使禁忌搜索算法在解空间中很快的搜索到好的解, 而较差的初始解则会降低禁忌搜索的收敛速度, 进而影响我们找到最优解; (2) 迭代搜索过程是串行的, 也就是仅仅是单一状态的移动, 而不是并行搜索。为了进一步改善禁忌搜索的性能, 一方面我们可以对禁忌搜索算法本身的算法参数的选取进行改进和优化, 另一方面则可以与其他算法相结合。

虽然, 禁忌搜索算法在求解组合优化问题上已显示出强大的生命力, 但还有不完善的地方。如解的质量与初始解有关, 在求解大规模TSP问题 (100城市以上) 时, 运行效率低等。如何将此种算法取其他算法结合在一起, 是笔者的下一步要进行的研究工作。

摘要：禁忌搜索在一系列应用范围内取得了很大的成功, 这篇论文致力于揭示其最主要的思想, 解释其最基本的原理, 并用它来求解组合优化难题中的典型代表旅行商问题 (TSP) , 经过试验和分析, 证明它是一种较好的全局启发式搜索算法。

关键词：禁忌搜索,组合优化,旅行商问题,启发式搜索算法

参考文献

[1]王凌.智能优化算法及其应用[M].北京:清华大学出版社, 2001.

[2]任小康, 代文征.基于禁忌搜索算法的旅行售货员问题[J].佳木斯大学学报 (自然科学版) 2005年7月第23卷 (第3期) :1.

[3]FRED CLOVER.Tabu Search—Part Ⅰ[J].ORSA Journal on Computing.Summer 1989.Vol.1. (No.3) .

禁忌搜索篇7

车间作业调度问题是NP-难问题[1],也是最难的组合优化问题之一。简单来说车间作业调度问题可以描述如下:有一些工件和一些机器,每个工件由一组工序组成(这些工序必须按给定顺序加工,加工过程中不能被打断),一台机器在任何时刻最多只能加工一个产品,一个工件不能同时在两台机器上加工。问题的目标是找到使所有工件完工时间(makespan)最短的调度。

对车间作业调度问题人们设计了很多启发式算法,包括人工神经网络、模拟退火算法、遗传算法[2]、局部搜索算法、转换瓶颈算法[3]、SB-GLS算法、TSSB算法等。这些算法各有不同的特点,它们在各种条件下的性能也各不相同。禁忌搜索是局部搜索中最有效的算法之一。本文提出了新的邻域构造方法,并利用改进的插入算法构造尽可能好的初始解,然后使用禁忌搜索算法改进当前解。实验结果表明该算法是可行的和有效的。

2 车间作业调度问题描述及模型的建立

车间作业调度(job shop scheduling)问题[4]可以简单的描述为n个工件(job)J1,J2,…,Jn在m台机器(machine)M1,M2,…,Mm上加工。每一个工件Ji有ni个工序(operation)Oi1,Oi2,…,Oini,在第Oij工序的加工时间为pij,必须按工序顺序进行加工且每一个工序必须一次加工完成(无抢占,no preemption)。一台机器在任何时刻最多只能加工一个产品,一个工件不能同时在两台机器上加工。求解如何在上面的条件下使最后一个完工的工件加工时间最短。

1)机器顺序阵M,M(i,j)表示加工i工件的第j个工序的机器号,M(i,*)表示i工件的所有工序按优先顺序加工的各机器号的排列。

2)加工时间阵T,T(i,j)为i工件的第j个工序在机器上的加工时间。

3)工件排列阵J,J(i,j)为i机器上第j次加工的工件号,J(i,*)表示i机器上依次加工的各工件的排列。

机器顺序阵即为技术约束矩阵,与加工时间阵一样,也是事先已知的。工件排列阵则是调度的一种表示形式,即最优调度的结果。 s.t.

Cij-Tij≥Cik,i=1,2,…,n,j=1,2,…,m (1)

Chj-Cij≥Thj,i,h=1,2,…,n,j=1,2,…,m (2)

Cij≥0,i=1,2,…,n,j=1,2,…,m (3)

将工件完工时间最小化作为目标,其目标函数为undefined

其中(1)式表示机器k先于机器j加工工件i;(2)式表示工件i先于工件h在机器j上加工;(3)表示初始时间从0开始。工件和机器满足:一台机器在某时刻只能同时加工一个工件的一个工序;不同工件的工序之间没有先后的,相同工件工序满足先后约束关系。

3 改进的禁忌搜索算法

禁忌搜索算法是在组合优化问题中寻找近似最优解的一种全局优化启发式算法,是Glover在1986年提出这个概念进而形成的一套完整算法。初始解、邻域函数、禁忌表、禁忌长度、候选解、特赦准则构成了禁忌搜索算法的关键因素。本文尝试给出新的初始可行解和新的邻域构造方法,提出改进的禁忌搜索方法。

3.1 改进的策略

3.1.1 初始解

禁忌搜索算法对初始解有很强的依赖性。初始解可以用随机的方法选择,也可以用一些经验的方法或其他算法计算得到。本文中利用改进插入算法[5]来得到初始解。求解步骤如下:

1)分别计算所有工件的完工时间,按工件所需的完工时间从大到小的排序,并安排最长的工件的所有工序在机器上的加工顺序即把所有工序放入机器Mi∈(M1,M2,…,Mm)中。

2)所有工件的工序全部安排到机器中,循环结束,否则,把次长工件中的所有工序放入机器Mi∈(M1,M2,…,Mm)中:把工件中的工序按照从大到小排列。每次选一个加工时间最长的工序Oini插入到机器Mi(i∈(1…m))中已经排好的序列中,假设机器Mi中已经排了m′Mi个工序,则工序Oini有m′Mi+1个位置可选(其中可能有不满足约束条件的位置),则从中选择使得经过工序Oini的最长路径最小的合法位置排放工序Oini。

3.1.2 邻域结构的构造

本文的邻域构造方法都是基于关键路径的思想,下面给出两种不同的邻域构造方法。

1)交换算子(工序):交换同在一条关键路径上且属于同一个块的两个加工工序的位置。禁忌对象为两个工序的交换,并将其放入禁忌表中。禁忌表初始为空;当一个交换被加入到禁忌表中时,若表未满,则将交换加到表的末尾;若表满,则删除表中顶头的一个,将最新禁忌对象加入表的末尾。

2)这是本文提出的一种新的邻域构造方法。这种构造方法一是块中的工序的交换,另一种是非块中工序的交换。可分别设主、次禁忌表来禁忌这两种交换。令JP(v)和JN(v)分别表示工序v在工件中的前一个工序和后一个工序,MP(v)和MN(v)分别表示工序v在机器(块)中的前一个工序和后一个工序。本邻域的构造包含三类移动,第一类可以交换块中边缘的两个相邻的工序v和w=MN(v),并且要求v不是第一块的第一个工序,w不是最后一块的最后一个工序;第二类是在第一类交换(v,w)的基础上,还交换(s=JN(v),t=MN(q))(如果s和t存在,并且L(s,N)=L(t,N)+dt)。其中L(s,N)表示有向图G(π)中以s为起点的最长路径的长度;第三类是做两对相邻的(v,w)和(x,y)的翻转,要求若两对翻转是在同一个块中,则该块中含的工序数必须大于3。

3.1.3 禁忌搜索过程

针对前面(2)中给出的两种不同邻域构造方法,制定不同的禁忌搜索策略。

禁忌搜索过程1:

STEP1:给以禁忌表(tabu list)H=⌀并选定一个初始解xnow;

STEP2:满足停止规则时,停止计算,输出结果;否则,在xnow的邻域N(xnow)中选出满足不受禁忌或已解禁的候选集Can-N(xnow);在Can-N(xnow)中选一个评价值最佳的解xnext,并禁忌对象放入禁忌表中,nnow:=xnext;若在Can-N(xnow)中的解的评价值都不优于当前的解,则选择一个最不差的未禁忌或已解禁的解xnext,nnow:=xnext;若所有邻域点都被禁忌,则特赦最优的解xnext,nnow:=xnext;更新历史记录H,重复STEP2。

禁忌搜索过程2:在邻域2)的构造过程中,不仅涉及到块中工序的交换,还涉及到非块中工序的交换,因此需设两个禁忌表即主、次禁忌表分别记录块中及非块的禁忌交换。只要有一个交换是被禁忌的,则该移动就被禁忌。

若存在好于当前最好的邻点,则选择搜索遇到的的第一个这样的邻点,并将其交换插入相应的禁忌表中。如果所有的邻点都不好于当前的解或邻点,若存在未被禁忌的邻点,则选择最不差的未被禁忌的邻点,并将其交换插入相应的禁忌表中;否则所有的邻点都被禁忌了且都不好于当前解,则从一类邻点中找在主禁忌表被禁忌时间最长的交换,并解禁该交换。当一个未被禁忌的交换插入禁忌表中时,若表中未满,则将该交换加在表的末尾;否则删除表中顶头的一个,再将该交换加在表的末尾。

4 实验结论

本文提出改进的禁忌搜索算法采用Visual C++6.0在Windows XP平台上编程实现,并以参考文献[6]中的数据(10个工件,每个工件有10个工序,机器数为10)为测试数据。下面根据文献[6]给出加工时间阵T、机器顺序阵M。

本实验中令算法的最大迭代次数为1000,最大连续无更好解次数20,禁忌表长度为30,本文对算法执行20次,取得最优解为87个时间单位,得到最佳调度如表4.1所示。

在求最优解的过程中(20次),记录每次得到的目标函数值,如表4.2所示。表4.2的结果表明改进的算法在20次运行中有5次达到最小值87,而且最差的值和最优值之间的偏差也只有4,结果差别不大。

为了验证改进的禁忌搜索算法(MTS)的有效性,对标准的禁忌搜索算法(TS)采用上述相同的参数取值进行了20次运行,得到的最优解为96,与最差值的偏差为6。通过比较可以得出,MTS比TS有较好的稳定性。

注:表中加工工件序列中的1-10为工件名

5 总结

本文利用改进的禁忌搜索算法对车间作业排序更广泛的情形进行了研究,实验结果证明提出的算法可行、有效,具有一定的应用性。另外,随着问题规模的不断扩大及约束条件的增加,可能还需建立更加经济可行的问题模型,以及对这一模型提出更加高效、先进的算法,这有待于进一步研究。

摘要：本文描述了一种解决车间作业调度最短完工时间问题的有效禁忌搜索算法,建立了该问题的数学模型,并提出了新的邻域构造方法。该算法利用改进的插入算法构造尽可能好的初始解,然后使用禁忌搜索算法改进当前解。实验结果表明该算法是可行和有效的。

关键词：禁忌搜索算法,NP-难,车间作业调度

参考文献

[1]Garey M R,Johnson D S.Computer and intrac-tability:a guide to the theory of NP-complete-ness[M].San Francisco:Freeman,1979.