禁忌搜索算法教程 ppt课件.ppt

第三章 禁忌搜索
1
禁忌搜索算法教程
第三章 禁忌搜索


三. TS举例
四. TS中短、中、长期表的使用

2
禁忌搜索算法教程
问题描述

目标函数
约束条件
定义域
注：X为离散点的集合，TS排斥实优化
3
禁忌搜索算法教程
局域搜索
邻域的概念
函数优化问题：
邻域(N(x))通常定义为在给定距离空间内，以一点
(x)为中心的一个球体
组合优化问题：

且 ，称为一个邻域映射，其中 表示X
所有子集组成的集合。
N(x)称为x的邻域， 称为x的一个邻居。

4
禁忌搜索算法教程
局域搜索
邻域的概念
例：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)}

5
禁忌搜索算法教程
局域搜索
邻域的概念
例：
解的邻域映射可由2-opt，推广到k-opt，即对k个元素按一定规则互换。

邻域的构造依赖于解的表示，邻域的结构在智能优化算法中起重要的作用。
6
禁忌搜索算法教程
练 习
定义邻域移动为：位值加1或减1
对整数编码[ 2 2 3 5 3]，下列编码是否在其邻
域内：

[2 3 3 5 3] [2 3 2 5 3] [2 2 3 5 5]

[2 2 3 4 3] [2 2 2 5 3] [2 2 3 4 4]
是
否
否
是
是
否
7
禁忌搜索算法教程
练 习
定义邻域移动为：2-Opt
对顺序编码[ 4 2 3 5 1]，下列编码是否在其邻
域内：

[4 3 2 5 1] [4 3 5 1 2] [4 3 3 5 1]

[5 2 3 4 1] [1 2 3 5 4] [3 4 2 5 1]
是
否
否
是
是
否
8
禁忌搜索算法教程
局域搜索
局域搜索算法过程

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；重复STEP 2。
9
禁忌搜索算法教程
局域搜索
示例
例：五个城市的对称TSP问题

初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。
10
禁忌搜索算法教程