禁忌搜索算法-课件·PPT.ppt

禁忌搜索算法
--昆昆
智能优化计算
概览
局部搜索
禁忌搜索
禁忌搜索关键参数和操作
禁忌搜索实现和应用
局部搜索
邻域
--定义
--tsp示例
--重要性
局部搜索
--操作步骤
搜索示例
--五城市对称tsp问题
邻域
函数优化问题:
邻域(N(x))通常定义为在给定距离空间内,以一点
(x)为中心的一个球体
组合优化问题:

且,称为一个邻域映射,其中表示X
所有子集组成的集合。
N(x)称为x的邻域, 称为x的一个邻居。
邻域
举两个简单的例子:
定义邻域移动为:位值加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]
邻域
定义邻域移动为: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]
邻域
重要性:
邻域的构造依赖于决策变量的表示,
邻域的结构在现代优化算法中起重要的作用。
局部搜索
操作步骤:
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。
局部搜索示例
五个城市的对称TSP问题
初始解为xbest=(ABCDE),f(xbest)=45,定义邻域映射为对换两个城市位置的2-opt,选定A城市为起点。