禁忌搜索算法局部搜索禁忌搜索禁忌搜索的关键参数和操作禁忌搜索的实现与应用局部搜索♦函数优化问题中在距离空间中，通常的邻域定义是以一点为中心的一个球体；♦组合优化问题中1. 邻域的概念:()2,()2()()D DN x D N x x N x D N x x y N x x ∈→∈∈∈且，称为一个邻域映射，其中表示的所有子集组成的集合。
称为的邻域，称为的一个邻居。
局部搜索1. 邻域的概念例TSP问题解的一种表示方法为D={x=(i1,i2,…,i n)| i1,i2,…,i n是1,2,…,n的排列}，定义它的邻域映射为2-OPT，即x中的两个元素进行对换，N(x)中共包含x的C n2=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)}局部搜索2. 局部搜索算法♦Step 1选定一个初始可行解x0，记录当前最优解x best:=x0, T=N(x best)；♦Step 2当T\{x best}=Φ时，或满足其它停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解x now；若f (x now)<f(x best)，则x best := x now，T=N(x best)；否则T:=T\S；重复Step 2。
局部搜索五个城市的对称TSP 问题初始解为x best =(ABCDE )，f (x best )=45，定义邻域映射为对换两个城市位置的2-OPT ，选定A 城市为起点。
3. 局部搜索示例局部搜索五个城市的对称TSP 问题方法1：全邻域搜索第1步N (x best )={(ABCDE )，(ACBDE )，(ADCBE )，(AECDB )，(ABDCE )，(ABEDC )，(ABCED )}， 对应目标函数为f (x )={45, 43, 45, 60, 60, 59, 44}x best :=x now =(ACBDE ) 3. 局部搜索示例A B C D E局部搜索3. 局部搜索示例五个城市的对称TSP问题方法1：全邻域搜索第2步N(x best)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43, 45, 44, 59, 59, 58, 43}x best:=x now=(ACBDE)局部搜索3. 局部搜索示例五个城市的对称TSP问题方法2：一步随机搜索第1步从N(x best)中随机选一点，如x now=(ACBDE)，对应目标函数为f(x now)=43< 45x best:=x now=(ACBDE)局部搜索3. 局部搜索示例五个城市的对称TSP问题方法2：一步随机搜索第2步从N(x best)中又随机选一点，如x now=(ADBCE)，对应目标函数为f(x now)=44> 43x best:=x now=(ACBDE)禁忌搜索1. 算法的主要思路♦算法的提出禁忌搜索（Tabu Search，TS）是局部邻域搜索算法的推广，Fred Glover在1986年提出这个概念，进而形成一套完整算法。
