2第忌搜索 22忌搜索示例一 0.5 四城市非对称TSP问题 第4步 解的形式禁忌对象及长度 候选解 B C D 对换评价值 AICIBID CD45T fx3)=7.5 B23 BC45T C|1 BD35T 禁忌长度的涉驭
2 禁忌搜索 ◼ 四城市非对称TSP问题 第4步 解的形式 禁忌对象及长度 候选解 f(x 3 )=7.5 禁忌长度的选取 2.2 禁忌搜索示例 A C B D B C D A B 2 3 C 1 对换 评价值 CD 4.5 BC 4.5 BD 3.5 T T T
2第忌搜索 22忌搜索示例一 0.5 四城市非对称TSP问题 第4步(如果减小禁忌长度 解的形式禁忌对象及长度 候选解 B C D 对换评价值 AICIBID CD4.5 fx3)=7.5 B1|2 BC45T CO BD35T
2 禁忌搜索 ◼ 四城市非对称TSP问题 第4步（如果减小禁忌长度） 解的形式 禁忌对象及长度 候选解 f(x 3 )=7.5 2.2 禁忌搜索示例 A C B D B C D A B 1 2 C 0 对换 评价值 CD 4.5 BC 4.5 BD 3.5 ☻ T T
2第忌搜索 2禁忌搜索示例一 0.5 四城市非对称TSP问题 第5步 解的形式禁忌对象及长度 候选解 B C D 对换评价值 AlDIBIC CD 7.5T fx4)=4.5 B01 BC 8 C|2 BD45T
2 禁忌搜索 ◼ 四城市非对称TSP问题 第5步 解的形式 禁忌对象及长度 候选解 f(x 4 )=4.5 2 禁忌搜索示例 A D B C B C D A B 0 1 C 2 对换 评价值 CD 7.5 BC 8 BD 4.5 ☻ T T
(开始 设置参数,产生初 始解,置空禁忌表 T 满足终止准则吗? 输出优解 入结束 TS算法 F 生成当前解的邻域解 框架 选出候选解 将满足藐视准则的解作为当前 T 满足视准则吗 解,用其对应的对象替换最早 进入禁忌表中的对象,更新最 优解 F 判断候选解禁总属性 将非禁忌的最佳候选解作为当 前解,用该解对应的对象替换 最早进入禁忌表中的对象
TS算法 框架
(1)是否有其他形式的候选集? (2)禁忌的长度如何确定?如果在算法中记忆下搜索到 的当前最优解,极端的两种情况是:一是将所有的对换 个数作为禁忌长度,此时等价于将候选集中的所有的对 换遍历;另外则取为1,这等价于局部搜索算法。 (3)是否有评价值的其他替代形式?有时计算目标值的 作量较大,或无法接受计算目标值所花费的时间,于 是需要其他的方法。 ■(4)被禁的对换能否再一次解禁?有这样的直观现象, 当搜索到一个局部最优解后,它邻域中的其他状态都被 禁,我们是否解禁一些状态以便跳岀局部最优?解禁的 功能就是为了获得更大的搜索范围,以免陷入局部最优 (5)如何利用更多的信息?在禁忌搜索算法中,还可记 录其他一些信息。如一个被禁对象(交换)被禁的次数 ,评价值变化的大小等。 6)终止原则,即一个算法停止的条件,怎样给出?
◼ (1)是否有其他形式的候选集？ ◼ (2)禁忌的长度如何确定？如果在算法中记忆下搜索到 的当前最优解，极端的两种情况是：一是将所有的对换 个数作为禁忌长度，此时等价于将候选集中的所有的对 换遍历；另外则取为1，这等价于局部搜索算法。 ◼ (3)是否有评价值的其他替代形式？有时计算目标值的 工作量较大，或无法接受计算目标值所花费的时间，于 是需要其他的方法。 ◼ (4)被禁的对换能否再一次解禁？有这样的直观现象， 当搜索到一个局部最优解后，它邻域中的其他状态都被 禁，我们是否解禁一些状态以便跳出局部最优？解禁的 功能就是为了获得更大的搜索范围，以免陷入局部最优 。 ◼ (5)如何利用更多的信息？在禁忌搜索算法中，还可记 录其他一些信息。如一个被禁对象（交换）被禁的次数 ，评价值变化的大小等。 ◼ (6)终止原则，即一个算法停止的条件，怎样给出？