忌搜索 2,算法的背景 噤忌搜索是一种亚启发式随机搜索算法,它从一个初始可 行解出发,选择一系列的特定搜索方向(移动)作为试探,选 择实现让特定的目标函数值变化最多的移动。为了避免陷 入局部最优解,TS搜索中采用了一种灵活的“记忆”技术 ,对已经进行的优化过程进行记录和选择,指导下一步的 搜索方向。TS是人工智能的一种体现,是局部领域搜索的 种扩展。禁忌搜索是在领域搜索的基础上,通过设置禁 忌表来禁忌一些已经历的操作,并利用藐视准则来奖励 些优良状态,其中涉及邻域、禁忌表、禁忌长度、候选解 藐视准则等影响禁忌搜索算法性能的关键因素。迄今为 止,TS算法在组合优化等计算机领域取得了很大的成功, 近年来又在函数全局优化方面得到较多的研究,并大有发 展的趋势
◼ 禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可 行解出发，选择一系列的特定搜索方向(移动)作为试探，选 择实现让特定的目标函数值变化最多的移动。为了避免陷 入局部最优解，TS搜索中采用了一种灵活的“记忆”技术 ，对已经进行的优化过程进行记录和选择，指导下一步的 搜索方向。 TS是人工智能的一种体现，是局部领域搜索的 一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁 忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一 些优良状态，其中涉及邻域 、禁忌表、禁忌长度、候选解 、藐视准则等影响禁忌搜索算法性能的关键因素。迄今为 止，TS算法在组合优化等计算机领域取得了很大的成功， 近年来又在函数全局优化方面得到较多的研究，并大有发 展的趋势。 2 禁忌搜索 2.1 算法的背景
2第忌搜索 2禁忌搜索示例 四城市非对称TSP问题 A B 0.5 010.51 D 1.550 D)1(c 初始解x=(ABCD),x)=4,邻域映射为两个城市 顺序对换的2-0pt,始、终点都是A城市
2 禁忌搜索 ◼ 四城市非对称TSP问题 初始解x 0=(ABCD)，f(x 0 )=4，邻域映射为两个城市 顺序对换的2－opt，始、终点都是A城市。 2.2 禁忌搜索示例
2第忌搜索 2禁忌搜索示例 0.5 四城市非对称TSP问题 第1步 解的形式禁忌对象及长度 候选解 B C D 对换评价值 AIBICID CD4.5 fx)=4 BC7.5 BD 8
2 禁忌搜索 ◼ 四城市非对称TSP问题 第1步 解的形式 禁忌对象及长度 候选解 f(x 0 )=4 2.2 禁忌搜索示例 A B C D B C D A B C 对换 评价值 CD 4.5 BC 7.5 BD 8 ☻
2第忌搜索 22忌搜索示例一 0.5 四城市非对称TSP问题 第2步 解的形式禁忌对象及长度 候选解 B C D 对换评价值 AlBIDIC CD45T fx)=4.5 B BC3.58 C|3 BD4.5
2 禁忌搜索 ◼ 四城市非对称TSP问题 第2步 解的形式 禁忌对象及长度 候选解 f(x 1 )=4.5 2.2 禁忌搜索示例 A B D C B C D A B C 3 对换 评价值 CD 4.5 BC 3.5 BD 4.5 ☻ T
2第忌搜索 22忌搜索示例一 0.5 四城市非对称TSP问题 第3步 解的形式禁忌对象及长度 候选解 B C D 对换评价值 AICIDIB CD8T fx2)=35 b3 BC45T C|2 BD7.5
2 禁忌搜索 ◼ 四城市非对称TSP问题 第3步 解的形式 禁忌对象及长度 候选解 f(x 2 )=3.5 2.2 禁忌搜索示例 A C D B B C D A B 3 C 2 对换 评价值 CD 8 BC 4.5 BD 7.5☻ T T