第七讲 禁忌搜索

1、3的邻域的邻域1的邻域的邻域12的邻域的邻域24的邻域的邻域43在邻域中找到最好的解w三种禁忌对象三种禁忌对象：（：（1）解的简单变化（类比于函数解的简单变化（类比于函数中的自变量中的自变量x的变化）的变化） 个解。是从一个解变化到另一则简单解变化为优化问题的定义域，其中，邻域映射为假设)( ,xNyxDNDyxn三种禁忌对象三种禁忌对象：（：（2）向量分量的变化（类比于函向量分量的变化（类比于函数中的映射规则变化）数中的映射规则变化） 设原有的解向量为设原有的解向量为(x1, , xi-1, xi, xi+1, , xn)，向量，向量分量的最基本变化为分量的最基本变化为 (x1, , xi-

2、1, xi, xi+1, xn)(x1, , xi-1, yi, xi+1, xn) 即只有第即只有第i个分量发生变化个分量发生变化。 也包含多个分量变化的情形。也包含多个分量变化的情形。n三种禁忌对象三种禁忌对象：（：（3）目标值的变化（类比于函数目标值的变化（类比于函数的值域的变化）的值域的变化） 目标值的变化隐含着解集合的变化。目标值的变化隐含着解集合的变化。无邻域的搜索无邻域的搜索有邻域的搜索有邻域的搜索有邻域的搜索有邻域的搜索 &分散搜索策略分散搜索策略因为这附近良解比较多再花点功夫找找看这附近已经探索得差不多了再到别的地方找找看多様化集中化 是离散值空间X .minXxts

3、xC ud,xsxudS xs sxud sXS x邻域的概念： 的邻域移动为，为单位步长， 为方向，则：邻域是邻域移动可达到的解的集合。 0,1,1,0,1,0,0s xxud是否是否否是是否是否否是 ks x ()() |kC sxOpt C s xs xSxT kxsxxsA ,sx ,C s xA s x xS s xTxsxxsA ,XxT0kxxx TxS1 kkNGk TxS |kC sxOpt C s xs xSxT kxsx Cx C x ,LC sxA s x sLxT Lxsx LC SxC x xCxCxx xCxCx,A s xC xXx T0k TxS1 kkNGk

4、 |kSxO p tsxsxSxTkxSx xsAxSCL, TxLS xSxL xCxCxxxcx,|kSxO ptsxsxSxT TxS TxS xSk xSCk xC 10 xcT xS xc xS xc xc xC xS xc xc xc xC xS xc xc xcxsA , xC xS xc xc xC xc xC xc xC |min|Opt C s xs xS xTC s xN s xs xS xT N s xs x其中是的移动次数， 是惩罚因子12345671162337442252,5562743N1x2x3x4x5x6x7x8x9x 2121 B,20nkliiL B i

5、nkliiL B ixxKArgMax D k D kxxKR K其中， 是已选初始解的集合这种方法使初始解充分分散到可行域的不同部分是随机产生的个点集变量定义：n 搜索次数N 搜索N 次，程序结束NI 连续没有找到更好解的次数M 连续M次没有找到更好解，执行分散搜索策略BS 找到的最好的解 Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的候选最好的候选解比解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换BS;En

6、dStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新

7、的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排

8、序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否BS初始解初始解Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初

9、始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否用插值的方法求得候选解

10、：生成随机数用插值的方法求得候选解：生成随机数r=1,6,选取选取第第r个位置上的元素，插入到其余位置前面个位置上的元素，插入到其余位置前面随机数随机数4Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=

11、n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否BS接受最好的候选解，并替换当前解接受最好的候选解，并替换当前解Tabu list 41， ，NI=1,n=1当前解当前解Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解

12、解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否用插值的方法求得候选解用插值的方法求得候选解随机数随机数2Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选

13、解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否BS考虑最好的候选解考虑最好的候选解Tabu list 41，

14、 ，NI=1,n=1新生成相邻关系(14), is Tabu! Reject it当前解当前解候选解候选解Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0

15、NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否BS考虑下一个最好的候选解考虑下一个最好的候选解Tabu list 41， ，NI=1,n=1新生成相邻关系(3,1), is not Tabu! accept it当前解当前解候选解候选解Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的

16、解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否BSTabu list 31，41 ，NI=2,n=2当前解当前解Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n

17、=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否BSTabu list ，NI=0

18、,n=2 连续M次没有出现更好解，因此产生新初始解随机生随机生产新的产新的当前解当前解Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是

19、是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否用插值的方法求得候选解用插值的方法求得候选解随机数随机数5Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一

20、个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否BS接受最好的候选解，并替换当前解接受最好的候选解，并替换当前解Tabu list 64， ，NI=1,n=3当前解当前解Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解

21、比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的解替换用新的解替换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替换当前解的解替换当前解是否为最后一是否为最后一个候选解？个候选解？是是否否是是否否用插值的方法求得候选解用插值的方法求得候选解随机数随机数2Tabu list 初始化初始化(清空清空)设设M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候选解，求得一系列候选解，并按优劣排序并按优劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替换当前解解替换当前解用新的