Chapter 4 禁忌搜索算法 tsp问题.pdf

禁忌搜索算法 禁忌搜索算法 局部搜索 局部搜索 禁忌搜索 禁忌搜索 禁忌搜索的关键参数和操作 禁忌搜索的关键参数和操作 禁忌搜索的实现与应用 禁忌搜索的实现与应用 局部搜索 局部搜索 1. 邻域的概念 1. 邻域的概念  函数优化问题中 在距离空间中，通常的邻域定义是以一点为中心的 一个球体；  组合优化问题中 N : xD N(x) 2D , 且xN(x)，称为一个邻域映射，其中2D表示D 的所有子集组成的集合。 N(x)称为x的邻域，yN(x)称为x的一个邻居。 局部搜索 局部搜索 1. 邻域的概念 1. 邻域的概念  例 TSP 问题解的一种表示方法为D={x=(i ,i , …,i )| i ,i , …,i 是 1 2 n 1 2 n 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)} 局部搜索 局部搜索 1. 邻域的概念 1. 邻域的概念  例 TSP 问题解的邻域映射可由2-OPT，推广到k-OPT。  邻域概念的重要性 邻域的构造依赖于决策变量的表示， 邻域的结构在现代优化算法中起重要的作用。 局部搜索 局部搜索 2. 局部搜索算法 2. 局部搜索算法  Step 1 0 best 0 选定一个初始可行解x ，记录当前最优解x :=x , 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。 局部搜索 局部搜索 3. 局部搜索示例 3. 局部搜索示例  五个城市的对称TSP问题 初始解为xbest=(ABCDE)，f (xbest)=45，定义邻域映射 为对换两个城市位置的2-OPT，选定A城市为起点。 局部搜索 局部搜索 3. 局部搜索示例 3. 局部搜索示例  五个城市的对称TSP问题 方法1：全邻域搜索 第1步 N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)， (AECDB)，(ABDCE)，(ABEDC)，(ABCED)}， 对应目标函数为f (x)={45, 43, 45, 60, 60, 59, 44} A B C D E xbest :=xnow=(ACBDE) 局部搜索 局部搜索 3. 局部搜索示例 3. 局部搜索示例  五个城市的