神经网络禁忌搜索算法

《神经网络禁忌搜索算法》由会员分享，可在线阅读，更多相关《神经网络禁忌搜索算法（73页珍藏版）》请在金锄头文库上搜索。

1、第二章第二章 禁忌搜索算法禁忌搜索算法 智能优化计算智能优化计算广东药学院医药信息工程学院 2021年 2.1 2.1 局部搜索局部搜索局部搜索局部搜索 2.1.1 2.1.1 邻域的概念邻域的概念邻域的概念邻域的概念 2.1.2 2.1.2 局部搜索算法局部搜索算法局部搜索算法局部搜索算法 2.1.3 2.1.3 局部搜索例如局部搜索例如局部搜索例如局部搜索例如 2.2 2.2 禁忌搜索禁忌搜索禁忌搜索禁忌搜索 2.2.1 2.2.1 算法的主要思路算法的主要思路算法的主要思路算法的主要思路 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如2.3 2.3 禁忌搜索的关

2、键参数和操作禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 2.3.1 2.3.1 变化因素变化因素变化因素变化因素 2.3.2 2.3.2 禁忌表禁忌表禁忌表禁忌表 2.3.3 2.3.3 其他其他其他其他 2.4 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用禁忌搜索的实现与应用禁忌搜索的实现与应用 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B d*=423.741 by D B FogelFogel 2.4.2 2.4.2 基于禁忌搜索算法的系统辨识基于禁忌搜索算法的系统辨识基于禁忌搜索算法的

3、系统辨识基于禁忌搜索算法的系统辨识智能优化计算智能优化计算广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算w函数优化问题中函数优化问题中 在距离空间中，通常的邻域定义是以一点为中心的在距离空间中，通常的邻域定义是以一点为中心的一个球体；一个球体；w组合优化问题中组合优化问题中 2 2.1.1 .1.1 邻域的概念邻域的概念邻域的概念邻域的概念 广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算w例例w TSP问题解的一种表示方法为问题解的一种表示方法为D=x=(i1,i2,in)| i1,i2,in是是1,2,n

4、的排列的排列，定义它的邻域映射为定义它的邻域映射为2opt，即，即x中的两个元素进中的两个元素进行对换，行对换，N(x)中共包含中共包含x的的Cn2=n(n-1)/2个邻居和个邻居和x本身。本身。w 例如：例如：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) 2 2.1.1 .1.1 邻域的概念邻域的概念邻域的概念邻域的概念 广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算w例例 TSP问题解的

5、邻域映射可由问题解的邻域映射可由2opt，推广到，推广到kopt。w邻域概念的重要性邻域概念的重要性 邻域的构造依赖于决策变量的表示，邻域的构造依赖于决策变量的表示， 邻域的结构在现代优化算法中起重要的作用。邻域的结构在现代优化算法中起重要的作用。 2 2.1.1 .1.1 邻域的概念邻域的概念邻域的概念邻域的概念 广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算wSTEP 1w 选定一个初始可行解选定一个初始可行解x0，记录当前最优解，记录当前最优解xbest:=x0, T=N(xbest)；wSTEP 2*注意集合注意集合S选取的大小选取的大小w

6、当当Txbest=时，或满足其他停止运算准那么时，或满足其他停止运算准那么时，输出计算结果，停止运算；否那么，从时，输出计算结果，停止运算；否那么，从T中选一中选一集合集合S，得到，得到S中的最好解中的最好解xnow；假设；假设f (xnow)f(xbest)，那么，那么xbest := xnow ，T=N(xbest)；否那么；否那么T:=TS；重复；重复SETP 2。 2 2.1.2 .1.2 局部搜索算法局部搜索算法局部搜索算法局部搜索算法 广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算w五个城市的对称五个城市的对称TSP问题问题 初始解为初始

7、解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射，定义邻域映射为对换两个城市位置的为对换两个城市位置的2-opt，选定，选定A城市为起点。城市为起点。 2.1.3 2.1.3 局部搜索例如局部搜索例如局部搜索例如局部搜索例如 广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算w五个城市的对称五个城市的对称TSP问题问题 方法方法1：全邻域搜索：全邻域搜索 第第1步步 N(xbest)=(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)， 对应目标函数为对应目标函数为f(x)=

8、45, 43, 45, 60, 60, 59, 44 xbest:=xnow=(ACBDE) 2.1.3 2.1.3 局部搜索例如局部搜索例如局部搜索例如局部搜索例如 A B C D E广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算w五个城市的对称五个城市的对称TSP问题问题 方法方法1：全邻域搜索：全邻域搜索 第第2步步 N(xbest)=(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)， 对应目标函数为对应目标函数为f(x)=43, 45, 44, 59, 59, 58, 43 xbe

9、st:=xnow=(ACBDE) 2.1.3 2.1.3 局部搜索例如局部搜索例如局部搜索例如局部搜索例如 广东药学院医药信息工程学院 2021年 2.1 局部搜索局部搜索 智能优化计算智能优化计算w五个城市的对称五个城市的对称TSP问题问题 方法方法2：一步随机搜索：一步随机搜索 第第1步步 从从N(xbest)中随机选一点，如中随机选一点，如xnow=(ACBDE)， 对应目标函数为对应目标函数为f(xnow)=43 43 xbest:=xnow=(ACBDE) 2.1.3 2.1.3 局部搜索例如局部搜索例如局部搜索例如局部搜索例如 广东药学院医药信息工程学院 2021年 2.1 局部搜

10、索局部搜索 智能优化计算智能优化计算w五个城市的对称五个城市的对称TSP问题问题w 简单易行，但无法保证全局最优性；简单易行，但无法保证全局最优性；w 局部搜索主要依赖起点的选取和邻域的结构；局部搜索主要依赖起点的选取和邻域的结构；w 为了得到好的解，可以比较不同的邻域结构和为了得到好的解，可以比较不同的邻域结构和不同的初始点；不同的初始点；w 如果初始点的选择足够多，如果初始点的选择足够多，w 总可以计算出全局最优解。总可以计算出全局最优解。 2.1.3 2.1.3 局部搜索例如局部搜索例如局部搜索例如局部搜索例如 广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计

11、算智能优化计算w算法的提出算法的提出w 禁忌搜索禁忌搜索Tabu Search 或或 Taboo Search是局部邻域搜索算法的推广，是局部邻域搜索算法的推广，Fred Glover在在1986年提出这个概念，进而形成一套完整算法。年提出这个概念，进而形成一套完整算法。w ?Operation Research of America?w算法的特点算法的特点w 禁忌禁忌禁止重复前面的工作。禁止重复前面的工作。w 跳出局部最优点。跳出局部最优点。 2 2.2.1 .2.1 算法的主要思路算法的主要思路算法的主要思路算法的主要思路 :/glover/广东药学院医药信息工程学院 2021年 2.2

12、禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非对称TSP问题问题 初始初始解解x0=(ABCD)，f(x0)=4，邻域映射为两个城市，邻域映射为两个城市顺序对换的顺序对换的2opt，始、终点都是，始、终点都是A城市。城市。 禁忌长度：禁忌长度：3 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如 广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非对称TSP问题问题w 第第1步步w 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解w f(x0)=4w局部最优搜索算法：局部最优搜索算

13、法：w已经到达局部最优而停止。已经到达局部最优而停止。w禁忌搜索算法：允许从候选集中选一个最好的对换。禁忌搜索算法：允许从候选集中选一个最好的对换。 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如 A B C DBCDABC对换评价值CD4.5BC7.5BD8广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非对称TSP问题问题 第第2步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x1)=4.5 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如 A B D C

14、BCDABC3对换评价值CD4.5BC3.5BD4.5T广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非对称TSP问题问题 第第3步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x2)=3.5 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如 A C D BBCDAB3C2对换评价值CD8BC4.5BD7.5TT广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非对称TSP问题问题 第第4步步 解的形式解的形式 禁忌对象及长

15、度禁忌对象及长度 候选解候选解 f(x3)=7.5*所有解都被禁忌，咋办？所有解都被禁忌，咋办？ *禁忌对象禁忌对象、*禁忌长度的选取禁忌长度的选取 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如 A C B DBCDAB23C1对换评价值CD4.5BC4.5BD3.5TTT广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非对称TSP问题问题w 第第4步如果减小禁忌长度步如果减小禁忌长度w 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解w f(x3)=7.5 2.2.2 2.2.2 禁忌搜索例

16、如禁忌搜索例如禁忌搜索例如禁忌搜索例如 A C B DBCDAB12C0对换评价值CD4.5BC4.5BD3.5TT广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非对称TSP问题问题 第第5步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x4)=4.5 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如 A D B CBCDAB01C2对换评价值CD7.5BC8BD4.5TT广东药学院医药信息工程学院 2021年 2.2 禁忌搜索禁忌搜索 智能优化计算智能优化计算w四城市非对称四城市非

17、对称TSP问题问题w 第第6步步w 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解w f(x5)=8w?死循环死循环 2.2.2 2.2.2 禁忌搜索例如禁忌搜索例如禁忌搜索例如禁忌搜索例如 A D C BBCDAB20C1对换评价值CD3.5BC4.5BD4TT广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌表的主要指标两项指标禁忌表的主要指标两项指标w 禁忌对象：禁忌表中被禁的那些变化元素禁忌对象：禁忌表中被禁的那些变化元素w 禁忌长度：禁忌的步数禁忌长度：禁忌的步数w状态变化三种变化状态变化三种

18、变化w 解的简单变化解的简单变化w 解向量分量的变化解向量分量的变化w 目标值变化目标值变化 2 2.3.1 .3.1 变化因素变化因素变化因素变化因素 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w解的简单变化解的简单变化 2 2.3.1 .3.1 变化因素变化因素变化因素变化因素 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w向量分量的变化向量分量的变化w 设原有的解向量为设原有的解向量为(x1, , xi-1, xi, xi+1, ,

19、 xn)，向量分量的最根本变化为，向量分量的最根本变化为w (x1, , xi-1, xi, xi+1, xn)(x1, , xi-1, yi, xi+1, xn)w 即只有第即只有第i个分量发生变化。个分量发生变化。w 也包含多个分量变化的情形。也包含多个分量变化的情形。 2 2.3.1 .3.1 变化因素变化因素变化因素变化因素 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w目标值的变化目标值的变化 目标值的变化隐含着解集合的变化。目标值的变化隐含着解集合的变化。 2 2.3.1 .3.1 变化因素变化因素变化因

20、素变化因素 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取w 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化w 禁忌长度为禁忌长度为4，从，从2opt邻域中选出最正确的邻域中选出最正确的5个解组成候选集个解组成候选集Can_N(xnow)，初始解，初始解xnow=x0=(ABCDE)，f(x0)=45，H=(ABCDE;45)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作

21、智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第1步步 xnow=(ABCDE)，f(xnow)=45，H=(ABCDE;45) Can_N(xnow)=(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(ACBDE)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解

22、变化：禁忌对象为简单的解变化 第第2步步 xnow=(ACBDE)，f(xnow)=43，H=(ABCDE;45)，(ACBDE;43) Can_N(xnow)=(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(ACBED)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第3步步 xnow=(ACBED

23、)，f(xnow)=43，H=(ABCDE;45)，(ACBDE;43) ，(ACBED;43) Can_N(xnow)=(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(ABCED)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第4步步 xnow=(ABCED)，f(xnow)=44，H=(ABCD

24、E;45)，(ACBDE;43) ，(ACBED;43) ，(ABCED;44) Can_N(xnow)=(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(AECBD)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化 第第5步步 xnow=(AECBD)，f(xnow)=44，H=(ACBDE;43) ，(

25、ACBED;43) ，(ABCED;44) ，(AECBD;44) Can_N(xnow)=(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(AEDBC)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取w 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化w 禁忌长度为禁忌长度为3，从，从2opt邻域中选出最正确的邻域中选出最正确的5个解组成候选集个解组成候选集Ca

26、n_N(xnow)，初始解，初始解xnow=x0=(ABCDE)，f(x0)=45。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 第第1步步 xnow=(ABCDE)，f(xnow)=45，H= Can_N(xnow)=(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 x

27、next=(ACBDE)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 第第2步步 xnow=(ACBDE)，f(xnow)=43，H=(B,C) Can_N(xnow)=(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(ACBED)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索

28、的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 第第3步步 xnow=(ACBED)，f(xnow)=43，H=(B,C)，(D,E) Can_N(xnow)=(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)，(ACEBD;58)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(AEBCD)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取w 情况情况3：禁忌

29、对象为目标值变化：禁忌对象为目标值变化w 禁忌长度为禁忌长度为3，从，从2opt邻域中选出最正确的邻域中选出最正确的5个解组成候选集个解组成候选集Can_N(xnow)，初始解，初始解xnow=x0=(ABCDE)，f(x0)=45。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况3：禁忌对象为目标值变化：禁忌对象为目标值变化 第第1步步 xnow=(ABCDE)，f(xnow)=45，H=45 Can_N(xnow)=(ABC

30、DE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(ACBDE)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 情况情况3：禁忌对象为目标值变化：禁忌对象为目标值变化 第第2步步 xnow=(ACBDE)，f(xnow)=43，H=45，43 Can_N(xnow)=(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)

31、。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 xnext=(ADBCE)广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌对象的选取禁忌对象的选取 解的简单变化比解的分量变化和目标值变化的受禁解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围；较大的搜索范围； 解分量的变化和目标值变化的禁忌范围大，减少了解分量的变化和目标值变化的禁忌范围大，减少了计算时间，可能导致陷在局部最优点。计算时间，可能导致陷在局部最优点

32、。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌长度的选取禁忌长度的选取w 1t可以为常数，易于实现；可以为常数，易于实现；w 2 ，t是可以变化的数，是可以变化的数，tmin和和tmax是确定的。是确定的。w tmin和和tmax根据问题的规模确定，根据问题的规模确定，t的大小的大小主要依据实际问题、实验和设计者的经验。主要依据实际问题、实验和设计者的经验。w 3 tmin和和tmax的动态选择。的动态选择。 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌

33、表 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w禁忌长度的选取禁忌长度的选取w 禁忌长度过短，一旦陷入局部最优点，出现循禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；环无法跳出；w 禁忌长度过长，造成计算时间较大，也可能造禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。例成计算无法继续下去。例 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w特赦藐视原那么特赦藐视原那么w

34、 1基于评价值的规那么，假设出现一个解的基于评价值的规那么，假设出现一个解的目标值好于前面任何一个最正确候选解，可特赦；目标值好于前面任何一个最正确候选解，可特赦；w 2基于最小错误的规那么，假设所有对象都基于最小错误的规那么，假设所有对象都被禁忌，特赦一个评价值最小的解；被禁忌，特赦一个评价值最小的解；w 3基于影响力的规那么，可以特赦对目标值基于影响力的规那么，可以特赦对目标值影响大的对象。如果一个对目标影响大的变化成影响大的对象。如果一个对目标影响大的变化成为被禁对象，应该使其自由，为被禁对象，应该使其自由，_ 2 2.3.2 .3.2 禁忌表禁忌表禁忌表禁忌表 广东药学院医药信息工程学

35、院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w候选集合确实定候选集合确实定w 1从邻域中选择假设干目标值最正确的邻居从邻域中选择假设干目标值最正确的邻居入选；入选；w 2在邻域中的一局部邻居中选择假设干目标在邻域中的一局部邻居中选择假设干目标值最正确的状态入选；值最正确的状态入选；w 3随机选取。随机选取。 2 2.3.3 .3.3 其他其他其他其他 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w评价函数评价函数w 1直接评价函数，通过目标函数的运算得到直接评价函

36、数，通过目标函数的运算得到评价函数；评价函数；w 2间接评价函数，构造其他评价函数替代目间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。标函数，应反映目标函数的特性，减少计算复杂性。 2 2.3.3 .3.3 其他其他其他其他 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w记忆频率信息记忆频率信息w 根据记忆的频率信息禁忌次数等来控制禁根据记忆的频率信息禁忌次数等来控制禁忌参数禁忌长度等。忌参数禁忌长度等。w 例如：例如：w 如果一个元素或序列重复出现或目标值变化很如果一个元素或序列

37、重复出现或目标值变化很小，可增加禁忌长度以避开循环；小，可增加禁忌长度以避开循环；w 如果一个最正确目标值出现频率很高，那么可如果一个最正确目标值出现频率很高，那么可以终止计算认为已到达最优值。以终止计算认为已到达最优值。 2 2.3.3 .3.3 其他其他其他其他 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w记忆频率信息记忆频率信息w 可记录的信息：可记录的信息：w 1静态频率信息：解、对换或目标值在计算静态频率信息：解、对换或目标值在计算中出现的频率；中出现的频率；w 2动态频率信息：从一个解、对换或目标值动态

38、频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。到另一个解、对换或目标值的变化趋势。 2 2.3.3 .3.3 其他其他其他其他 广东药学院医药信息工程学院 2021年 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能优化计算智能优化计算w终止规那么终止规那么w 1确定步数终止，无法保证解的效果，应记确定步数终止，无法保证解的效果，应记录当前最优解；录当前最优解；w 2频率控制原那么，当某一个解、目标值或频率控制原那么，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；元素序列的频率超过一个给定值时，终止计算；w 3目标控制原那么，如果在一个给定步

39、数内，目标控制原那么，如果在一个给定步数内，当前最优值没有变化，可终止计算；当前最优值没有变化，可终止计算；w 4目标值偏离程度原那么，如果目标值与问目标值偏离程度原那么，如果目标值与问题的下界求极小小于给定的误差，可终止计算。题的下界求极小小于给定的误差，可终止计算。 2 2.3.3 .3.3 其他其他其他其他 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算wTSP Benchmark 问题问题 41 94;37 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;64 60;

40、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 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w算法流程算法流程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问

41、题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w初始条件初始条件w 禁忌长度为禁忌长度为50w 从从2opt邻域中随机选择邻域中随机选择200个邻域解，选出其个邻域解，选出其中中100个最正确解组成候选集个最正确解组成候选集w 终止步数终止步数2000 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广

42、东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B F

43、ogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by

44、 D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.

45、741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld

46、*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B

47、Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w初始条件初始条件w 禁忌长度为禁忌长度为10w 从从2opt邻域中随机选择邻域中随机选择200个邻域解，选出其个邻域解，选出其中中100个最正确解组成候选集个最正确解组成候选集w 终止步数终止步数2000w 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4

48、 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 202

49、1年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程

50、学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院

51、医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel

52、 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程运行过程 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 2.4 禁忌搜索的实现与应用禁忌搜索的实现与应用 智能优化计算智能优化计算w运行过程比较运行过程比较w w 禁忌长度禁忌长度50 禁忌长度禁忌长度10 2.4.1 30 2.4.1 30城市城市城市城市TSPTSP问题问题问题问题d*=423.741 by D B Fogeld*=423.741 by D B Fogel 广东药学院医药信息工程学院 2021年 第二章第二章 结束结束智能优化计算智能优化计算广东药学院医药信息工程学院 2021年