APS算法之六禁忌搜索TS（上）

文章来源：泛普软件禁忌搜索Tabu Search (TS)：它的算法是创立一初始化的方案；基于初始化的方案，算法“移动” 到一相邻的方案。一般来说，许多移动是连续的过程，方案的质量被提高。一个禁忌 tabu 清单被用于指导搜寻，当一特殊的中断条件达到时，算法就结束。 (如. 当运行时间已经达到时)，它是(确定性) 搜寻算法。　它和基因算法GA不同是, 禁忌TS，它是(确定性) 搜寻算法，试图找到一组合优化问题的最佳方案。但是，它的算法也还是包括随机取样的方法。禁忌搜索TS: 基本概念：它的约束搜寻是由它的移动禁止的分类条件来进行的 (如, tabu)。　爬山探索”“ (对最小化问题) 1. 选择初始化方案 x 2. 选择一些移动s(x) 如下目标函数值 s(x) < 目标函数值 x 　如果没有移动存在，那么x 就是最佳的，方法停止。否者 ,

让 x := s(x)

及回到第二步 2. 它是非常简单的探索，其缺点是：局部优化，也许不是全局的优化。　禁忌搜索TS 特点： l 它的约束搜寻是由它的移动禁止的分类条件来进行的 l 是由一“遗忘策略”提供的短期记忆函数来自由搜索。熟悉分类的方法：爬山探索, 从它们的开始点到一个本地优化采取单向的前进。 (在前后最小化里, 山是“倒置”以致于爬山的方向是向下的。) 　在一组合问题里，爬山过程的主要限制：在开始点得到本地优化，当没有提高的移动是可能的时候，也许不是一个全局优化。　爬山探索不能保证一个全局的优化。 =>禁忌搜索TS 向导就像一个探索连续探险。由于没有提高移动，就不会成为困惑，也不会落后到一个先前出现本地优化。爬山法：依赖于初始方案和移动的定义“爬山探索”可以找到最佳方案，但是，大部分情况下，它总是局部优化。 1，选择初始化方案 x 和让 x* := x. 设置重复计数 k := 0, and 开始用一个空的tabu 清单. 2，邻近的决策方案和选择最佳方案:
如果删除所有的禁忌, 那么就去第四步4.
否则设置 k := k+1 and 选择最佳的可能的移动用相应的事先定义好的评估函数 3，检查, 是否从第二步改善目前最佳目标函数值：
如果是真，那么让 x* := x. 4，检查, 是否中断条件达到:
如果一个选择迭代次数已经占用，或是在整个，或是因为 x* 是最后的改善, 或如果所有移动被禁止，在从第二步直接达到这一步时，或如果运行时间被消耗，停止。 x* 是最好的方案.
　否则, 更新tabu清单 and 回到第二步2. l 本地搜索算法的组合（如爬山探索）用禁忌tabu 清单来克服局部优化。 l 禁忌清单tabu使用，提供“约束搜索”的方法。方案的产生关键依赖于禁忌清单的组成内容和第4步的更新方法。 l 对局部优化的条件没有参照的方法，除非指明那里是局部优化在先前找到的最佳方案上的提高。一个“最好”的移动（而不是提高移动），在每一步被选择，在评估函数里嵌入使用条件。 l 3个重要方面：　 1，评估函数的定义：
第二步的每一执行移动，从当前的方案x 到一相邻的方案，产出最大的提高－或, 缺少提高的可能性, 最小化的没有提高。在目标里，以允许只有非禁忌移动的限制为条件。　 2，更新禁忌 tabu清单
使用禁忌清单的主要目标是避免回到先前的方案状态。禁忌 tabu清单是以移动集合，，在最后最近搜索过程中迭代次数里，可以“倒退”（或undo) 一个移动　 3，中断条件
这里：迭代次数 (要么整个，要么提高步骤), 或运行时间. （待续）来源：AMT

发布：2007-04-22 10:21 编辑：泛普软件 · xiaona [打印此页] [关闭]

APS算法之六禁忌搜索TS（上）

泛普哈尔滨OA快博其他应用