第4章_禁忌搜索.ppt

1、1,第四章禁忌搜索,2,第四章 禁忌搜索（Tabu Search）,一.导言 二.TS的构成要素 三.TS的算法步骤 四.TS可以克服局优的分析 五.TS举例 六.TS的中、长期表的使用 七.学习TS的几点体会,3,TS的提出 局域搜索LS过程： 产生一个初始解 ； 在 的邻域中选择一个能得到最好解的移动 ，若 不存在 ，则停止，输出 ； 令 ，返回上一步。,一.导言,LS的搜索结果完全依赖于初始解和邻域移动,4,5,TS的提出 Glover在1977年提出TS。相对于LS，TS的优点是能够 通过接受劣解来逃离局优，在90年代初开始受到广泛 的关注。,一.导言,6,TS的基本思想模拟人类的记忆

2、功能 允许接受劣解，逃离局优； 使用禁忌表，避免循环。,一.导言,7,问题的描述 TS仅用于离散优化，排斥实优化。,二. TS的构成要素,8,问题的描述 编码方法：与GA类似，用数学的形式来表示问题的解 初始解 的产生：随机产生或者采用启发式方法产生一个可行解 适值函数 的构造：往往直接将目标函数作为适值函数,二. TS的构成要素,9,邻域及邻域移动 邻域移动 ： ，其中 为单位步长， 为方向 邻域 ：,二. TS的构成要素,邻域 是邻域移动 可达到的解的集合,10,邻域举例： X=0,1,0,0,1,0,0 u=1,d=0,0,1,0,0,0,0 注意：移动的意义是灵活的，目的是便于搜索。如

3、： 排序问题中一次换位可称为一次移动，还可以使用交 叉和变异算子作为移动。,二. TS的构成要素,11,练 习,定义邻域移动为位值加1或减1, 对整数编码 2 2 3 5 3 ，下列编码是否在其邻域内： 2 3 3 5 3 ， 2 3 2 5 3 ， 2 2 3 5 5 ， 2 2 3 4 3 ， 2 2 2 5 3 ， 2 2 3 4 4 ，,是,否,是,否,否,是,12,练 习,定义邻域移动为两两换位, 对顺序编码 4 2 3 5 1 ，下列编码是否在其邻域内： 4 3 2 5 1 ， 4 3 5 1 2 ， 4 3 3 5 1 ， 5 2 3 4 1 ， 1 2 3 5 4 ， 3 4

4、2 5 1 ，,是,否,是,否,否,是,13,禁忌表短期表 禁忌表的作用：防止搜索出现循环 将移动、移动分量或适值作为禁忌对象 表的长度称为Tabu-Size，可以用来控制局域搜索和广域搜索 表是动态更新的把最新的解记入，最老的解从表中释放(解禁),二. TS的构成要素,14,选择策略 选择策略的作用：保证TS的优良局部搜索功能 每一步移动到不在T表中的邻域中的最优解，即若 ， 则令 ，本次移动到最优解,二. TS的构成要素,15,渴望水平 是一个取决于 和 的值，若有 则 是不受T表限制。即使 ，仍可取 渴望水平，一般为历史上曾经达到的最好适值。,二. TS的构成要素,禁忌策略和渴望水平共同

5、构成了TS的两大核心移动规则,16,停止准则 设定最大迭代次数 得到满意解 设定某个对象的最大禁忌频率,二. TS的构成要素,17,步骤： 选一个初始点 ， ，令 ， ，渴望水平 ，迭代指标 ； 若停止，否则令 ；若 (其中NG为最大迭代数)停止； 注：表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度邻域大小)。步骤的作用是设置循环体出口。,三. TS的算法步骤,18,若 ，若 ，令 ，转5； 注：步骤的作用破禁检查 若 ， 令 ； 注：步骤的作用邻域选优,三. TS的算法步骤,19,三. TS的算法步骤,若 ，令 ， ， ； 注：步骤的作用选优并记录历史最好点，更新渴望水平

6、更新T表，转步2； 注： 存入T表中的第一个位置,20,从邻域搜索的方法看 移向中最好的解，但不与当前解比较 是 中的最优点，但 可能劣于,四.TS可以克服局优的分析,21,从选优规则看 始终保持历史上的最优解，不以当前解为最优 从停止规则上看 不以最优判据为停止规则，而是指定最大迭代步数为 停止条件，这样不能保证最优性。,四.TS可以克服局优的分析,22,问题的提出 由7层不同的绝缘材料构成的一种绝缘体，应如 何排列顺序，可获得最好的绝缘性能。,五.TS举例,23,编码方式：顺序编码 初始编码：2-5-7-3-4-6-1 目标值：极大化目标值。 邻域定义：两两交换是一个邻域移动 邻域大小：

7、Tabu Size：3NG：5,五.TS举例,24,初始表 初始编码：2-5-7-3-4-6-1 结论：交换4和5,五.TS举例,25,迭代1编码：2-4-7-3-5-6-1 结论：交换1和3,五.TS举例,26,迭代2编码：2-4-7-1-5-6-3 结论：因交换1和3已在禁忌表中，故只能交换2和4,五.TS举例,若选择这项 C(x)=16，渴望水平 不能发生作用,27,迭代3编码：4-2-7-1-5-6-3 结论：因渴望水平发挥作用，交换4和5,五.TS举例,因C(x)=20A(s,x)=18，此时渴望水平 发生作用，破禁。交换4和5。,28,迭代4编码：5-2-7-1-4-6-3 结论：

8、交换7和1,五.TS举例,29,迭代5编码：5-2-1-7-4-6-3 结论：迭代已到5次，得到最优解 5-2-7-1-4-6-3和5-2-1-7-4-6-3,五.TS举例,30,引入中长期表的目的 改善TS的广域搜索能力，TS的局域搜索能力很好，邻 域选优快，但仅依靠禁忌表（短期表）长来控制广域 搜索能力有限，故可采用中长期表可改善TS的广域搜 索能力。,六.TS的中、长期表的使用,31,中期表频数表 频数表的作用 频数表是用来记忆不同方向的移动次数，从而加以惩 罚（比如两两交换，记录每对交换的发生次数）从而 提高搜索方向的多样性。,六.TS的中、长期表的使用,32,在邻域选优公式中，令 注

9、：惩罚因子 的取值一般应远小于目标值（1%目标 值或1目标值）， 越大分散性越好，广域搜索能力 强，但会损坏邻域搜索。,六.TS的中、长期表的使用,33,频数表的记录方法 建立nn的数组，对上半部分每做一步搜索将所有0的数减1； 对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size； T表的下半部分，用来记频数，每次(i,j)交(ij)，对应的(j,i)+1)来记忆频数。,六.TS的中、长期表的使用,频数表的优点：同一数组作为T表和频数表共同使用，方便操作又节省了时间。,34,频数表：Tabu-Size=7,六.TS的中、长期表的使用,35,频数表：Tabu-Size=7,六.T

10、S的中、长期表的使用,36,长期表的使用多阶段TS算法 长期表的作用 长期表用来记录每个阶段的初始解，在下一阶段产生 初始解时，使之尽可能与已有的初始解有较大的距离,六.TS的中、长期表的使用,37,图示,六.TS的中、长期表的使用,38,函数表达式 长期表的TS有很好的性能。,六.TS的中、长期表的使用,39,TS的记忆功能短、中、长期表要灵活使用 TS相对于GA是更快的算法，局域搜索能力强，但全局搜索能力较弱； 改善TS的全局搜索能力，提高TS的分散性的方法 用长期表,七.学习TS的几点体会,40,加大Tabu Size 加大对频数的惩罚，即增大 TS仍是一种启发式，不能保证最优性 TS的理论工作较少,七.学习TS的几点体会,41,练 习,某公司拟在4个地点建