禁忌搜索算法评述.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禁忌搜索算法的关键设计?禁忌长度的选取则主要有静态和动态两种方法。静态方法是指在搜索过程中,禁忌长度是一个固定值,比如√n, 其中 n为问题维数或规模。动态方法是指在搜索过程中, 禁忌长度也是动态变化的,当算法搜索能力较强时,可以增大禁忌长度从而延续当前的搜索能力,并避免搜索陷入局部优解。?禁忌频率记录每个禁忌对象出现在禁忌表中的次数,以此作为搜索过程的重要参考,如若某个对象出现频繁,则可以增加禁忌长度来避免循环。 3禁忌搜索算法的关键设计?特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解(或状态)被禁时,能够释放特定解(或状态),从而实现高效的全局优化搜索。?终止准则也称停止准则,即算法在何条件下停止搜索过程。实际应用中往往使用如下近似终止(收敛)准则。?(1)算法迭代次数达到指定最大次数停止。?(2)最优解的目标函数值小于指定误差。?(3)最优解的禁忌频率达到指定值。 4总结和展望?文章简述了禁忌搜索算法的发展、特点及应用,给出了基本禁忌搜索算法实现的流程,对禁忌搜索设计过程中的关键步骤进行了分析和总结,为推广禁忌搜索算法在优化领域的应用有一定意义。 4总结和展望?今后关于禁忌搜索算法的研究热点主要有以下几个方面。?(1)与其他优化算法结合,如与传统启发式算法、遗传算法、模拟退火算法、粒子群算法、神经网络算法、蚁群算法、混沌算法等结合,构成更新型的混合优化算法。?(2)为推广禁忌搜索算法在超大规模优化领域中的应用, 突破禁忌搜索的串行性限制,研究并行禁忌搜索算法。包括基于问题空间分解的并行策略和基于多禁忌搜索任务的并行策略。?(3)对禁忌搜索算法本身的关键步骤进行改良设计。?(4)探索禁忌搜索算法适于应用的新的优化领域。