高等运筹学6.ppt

1 第 章禁忌搜索算法 禁忌搜索 TabuSearch TS 的思想是由Glover于1986年提出的 并逐步形成了一套完整的算法 算法思想源于对人类智力过程的一种模拟 所以TS也是一种人工智能算法 模拟退火 SA 模拟固体物质退火过程 禁忌搜索 TS 模拟人类智力过程 遗传算法 GA 模拟生物进化过程 与SA GA等通用启发式算法一样 TS也是对局部搜索算法的一种扩展 是一种全局逐步寻优算法 所谓禁忌就是禁止重复前面的工作 算法引入一个禁忌表记录下已经搜索过的点 在下一次搜索中 利用禁忌表中的信息不再或有选择地搜索这些点 2 主要内容 6 1禁忌搜索算法示例6 2禁忌搜索算法的基本思想和步骤6 3禁忌搜索算法的关键参数和操作设计 3 6 1禁忌搜索算法示例 以TSP为例说明禁忌搜索的主要思想 问题规模n 7 邻域结构 定义为 互换 swap 操作 即随机交换两个城市在当前解中的排列位置 则每个解的邻域解有 n n 1 2 7 7 1 2 21个 每次迭代用其中最好的5次变换作为候选解 每次变换将导致目标函数节约值 即目标函数差 的变化 每个被采纳的变换在禁忌表中将滞留3步 称为禁忌长度 但若禁忌对象对应的目标函数节约值优于到目前为止所搜索到的最好解 best so far 则无视其禁忌属性而仍接受该解 藐视准则 4 归纳起来TS有如下主要特征 1 邻域结构的设计很关键 它决定了当前解的邻域解的产生形式和数目 2 候选解集仅取其中的少量最佳状态组成 3 禁忌长度直接影响整个算法的搜索进程和行为 4 藐视准则的设置是算法避免遗失优良状态 5 对于非禁忌的候选解 算法无视它与当前解的目标函数值的优劣关系 即可能比当前解差 仅考虑从中取出最佳的一个作为下一步的当前解 以此来实现跳出局部最优 是一种确定性策略 6 新解不是在当前解的邻域中随机产生 而是非禁忌的最佳候选解 或者是优于 最好解 的候选解 7 必须设置一个合理的终止准则 5 6 2TS的基本思想和步骤 算法的基本思想 给定一个当前解 初始解 和候选解产生函数 邻域结构 然后在当前解的邻域中确定若干候选解 若最佳候选解对应的目标值优于到目前为止搜索到的 最好解 best so far 则忽视其禁忌特性 用其替代当前解和 最好解 若不存在上述候选解 则在候选解集中选择非禁忌的最佳候选解为新的当前解 而无视它与当前解的优劣 两种情况下都将相应的对象加入禁忌表 并修改禁忌表中各对象的任期 如此重复上述迭代搜索过程 直到满足停止准则 6 禁忌搜索算法主要步骤流程图 由当前解产生候选解集 将该解作为新的当前解和到目前为止的最好解 有满足藐视准则的候选解否 算法终止准则满足否 输出结果 更新禁忌表中各对象的任期 给定算法参数 产生初始解 置禁忌表为空 N Y N Y 选择非禁忌的最佳候选解为新的当前解 7 6 3TS的关键参数和操作设计 1 初始解可以随机产生 也可以借助一些经典启发式方法产生以保证一定的初始解性能 2 邻域结构即候选解产生函数 用于从当前解的邻域中产生一个新解 对算法搜索质量和效率有重要影响 通常选择当前解经过简单地变换即可产生新解的方法 如上例中的 互换 swap 操作 为了使算法渐近收敛于全局最优解 所构造的邻域结构应能使解空间中的任何两个状态通过有限步邻域搜索后互达 8 3 候选解的选择候选解数量的确定 确定性或随机性地在当前解的邻域解集中选取一个子集作为候选解集 其大小一般为50 500个 最佳候选解的选取 选择候选解集中满足藐视准则或非禁忌的最佳候选解 4 解评价函数用于对搜索到的候选解进行评价 方法 直接用目标函数作为解评价函数 用反映问题目标的某些特征值来作为解评介函数 但要保证特征值的最佳性与目标函数的最优性一致 如上例中用 节约值 9 5 禁忌对象被置入禁忌表中的那些变化元素 禁忌的目的是为了尽量避免迂回搜索 1 以整个解的变化为禁忌对象 当解状态由x变化到解状态y时 将解y 或x y的变化 视为禁忌对象 2 以解分量的变化为禁忌对象 如示例中的情形 3 以目标值的变化作为禁忌对象 6 禁忌表和禁忌长度禁忌表 tabulist 是针对禁忌对象所设计的一种结构 可以是一维或二维的 禁忌长度t tabulength 是禁忌对象的禁忌期 即不允许再次被选取的迭代次数 每迭代一步 t减少1 当t 0时解禁 10 禁忌长度t的选取 1 t是一个固定的数 如t 7 或者固定为与问题规模相关的一个量 如t 或t 2 2 t是动态变化的 即设定禁忌长度的变化区间 tmin tmax 如 5 10 等 7 藐视准则若某个禁忌候选解的目标值优于到目前为止搜索到的 最好解 bestsofar 则解禁此候选解为当前解和新的 最好解 若候选解均被禁忌 且不存在优于 最好解 的候选解 则对候选解中的最佳者进行解禁 以便搜索过程继续进行下去 11 8 终止条件 1 给定最大迭代步数 如N 10000 优点是易于操作和控制计算时间 但无法保证解的质量 2 给定当前的最好解保持不变的最大连续迭代次数 如2500次 3 设定目标值的偏离幅度 若ZLB为问题的下界 为给定的偏离幅度 则当f x ZLB 时 终止计算 4 设定禁忌对象的最大禁忌频率 若某个禁忌对象的禁忌频率超过给定的值 则终止计算 12 TS求解过程演示参考文献 1 符卓 带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究 系统工程理论与实践 2004 24 3 123 128 2 ZFu 符卓 REgleseandLYO