禁忌搜索算法 (第6章).ppt

禁忌搜索算法 (第6章).ppt1
第6章禁忌搜索算法
禁忌搜索(Tabu Search, TS)的思想是由Glover于1986年提出的,并逐步形成了一套完整的算法.
算法思想源于对人类智力过程的一种模拟. 所以TS也是一种人工智能算法.
模拟退火(SA):模拟固体物质退火过程.
禁忌搜索(TS):模拟人类智力过程.
遗传算法(GA):模拟生物进化过程.
与SA、GA等通用启发式算法一样,TS也是对局部搜索算法的一种扩展,是一种全局逐步寻优算法.
,在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点.
2
主要内容
禁忌搜索算法示例
禁忌搜索算法的基本思想和步骤
禁忌搜索算法的关键参数和操作设计
3
禁忌搜索算法示例
以TSP为例说明禁忌搜索的主要思想.
问题规模n=7.
邻域结构:定义为“互换(swap)”操作,即随机交换两个城市在当前解中的排列位置,则每个解的邻域解有= n (n-1) / 2= 7 (7-1) /2 = .
每次变换将导致目标函数节约值(即目标函数差)的变化.
每个被采纳的变换在禁忌表中将滞留3步(称为禁忌长度).
但若禁忌对象对应的目标函数节约值优于到目前为止所搜索到的最好解(“best-so-far”),则无视其禁忌属性而仍接受该解.——藐视准则.
4
归纳起来TS有如下主要特征:
(1)邻域结构的设计很关键,它决定了当前解的邻域解的产生形式和数目.
(2)候选解集仅取其中的少量最佳状态组成.
(3)禁忌长度直接影响整个算法的搜索进程和行为.
(4)藐视准则的设置是算法避免遗失优良状态.
(5)对于非禁忌的候选解,算法无视它与当前解的目标函数值的优劣关系(即可能比当前解差),仅考虑从中取出最佳的一个作为下一步的当前解,以此来实现跳出局部最优(是一种确定性策略).
(6)新解不是在当前解的邻域中随机产生,而是非禁忌的最佳候选解,或者是优于“最好解”的候选解.
(7)必须设置一个合理的终止准则.
5
TS的基本思想和步骤
算法的基本思想:给定一个当前解(初始解)和候选解产生函数(邻域结构),然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于到目前为止搜索到的“最好解”(best-so-far),则忽视其禁忌特性,用其替代当前解和“最好解”;若不存在上述候选解,则在候选解集中选择非禁忌的最佳候选解为新的当前解,而无视它与当前解的优劣;两种情况下都将相应的对象加入禁忌表,并修改禁忌表中各对象的任期;如此重复上述迭代搜索过程,直到满足停止准则.
6
禁忌搜索算法主要步骤流程图
由当前解产生候选解集
将该解作为新的当前解
和到目前为止的最好解
有满足藐视准则的候选解否?
算法终止准则满足否?
输出结果
更新禁忌表中各对象的任期
给定算法参数,产生初始解,置禁忌表为空
N
Y
N
Y
选择非禁忌的最佳
候选解为新的当前解
7
TS的关键参数和操作设计

可以随机产生,也可以借助一些经典启发式方法产生以保证一定的初始解性能.

即候选解产生函数,.
“互换(swap)”操作.
为了使算法渐近收敛于全局最优解,所构造的邻域结构应能使解空间中的任何两个状态通过有限步邻域搜索后互达.
8

候选解数量的确定:确定性或随机性地在当前解的邻域解集中选取一个子集作为候选解集,其大小一般为50~500个.
最佳候选解的选取:选择候选解集中满足藐视准则或非禁忌的最佳候选解.

用于对搜索到的候选解进行评价.
方法:
直接用目标函数作为解评价函数;
用反映问题目标的某些特征值来作为解评介函数,“节约值”.
9

.
(1),将解y(或x→y的变化)视为禁忌对象.
(2).
(3)以目标值的变化作为禁忌对象.

禁忌表(tabu list)是针对禁忌对象所设计的一种结构,可以是一维或二维的.
禁忌长度t(tabu length)是禁忌对象的禁忌期,,t减少1,当t=0时解禁.
10
禁忌长度t的选取:
(1)=7,或