禁忌搜索算法.pptx

第三章禁忌搜索算法
智能算法导论
浙江大学
1
3
局部搜索
邻域的概念
局部搜索算法
局部搜索示例
禁忌搜索
算法的主要思路
禁忌搜索示例
禁忌搜索的关键参数和操作
变化因素
禁忌表
其他
禁忌搜索的实现与应用
30城市TSP问题(d*= by D B Fogel)
基于禁忌搜索算法的系统辨识
智能算法导论
浙江大学
2/82
局部搜索
智能算法导论
浙江大学
函数优化问题中
在距离空间中,通常的邻域定义是以一点为中心的一个球体;
组合优化问题中
邻域的概念
3/82
局部搜索
智能算法导论
浙江大学
例
TSP问题解的一种表示方法为D={x=(i1,i2,…,in)| i1,i2,…,in是1,2,…,n的排列},定义它的邻域映射为2-opt,即x中的两个元素进行对换,N(x)2=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)}
邻域的概念
4/82
局部搜索
智能算法导论
浙江大学
TSP问题解的邻域映射可由2-opt,推广到k-opt。
邻域概念的重要性
邻域的构造依赖于决策变量的表示,
邻域的结构在现代优化算法中起重要的作用。
邻域的概念
5/82
局部搜索
智能算法导论
浙江大学
STEP 1
选定一个初始可行解x0,记录当前最优解xbest:=x0, T=N(xbest);
STEP 2
当T\{xbest}=Φ时,或满足其他停止运算准则时,输出计算结果,停止运算;否则,从T中选一集合S,得到S中的最好解xnow;若f (xnow)<f(xbest),则xbest := xnow ,T=N(xbest);否则T:=T\S;重复SETP 2。
局部搜索算法
6/82
局部搜索
智能算法导论
浙江大学
五个城市的对称TSP问题


初始解为xbest=(ABCDE),f(xbest)=45,定义邻域映射为对换两个城市位置的2-opt,选定A城市为起点。
局部搜索示例
7/82
局部搜索
智能算法导论
浙江大学
五个城市的对称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
8/82
局部搜索
智能算法导论
浙江大学
五个城市的对称TSP问题
方法1:全邻域搜索
第2步
N(xbest)={(ACBDE),(ABCDE),(ADBCE),(AEBDC),(ACDBE),(ACEDB),(ACBED)},
对应目标函数为f(x)={43, 45, 44, 59, 59, 58, 43}

xbest:=xnow=(ACBDE)
局部搜索示例
9/82
局部搜索
智能算法导论
浙江大学
五个城市的对称TSP问题
方法2:一步随机搜索
第1步
从N(xbest)中随机选一点,如xnow=(ACBDE),
对应目标函数为f(xnow)=43< 45

xbest:=xnow=(ACBDE)
局部搜索示例
10/82