三章禁忌搜索ppt课件.pptx

文档介绍：1
第三章 禁忌搜索
2
第三章禁忌搜索
一. 前言
二. 禁忌搜索
三. 算法举例
四. 短、中、长期表的使用

3
问题描述

目标函数
约束条件
定义域
4
局域搜索
邻域的概念
函数优化问题:
邻域(N(x))通常定义为在给定距离空间内,以一点
(x)为中心的一个球体。
组合优化问题:

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

5
局域搜索
邻域的概念
例: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)}

8
练习
定义邻域移动为: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]
9
练习
定义邻域移动为:位值+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]
是
否
否
是
是
否
10
练习
定义邻域移动为: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]
是
否
否
是
是
否