禁忌搜索算法.

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

1、第三章第三章 禁忌搜索算法禁忌搜索算法 智能算法导论智能算法导论浙江大学 1 3 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.3.1 2.3.1 变化因素变化因素 2.3.2 2.3.2 禁忌表禁忌表 2.3.3 2.3.3 其他其他 2.4 2.4 禁忌

2、搜索的实现与应用禁忌搜索的实现与应用 2.4.1 302.4.1 30城市城市TSPTSP问题（问题（d d * * =423.741 by D B =423.741 by D B FogelFogel） 2.4.2 2.4.2 基于禁忌搜索算法的系统辨识基于禁忌搜索算法的系统辨识 智能算法导论智能算法导论浙江大学 2/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 w函数优化问题中 在距离空间中，通常的邻域定义是以一点为中心的 一个球体； w组合优化问题中 2 2.1.1 .1.1 邻域的概念邻域的概念 3/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算

3、法导论浙江大学 w例 TSP问题解的一种表示方法为D=x=(i1,i2,in)| i1,i2,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) 2 2.1.1 .1.1 邻域的概念邻域的概念 4/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 TSP问题解的邻域映射可由2o

4、pt，推广到kopt 。 w邻域概念的重要性 邻域的构造依赖于决策变量的表示， 邻域的结构在现代优化算法中起重要的作用。 2 2.1.1 .1.1 邻域的概念邻域的概念 5/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 wSTEP 1 选定一个初始可行解x0，记录当前最优解xbest:=x0, T=N(xbest)； wSTEP 2 当Txbest=时，或满足其他停止运算准则时，输出 计算结果，停止运算；否则，从T中选一集合S，得 到S中的最好解xnow；若f (xnow)f(xbest)，则xbest := xnow ，T=N(xbest)；否则T:=TS；重复S

5、ETP 2。 2 2.1.2 .1.2 局部搜索算法局部搜索算法 6/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 w五个城市的对称TSP问题 初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射 为对换两个城市位置的2-opt，选定A城市为起点。 2 2.1.3 .1.3 局部搜索示例局部搜索示例 7/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 w五个城市的对称TSP问题 方法1：全邻域搜索 第1步 N(xbest)=(ABCDE)，(ACBDE)，(ADCBE)， (AECDB)，(ABDCE)，(ABEDC)，

6、(ABCED)， 对应目标函数为f(x)=45, 43, 45, 60, 60, 59, 44 xbest:=xnow=(ACBDE) 2 2.1.3 .1.3 局部搜索示例局部搜索示例 A B C D E 8/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 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) 2 2

7、.1.3 .1.3 局部搜索示例局部搜索示例 9/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 w五个城市的对称TSP问题 方法2：一步随机搜索 第1步 从N(xbest)中随机选一点，如xnow=(ACBDE)， 对应目标函数为f(xnow)=43 43 xbest:=xnow=(ACBDE) 2 2.1.3 .1.3 局部搜索示例局部搜索示例 11/82 2.1 2.1 局部搜索局部搜索 智能算法导论智能算法导论浙江大学 w五个城市的对称TSP问题 简单易行，但无法保证全局最优性,表现不稳定； 局部搜索主要依赖起点的选取和邻域的结构； 为了得到好的解，可以比较不

8、同的邻域结构和不同 的初始点； 如果初始点的选择足够多， 总可以计算出全局最优解。 2 2.1.3 .1.3 局部搜索示例局部搜索示例 12/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w算法的提出 禁忌搜索（Tabu search）是局部邻域搜索算法的 推广，Fred Glover在1986年提出这个概念，进而 形成一套完整算法。 w算法的特点 禁忌禁止重复前面的工作。 跳出局部最优点。 2 2.2.1 .2.1 算法的主要思路算法的主要思路 http:/spot.colorado.edu/glover/ 13/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导

9、论智能算法导论浙江大学 w为了找到“全局最优解”，就不应该执着于某一个特定 的区域。局部搜索的缺点就是太贪婪地对某一个局部 区域以及其邻域搜索，导致一叶障目，不见泰山。禁 忌搜索就是对于找到的一部分局部最优解，有意识地 避开它（但不是完全隔绝），从而获得更多的搜索区 间。 w兔子们找到了泰山，它们之中的一只就会留守在这里 ，其他的再去别的地方寻找。就这样，一大圈后，把 找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 2 2.2.1 .2.1 兔子的比喻兔子的比喻 14/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他

10、们知道， 这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁 忌表（tabu list）”的含义。 w那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新 回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟 也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面 叫做“禁忌长度（tabu length）”； w如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全 是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就 是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的 状态，就可以不顾及有没有兔子留守，都把这

11、个地方考虑进来，这就叫 “特赦准则（aspiration criterion）”。 2 2.2.1 .2.1 兔子的比喻兔子的比喻 15/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w四城市非对称TSP问题 初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市 顺序对换的2opt，始、终点都是A城市,禁忌长度 为3。 2 2.2.2 .2.2 禁忌搜索示例禁忌搜索示例 16/82 17/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w四城市非对称TSP问题 第1步 解的形式 禁忌对象及长度 候选解 f(x0)=4 2 2.2.2

12、 .2.2 禁忌搜索示例禁忌搜索示例 A B C D BCD A B C 对换评价值 CD4.5 BC7.5 BD8 18/82 A B D C 第2步 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w四城市非对称TSP问题 第2步 解的形式 禁忌对象及长度 候选解 f(x1)=4.5 2 2.2.2 .2.2 禁忌搜索示例禁忌搜索示例 A B D C BCD A B C3 对换评价值 CD4.0 BC3.5 BD4.5 T 19/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w四城市非对称TSP问题 第3步 解的形式 禁忌对象及长度 候选解

13、f(x2)=3.5 2 2.2.2 .2.2 禁忌搜索示例禁忌搜索示例 A C D B BCD A B3 C2 对换评价值 CD8 BC4.5 BD7.5 T T 20/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w四城市非对称TSP问题 第4步 解的形式 禁忌对象及长度 候选解 f(x3)=7.5 禁忌长度的选取 2 2.2.2 .2.2 禁忌搜索示例禁忌搜索示例 A C B D BCD A B23 C1 对换评价值 CD4.5 BC4.5 BD3.5 T T T 21/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w四城市非对称TS

14、P问题 第4步（如果减小禁忌长度） 解的形式 禁忌对象及长度 候选解 f(x3)=7.5 2 2.2.2 .2.2 禁忌搜索示例禁忌搜索示例 A C B D BCD A B12 C0 对换评价值 CD4.5 BC4.5 BD3.5 T T 22/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 w四城市非对称TSP问题 第5步 解的形式 禁忌对象及长度 候选解 f(x4)=4.5 2 2.2.2 .2.2 禁忌搜索示例禁忌搜索示例 A D B C BCD A B01 C2 对换评价值 CD7.5 BC8 BD4.5 T T 23/82 2.2 2.2 禁忌搜索禁忌搜索

15、智能算法导论智能算法导论浙江大学 w四城市非对称TSP问题 第6步 解的形式 禁忌对象及长度 候选解 f(x5)=8 2 2.2.2 .2.2 禁忌搜索示例禁忌搜索示例 A D C B BCD A B20 C1 对换评价值 CD3.5 BC4.5 BD4 T T 第7步 A B C D 回到第一步，出现循环，结束程序，最优解 为3.5，通过记忆每一步的最优评价值(best to far)实现 24/82 2.2 2.2 禁忌搜索禁忌搜索 智能算法导论智能算法导论浙江大学 2 2.2.2 .2.2 示例引出的问题示例引出的问题 25/82 w是否有其他形式的候选集？ w禁忌长度如何确定？（极限情况：禁忌长度=候选集中所有对换个数 如前面的3，相当于将候选集中的所有变换遍历；=1，等价于局部搜索算法） w是否有评价值的其他表示方法？ w被禁的对象能否再一次解禁？ 2.3 2.3 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 智能算法导论智能算法导论浙江大学 w禁忌表的主要指标（三项指标） 禁忌对象：禁忌表中被禁的那些变化元素 禁忌长度：禁忌的步数 候选集：从邻域中选择若干评价值最佳的邻居 w状态变化（三种变化） 解的简单变化 解向量分量的变化 目标值变化 2 2.3.1 .3.1 变化因素变化因素 26/82