第二章禁忌搜索算法智能优化计算课件.ppt

1、 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w函数优化问题中函数优化问题中 在距离空间中，通常的邻域定义是以一点为中心的在距离空间中，通常的邻域定义是以一点为中心的一个球体；一个球体；w组合优化问题中组合优化问题中 的一个邻居。称为的邻域，称为。的所有子集组成的集合表示其中，称为一个邻域映射，且xxNyxxNDxNxxNDxNDD)()(2)(,2)(:华东

2、理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w例例 TSP问题解的一种表示方法为问题解的一种表示方法为D=x=(i1,i2,in)|i1,i2,in是是1,2,n的排列的排列，定义它的邻域映射为，定义它的邻域映射为2opt，即，即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,

3、4,3)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w例例 TSP问题解的邻域映射可由问题解的邻域映射可由2opt，推广到，推广到kopt。w邻域概念的重要性邻域概念的重要性 邻域的构造依赖于决策变量的表示，邻域的构造依赖于决策变量的表示，邻域的结构在现代优化算法中起重要的作用。邻域的结构在现代优化算法中起重要的作用。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wSTEP 1 选定一个初始可行解选定一个初始可行解x0，记录当前最优解，记录当前最优解xbest:=x0,T=N(xbest)；wST

4、EP 2 当当Txbest=时，或满足其他停止运算准则时，输出时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从计算结果，停止运算；否则，从T中选一集合中选一集合S，得，得到到S中的最好解中的最好解xnow；若；若f(xnow)f(xbest)，则，则xbest:=xnow，T=N(xbest)；否则；否则T:=TS；重复；重复SETP 2。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w五个城市的对称五个城市的对称TSP问题问题 初始解为初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射，定义邻域映射为对换两个

5、城市位置的为对换两个城市位置的2-opt，选定，选定A城市为起点。城市为起点。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w五个城市的对称五个城市的对称TSP问题问题 方法方法1：全邻域搜索：全邻域搜索 第第1步步 N(xbest)=(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)，对应目标函数为对应目标函数为f(x)=45,43,45,60,60,59,44 xbest:=xnow=(ACBDE)A B C D E 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 20

6、0720072007年年年 w五个城市的对称五个城市的对称TSP问题问题 方法方法1：全邻域搜索：全邻域搜索 第第2步步 N(xbest)=(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)，对应目标函数为对应目标函数为f(x)=43,45,44,59,59,58,43 xbest:=xnow=(ACBDE)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w五个城市的对称五个城市的对称TSP问题问题 方法方法2：一步随机搜索：一步随机搜索 第第1步步 从从N(xbest)中随机选一点，如中

7、随机选一点，如xnow=(ACBDE)，对应目标函数为对应目标函数为f(xnow)=43 43 xbest:=xnow=(ACBDE)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w五个城市的对称五个城市的对称TSP问题问题 简单易行，但无法保证全局最优性；简单易行，但无法保证全局最优性；局部搜索主要依赖起点的选取和邻域的结构；局部搜索主要依赖起点的选取和邻域的结构；为了得到好的解，可以比较不同的邻域结构和不同为了得到好的解，可以比较不同的邻域结构和不同的初始点；的初始点；如果初始点的选择足够多，如果初始点的选择足够多，总可以计算出全局最优解。总

8、可以计算出全局最优解。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w算法的提出算法的提出 禁忌搜索（禁忌搜索（Tabu search）是局部邻域搜索算法的）是局部邻域搜索算法的推广，推广，Fred Glover在在1986年提出这个概念，进而年提出这个概念，进而形成一套完整算法。形成一套完整算法。w算法的特点算法的特点 禁忌禁忌禁止重复前面的工作。禁止重复前面的工作。跳出局部最优点。跳出局部最优点。http:/spot.colorado.edu/glover/华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007

9、年年年 w四城市非对称四城市非对称TSP问题问题 初始初始解解x0=(ABCD)，f(x0)=4，邻域映射为两个城市，邻域映射为两个城市顺序对换的顺序对换的2opt，始、终点都是，始、终点都是A城市。城市。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w四城市非对称四城市非对称TSP问题问题 第第1步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x0)=4 A B C DBCDABC对换评价值CD4.5BC7.5BD8 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w四城市非

10、对称四城市非对称TSP问题问题 第第2步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x1)=4.5 A B D CBCDABC3对换评价值CD4.5BC3.5BD4.5T 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w四城市非对称四城市非对称TSP问题问题 第第3步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x2)=3.5 A C D BBCDAB3C2对换评价值CD8BC4.5BD7.5TT 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w四城

11、市非对称四城市非对称TSP问题问题 第第4步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x3)=7.5 禁忌长度的选取禁忌长度的选取 A C B DBCDAB23C1对换评价值CD4.5BC4.5BD3.5TTT 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w四城市非对称四城市非对称TSP问题问题 第第4步步（如果减小禁忌长度）（如果减小禁忌长度）解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x3)=7.5 A C B DBCDAB12C0对换评价值CD4.5BC4.5BD3.5TT 华东理工大学自

12、动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w四城市非对称四城市非对称TSP问题问题 第第5步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x4)=4.5 A D B CBCDAB01C2对换评价值CD7.5BC8BD4.5TT 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w四城市非对称四城市非对称TSP问题问题 第第6步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x5)=8 A D C BBCDAB20C1对换评价值CD3.5BC4.5BD4TT 华东理工大

13、学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌表的主要指标（两项指标）禁忌表的主要指标（两项指标）禁忌对象：禁忌表中被禁的那些变化元素禁忌对象：禁忌表中被禁的那些变化元素 禁忌长度：禁忌的步数禁忌长度：禁忌的步数w状态变化（三种变化）状态变化（三种变化）解的简单变化解的简单变化 解向量分量的变化解向量分量的变化 目标值变化目标值变化 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解的简单变化解的简单变化 个解。是从一个解变化到另一则简单解变化为优化问题的定义域，其中，邻域映射为假设)(,xNyxDND

14、yx 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w向量分量的变化向量分量的变化 设原有的解向量为设原有的解向量为(x1,xi-1,xi,xi+1,xn)，向量，向量分量的最基本变化为分量的最基本变化为 (x1,xi-1,xi,xi+1,xn)(x1,xi-1,yi,xi+1,xn)即只有第即只有第i个分量发生变化个分量发生变化。也包含多个分量变化的情形。也包含多个分量变化的情形。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w目标值的变化目标值的变化 目标值的变化隐含着解集合的变化。目标值的变化

15、隐含着解集合的变化。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 禁忌长度为禁忌长度为4，从，从2opt邻域中选出最佳的邻域中选出最佳的5个解组个解组成候选集成候选集Can_N(xnow)，初始解，初始解xnow=x0=(ABCDE)，f(x0)=45，H=(ABCDE;45)。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解

16、变化 第第1步步 xnow=(ABCDE)，f(xnow)=45，H=(ABCDE;45)Can_N(xnow)=(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)。xnext=(ACBDE)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第2步步 xnow=(ACBDE)，f(xnow)=43，H=(ABCDE;45)，(ACBDE;43)Can_N(xnow)=(ACBDE;43)，(ACBED

17、;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)。xnext=(ACBED)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第3步步 xnow=(ACBED)，f(xnow)=43，H=(ABCDE;45)，(ACBDE;43)，(ACBED;43)Can_N(xnow)=(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)。xnext=(ABCED)华东理工大学自动化系华东

18、理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第4步步 xnow=(ABCED)，f(xnow)=44，H=(ABCDE;45)，(ACBDE;43)，(ACBED;43)，(ABCED;44)Can_N(xnow)=(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)。xnext=(AECBD)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情

19、况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第5步步 xnow=(AECBD)，f(xnow)=44，H=(ACBDE;43)，(ACBED;43)，(ABCED;44)，(AECBD;44)Can_N(xnow)=(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)。xnext=(AEDBC)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 禁忌长度为禁忌长度为3，从，从2opt邻域中选出最佳的

20、邻域中选出最佳的5个解组个解组成候选集成候选集Can_N(xnow)，初始解，初始解xnow=x0=(ABCDE)，f(x0)=45。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 第第1步步 xnow=(ABCDE)，f(xnow)=45，H=Can_N(xnow)=(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)。xnext=(ACBDE)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2

21、00720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 第第2步步 xnow=(ACBDE)，f(xnow)=43，H=(B,C)Can_N(xnow)=(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)。xnext=(ACBED)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 第第3步步 xnow=(ACBED)，f(xnow)=43，H=(B,C)

22、，(D,E)Can_N(xnow)=(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)，(ACEBD;58)。xnext=(AEBCD)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况3：禁忌对象为目标值变化：禁忌对象为目标值变化 禁忌长度为禁忌长度为3，从，从2opt邻域中选出最佳的邻域中选出最佳的5个解组个解组成候选集成候选集Can_N(xnow)，初始解，初始解xnow=x0=(ABCDE)，f(x0)=45。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化

23、系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况3：禁忌对象为目标值变化：禁忌对象为目标值变化 第第1步步 xnow=(ABCDE)，f(xnow)=45，H=45 Can_N(xnow)=(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)。xnext=(ACBDE)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 情况情况3：禁忌对象为目标值变化：禁忌对象为目标值变化 第第2步步 xnow=(ACBDE)，f(xnow)=43，H=

24、45，43 Can_N(xnow)=(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)。xnext=(ADBCE)华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌对象的选取禁忌对象的选取 解的简单变化比解的分量变化和目标值变化的受禁解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围；较大的搜索范围；解分量的变化和目标值变化的禁忌范围大，减少了解分量的变化和目标值变化的禁忌范围大，减少了计算时

25、间，可能导致陷在局部最优点。计算时间，可能导致陷在局部最优点。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w禁忌长度的选取禁忌长度的选取 （1）t可以为常数，易于实现；可以为常数，易于实现；（2），t是可以变化的数，是可以变化的数，tmin和和tmax是确是确定的。定的。tmin和和tmax根据问题的规模确定，根据问题的规模确定，t的大小主要依的大小主要依据实际问题、实验和设计者的经验。据实际问题、实验和设计者的经验。（3）tmin和和tmax的动态选择。的动态选择。,maxminttt 华东理工大学自动化系华东理工大学自动化系华东理工大学自动

26、化系 200720072007年年年 w禁忌长度的选取禁忌长度的选取 禁忌长度过短，一旦陷入局部最优点，出现循环无禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；法跳出；禁忌长度过长，造成计算时间较大，也可能造成计禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。（算无法继续下去。（例例）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w特赦（藐视）原则特赦（藐视）原则 （1）基于评价值的规则，若出现一个解的目标值）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；好于前面任何一个最佳候选解，可特赦；（2）基于

27、最小错误的规则，若所有对象都被禁忌，）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；特赦一个评价值最小的解；（3）基于影响力的规则，可以特赦对目标值影响）基于影响力的规则，可以特赦对目标值影响大的对象。大的对象。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w候选集合的确定候选集合的确定 （1）从邻域中选择若干目标值最佳的邻居入选；）从邻域中选择若干目标值最佳的邻居入选；（2）在邻域中的一部分邻居中选择若干目标值最）在邻域中的一部分邻居中选择若干目标值最佳的状态入选；佳的状态入选；（3）随机选取。）随机选取。华东理工大学自动化系

28、华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w评价函数评价函数 （1）直接评价函数，通过目标函数的运算得到评）直接评价函数，通过目标函数的运算得到评价函数；价函数；（2）间接评价函数，构造其他评价函数替代目标）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。函数，应反映目标函数的特性，减少计算复杂性。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w记忆频率信息记忆频率信息 根据记忆的频率信息（禁忌次数等）来控制禁忌参根据记忆的频率信息（禁忌次数等）来控制禁忌参数（禁忌长度等）。数（禁

29、忌长度等）。例如：例如：如果一个元素或序列重复出现或目标值变化很小，如果一个元素或序列重复出现或目标值变化很小，可增加禁忌长度以避开循环；可增加禁忌长度以避开循环；如果一个最佳目标值出现频率很高，则可以终止计如果一个最佳目标值出现频率很高，则可以终止计算认为已达到最优值。算认为已达到最优值。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w记忆频率信息记忆频率信息 可记录的信息：可记录的信息：（1）静态频率信息：解、对换或目标值在计算中）静态频率信息：解、对换或目标值在计算中出现的频率；出现的频率；（2）动态频率信息：从一个解、对换或目标值到）动态

30、频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。另一个解、对换或目标值的变化趋势。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w终止规则终止规则 （1）确定步数终止，无法保证解的效果，应记录）确定步数终止，无法保证解的效果，应记录当前最优解；当前最优解；（2）频率控制原则，当某一个解、目标值或元素）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；序列的频率超过一个给定值时，终止计算；（3）目标控制原则，如果在一个给定步数内，当）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。前

31、最优值没有变化，可终止计算。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP 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 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007

32、年年年 w算法流程算法流程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w初始条件初始条件 禁忌长度为禁忌长度为50 从从2opt邻域中随机选择邻域中随机选择200个邻域解，选出其中个邻域解，选出其中100个最佳解组成候选集个最佳解组成候选集 终止步数终止步数2000 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学

33、自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007200720

34、07年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w初始条件初始条件 禁忌长度为禁忌长度为10 从从2opt邻域中随机选择邻域中随机选择200个邻域解，选出其中个邻域解，选出其中100个最佳解组成候选集个最佳解组成候选集 终止步数终止步数2000 华东理工大学自动化系华东理工大学自动化系华东理工

35、大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 20072007

36、2007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程运行过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w运行过程比较

37、运行过程比较 禁忌长度禁忌长度50 禁忌长度禁忌长度10 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解决连续系统优化的禁忌搜索算法解决连续系统优化的禁忌搜索算法 邻域邻域引入超矩形来定义一个点的邻域引入超矩形来定义一个点的邻域 njubxxlbxhxxxhxHjjjjjj,2,1,_,),(kinjubxxlbxhxxhxhhxHjjjjijjjiiii,2,1 ,2,1,_,),(,11njubxxlbxhxxxhxHjjjjjj,2,1,_,),(,000 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072

38、007年年年 w解决连续系统优化的禁忌搜索算法解决连续系统优化的禁忌搜索算法 禁忌表禁忌表将当前点及其目标函数值放入禁忌表中，将当前点及其目标函数值放入禁忌表中，作为禁忌区域的中心作为禁忌区域的中心 首先判断点首先判断点 x 的目标函数值的目标函数值 f(x)，如果，如果 f(x)跟禁忌跟禁忌表中的任一个函数值都不接近，则点表中的任一个函数值都不接近，则点 x 没被禁忌；没被禁忌；如果如果 f(x)跟禁忌表中点跟禁忌表中点 x*的函数值的函数值 f(x*)接近，则接近，则判断点判断点 x 跟点跟点 x*是否接近，如果接近，则点是否接近，如果接近，则点 x 被被禁忌，否则就没被禁忌。禁忌，否则就

39、没被禁忌。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解决连续系统优化的禁忌搜索算法解决连续系统优化的禁忌搜索算法 特赦原则特赦原则 若点若点 x 的目标函数值优于目前为止搜索到的最优点的目标函数值优于目前为止搜索到的最优点的目标函数值，则点的目标函数值，则点 x 满足特赦规则。满足特赦规则。终止原则终止原则 当达到最大迭代步数，或在一个给定的迭代步数内当达到最大迭代步数，或在一个给定的迭代步数内算法搜索到的最优点没有改善时，将终止迭代。算法搜索到的最优点没有改善时，将终止迭代。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2

40、00720072007年年年 w将系统辨识转化为优化问题将系统辨识转化为优化问题 待辨识模型：待辨识模型：估计模型输出：估计模型输出：准则函数：准则函数：优化问题：优化问题：),(pxfym),(pxfy NkmNkmpxfkyNkykyNpE1212),()(1)()(1)(ubpplbptspxfkyNpENkmp_ .,),()(1)(min12 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w辨识结果辨识结果 辨识模型：辨识模型：统计结果：统计结果：0.15.00.10.1)()(2ssssusy华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年