计算机算法（PPT讲稿）禁忌搜索算法 Tabu Search

合分合你小中分你你 禁忌搜索算法 (Tabu Search 吴浩博

禁忌搜索算法 （Tabu Search） 吴浩博

分合分专你你分合你小守分合小 1局部搜索 2禁忌搜索 算法的主要思路 2禁忌搜索示例 3禁忌搜索的关键参数和操作 3.1变化因素 32禁忌表 33其他 4禁忌搜索的实现与应用 41图结点染色

1 局部搜索 2 禁忌搜索 1 算法的主要思路 2 禁忌搜索示例 3 禁忌搜索的关键参数和操作 3.1 变化因素 3.2 禁忌表 3.3 其他 4 禁忌搜索的实现与应用 4.1 图结点染色

上局部搜索 局部搜索示例一 ■n个城市的对称旅行商问题 简单易行,但无法保证全局最优性 局部搜索主要依赖起点的选取和邻城的结构; 为了得到好的解,可以比较不同的邻域结构和不同 的初始点; 如果初始点的选择足够多, 总可以计算出全局最优解

1 局部搜索 ◼ n个城市的对称旅行商问题 简单易行，但无法保证全局最优性； 局部搜索主要依赖起点的选取和邻域的结构； 为了得到好的解，可以比较不同的邻域结构和不同 的初始点； 如果初始点的选择足够多， 总可以计算出全局最优解。 局部搜索示例

绕忌搜索 2,算法的背景 禁忌搜索算法( Tabu search)是由美国 科罗拉多州大学的 Fred glover教授在 1986年左右提出来的,是一个用来跳出 局部最优的搜寻方法。在解决最优问题 上,一般区分为两种方式:一种是传统 的方法,另一种方法则是一些启发式搜 索算法。 TABL

◼ 禁忌搜索算法（Tabu Search）是由美国 科罗拉多州大学的Fred Glover教授在 1986年左右提出来的，是一个用来跳出 局部最优的搜寻方法。在解决最优问题 上，一般区分为两种方式：一种是传统 的方法，另一种方法则是一些启发式搜 索算法。 2 禁忌搜索 2.1 算法的背景

2第忌搜索 2算法的背景 使用传统的方法,我们必须对每一个问题都去设 计一套算法,相当不方便,缺乏广泛性,优点在 于我们可以证明算法的正确性,我们可以保证找 到的答案是最优的;而对于启发式算法,针对不 同的问题,我们可以套用同一个架构来寻找答案, 在这个过程中,我们只需要设计评价函数以及如 何找到下一个可能解的函数等,所以启发式算法 的广泛性比较高,但相对在准确度上就不一定能 够达到最优,但是在实际问题中启发式算法那有 着更广泛的应用

2 禁忌搜索 2.1 算法的背景 使用传统的方法，我们必须对每一个问题都去设 计一套算法，相当不方便，缺乏广泛性，优点在 于我们可以证明算法的正确性，我们可以保证找 到的答案是最优的；而对于启发式算法，针对不 同的问题，我们可以套用同一个架构来寻找答案， 在这个过程中，我们只需要设计评价函数以及如 何找到下一个可能解的函数等，所以启发式算法 的广泛性比较高，但相对在准确度上就不一定能 够达到最优，但是在实际问题中启发式算法那有 着更广泛的应用

忌搜索 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