文档介绍：第二章 禁忌搜索算法
智能优化计算
广东药学院医药信息工程学院 2021年
局部搜索
邻域的概念
局部搜索算法
局部搜索例如
局部搜索例如
广东药学院医药信息工程学院 2021年
局部搜索
智能优化计算
五个城市的对称TSP问题
方法2：一步随机搜索
第2步
从N(xbest)中又随机选一点，如xnow=(ADBCE)，
对应目标函数为f(xnow)=44> 43
xbest:=xnow=(ACBDE)
局部搜索例如
广东药学院医药信息工程学院 2021年
局部搜索
智能优化计算
五个城市的对称TSP问题
简单易行，但无法保证全局最优性；
局部搜索主要依赖起点的选取和邻域的结构；
为了得到好的解，可以比较不同的邻域结构和不同的初始点；
如果初始点的选择足够多，
总可以计算出全局最优解。
局部搜索例如
广东药学院医药信息工程学院 2021年
禁忌搜索
智能优化计算
算法的提出
禁忌搜索〔Tabu Search 或 Taboo Search〕是局部邻域搜索算法的推广，Fred Glover在1986年提出这个概念，进而形成一套完整算法。
?Operation Research of America?
算法的特点
禁忌——禁止重复前面的工作。
跳出局部最优点。
算法的主要思路
:///~glover/
广东药学院医药信息工程学院 2021年
禁忌搜索
智能优化计算
四城市非对称TSP问题
初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。
禁忌长度：3
禁忌搜索例如
广东药学院医药信息工程学院 2021年
禁忌搜索
智能优化计算
四城市非对称TSP问题
第1步
解的形式 禁忌对象及长度 候选解
f(x0)=4
局部最优搜索算法：
已经到达局部最优而停止。
禁忌搜索算法：允许从候选集中选一个最好的对换。
禁忌搜索例如
A
B
C
D
B
C
D
A
B
C
对换
评价值
CD
BC
BD
8
☻
广东药学院医药信息工程学院 2021年
禁忌搜索
智能优化计算
四城市非对称TSP问题
第2步
解的形式 禁忌对象及长度 候选解
f(x1)=
禁忌搜索例如
A
B
D
C
B
C
D
A
B
C
3
对换
评价值
CD
BC
BD
☻
T
广东药学院医药信息工程学院 2021年
禁忌搜索
智能优化计算
四城市非对称TSP问题
第3步
解的形式 禁忌对象及长度 候选解
f(x2)=
禁忌搜索例如
A
C
D
B
B
C
D
A
B
3
C
2
对换
评价值
CD
8
BC
BD
☻
T
T
广东药学院医药信息工程学院 2021年
禁忌搜索
智能优化计算
四城市非对称TSP问题
第4步
解的形式 禁忌对象及长度 候选解
f(x3)=
*所有解都被禁忌，咋办？
*禁忌对象、*禁忌长度的选取
禁忌搜索例如
A
C
B
D
B
C
D
A
B
2
3
C
1
对换
评价值
CD
BC
BD
T
T
T
广东药学院医药信息工程学院 2021年
禁忌搜索
智能优化计算
四城市非对称TSP问题
第4