摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。
关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法
1 引言
工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识,属于局部优化算法。智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(tabu search, ts)最早是由glover在1986年提出,它的实质是对局部邻域搜索的一种拓展。ts算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。ts算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化[1]。
迄今为止,ts算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景[2~9,11~15]。Www.133229.CoM目前关于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~15]。
(2)为推广禁忌搜索算法在超大规模优化领域中的应用,突破禁忌搜索的串行性限制,研究并行禁忌搜索算法。包括基于问题空间分解的并行策略和基于多禁忌搜索任务的并行策略[1]。
(3)对禁忌搜索算法本身的关键步骤进行改良设计。如根据禁忌频率信息在算法中增加集中搜索和分散搜索,分别实现优良区域的重点搜索和搜索范围的扩展。
(4)探索禁忌搜索算法适于应用的新的优化领域。
进一步研究禁忌搜索算法中相关参数及操作对算法性能影响的相关理论,开发更加高效的禁忌搜索算法。
参考文献
[1] 王凌. 智能优化算法及其应用[m]. 北京:清华大学出版社,2001.
[2] 李新振,腾欢.自适应遗传——禁忌搜索混合算法在pmu最优配置中的应用[j].四川电力技术,2009,32(3):56-60.
[3] 刘嘉敏,董宗然,马广焜.基于禁忌搜索算法求解集装箱装载问题[j].沈阳工业大学学报,2009,31(2):212-216.
[4] 王竹芳,潘德惠.用遗传:禁忌搜索混合算法求解组合投资问题[j].东北大学学报(自然科学版),2006,27(1):111-114.
[5] 肖丽,刘光远,贺一等.基于禁忌搜索的模糊神经网络结构优化[j].计算机科学,2006,33(7):217-219.
[6] 宋晓宇,孟秋宏,曹阳.求解job shop调度问题的改进禁忌搜索算法[j].信息工程与电子技术,2008,30(1):94-96.
[7] 黄志,黄文奇.一种基于禁忌搜索的作业车间调度算法[j].计算机工程与应用,2006,42(3):12-14.
[8] 段凤华,符卓.有软时窗约束带取送作业的车辆路径问题及其禁忌搜索算法研究[j].计算机工程与科学,2009,31(3):68-70.
[9] 汪翼,孙林岩,李刚,等.集装箱车辆调度问题的变邻域禁忌搜索算法[j].工业工程与管理,2008,13(5):6-10.
[10] 孙艳丰,郑加齐,王德兴,等.基于遗传算法的约束优化方法评述[j].北方交通大学学报,2000,24(6):14-19.
[11] 陈年生,李腊元,董武世,等.基于禁忌搜索的qos路由算法[j].计算机工程与应用,2005,41(8):134-136.
[12] 张玉芳,薛青松,熊忠阳.基于禁忌搜索的动态粒子群算法[j].计算机工程与应用,2008,44(24):56-58.
[13] 康雁,黄文奇.基于禁忌搜索的启发式算法求解圆形packing问题[j].计算机研究与发展,2004,41(9):1554-1558.
[14] 吴良杰,魏东,刘刚.基于禁忌搜索和蚁群算法的广义分配问题研究[j].计算机工程与设计,2009,30(15):3591-3593.
[15] 王伟,余利华.基于贪心法和禁忌搜索的实用高校排课系统[j].计算机应用,2007,27(11):2874-2876.
