当前位置:文档之家› 第七讲 禁忌搜索..

第七讲 禁忌搜索..

13
三种禁忌对象:(1)解的简单变化(类比于函数
中的自变量x的变化)
假设x, y D,邻域映射为 N,其中D为优化问题的定义域, 则简单解变化 x y N ( x) 是从一个解变化到另一 个解。

三种禁忌对象:(2)向量分量的变化(类比于函 数中的映射规则变化) 设原有的解向量为(x1, …, xi-1, xi, xi+1, …, xn),向量 分量的最基本变化为 (x1, …, xi-1, xi, xi+1,…, xn)→(x1, …, xi-1, yi, xi+1,…, xn) 即只有第i个分量发生变化。 也包含多个分量变化的情形。
Байду номын сангаас
历史搜索过程存放在禁忌表中,防止算法重新进 入。
② 不以局部最优作为停止准则,算法接受劣解,只
要不在禁忌表的较好解都可作为下一次迭代的初 始解。
③ 邻域选优的规则模拟了人类的记忆功能——找过
的地方都记下来,不再找第二次。随着迭代的进 行,禁忌表不断更新,一定迭代次数后,早期进 4 入禁忌表解被解禁退出。
2(正值表示绝缘效果
变好)
1 -1(负值表示绝缘效果
变坏)
-2 -4


5
禁忌表作用示例(2)
可见,交换材料1和3 可增加绝缘数值2,并 且改善效果最好,交 换后2-4-7-1-5-6-3.绝 缘数值为18,将交换 (1,3)加入禁忌表。 此时两两交换材料对 绝缘效果的影响见下 表。 交换的材料 绝缘效果
1,3 2,4 -2 -4
6,7
4,5
-6
-7
3,5

-9

6
禁忌表作用示例(3)
上表看出,交换(1,3)对绝缘数值的降 低最小,但是交换后又回到以前的状态, 为避免回到上一次交换前的状态,采用禁 忌表。 所以,选择交换(2,4),是其它选择中 使绝缘数值降低最小的一对。 此禁忌表中存放的不是解,而是解的移动。 为实现全局搜索,往往设置渴望水平,若 一个移动达到渴望水平,能跳离局部最优, 该移动可以不受禁忌表的限制,称为破禁。
禁忌表作用示例(1)
七种不同绝缘材料构 成一种绝缘体,如何 排列七种材料使得绝 缘效果最好? 绝缘效果以绝缘数值 表示,数值越大,效 果越好。 某次迭代后,材料的 排列顺序为2-4-7-3-56-1,交换各种材料对 绝缘效果的改善情况 见下表:
交换的材料 绝缘效果改善
1,3 2,3 3,4 1,7 1,6

三种禁忌对象:(3)目标值的变化(类比于函数 的值域的变化) 目标值的变化隐含着解集合的变化。
(6) 选择策略
选择策略是从邻域中选择一个较好解作为 下一次迭代初始解的方法。 候选解集的确定是选择策略的关键,对算 法性能影响很大。 候选解集为整个邻域。选择策略是从整个 邻域内选择一个最优解为下一次迭代的初 始解,计算时间较长。 候选解集为邻域的真子集。这种选择策略 只扫描邻域的一部分构成候选解集,虽不 能找到邻域内最优解,但减少了搜索时间。
9
(2) 适值函数的构造
适值函数是用来对搜索状态进行评价的。 对目标函数的任何变形都可作为目标函数, 只要该变形保持严格单调。
10
(3)初始解的获得
可以随机给出初始解,也可以是其它启发 式算法给出的较好的初始解。 禁忌搜索算法主要是基于邻域搜索的,所 以初始解对算法搜索性能影响很大。 对于较为复杂的约束问题,随机产生的初 始解可能是不可行解,应该采用一些启发 式方法找到一个可行解作为初始解。
1977年F.Glover提出禁忌搜索算法,90年代
初得到广泛重视。
是GA之后提出的另一启发式优化方法。
模仿人类的记忆功能,使用禁忌表封锁刚搜
索过的区域,以避免迂回搜索。
同时赦免禁忌区域中的一些优良状态,以保
证搜索的多样性。
3
一.导言(2)
2. TS的基本思想——避免在搜索过程中的循环 ① 只进不退的原则——用Tabu表锁住退路,将近期
17
(7) 渴望水平函数
在有些特定的条件下,不管某个移动是否在禁忌表中, 都接受这个移动并更新当前解和历史最优解。这个特 定的条件即为渴望水平。 渴望水平的设定有如下几种形式: (1)基于适配值的准则,如果某个候选解的适配值高 于历史最优解,无论是否处于禁忌表中,都选择接受。 (2)基于搜索方向的准则,某禁忌对象进入紧急表时 改善了适配值,而这次这个被禁忌的候选解由改善了 适配值,故破禁。 (3)基于影响力的准则,有的禁忌对象对适配值的影 响较大,解禁会对解有较大影响,解禁时要考虑。 (4)其它准则 18
11
(4) 移动与邻域移动
移动是产生新解的途径,从当前解可以进 行的所有的移动构成邻域,因此移动规则 的设计是算法的关键。 移动规则类似于交叉算子,根据具体问题 进行分析设计,如排序问题中采用两两交 换方式的移动规则。
12
(5) 禁忌表(Tabu List)
禁忌表是为了防止搜索过程出现循环而陷入局部 最优的,是禁忌搜索算法的核心。 某些移动经一定迭代次数后被解禁,又可重新访 问,因此禁忌表称为短期表。 禁忌对象:放入禁忌表的元素,主要包括三种, (1)以状态本身或状态变化为禁忌对象,其禁忌 范围适中;(2)以状态分量或状态分量的变化作 为禁忌对象,其禁忌范围较小;(3)以目标值为 禁忌对象,其禁忌范围较大。 禁忌长度:禁忌表的大小。禁忌表越小,计算时 间和存储空间越少,但禁忌表过小,会造成搜索 过程进入循环。禁忌长度分为固定禁忌长度和随 时间变化禁忌长度两类。
灵活的选择编码方法,如背包的0-1编码。 同一问题有多种编码方法,如分组问题:不相 同的n件物品分为m组,n=9,m=3. 编码1: 1-3-4-0-2-6-7-5-0-8-9 (1-4-3-0-6-2-5-7-0-9-8) 0起到隔开作用1-3-4分为一组,2-6-7-5一组, 8-9一组。 编码2: 1-2-1-1-2-2-2-3-3 (2-1-2-2-1-1-1-3-3) 表示1-3-4分为一组,2-6-7-5一组,8-9一组
第四章 禁忌搜索( Tabu Search )
一.导言 二.TS的基本原理及步骤 三.TS的算法步骤 四.TS可以克服局优的分析 五.TS举例 六.TS的中、长期表的使用 七.TS表的应用举例 八.学习TS的几点体会
1
搜索陷入循环
1的邻域
2
2的邻域 3
1
4的邻域
4
在邻域中找到最好的解
一.导言(1)
7
一.导言(3)
3.
TS的要素构成
(1) 编码方法
(2) 适值函数的构造 (3) 初始解的获得 (4) 移动与邻域移动 (5) 禁忌表(Tabu List)
(6) 选择策略
(7) 渴望水平函数(Aspiration Level Function) (8) 停止准则——与GA相似
8
(1) 编码方法
相关主题