禁忌搜索算法评述.ppt

禁忌搜索算法评述
——董宗然周慧(大连东软信息学院,工学硕士)
讲述人:孙辉
禁忌搜索算法评述
4 总结展望
2 基本流程
3 关键设计
1 引言
论文结构
1 引言
优化算法
优化问题
启发式算法
智能随机算法
工程领域
计算机领域
……
TS算法
依赖对问题
性质的认识;
局部优化算法
按照一定的规则
搜索解空间,
直到似优解或最优解
全局优化算法
如:遗传算法
模拟退火算法
粒子群算法
禁忌搜索算法
……
模拟人类智能的记忆机制
采用禁忌策略,
限制局部最优,
避免迂回搜索。
2禁忌搜索算法的基本流程
(1)设定算法参数,产生初始解x,置空禁忌表。
(2)判断是否满足终止条件?若是,则结束,并输出结果否则,继续以下步骤。
(3)利用当前解x的邻域结构产生邻域解,并从中确定若干候选解。
(4)对候选解判断是否满足藐视准则?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“best so far”状态,然后转步骤(6);否则,继续以下步骤。
(5)判断候选解对应的各对象的禁忌情况,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。
(6)转步骤(2)。
3禁忌搜索算法的关键设计
禁忌搜索对初始解的依赖较大,好的初始解往往会提高最终的优化效果。初始解的构造可以借助一些启发式方法产生,以保证初始解的性能。
邻域移动:在当前解的基础上,按照特定的移动策略产生一定数目的新解,这些新解被称为邻域解,新解的数目称为邻域解规模。不同的移动将导致邻域解个数及其变化情况的不同,进而影响搜索的质量和效率。在一些应用中为了取得好的搜索效果,会根据搜索的进展情况动态改变邻域移动策略,即变邻域移动。
对于禁忌搜索空间中的解,通过评价函数来计算其对应的评价函数值,评价函数值的大小代表了解的优劣程度。
3禁忌搜索算法的关键设计
禁忌表是用来存放禁忌对象的一个容器,被放入禁忌表中的禁忌对象在解禁之前不能被再次搜索,可见禁忌表模拟了人的记忆机制,防止搜索陷入局部最优,进而探索更多的搜索空间。
禁忌长度就是每个禁忌对象在禁忌表中的生存时间,也称为禁忌对象的任期。搜索过程每迭代一次,禁忌表中的各禁忌对象的任期自动减1,当某一禁忌对象任期为0时,将其从禁忌表中删除。任期不为0的禁忌对象处于禁忌状态,不能被搜索过程选为新解。
候选解是当前解邻域解集的一个子集。搜索中为了减少搜索的代价(包括空间和时间),要求禁忌长度和候选解集尽量小。但禁忌长度过小将使搜索无法跳出局部最优,候选解集过小将使搜索早熟收敛。
3禁忌搜索算法的关键设计
特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解(或状态)被禁时,能够释放特定解(或状态),从而实现高效的全局优化搜索。
终止准则也称停止准则,即算法在何条件下停止搜索过程。实际应用中往往使用如下近似终止(收敛)准则。
(1)算法迭代次数达到指定最大次数停止。
(2)最优解的目标函数值小于指定误差。
(3)最优解的禁忌频率达到指定值。
4总结和展望
文章简述了禁忌搜索算法的发展、特点及应用,给出了基本禁忌搜索算法实现的流程,对禁忌搜索设计过程中的关键步骤进行了分析和总结,为推广禁忌搜索算法在优化领域的应用有一定意义。
4总结和展望
今后关于禁忌搜索算法的研究热点主要有以下几个方面。
(1)与其他优化算法结合,如与传统启发式算法、遗传算法、模拟退火算法、粒子群算法、神经网络算法、蚁群算法、混沌算法等结合,构成更新型的混合优化算法。
(2)为推广禁忌搜索算法在超大规模优化领域中的应用,突破禁忌搜索的串行性限制,研究并行禁忌搜索算法。包括基于问题空间分解的并行策略和基于多禁忌搜索任务的并行策略。
(3)对禁忌搜索算法本身的关键步骤进行改良设计。
(4)探索禁忌搜索算法适于应用的新的优化领域。