第七講 禁忌搜索

1第四章禁忌搜索（TabuSearch

）一.導言二.TS的基本原理及步驟三.TS的算法步驟四.TS可以克服局優(yōu)的分析五.TS舉例六.TS的中、長期表的使用七.TS表的應用舉例八.學習TS的幾點體會3的鄰域搜索陷入循環(huán)1的鄰域12的鄰域24的鄰域43在鄰域中找到最好的解31977年F.Glover提出禁忌搜索算法，90年代初得到廣泛重視。是GA之后提出的另一啟發(fā)式優(yōu)化方法。模仿人類的記憶功能，使用禁忌表封鎖剛搜索過的區(qū)域，以避免迂回搜索。同時赦免禁忌區(qū)域中的一些優(yōu)良狀態(tài)，以保證搜索的多樣性。一.導言（1）4TS的基本思想——避免在搜索過程中的循環(huán)只進不退的原則——用Tabu表鎖住退路，將近期歷史搜索過程存放在禁忌表中，防止算法重新進入。不以局部最優(yōu)作為停止準則，算法接受劣解，只要不在禁忌表的較好解都可作為下一次迭代的初始解。鄰域選優(yōu)的規(guī)則模擬了人類的記憶功能——找過的地方都記下來，不再找第二次。隨著迭代的進行，禁忌表不斷更新，一定迭代次數(shù)后，早期進入禁忌表解被解禁退出。一.導言（2）5禁忌表作用示例（1）七種不同絕緣材料構成一種絕緣體，如何排列七種材料使得絕緣效果最好？絕緣效果以絕緣數(shù)值表示，數(shù)值越大，效果越好。某次迭代后，材料的排列順序為2-4-7-3-5-6-1，交換各種材料對絕緣效果的改善情況見下表：交換的材料絕緣效果改善1，32(正值表示絕緣效果變好)2，313，4-1(負值表示絕緣效果變壞)1，7-21，6-4……6禁忌表作用示例（2）可見，交換材料1和3可增加絕緣數(shù)值2，并且改善效果最好，交換后2-4-7-1-5-6-3.絕緣數(shù)值為18，將交換（1，3）加入禁忌表。此時兩兩交換材料對絕緣效果的影響見下表。交換的材料絕緣效果1，3-22，4-46，7-64，5-73，5-9……7禁忌表作用示例（3）上表看出，交換（1，3）對絕緣數(shù)值的降低最小，但是交換后又回到以前的狀態(tài)，為避免回到上一次交換前的狀態(tài)，采用禁忌表。所以，選擇交換（2，4），是其它選擇中使絕緣數(shù)值降低最小的一對。此禁忌表中存放的不是解，而是解的移動。為實現(xiàn)全局搜索，往往設置渴望水平，若一個移動達到渴望水平，能跳離局部最優(yōu)，該移動可以不受禁忌表的限制，稱為破禁。8TS的要素構成(1)編碼方法(2)適值函數(shù)的構造(3)初始解的獲得(4)移動與鄰域移動(5)禁忌表(TabuList)(6)選擇策略(7)渴望水平函數(shù)(AspirationLevelFunction)(8)停止準則——與GA相似一.導言（3）9(1)編碼方法靈活的選擇編碼方法，如背包的0-1編碼。同一問題有多種編碼方法，如分組問題：不相同的n件物品分為m組，n=9，m=3.編碼1：

1-3-4-0-2-6-7-5-0-8-9（1-4-3-0-6-2-5-7-0-9-8）

0起到隔開作用1-3-4分為一組，2-6-7-5一組，8-9一組。編碼2：

1-2-1-1-2-2-2-3-3（2-1-2-2-1-1-1-3-3）表示1-3-4分為一組，2-6-7-5一組，8-9一組10(2)適值函數(shù)的構造適值函數(shù)是用來對搜索狀態(tài)進行評價的。對目標函數(shù)的任何變形都可作為目標函數(shù)，只要該變形保持嚴格單調(diào)。11（3）初始解的獲得可以隨機給出初始解，也可以是其它啟發(fā)式算法給出的較好的初始解。禁忌搜索算法主要是基于鄰域搜索的，所以初始解對算法搜索性能影響很大。對于較為復雜的約束問題，隨機產(chǎn)生的初始解可能是不可行解，應該采用一些啟發(fā)式方法找到一個可行解作為初始解。12(4)移動與鄰域移動移動是產(chǎn)生新解的途徑，從當前解可以進行的所有的移動構成鄰域，因此移動規(guī)則的設計是算法的關鍵。移動規(guī)則類似于交叉算子，根據(jù)具體問題進行分析設計，如排序問題中采用兩兩交換方式的移動規(guī)則。

13(5)禁忌表(TabuList)禁忌表是為了防止搜索過程出現(xiàn)循環(huán)而陷入局部最優(yōu)的，是禁忌搜索算法的核心。某些移動經(jīng)一定迭代次數(shù)后被解禁，又可重新訪問，因此禁忌表稱為短期表。禁忌對象：放入禁忌表的元素，主要包括三種，（1）以狀態(tài)本身或狀態(tài)變化為禁忌對象，其禁忌范圍適中；（2）以狀態(tài)分量或狀態(tài)分量的變化作為禁忌對象，其禁忌范圍較??；（3）以目標值為禁忌對象，其禁忌范圍較大。禁忌長度：禁忌表的大小。禁忌表越小，計算時間和存儲空間越少，但禁忌表過小，會造成搜索過程進入循環(huán)。禁忌長度分為固定禁忌長度和隨時間變化禁忌長度兩類。三種禁忌對象：（1）解的簡單變化（類比于函數(shù)中的自變量x的變化）

三種禁忌對象：（2）向量分量的變化（類比于函數(shù)中的映射規(guī)則變化）

設原有的解向量為(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本變化為(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)即只有第i個分量發(fā)生變化。也包含多個分量變化的情形。三種禁忌對象：（3）目標值的變化（類比于函數(shù)的值域的變化）

目標值的變化隱含著解集合的變化。17(6)選擇策略選擇策略是從鄰域中選擇一個較好解作為下一次迭代初始解的方法。候選解集的確定是選擇策略的關鍵，對算法性能影響很大。候選解集為整個鄰域。選擇策略是從整個鄰域內(nèi)選擇一個最優(yōu)解為下一次迭代的初始解，計算時間較長。候選解集為鄰域的真子集。這種選擇策略只掃描鄰域的一部分構成候選解集，雖不能找到鄰域內(nèi)最優(yōu)解，但減少了搜索時間。18(7)渴望水平函數(shù)在有些特定的條件下，不管某個移動是否在禁忌表中，都接受這個移動并更新當前解和歷史最優(yōu)解。這個特定的條件即為渴望水平。渴望水平的設定有如下幾種形式：（1）基于適配值的準則，如果某個候選解的適配值高于歷史最優(yōu)解，無論是否處于禁忌表中，都選擇接受。（2）基于搜索方向的準則，某禁忌對象進入緊急表時改善了適配值，而這次這個被禁忌的候選解由改善了適配值，故破禁。（3）基于影響力的準則，有的禁忌對象對適配值的影響較大，解禁會對解有較大影響，解禁時要考慮。（4）其它準則19(8)停止準則——與GA相似給定最大迭代次數(shù)得到滿意解設定某對象的最大禁忌頻率分散搜索：是為了對整個解的空間進行更廣泛的覆蓋，而不是僅僅局限在某個局部的區(qū)域。分散搜索（Diversification）和集中搜索（Intensification）策略無鄰域的搜索有鄰域的搜索有鄰域的搜索&分散搜索策略集中搜索：如果當前搜索區(qū)域內(nèi)發(fā)現(xiàn)了比較好的解，如果進一步對當前區(qū)域進行更集中的搜索，那么可能會發(fā)現(xiàn)更多更好的解。分散搜索（Diversification）和集中搜索（Intensification）策略分散搜索策略（Diversificationstrategy）在當前搜索區(qū)域內(nèi)進行了一定次數(shù)的搜索了之后（如25次），若不能發(fā)現(xiàn)更好的解，那么就執(zhí)行分散搜索策略。把tabulist清空，然后從一個新的初始解開始搜索。集中搜索：如果最好解的記錄被更新，那么就執(zhí)行集中搜索策略，即清空tabulist.這樣可以在當前區(qū)域進行更自由的搜索。集中化intensification因為這附近良解比較多再花點功夫找找看多樣化diversification這附近已經(jīng)探索得差不多了再到別的地方找找看集中化與多樣化的有機結合

φ多様化集中化現(xiàn)代啟發(fā)式算法的核心問題26問題的描述及鄰域的概念

TS僅用于離散優(yōu)化，排斥實優(yōu)化 二.TS的基本原理及步驟（1）27

二.TS的基本原理及步驟（2）28鄰域舉例：

x=[0,1,0,0,1,0,0] u=1, d=[0,0,1,0,0,0,0]注意：移動的意義是靈活的，目的是便于搜索。如：排序問題中一次換位可稱為一次移動，還可以定義為選一個切點，兩部分作交叉運算。二.TS的基本原理及步驟（3）29練習定義鄰域移動為位值加1或減1,對整數(shù)編碼[22353]，以下染色體是否在其鄰域內(nèi)：

[23353]，[23253]，[22355]，

[22343]，[22253]，[22344]，

是否是否否是30練習（2）定義鄰域移動為兩兩換位,對順序編碼[42351]，以下染色體是否在其鄰域內(nèi)：

[43251]，[43512]，[43351]，

[52341]，[12354]，[34251]，

是否是否否是31禁忌表的概念禁忌表的作用：防止搜索出現(xiàn)循環(huán)記錄前若干步走過的點、方向或目標值，禁止返回表是動態(tài)更新的——把最新的解記入，最老的解從表中釋放(解禁)。表的長度稱為Tabu-Size，一般取5、7、11，表長越大分散性越好。二.TS的基本原理及步驟（4）32鄰域搜索規(guī)則每一步移動到不在T表中的鄰域中的最優(yōu)解，即若 ，則令則本次移動到最優(yōu)解鄰域搜索規(guī)則的作用：保證TS的優(yōu)良局部搜索功能二.TS的基本原理及步驟（5）33渴望水平函數(shù) 是一個取決于和的值，若有則是不受T表限制。即使，仍可取渴望水平，一般為歷史上曾經(jīng)達到的最好目標值。二.TS的基本原理及步驟（6）34步驟：選一個初始點， ，令 ， ，迭代指標 ；若 停止，否則令 ，若

(其中NG為最大迭代數(shù))停止；注： 表示非正常終止，造成的原因：鄰域小，T表長。正常設置為(T表長度<鄰域大小)。步驟②的作用是設置循環(huán)體出口。三.TS的算法步驟（1）35若 ，令 ,更新 (當前鄰域最優(yōu)目標函數(shù)值)；注：步驟③的作用鄰域選優(yōu)若 ， 且 ，令

,更新C(x)；注：步驟④的作用破禁檢查三.TS的算法步驟（2）36三.TS的算法步驟（3）若 ，令，注：步驟⑤的作用選優(yōu)并記錄歷史最好點,更新渴望水平)更新T表，轉(zhuǎn)步2(存入T表中的第一個位置)37失敗出口(避免)破禁檢查初始開始更新T表停止YN停止YN若令若輸出終止出口step2step3step4step5step1鄰域移動擇優(yōu)規(guī)則38從鄰域搜索的方法看移向 中最好的解，但不與當前解比較 是 中的最優(yōu)點，但 可能劣于四.TS可以克服局優(yōu)的分析（1）39選優(yōu)規(guī)則看始終保持歷史上的最優(yōu)解，不以當前解為最優(yōu)從停止規(guī)則上看不以最優(yōu)判據(jù)為停止規(guī)則，而是指定最大迭代步數(shù)為停止條件，這樣不能保證最優(yōu)性。四.TS可以克服局優(yōu)的分析（2）40問題的提出由7層不同的絕緣材料構成的一種絕緣體，應如何排列順序，可獲得最好的絕緣性能。五.TS舉例（1）41

編碼方式：順序編碼 初始編碼：2-5-7-3-4-6-1

目標值：極大化目標值。鄰域定義：兩兩交換是一個鄰域移動鄰域大?。篢abuSize：3 NG：5五.TS舉例（2）42初始表初始編碼：2-5-7-3-4-6-1結論：交換4和5五.TS舉例（3）移動5，467，443，622，304，1-1…………T表12343迭代1

編碼：2-4-7-3-5-6-1 ==16結論：交換1和3五.TS舉例（4）移動3，122，313，4-17，1-26，1-4…………T表14，52344迭代2

編碼：2-4-7-1-5-6-3 ==18結論：因交換1和3已在禁忌表中，故只能交換2和4五.TS舉例（5）移動1，3-22，4-47，6-64，5-75，3-9…………T表11，324，53若選擇這項 =16，渴望水平不能發(fā)生作用45迭代3

編碼：4-2-7-1-5-6-3 =14， =18結論：因渴望水平發(fā)揮作用，交換在破禁表中的4,5五.TS舉例（6）移動4，565，327，101，3-32，6-6…………T表12，421，334，5因 =20大于渴望水平=18此時渴望水平發(fā)生作用，破禁。交換4和5。 46迭代4

編碼：5-2-7-1-4-6-3 = =20結論：交換7和1五.TS舉例（7）移動7，104，3-36，3-55，4-62，6-8…………T表14，522，431，347迭代5

編碼：5-2-1-7-4-6-3 = =20結論：迭代已到5次，得到最優(yōu)解

5-2-7-1-4-6-3和5-2-1-7-4-6-3 = =20五.TS舉例（8）48引入中長期表的目的改善TS的廣域搜索能力，TS的局域搜索能力很好，鄰域選優(yōu)快，但廣域搜索能力較差。搜索能力是TS的關鍵，采用中長期表可改善TS的廣域搜索能力。六.TS的中、長期表的使用（1）49中期表——頻數(shù)表,頻率表頻數(shù)表的作用頻數(shù)表是用來記憶不同方向的移動次數(shù)，從而加以懲罰(比如兩兩交換，記錄每對交換的發(fā)生次數(shù))以提高搜索方向的多樣性。在不考慮中期表的情況下，每一次迭代在候選解集中選擇目標函數(shù)值最小的解，若考慮中期表，每一次迭代是在候選解集中選擇目標函數(shù)值小且被禁忌次數(shù)比較少的解。六.TS的中、長期表的使用（2）50在鄰域選優(yōu)公式中，令注：懲罰因子的取值一般應遠小于目標值(1%目標值或1‰目標值)，越大分散性越好，廣域搜索能力強，但會損壞鄰域搜索。六.TS的中、長期表的使用（3）51頻數(shù)表的記錄方法（以n元素排列問題為例）將短期表和中期表放在一起，建立n×n的矩陣，右上部分為短期表，左下部分為中期表，對角線上的元素沒有意義。對上半部分每做一步搜索將所有>0的數(shù)減1；對數(shù)組上半部分，給新發(fā)生的移動所對應的數(shù)組元加上Tabu-Size;T表的下半部分，用來記頻數(shù)，每次(i,j)交換(i<j)，對應的((j,i)+1)來記憶頻數(shù)。六.TS的中、長期表的使用（4）52頻數(shù)表的優(yōu)點：同一數(shù)組作為T表和頻數(shù)表共同使用，方便操作又節(jié)省了時間。六.TS的中、長期表的使用（5）53頻數(shù)表：Tabu-Size=7六.TS的中、長期表的使用（6）T表73，461，755，643，732，624，511，354長期表的使用——多階段TS算法長期表的作用 使用短期表（禁忌表）的搜索方式為鄰域搜索，中期表的搜索方式為區(qū)域強化式搜索，長期表的搜索方式實現(xiàn)了全局多樣化搜索。 長期表用來記錄多個初始解，從這些初始解開始進行禁忌搜索，每個階段的初始解，在下一階段產(chǎn)生初始解時，使之盡可能與已有的初始解有較大的距離，為了使各個初始解在可行域內(nèi)具有良好的分散性，以實現(xiàn)全局搜索。短期表（禁忌表）僅記錄禁忌信息，中期表記錄禁忌信息和禁忌次數(shù)，長期表將各階段初始解記錄下來。六.TS的中、長期表的使用（7）55圖示六.TS的中、長期表的使用（8）56函數(shù)表達式長期表的TS有很好的性能。六.TS的中、長期表的使用（9）57七.TS表的應用舉例（TSP問題）變量定義：n＝搜索次數(shù)N＝搜索N次，程序結束NI＝連續(xù)沒有找到更好解的次數(shù)M＝連續(xù)M次沒有找到更好解，執(zhí)行分散搜索策略BS＝找到的最好的解

58Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的候選解比BS好？接受新的解用新的解替換當前解用新的解替換BS;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否59TSP算例Citytocity1234561124791021120138361713469515660Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否61Tabulist初始化(清空)設M,N的值

Tabulist{}，長度為2。記錄從當前解生成新的解的過程中，產(chǎn)生的新的相鄰關系M=2N=462Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否63求得初始解BS=初始解

SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解64Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否65求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute4132563014325635134256381325464013256445用插值的方法求得候選解：生成隨機數(shù)r=[1,6],選取第r個位置上的元素，插入到其余位置前面隨機數(shù)＝466Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否67判斷是否為tabu,決定接受與否SequenceThelengthoftheroute41325630BSSequenceThelengthoftheroute13245628接受最好的候選解，并替換當前解Tabulist{41，}，NI=1,n=1當前解68Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否69求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute1432562943125633432156354325163643256138用插值的方法求得候選解隨機數(shù)＝270Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否71判斷是否為tabu,決定接受與否SequenceThelengthoftheroute4132563014325629BSSequenceThelengthoftheroute13245628考慮最好的候選解Tabulist{41，}，NI=1,n=1新生成相鄰關系(14),isTabu!Rejectit當前解候選解72Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否73判斷是否為tabu,決定接受與否SequenceThelengthoftheroute4132563043125633BSSequenceThelengthoftheroute13245628考慮下一個最好的候選解Tabulist{41，}，NI=1,n=1新生成相鄰關系(3,1),isnotTabu!acceptit當前解候選解74Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否75更新當前解、最好解、tabulist

及相關參數(shù)SequenceThelengthoftheroute43125633BSSequenceThelengthoftheroute13245628Tabulist{31，41}，NI=2,n=2當前解76Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否77分散搜索（diversification）SequenceThelengthoftheroute45326145BSSequenceThelengthoftheroute13245628Tabulist{}，NI=0,n=2連續(xù)M次沒有出現(xiàn)更好解，因此產(chǎn)生新初始解隨機生產(chǎn)新的當前解78Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否79求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute6453212846532132456321344536213645321637用插值的方法求得候選解隨機數(shù)＝580Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當前解是否為最后一個候選解？是否是否81判斷是否為tabu,決定接受與否SequenceThelengthoftheroute64532128BSSequenceThelengthoftheroute13245628接受最好的候選解，并替換當前解Tabulist{64，}，NI=1,n=3當前解82Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當前解用新的解替換當前解;EndStart