第二章禁忌搜索算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 禁忌搜索算法,智能优化计算,华东理工大学自动化系,2007,年,2.1,局部搜索,2.1.1,邻域的概念,2.1.2,局部搜索算法,2.1.3,局部搜索示例,2.2,禁忌搜索,2.2.1,算法的主要思路,2.2.2,禁忌搜索示例,2.3,禁忌搜索的关键参数和操作,2.3.1,变化因素,2.3.2,禁忌表,2.3.3,其他,2.4,禁忌搜索的实现与应用,2.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4.2,基于禁忌搜索算法的系统辨识,智能优化计算,华东理工大学自动化系,2007,年,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,函数优化问题中,在距离空间中，通常的邻域定义是以一点为中心的一个球体；,组合优化问题中,2,.1.1,邻域的概念,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,例,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),2,.1.1,邻域的概念,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,例,TSP,问题解的邻域映射可由,2,opt,，推广到,k,opt,。,邻域概念的重要性,邻域的构造依赖于决策变量的表示，,邻域的结构在现代优化算法中起重要的作用。,2,.1.1,邻域的概念,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,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,),f,(,x,best,),，则,x,best,:=,x,now,，,T,=,N,(,x,best,),；否则,T,:=,T,S,；重复,SETP 2,。,2,.1.2,局部搜索算法,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,五个城市的对称TSP,问题,初始解为,x,best,=(,ABCDE,),，,f,(,x,best,)=45,，定义邻域映射为对换两个城市位置的,2-opt,，选定,A,城市为起点。,2,.1.3,局部搜索示例,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,五个城市的对称TSP,问题,方法,1,：全邻域搜索,第,1,步,N,(,x,best,)=(,ABCDE,),，,(,ACBDE,),，,(,ADCBE,),，,(,AECDB,),，,(,ABDCE,),，,(,ABEDC,),，,(,ABCED,),，,对应目标函数为,f,(,x,)=45,43,45,60,60,59,44,x,best,:=,x,now,=(,ACBDE,),2,.1.3,局部搜索示例,A B C D E,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,五个城市的对称TSP,问题,方法,1,：全邻域搜索,第,2,步,N,(,x,best,)=(,ACBDE,),，,(,ABCDE,),，,(,ADBCE,),，,(,AEBDC,),，,(,ACDBE,),，,(,ACEDB,),，,(,ACBED,),，,对应目标函数为,f,(,x,)=43,45,44,59,59,58,43,x,best,:=,x,now,=(,ACBDE,),2,.1.3,局部搜索示例,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,五个城市的对称TSP,问题,方法,2,：一步随机搜索,第,1,步,从,N,(,x,best,),中随机选一点，如,x,now,=(,ACBDE,),，,对应目标函数为,f,(,x,now,)=43 43,x,best,:=,x,now,=(,ACBDE,),2,.1.3,局部搜索示例,2.1,局部搜索,智能优化计算,华东理工大学自动化系,2007,年,五个城市的对称TSP,问题,简单易行，但无法保证全局最优性；,局部搜索主要依赖起点的选取和邻域的结构；,为了得到好的解，可以比较不同的邻域结构和不同的初始点；,如果初始点的选择足够多，,总可以计算出全局最优解。,2,.1.3,局部搜索示例,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,算法的提出,禁忌搜索（,Tabu,search,）是局部邻域搜索算法的推广，,Fred Glover,在,1986,年提出这个概念，进而形成一套完整算法。,算法的特点,禁忌,禁止重复前面的工作。,跳出局部最优点。,2,.2.1,算法的主要思路,,spot.colorado.edu,/glover/,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,初始,解,x,0,=(,ABCD,),，,f,(,x,0,)=4,，邻域映射为两个城市顺序对换的,2,opt,，始、终点都是,A,城市。,2,.2.2,禁忌搜索示例,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,第,1,步,解的形式 禁忌对象及长度 候选解,f,(,x,0,)=4,2,.2.2,禁忌搜索示例,A,B,C,D,B,C,D,A,B,C,对换,评价值,CD,4.5,BC,7.5,BD,8,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,第,2,步,解的形式 禁忌对象及长度 候选解,f,(,x,1,)=4.5,2,.2.2,禁忌搜索示例,A,B,D,C,B,C,D,A,B,C,3,对换,评价值,CD,4.5,BC,3.5,BD,4.5,T,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,第,3,步,解的形式 禁忌对象及长度 候选解,f,(,x,2,)=3.5,2,.2.2,禁忌搜索示例,A,C,D,B,B,C,D,A,B,3,C,2,对换,评价值,CD,8,BC,4.5,BD,7.5,T,T,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,第,4,步,解的形式 禁忌对象及长度 候选解,f,(,x,3,)=7.5,禁忌长度的选取,2,.2.2,禁忌搜索示例,A,C,B,D,B,C,D,A,B,2,3,C,1,对换,评价值,CD,4.5,BC,4.5,BD,3.5,T,T,T,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,第,4,步,（如果减小禁忌长度）,解的形式 禁忌对象及长度 候选解,f,(,x,3,)=7.5,2,.2.2,禁忌搜索示例,A,C,B,D,B,C,D,A,B,1,2,C,0,对换,评价值,CD,4.5,BC,4.5,BD,3.5,T,T,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,第,5,步,解的形式 禁忌对象及长度 候选解,f,(,x,4,)=4.5,2,.2.2,禁忌搜索示例,A,D,B,C,B,C,D,A,B,0,1,C,2,对换,评价值,CD,7.5,BC,8,BD,4.5,T,T,2.2,禁忌搜索,智能优化计算,华东理工大学自动化系,2007,年,四城市非对称,TSP,问题,第,6,步,解的形式 禁忌对象及长度 候选解,f,(,x,5,)=8,2,.2.2,禁忌搜索示例,A,D,C,B,B,C,D,A,B,2,0,C,1,对换,评价值,CD,3.5,BC,4.5,BD,4,T,T,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌表的主要指标（两项指标）,禁忌对象：禁忌表中被禁的那些变化元素,禁忌长度：禁忌的步数,状态变化（三种变化）,解的简单变化,解向量分量的变化,目标值变化,2,.3.1,变化因素,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,解的简单变化,2,.3.1,变化因素,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,向量分量的变化,设原有的解向量为,(,x,1,x,i,-1,x,i,x,i,+1,x,n,),，向量分量的最基本变化为,(,x,1,x,i,-1,x,i,x,i,+1,x,n,),(,x,1,x,i,-1,y,i,x,i,+1,x,n,),即只有第,i,个分量发生变化,。,也包含多个分量变化的情形。,2,.3.1,变化因素,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,目标值的变化,目标值的变化隐含着解集合的变化。,2,.3.1,变化因素,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,1,：禁忌对象为简单的解变化,禁忌长度为,4,，从,2,opt,邻域中选出最佳的,5,个解组成候选集,Can_,N,(,x,now,),，初始解,x,now,=,x,0,=(,ABCDE,),，,f,(,x,0,)=45,，,H,=(,ABCDE,;45),。,2,.3.2,禁忌表,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,1,：禁忌对象为简单的解变化,第,1,步,x,now,=(,ABCDE,),，,f,(,x,now,)=45,，,H,=(,ABCDE,;45),Can_,N,(,x,now,)=(,ACBDE,;43),，,(,ABCDE,;45),，,(,ADCBE,;45),，,(,ABEDC,;59),，,(,ABCED,;44),。,2,.3.2,禁忌表,x,next,=(,ACBDE,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,1,：禁忌对象为简单的解变化,第,2,步,x,now,=(,ACBDE,),，,f,(,x,now,)=43,，,H,=(,ABCDE,;45),，,(,ACBDE,;43),Can_,N,(,x,now,)=(,ACBDE,;43),，,(,ACBED,;43),，,(,ADBCE,;44),，,(,ABCDE,;45),，,(,ACEDB,;58),。,2,.3.2,禁忌表,x,next,=(,ACBED,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,1,：禁忌对象为简单的解变化,第,3,步,x,now,=(,ACBED,),，,f,(,x,now,)=43,，,H,=(,ABCDE,;45),，,(,ACBDE,;43),，,(,ACBED,;43),Can_,N,(,x,now,)=(,ACBED,;43),，,(,ACBDE,;43),，,(,ABCED,;44),，,(,AEBCD,;45),，,(,ADBEC,;58),。,2,.3.2,禁忌表,x,next,=(,ABCED,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,1,：禁忌对象为简单的解变化,第,4,步,x,now,=(,ABCED,),，,f,(,x,now,)=44,，,H,=(,ABCDE,;45),，,(,ACBDE,;43),，,(,ACBED,;43),，,(,ABCED,;44),Can_,N,(,x,now,)=(,ACBED,;43),，,(,AECBD,;44),，,(,ABCDE,;45),，,(,ABCED,;44),，,(,ABDEC,;58),。,2,.3.2,禁忌表,x,next,=(,AECBD,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,1,：禁忌对象为简单的解变化,第,5,步,x,now,=(,AECBD,),，,f,(,x,now,)=44,，,H,=(,ACBDE,;43),，,(,ACBED,;43),，,(,ABCED,;44),，,(,AECBD,;44),Can_,N,(,x,now,)=(,AEDBC,;43),，,(,ABCED,;44),，,(,AECBD,;44),，,(,AECDB,;44),，,(,AEBCD,;45),。,2,.3.2,禁忌表,x,next,=(,AEDBC,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,2,：禁忌对象为分量变化,禁忌长度为,3,，从,2,opt,邻域中选出最佳的,5,个解组成候选集,Can_,N,(,x,now,),，初始解,x,now,=,x,0,=(,ABCDE,),，,f,(,x,0,)=45,。,2,.3.2,禁忌表,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,2,：禁忌对象为分量变化,第,1,步,x,now,=(,ABCDE,),，,f,(,x,now,)=45,，,H,=,Can_,N,(,x,now,)=(,ACBDE,;43),，,(,ADCBE,;45),，,(,AECDB,;60),，,(,ABEDC,;59),，,(,ABCED,;44),。,2,.3.2,禁忌表,x,next,=(,ACBDE,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,2,：禁忌对象为分量变化,第,2,步,x,now,=(,ACBDE,),，,f,(,x,now,)=43,，,H,=(,B,C,),Can_,N,(,x,now,)=(,ACBED,;43),，,(,ADBCE,;44),，,(,ABCDE,;45),，,(,ACEDB,;58),，,(,AEBDC,;59),。,2,.3.2,禁忌表,x,next,=(,ACBED,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,2,：禁忌对象为分量变化,第,3,步,x,now,=(,ACBED,),，,f,(,x,now,)=43,，,H,=(,B,C,),，,(,D,E,),Can_,N,(,x,now,)=(,ACBDE,;43),，,(,ABCED,;44),，,(,AEBCD,;45),，,(,ADBEC,;58),，,(,ACEBD,;58),。,2,.3.2,禁忌表,x,next,=(,AEBCD,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,3,：禁忌对象为目标值变化,禁忌长度为,3,，从,2,opt,邻域中选出最佳的,5,个解组成候选集,Can_,N,(,x,now,),，初始解,x,now,=,x,0,=(,ABCDE,),，,f,(,x,0,)=45,。,2,.3.2,禁忌表,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,3,：禁忌对象为目标值变化,第,1,步,x,now,=(,ABCDE,),，,f,(,x,now,)=45,，,H,=45,Can_,N,(,x,now,)=(,ABCDE,;45),，,(,ACBDE,;43),，,(,ADCBE,;45),，,(,ABEDC,;59),，,(,ABCED,;44),。,2,.3.2,禁忌表,x,next,=(,ACBDE,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,情况,3,：禁忌对象为目标值变化,第,2,步,x,now,=(,ACBDE,),，,f,(,x,now,)=43,，,H,=45,，,43,Can_,N,(,x,now,)=(,ACBDE,;43),，,(,ACBED,;43),，,(,ADBCE,;44),，,(,ABCDE,;45),，,(,ACEDB,;58),。,2,.3.2,禁忌表,x,next,=(,ADBCE,),2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌对象的选取,解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围；,解分量的变化和目标值变化的禁忌范围大，减少了计算时间，可能导致陷在局部最优点。,2,.3.2,禁忌表,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌长度的选取,（,1,）,t,可以为常数，易于实现；,（,2,），,t,是可以变化的数，,t,min,和,t,max,是确定的。,t,min,和,t,max,根据问题的规模确定，,t,的大小主要依据实际问题、实验和设计者的经验。,（,3,）,t,min,和,t,max,的动态选择。,2,.3.2,禁忌表,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,禁忌长度的选取,禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；,禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。（,例,）,2,.3.2,禁忌表,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,特赦（藐视）原则,（,1,）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；,（,2,）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；,（,3,）基于影响力的规则，可以特赦对目标值影响大的对象。,2,.3.2,禁忌表,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,候选集合的确定,（,1,）从邻域中选择若干目标值最佳的邻居入选；,（,2,）在邻域中的一部分邻居中选择若干目标值最佳的状态入选；,（,3,）随机选取。,2,.3.3,其他,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,评价函数,（,1,）直接评价函数，通过目标函数的运算得到评价函数；,（,2,）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。,2,.3.3,其他,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,记忆频率信息,根据记忆的频率信息（禁忌次数等）来控制禁忌参数（禁忌长度等）。,例如：,如果一个元素或序列重复出现或目标值变化很小，可增加禁忌长度以避开循环；,如果一个最佳目标值出现频率很高，则可以终止计算认为已达到最优值。,2,.3.3,其他,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,记忆频率信息,可记录的信息：,（,1,）静态频率信息：解、对换或目标值在计算中出现的频率；,（,2,）动态频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。,2,.3.3,其他,2.3,禁忌搜索的关键参数和操作,智能优化计算,华东理工大学自动化系,2007,年,终止规则,（,1,）确定步数终止，无法保证解的效果，应记录当前最优解；,（,2,）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；,（,3,）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。,2,.3.3,其他,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,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,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,算法流程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,初始条件,禁忌长度为,50,从,2,opt,邻域中随机选择,200,个邻域解，选出其中,100,个最佳解组成候选集,终止步数,2000,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,初始条件,禁忌长度为,10,从,2,opt,邻域中随机选择,200,个邻域解，选出其中,100,个最佳解组成候选集,终止步数,2000,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,运行过程比较,禁忌长度,50,禁忌长度,10,2,.4.1 30,城市,TSP,问题（,d,*,=423.741 by D B,Fogel,）,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,解决连续系统优化的禁忌搜索算法,邻域,引入超矩形来定义一个点的邻域,2,.4.2,基于禁忌搜索算法的系统辨识,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,解决连续系统优化的禁忌搜索算法,禁忌表,将当前点及其目标函数值放入禁忌表中，作为禁忌区域的中心,首先判断点,x,的目标函数值,f,(,x,),，如果,f,(,x,),跟禁忌表中的任一个函数值都不接近，则点,x,没被禁忌；,如果,f,(,x,),跟禁忌表中点,x,*,的函数值,f,(,x,*),接近，则判断点,x,跟点,x,*,是否接近，如果接近，则点,x,被禁忌，否则就没被禁忌。,2,.4.2,基于禁忌搜索算法的系统辨识,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,解决连续系统优化的禁忌搜索算法,特赦原则,若点,x,的目标函数值优于目前为止搜索到的最优点的目标函数值，则点,x,满足特赦规则。,终止原则,当达到最大迭代步数，或在一个给定的迭代步数内算法搜索到的最优点没有改善时，将终止迭代。,2,.4.2,基于禁忌搜索算法的系统辨识,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,将系统辨识转化为优化问题,待辨识模型：,估计模型输出：,准则函数：,优化问题：,2,.4.2,基于禁忌搜索算法的系统辨识,2.4,禁忌搜索的实现与应用,智能优化计算,华东理工大学自动化系,2007,年,辨识结果,辨识模型：,统计结果：,2,.4.2,基于禁忌搜索算法的系统辨识,第二章 结束,智能优化计算,华东理工大学自动化系,2007,年,