禁忌搜索算法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第三章禁忌搜索,1第三章禁忌搜索,2,第三章 禁忌搜索,一,.,导言,二,.,禁忌搜索,三,.TS,举例,四,.TS,中短、中、长期表的使用,五,.,学习,TS,的几点体会,2第三章 禁忌搜索,3,问题描述,一,.,导言,目标函数,约束条件,定义域,注：,X,为离散点的集合，,TS,排斥实优化,3问题描述一.导言目标函数约束条件定义域注：X为离散点的集合,4,局域搜索,邻域的概念,函数优化问题：,邻域,(,N,(,x,),通常定义为在给定距离空间内，以一点,(,x,),为中心的一个球体,组合优化问题：,且,，称为一个,邻域映射,，其中 表示,X,所有子集组成的集合。,N,(,x,),称为,x,的,邻域,，称为,x,的一个,邻居,。,一,.,导言,4局域搜索一.导言,5,局域搜索,邻域的概念,例：,TSP,问题解的一种表示方法为,D,=,x,=(,i,1,i,2,i,n,)|,i,1,i,2,i,n,是,1,2,n,的排列,，定义它的邻域映射为,2-opt,，即,x,中的两个元素进行对换，,N,(,x,),中共包含,x,的,C,n,2,=,n,(,n,-1)/2,个邻居和,x,本身。,例如：,x,=(1,2,3,4),，,则,C,4,2,=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),一,.,导言,5局域搜索一.导言,6,局域搜索,邻域的概念,例：,解的邻域映射可由,2-opt,，推广到,k,-opt,，即对,k,个元素按一定规则互换。,一,.,导言,邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。,6局域搜索一.导言邻域的构造依赖于解的表示，邻域的结构在智能,7,练 习,定义邻域移动为：位值加,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,是,否,否,是,是,否,7练 习定义邻域移动为：位值加1或减1是否否是是否,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,是,否,否,是,是,否,8练 习定义邻域移动为：2-Opt是否否是是否,9,局域搜索,局域搜索算法过程,Step 1,选定一个初始可行解,x,0,，记录当前最优解,x,best,:=,x,0,T,=,N,(,x,best,),；,Step 2,当,T,x,best,=,时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从,T,中选一集合,S,，得到,S,中的最好解,x,now,；若,f,(,x,now,),NG,(,其中,NG,为最大迭代数,),，则停止；,二,.,禁忌搜索,注：表示非正常终止，造成的原因：邻域小，,T,表长。正常设置为,(,T,表长度,A,(,s,x,)=18,，,此时渴望水平,发生作用，破禁。交换,4,和,5,。,32迭代3编码：4-2-7-1-5-6-3三.TS举例移动,33,迭代,4,编码：,5-2-7-1-4-6-3,结论：交换,7,和,1,三,.TS,举例,移动,7,，,1,0,4,，,3,-3,6,，,3,-5,5,，,4,-6,2,，,6,-8,T,表,1,4,，,5,2,2,，,4,3,1,，,3,33迭代4编码：5-2-7-1-4-6-3三.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,举例,T,表,1,1,，,7,2,4,，,5,3,2,，,4,34迭代5编码：5-2-1-7-4-6-3三.TS举例T表,35,短期表,-,T,表,T,表的主要指标：,禁忌对象：,T,表中被禁忌的那些变化元素,禁忌长度：,T,表的长度，禁忌对象的最大值,四,.TS,中短、中、长期表的使用,35短期表-T表四.TS中短、中、长期表的使用,36,短期表,-,T,表,T,表的主要指标：,禁忌对象：,T,表中被禁忌的那些,变化元素,禁忌长度：,T,表的长度，禁忌对象的最大值,四,.TS,中短、中、长期表的使用,变化因素,解的变化,解分量的变化,函数值的变化,36短期表-T表四.TS中短、中、长期表的使用变化因素解的变,37,短期表,-,T,表,T,表的主要指标：,禁忌对象,：,T,表中被禁忌的那些,变化元素,禁忌长度：,T,表的长度，禁忌对象的最大值,四,.TS,中短、中、长期表的使用,禁忌对象,解,移动,函数值,37短期表-T表四.TS中短、中、长期表的使用禁忌对象解移动,38,练 习,初始解,：,(ABCDE),，邻域移动方式为,2-OPT,，,T,表长度为,4,，,NG=5,，分别以解、移动和函数值为禁忌对象进行求解，并分析各自的特点。,38练 习初始解：(ABCDE)，邻域移动方式为2-OPT,39,短期表,-,T,表,T,表的主要指标：,禁忌对象：,T,表中被禁忌的那些变化元素,禁忌长度：,T,表的长度，禁忌对象的最大值,四,.TS,中短、中、长期表的使用,受禁范围：解的变化 邻域移动 函数值,计算时间：函数值 邻域移动 解的变化,摆脱局优：函数值 邻域移动 解的变化,39短期表-T表四.TS中短、中、长期表的使用受禁范围：解的,40,短期表,-,T,表,T,表的主要指标：,禁忌对象：,T,表中被禁忌的那些变化元素,禁忌长度：,T,表的长度，禁忌对象的最大值,设为常数，易于实现,设为变化的数，在 之间变化,四,.TS,中短、中、长期表的使用,禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；,禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。,40短期表-T表四.TS中短、中、长期表的使用禁忌长度过短，,41,练 习,初始解,：,(ABCDE),，邻域移动方式为,2-OPT,，以移动为禁忌对象，,NG=5,，,T,表长度分别设为,2,4,和,6,进行求解，并分析各自的特点。,41练 习初始解：(ABCDE)，邻域移动方式为2-OPT,42,中期表,-,频数,表,频数表的作用：,频数表是用来记忆不同方向的移动次数，从而加以惩罚（比如,2-OPT,，记录每对交换的发生次数）从而提高搜索方向的多样性,在邻域选优公式中，令,其中，,E,(,s,(,x,),表示移动,s,(,x,),的出现频数，,为惩罚因子,四,.TS,中短、中、长期表的使用,注：惩罚因子,的取值一般应远小于目标值（,1%,目标值或,1,目标值），,越大分散性越好，广域搜索能力强，但会损坏邻域搜索。,42中期表-频数表四.TS中短、中、长期表的使用注：惩罚因子,43,中期表,-,频数,表,频数表的记录方法,建立,n,n,的数组，对上半部分每做一步搜索将所有,0,的数减,1,；,对数组上半部分，给新发生的移动所对应的数组元加上,Tabu-Size,；,下半部分用来记频数，每次,(,i,j,),(,i,j,),交换，对应的,(,j,i,)+1),来记忆频数,四,.TS,中短、中、长期表的使用,频数表的优点：同一数组作为,T,表和频数表共同使用，方便操作又节了时间。,43中期表-频数表四.TS中短、中、长期表的使用频数表的优点,44,频数表：,Tabu-Size=7,四,.TS,中短、中、长期表的使用,T,表,1,3,，,4,2,1,，,7,3,5,，,6,4,3,，,7,5,2,，,6,6,4,，,5,7,1,，,3,1,2,3,4,5,6,7,1,1,6,2,3,3,1,7,4,4,1,2,5,1,5,6,1,1,7,1,1,44频数表：Tabu-Size=7四.TS中短、中、长期表的,45,频数表：,Tabu-Size=7,四,.TS,中短、中、长期表的使用,T,表,1,1,，,3,2,3,，,4,3,1,，,7,4,5,，,6,5,3,，,7,6,2,，,6,7,4,，,5,1,2,3,4,5,6,7,1,7,5,2,2,3,2,6,3,4,1,1,5,1,4,6,1,1,7,1,1,45频数表：Tabu-Size=7四.TS中短、中、长期表的,46,长期表,-,多阶段,TS,长期表的作用：,长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离,四,.TS,中短、中、长期表的使用,46长期表-多阶段TS四.TS中短、中、长期表的使用,47,长期表,-,多阶段,TS,函数表达式,四,.TS,中短、中、长期表的使用,47长期表-多阶段TS四.TS中短、中、长期表的使用,48,TS,的记忆功能,短、中、长期表要灵活使用,TS,相对于,GA,是更快的算法，局域搜索能力强，但全局搜索能力较弱；,改善,TS,的全局搜索能力，提高,TS,的分散性的方法,用长期表,加大,Tabu Size,加大对频数的惩罚，即增大,TS,仍是一种启发式，不能保证最优性,TS,的理论工作较少,五,.,学习,TS,的几点体会,48TS的记忆功能短、中、长期表要灵活使用五.学习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 58;71 44;54,62;83 69;64 60;18 54;22,60;83 46;91 38;25 38;24,42;58 69;71 71;74 78;87,76;18 40;13 40;82 7;62 32;,58 35;45 21;41 26;44 35;4 50,49作 业30城市TSP问题（d*=423.741 by,