第七講禁忌搜索

1、3的鄰域的鄰域1的鄰域的鄰域12的鄰域的鄰域24的鄰域的鄰域43在鄰域中找到最好的解w三種禁忌對(duì)象三種禁忌對(duì)象：（：（1）解的簡(jiǎn)單變化（類比于函數(shù)解的簡(jiǎn)單變化（類比于函數(shù)中的自變量中的自變量x的變化）的變化） 個(gè)解。是從一個(gè)解變化到另一則簡(jiǎn)單解變化為優(yōu)化問題的定義域，其中，鄰域映射為假設(shè))( ,xNyxDNDyxn三種禁忌對(duì)象三種禁忌對(duì)象：（：（2）向量分量的變化（類比于函向量分量的變化（類比于函數(shù)中的映射規(guī)則變化）數(shù)中的映射規(guī)則變化） 設(shè)原有的解向量為設(shè)原有的解向量為(x1, , xi-1, xi, xi+1, , xn)，向量，向量分量的最基本變化為分量的最基本變化為 (x1, , xi-

2、1, xi, xi+1, xn)(x1, , xi-1, yi, xi+1, xn) 即只有第即只有第i個(gè)分量發(fā)生變化個(gè)分量發(fā)生變化。 也包含多個(gè)分量變化的情形。也包含多個(gè)分量變化的情形。n三種禁忌對(duì)象三種禁忌對(duì)象：（：（3）目標(biāo)值的變化（類比于函數(shù)目標(biāo)值的變化（類比于函數(shù)的值域的變化）的值域的變化） 目標(biāo)值的變化隱含著解集合的變化。目標(biāo)值的變化隱含著解集合的變化。無鄰域的搜索無鄰域的搜索有鄰域的搜索有鄰域的搜索有鄰域的搜索有鄰域的搜索 &分散搜索策略分散搜索策略因?yàn)檫@附近良解比較多再花點(diǎn)功夫找找看這附近已經(jīng)探索得差不多了再到別的地方找找看多様化集中化 是離散值空間X .minXxtsxC u

3、d,xsxudS xs sxud sXS x鄰域的概念： 的鄰域移動(dòng)為，為單位步長(zhǎng)， 為方向，則：鄰域是鄰域移動(dòng)可達(dá)到的解的集合。 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 xS xT kxsx Cx C x ,LC sxA s x sLxT Lxsx LC SxC x xCxCxx xCxCx,A s xC xXx T0k TxS1 kkNGk |k

4、SxO 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其中是的移動(dòng)次數(shù)， 是懲罰因子12345671162337442252,5562743N1x2x3x4x5x6x7x8x9x 2121 B,20nkliiL B inkl

5、iiL B ixxKArgMax D k D kxxKR K其中， 是已選初始解的集合這種方法使初始解充分分散到可行域的不同部分是隨機(jī)產(chǎn)生的個(gè)點(diǎn)集變量定義：n 搜索次數(shù)N 搜索N 次，程序結(jié)束NI 連續(xù)沒有找到更好解的次數(shù)M 連續(xù)M次沒有找到更好解，執(zhí)行分散搜索策略BS 找到的最好的解 Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的候選最好的候選解比解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換BS;EndSt

6、art是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替

7、換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好

8、的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否BS初始解初始解Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初

9、始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否用插值的方法求得候選解：生成

10、隨機(jī)數(shù)用插值的方法求得候選解：生成隨機(jī)數(shù)r=1,6,選取選取第第r個(gè)位置上的元素，插入到其余位置前面?zhèn)€位置上的元素，插入到其余位置前面隨機(jī)數(shù)隨機(jī)數(shù)4Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1

11、nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否BS接受最好的候選解，并替換當(dāng)前解接受最好的候選解，并替換當(dāng)前解Tabu list 41， ，NI=1,n=1當(dāng)前解當(dāng)前解Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換

12、當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否用插值的方法求得候選解用插值的方法求得候選解隨機(jī)數(shù)隨機(jī)數(shù)2Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求

13、得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否BS考慮最好的候選解考慮最好的候選解Tabu list 41， ，N

14、I=1,n=1新生成相鄰關(guān)系(14), is Tabu! Reject it當(dāng)前解當(dāng)前解候選解候選解Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=

15、M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否BS考慮下一個(gè)最好的候選解考慮下一個(gè)最好的候選解Tabu list 41， ，NI=1,n=1新生成相鄰關(guān)系(3,1), is not Tabu! accept it當(dāng)前解當(dāng)前解候選解候選解Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新

16、的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否BSTabu list 31，41 ，NI=2,n=2當(dāng)前解當(dāng)前解Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;

17、NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否BSTabu list ，NI=0,n=

18、2 連續(xù)M次沒有出現(xiàn)更好解，因此產(chǎn)生新初始解隨機(jī)生隨機(jī)生產(chǎn)新的產(chǎn)新的當(dāng)前解當(dāng)前解Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否

19、是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否用插值的方法求得候選解用插值的方法求得候選解隨機(jī)數(shù)隨機(jī)數(shù)5Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出

20、下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否BS接受最好的候選解，并替換當(dāng)前解接受最好的候選解，并替換當(dāng)前解Tabu list 64， ，NI=1,n=3當(dāng)前解當(dāng)前解Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS

21、好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解替換用新的解替換當(dāng)前解當(dāng)前解;EndStart是是IntensificationIts in tabu？找出下一個(gè)找出下一個(gè)次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替換當(dāng)前解的解替換當(dāng)前解是否為最后一是否為最后一個(gè)候選解？個(gè)候選解？是是否否是是否否用插值的方法求得候選解用插值的方法求得候選解隨機(jī)數(shù)隨機(jī)數(shù)2Tabu list 初始化初始化(清空清空)設(shè)設(shè)M,N的值的值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候選解，求得一系列候選解，并按優(yōu)劣排序并按優(yōu)劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替換當(dāng)前解解替換當(dāng)前解用新的解