1、局域搜索與隨機(jī)搜索,概要,爬山法 隨機(jī)搜索 模擬退火法 局域射線搜索 遺傳算法,局域搜索,假設(shè)對(duì)每個(gè)狀態(tài)X，定義一個(gè)鄰域（或移動(dòng)集）Neighbors(X)，其是從X出發(fā)在一步內(nèi)能到達(dá)的狀態(tài)集。 X0初始態(tài) 重復(fù)直到滿意當(dāng)前狀態(tài)為止。 評(píng)估Neighbors(Xi)中的一些近鄰 選擇其中一個(gè)近鄰，Xi+1 移到Xi+1,最簡(jiǎn)單實(shí)例,S=1,100 Neighbors(X)=X-1,X+1,最簡(jiǎn)單實(shí)例,雖然對(duì)全域極值有興趣，但可能只有滿足于局域極值。 事實(shí)上，每次迭代只能得到局域極值。 挑戰(zhàn)性：通過一系列的局域移動(dòng)來試圖達(dá)到全域極值。,S=1,100,全域極值Eval(X*)所有X的Eval(X

2、),局域極值Eval(X*)在Neighbors(X)中所有X的Eval(X),Neighbors(X)=X-1,X+1,搜索問題的提出：,已知： 一個(gè)狀態(tài)（或構(gòu)形）集：S=X1,XM, 一個(gè)評(píng)估每個(gè)狀態(tài)的函數(shù)：Eval(X). 求解： 尋找全域極值：尋找X*使得Eval(X*)比所有其它Eval(Xi)都更大，Xi是所有可能的值。,實(shí)例,調(diào)度：已知m個(gè)機(jī)器，n個(gè)任務(wù)。 X=給機(jī)器的任務(wù)安排 Eval=這n個(gè)任務(wù)完成時(shí)間的極小化 其它：車輛路由、設(shè)計(jì)、處理排序，,任務(wù),機(jī)器,時(shí)間,實(shí)例：旅行推銷商問題（TSP）,尋找一個(gè)經(jīng)過每個(gè)結(jié)點(diǎn)一次，且長(zhǎng)度最小的旅行路線。,Eval(X1)Eval(X2)

3、,X1=1,2,5,3,6,7,4,X2=1,2,5,4,7,6,3,實(shí)例：旅行推銷商問題（TSP）,構(gòu)形X=經(jīng)過結(jié)點(diǎn)1,N的旅行 Eval=由一個(gè)1,N的排列來定義的路徑長(zhǎng)度 尋找X*來實(shí)現(xiàn)Eval(X)的極小。 搜索空間尺寸=(N-1)!/2量級(jí)。 注意：N為幾十萬時(shí)，搜索空間是巨大的。,Eval(X1)Eval(X2),X1=1,2,5,3,6,7,4,X2=1,2,5,4,7,6,3,實(shí)例：N個(gè)皇后,尋找一個(gè)構(gòu)形，使得沒有一個(gè)皇后能攻擊其她任何一個(gè)皇后。,EVAL(X)=5,EVAL(X)=2,EVAL(X)=0,實(shí)例：N個(gè)皇后,構(gòu)形X=在N列中N個(gè)皇后的位置。 Eval(X)=能兩兩

4、相互攻擊的皇后對(duì)數(shù)目。 尋找X*來實(shí)現(xiàn)極?。篍val(X)=0。 搜索空間尺寸：NN量級(jí)。 注意：N10時(shí)，搜索空間是巨大的。,EVAL(X)=5,EVAL(X)=2,EVAL(X)=0,最基本的算法：爬山法（局域貪婪搜索）,算法描述： 顧名思義，爬山法就是向Eval(X)值增大的方向持續(xù)移動(dòng)。 算法分析： 爬上法終將在一個(gè)“峰頂”終止，此時(shí)相鄰狀態(tài)中沒有比它更高的值。算法不維護(hù)搜索樹，當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)只記錄當(dāng)前狀態(tài)和它的目標(biāo)函數(shù)值。爬山法不會(huì)前瞻與當(dāng)前狀態(tài)不直接相鄰的那些狀態(tài)值。所以爬山法到達(dá)一個(gè)局部最大值或者“平原”的時(shí)候，就會(huì)無路可走，可見，爬山法不是最優(yōu)的。,爬山法（局域貪婪搜索）,

5、X初始構(gòu)形(狀態(tài)） loop do： E Eval(X) N Neighbors(X) 對(duì)在N中的每個(gè)Xi Ei Eval(Xi) /評(píng)估每個(gè)后續(xù)的值 Ei*=argmaxi(Ei) /選擇具有最大值的后續(xù) if (Ei* E) return X else XXi* EEi*,爬山法的局限,多個(gè)局域極值,Eval(.)恒定值的平臺(tái)區(qū),山脊=僅用爬山移動(dòng)是不可能從Xstart到達(dá)X*的。,隨機(jī)搜索：隨機(jī)爬山法,隨機(jī)爬山法就是指在上山的過程中隨機(jī)的選擇下一步，選擇的概率隨上山的陡峭程度而變化。 X初始狀態(tài) 迭代： EEval(X) X在Neighbors(X)中隨機(jī)選擇一個(gè)狀態(tài) EEval(X)

6、if EE XX EE 問題： 迭代停止條件？選擇下一步的概率為0，即周圍的值都比E小（EE） 不再選擇在整個(gè)鄰域中的最佳移動(dòng)。,模擬退火法（SA）,算法描述： SA算法是爬山法和隨機(jī)行走算法的結(jié)合，以同時(shí)求的有效性和完備性。SA算法沒有選擇最佳的移動(dòng)，而是選擇隨機(jī)的移動(dòng)。如果移動(dòng)使情況改善，那么該移動(dòng)。否則，算法以某個(gè)小于1的概率接受該移動(dòng)。這個(gè)概率按照移動(dòng)的“惡劣狀態(tài)”評(píng)價(jià)值變壞的梯度E(E-E)成指數(shù)級(jí)下降。這個(gè)概率同時(shí)也隨著“溫度”的降低而下降：當(dāng)一開始溫度高的時(shí)候，“壞的”移動(dòng)更可能被允許發(fā)生，T越低就越不可能發(fā)生。如果讓T下降的足夠慢，這個(gè)算法找到全局最優(yōu)解的概率將逼近1。,模擬退

7、火法（SA）,EEval(X) X一個(gè)在Neighbors(X)中隨機(jī)選擇的狀態(tài)。 EEval(X) if EE /即E0 XX EE else 以某概率p接受此到達(dá)X的移動(dòng)： XX EE 注：不再總是爬山移動(dòng)了。怎樣選擇p？,怎樣給p賦值？,X初始構(gòu)形 loop do： EEval(X) X一個(gè)在Neighbors(X)中隨機(jī)選擇的構(gòu)形。 EEval(X) if EE XX EE else 以某概率p接受此到達(dá)X的移動(dòng)： XX EE,如果p為常數(shù)：則不知道該給p賦怎樣的值。其值應(yīng)依賴于Eval函數(shù)的形狀。 隨著迭代的發(fā)展，p應(yīng)降低。由此可在趨向全域極值時(shí)，接受較少的下山移動(dòng)。 隨著E-E 增

8、加，p應(yīng)降低。如果坡度陡，則應(yīng)降低下山移動(dòng)的概率。,怎樣給p賦值？,E-E 大：較可能的是，迭代正朝著一個(gè)敏銳的極大值移動(dòng)。因此，此時(shí)不宜采取大的下山移動(dòng)。,E-E 小：可能是迭代正朝著一個(gè)平緩的極大值移動(dòng)。這類極值可能是一個(gè)局域極值，因此，希望移下山，去探索其它地方。,選擇p：模擬退火法,if EE，接受該移動(dòng) else 接受該移動(dòng)，并置概率為： p=e(E-E)/T 從高溫開始，隨著迭代開展而逐漸降低T,即冷卻調(diào)度,增加E,p,增加T,模擬退火法,X初始構(gòu)形 T初始高溫 loop do： 循環(huán)K次： EEval(X) X一個(gè)在Neighbors(X)中隨機(jī)選擇的構(gòu)形 EEval(X) if

9、 EE XX；EE else 以概率p=e(E-E)/T接受該移動(dòng) XX；EE TT 需要處理的參數(shù)有： 初始構(gòu)形、K、初始溫度、隨機(jī)選擇、Neighbors(X)、等。,模擬退火法,注意事項(xiàng)： 循環(huán)K次時(shí)，保持溫度恒定。 T=0，以p=1的概率選擇最大值后繼（貪婪爬山法）；T=，以p=0的概率選擇最大值后繼（隨機(jī)行走）。 采用一個(gè)指數(shù)冷卻函數(shù)來逐步降低溫度：T(n)= T，其中=n，且1。 采用p=e(E-E)/T概率值來接受下山移動(dòng)。,局域射線搜索,算法描述： 局部射線搜索記錄k個(gè)狀態(tài)，而不是一個(gè)。它由K個(gè)隨機(jī)生成的狀態(tài)開始。在每步產(chǎn)生這k個(gè)狀態(tài)的所有后繼狀態(tài)，如果有一個(gè)是終態(tài)，則停止。否

10、則從后繼列表中選擇k個(gè)最佳的后繼，然后重復(fù)這個(gè)過程。 改進(jìn)： 隨機(jī)重啟搜索 局域射線搜索與平行k個(gè)隨機(jī)重啟搜索 隨機(jī)射線搜索 隨機(jī)射線搜索不是從候選后繼集合中選擇最好的k個(gè)后繼狀態(tài)，而是按一定的概率隨機(jī)地選擇k個(gè)后繼狀態(tài)。其中選擇給定后繼狀態(tài)的概率是狀態(tài)值的遞增函數(shù)。,遺傳算法（GA）,以進(jìn)化來看待優(yōu)化。 把狀態(tài)看做群體中的個(gè)體。 把Eval看做適應(yīng)性度量。（適應(yīng)度函數(shù)） 讓最不適應(yīng)個(gè)體無繁殖死去。 對(duì)比上一代來說，每代總體上應(yīng)有更好的適應(yīng)，即較高的Eval值。 如果等得足夠長(zhǎng)，則群體應(yīng)進(jìn)化成每個(gè)體都具有高適應(yīng)性，即Eval最大。 遺傳算法的操作主要有：選擇、繁殖、變異。,適應(yīng)度函數(shù),為了對(duì)個(gè)

11、體的適應(yīng)能力進(jìn)行度量，而引入了一個(gè)適應(yīng)度函數(shù)。通過適應(yīng)度函數(shù)來決定染色體的優(yōu)劣程度。對(duì)于優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)，TSP的目標(biāo)是路徑總長(zhǎng)度為最短，自然地，路徑總長(zhǎng)度就可以作為TSP問題的適應(yīng)度函數(shù)。 適應(yīng)度函數(shù)要有效地反映每一個(gè)個(gè)體與群體的最優(yōu)個(gè)體之間的差距。若一個(gè)個(gè)體與群體的最優(yōu)個(gè)體差距較小，則對(duì)應(yīng)的適應(yīng)度函數(shù)之差就較小，否則就較大。,基本GA概述,產(chǎn)生初始群體X=X1, Xp 迭代： 選擇K對(duì)隨機(jī)雙親(X,X) 對(duì)每對(duì)雙親(X,X)： 采用交叉操作來生產(chǎn)后代(Y1,Y2) 對(duì)每個(gè)后代Yi： 用Yi來替換在群體中隨機(jī)選取的組元 以概率來對(duì)Yi實(shí)施一個(gè)隨機(jī)變異。 給出群體中的最佳個(gè)體。

12、 注: 迭代的停止條件不是很明了。 選擇K可能的策略：選擇最佳的rP個(gè)個(gè)體(r1)來繁殖，并去掉所有剩余個(gè)體，即選擇最適應(yīng)的個(gè)體。 一種生產(chǎn)后代的方式：只產(chǎn)生一個(gè)后代。,遺傳算法的實(shí)現(xiàn),構(gòu)形用位串來表示：X= 類比： 串是代表個(gè)體的染色體。 串由基因組成。 基因構(gòu)形被傳給后代。 對(duì)高實(shí)用性有貢獻(xiàn)的基因構(gòu)形趨向于在群體中繼續(xù)生存。 從一個(gè)有P個(gè)構(gòu)形的隨機(jī)群體開始，并實(shí)施下面兩個(gè)操作： 繁殖：選擇2個(gè)雙親，并生產(chǎn)2個(gè)后代。 變異：在一個(gè)隨機(jī)選擇的構(gòu)形中，選擇一個(gè)隨機(jī)入口處，并改變它。,遺傳算法：選擇,通過對(duì)Eval的閥值或固定的群體百分?jǐn)?shù)來去掉最不適應(yīng)的個(gè)體。 優(yōu)先選擇最適應(yīng)（較大Eval）的雙親

13、。 示例：根據(jù)概率分布來隨機(jī)選擇個(gè)體： 示例（比賽）：選擇群體的一個(gè)小隨機(jī)亞組，并選擇其中最適應(yīng)的個(gè)體作為一個(gè)。 實(shí)施最適者生存。 可對(duì)應(yīng)于爬山法的貪婪部分。,遺傳算法：繁殖（交叉）,一個(gè)后代從雙親那里接受部分基因。 通過交叉操作來實(shí)現(xiàn)。,后代：,選擇隨機(jī)交叉點(diǎn)： (此處選擇的交叉 點(diǎn)為5),雙親：,遺傳算法：變異,在一個(gè)構(gòu)形中隨機(jī)改變某一組元 實(shí)現(xiàn)對(duì)遺傳特征的隨機(jī)偏離。 可對(duì)應(yīng)于隨機(jī)行走：引進(jìn)隨機(jī)移動(dòng)來避免小局域極值。,選擇一個(gè)隨機(jī)個(gè)體,選擇一個(gè)隨機(jī)入口,改變此入口,變異就是隨機(jī)地改變位串上某個(gè)位置上的組元。二進(jìn)制表示位串 只有0和1兩種可能。,此處隨機(jī)為6,GA與爬山法,產(chǎn)生初始群體X=X1, Xp 迭代： 選擇K對(duì)隨機(jī)雙親(X,X) 對(duì)每對(duì)雙親(X,X)： 采用交叉操作來生產(chǎn)后代(Y1,Y2) 對(duì)每個(gè)后代Yi： 用Yi來替換在群