禁忌搜索算法教程

1、.,1,第三章 禁忌搜索,.,2,第三章 禁忌搜索,一.导言 二.禁忌搜索 三. TS举例 四. TS中短、中、长期表的使用 五.学习TS的几点体会,.,3,问题描述,一.导言,目标函数,约束条件,定义域,注：X为离散点的集合，TS排斥实优化,.,4,局域搜索 邻域的概念 函数优化问题： 邻域(N(x)通常定义为在给定距离空间内，以一点 (x)为中心的一个球体 组合优化问题： 且 ，称为一个邻域映射，其中 表示X 所有子集组成的集合。 N(x)称为x的邻域， 称为x的一个邻居。,一.导言,.,5,局域搜索 邻域的概念 例：TSP问题解的一种表示方法为D=x=(i1,i2,in)| i1,i2,

2、in是1,2,n的排列，定义它的邻域映射为 2-opt，即x中的两个元素进行对换，N(x)中共包含x的Cn2=n(n-1)/2个邻居和x本身。 例如：x=(1,2,3,4)， 则C42=6，N(x)=(1,2,3,4), (2,1,3,4), (3,2,1,4), (4,2,3,1), (1,3,2,4), (1,4,3,2), (1,2,4,3),一.导言,.,6,局域搜索 邻域的概念 例： 解的邻域映射可由2-opt，推广到k-opt，即对k个元素按一定规则互换。,一.导言,邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。,.,7,练 习,定义邻域移动为：位值加1或减1

3、对整数编码 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,是,否,否,是,是,否,.,8,练 习,定义邻域移动为：2-Opt 对顺序编码 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 2 5 1,是,否,否,是,是,否,.,9,局域搜索 局域搜索算法过程,一.导言,STEP 1 选定一个初始可行解x0，记录当前最优解xbest:=x0, T=N(xbest)； ST

4、EP 2 当Txbest=时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解xnow；若f (xnow)NG(其中NG为最大迭代数)，则停止；,二.禁忌搜索,注： 表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度A(s,x)=18，此时渴望水平 发生作用，破禁。交换4和5。,.,33,迭代4 编码：5-2-7-1-4-6-3 结论：交换7和1,三.TS举例,.,34,迭代5 编码：5-2-1-7-4-6-3 结论：迭代已到5次，得到最优解 5-2-7-1-4-6-3和5-2-1-7-4-6-3,三.TS举例,.,35,短期表-T表 T

5、表的主要指标： 禁忌对象：T表中被禁忌的那些变化元素 禁忌长度：T表的长度，禁忌对象的最大值,四.TS中短、中、长期表的使用,.,36,短期表-T表 T表的主要指标： 禁忌对象：T表中被禁忌的那些变化元素 禁忌长度：T表的长度，禁忌对象的最大值,四.TS中短、中、长期表的使用,.,37,短期表-T表 T表的主要指标： 禁忌对象：T表中被禁忌的那些变化元素 禁忌长度：T表的长度，禁忌对象的最大值,四.TS中短、中、长期表的使用,.,38,练 习,初始解：(ABCDE)，邻域移动方式为2-OPT，T表长度为4，NG=5，分别以解、移动和函数值为禁忌对象进行求解，并分析各自的特点。,.,39,短期表

6、-T表 T表的主要指标： 禁忌对象：T表中被禁忌的那些变化元素 禁忌长度：T表的长度，禁忌对象的最大值,四.TS中短、中、长期表的使用,受禁范围：解的变化 邻域移动 函数值,计算时间：函数值 邻域移动 解的变化,摆脱局优：函数值 邻域移动 解的变化,.,40,短期表-T表 T表的主要指标： 禁忌对象：T表中被禁忌的那些变化元素 禁忌长度：T表的长度，禁忌对象的最大值 设为常数，易于实现 设为变化的数，在 之间变化,四.TS中短、中、长期表的使用,禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出； 禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。,.,41,练 习,初始解：(ABC

7、DE)，邻域移动方式为2-OPT，以移动为禁忌对象，NG=5，T表长度分别设为2,4和6进行求解，并分析各自的特点。,.,42,中期表-频数表 频数表的作用：频数表是用来记忆不同方向的移动次数，从而加以惩罚（比如2-OPT，记录每对交换的发生次数）从而提高搜索方向的多样性 在邻域选优公式中，令 其中，E(s(x)表示移动s(x)的出现频数，为惩罚因子,四.TS中短、中、长期表的使用,注：惩罚因子的取值一般应远小于目标值（1%目标值或1目标值），越大分散性越好，广域搜索能力强，但会损坏邻域搜索。,.,43,中期表-频数表 频数表的记录方法 建立nn的数组，对上半部分每做一步搜索将所有0的数减1；

8、 对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size； 下半部分用来记频数，每次(i,j) (ij)交换，对应的(j,i)+1)来记忆频数,四.TS中短、中、长期表的使用,频数表的优点：同一数组作为T表和频数表共同使用，方便操作又节了时间。,.,44,频数表：Tabu-Size=7,四.TS中短、中、长期表的使用,.,45,频数表：Tabu-Size=7,四.TS中短、中、长期表的使用,.,46,长期表- 多阶段TS 长期表的作用：长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离,四.TS中短、中、长期表的使用,.,47,长期表- 多阶段TS 函数表达式,四.TS中短、中、长期表的使用,.,48,TS的记忆功能短、中、长期表要灵活使用 TS相对于GA是更快的算法，局域搜索能力强，但全局搜索能力较弱； 改善TS的全局搜索能力，提高TS的分散性的方法 用长期表 加大Tabu Size 加大对频数的惩罚，即增大 TS仍是一种启发式，不能保证最优性 TS的理论工作较少,五.学习TS的几点体会,.,49,作 业,30城市TSP问题（d*=423.741 by D B Fogel）,TSP Benchmark 问题 41 94;37 84;54 67;25 62; 7 64;2 99;68