大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài)

1、大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),1,現(xiàn)代優(yōu)化技術(shù),第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),2,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,構(gòu)筑法的改進(jìn)形 （貪婪算法的改進(jìn)形） 改善法的改進(jìn)形 （局部探索法的改進(jìn)形）,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),3,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,構(gòu)筑法（貪婪算法）的局限性,構(gòu)筑法（貪婪算法）在任何給定的時(shí)點(diǎn)都采取當(dāng)時(shí)的最佳移動(dòng)，但最終的整體結(jié)果卻不一定是最佳的。其問(wèn)題在于現(xiàn)時(shí)點(diǎn)局部是最好的，卻不一定是后面所需要的。如果在探索的途中有一個(gè)評(píng)估函數(shù)，能提供現(xiàn)在及未來(lái)的一些信息，就可以改善

2、、避免短期的貪婪行為。,改進(jìn)的貪婪法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),4,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,最佳優(yōu)先（best-first）探索：A*算法,深度優(yōu)先策略(deep-first): 以一種任意的模式往盡可能深的空間探索。 廣度優(yōu)先策略(wide-first): 探索完某一層次中所有節(jié)點(diǎn)后才進(jìn)入下一層次。 例：TSP的探索樹(shù),兩種傳統(tǒng)的探索策略：,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),5,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,兩種傳統(tǒng)的探索策略：例,B,R,L,R,B,B,L,R,L,B,R,L,B,L,R,M,B,R,M,R,B,B,M,R,M,B,R,M,

3、B,B,R,L,B,L,M,L,B,B,M,L,M,B,L,M,B,M,L,R,R,L,M,L,R,R,M,L,M,R,L,M,R,M,L,B,Z,3047,3047,3407,3485,3485,3596,3297,3497,3407,3825,4034,3256,3297,3784,4034,3674,3825,3584,3297,3674,3784,3497,3256,3596,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),6,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,最佳優(yōu)先（best-first）探索：,最佳優(yōu)先探索使用啟發(fā)性規(guī)則，在探索過(guò)程中給每個(gè)已經(jīng)構(gòu)造的部分解q提供一個(gè)性能值來(lái)輔助下

4、一個(gè)節(jié)點(diǎn)的選擇、引導(dǎo)進(jìn)一步的探索。這一性能值包括： 1）已作決策的性能值-c(q) 2）有待決策的潛在性能值-h(q) 一個(gè)部分解q的性能評(píng)價(jià)函數(shù)為： eval (q)=c(q)+h(q),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),7,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,最佳優(yōu)先（best-first）探索：,評(píng)估函數(shù)的確定 c(q): 已構(gòu)造部分解的性能值： 易于評(píng)估，甚至可以得到精確的度量，如TSP的部分解性能就是以得到的部分巡回路的長(zhǎng)度。 h(q): 現(xiàn)有部分解的潛在性能值： 從現(xiàn)時(shí)點(diǎn)出發(fā)到達(dá)目標(biāo)所需的剩余代價(jià)-難以評(píng)估,用到達(dá)目標(biāo)所需剩余代價(jià)的最小估算值 h 來(lái)代替,如果 h 是有

5、上界的 ，即 h(q)=h* ，可保證不漏掉全局最優(yōu)解,A*算法能夠取得全局最優(yōu)解的保證,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),8,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,最佳優(yōu)先（best-first）探索：A*算法,Procedure best-first(v) Begin 訪問(wèn)v for 每一個(gè)可用節(jié)點(diǎn) w， do 給 w 指定一個(gè)啟發(fā)值 q 最好的可用節(jié)點(diǎn) best-first (q) End,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),9,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,改善法（局部探索法）的改進(jìn)形,改善法的探索路徑 改善法的局限性 改善法的改進(jìn)形,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)

6、第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),10,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,近鄰與局部最優(yōu)解（概念図）,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),11,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,鄰域解一臺(tái)機(jī)器的交貨期最小遲延排序問(wèn)題,工件的集合 1,2,3,4,可行解的集合 從1,2,3,4中構(gòu)成4!種可能的排序,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),12,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,目標(biāo)函數(shù)：一臺(tái)機(jī)器的交貨期最小遲延排序問(wèn)題,目標(biāo)函數(shù)：交貨期遲延的合計(jì)（最小化）,可行解（順列）1234 所對(duì)應(yīng)的目標(biāo)函數(shù),J1,=6,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),13,傳統(tǒng)啟發(fā)式

7、算法之改進(jìn)形,鄰域解一臺(tái)機(jī)器的交貨期最小遲延排序問(wèn)題,近鄰兩個(gè)相鄰工件交換后得到的排序,可行解 1 2 3 4 的近鄰,1 2 4 3,1 3 2 4,2 1 3 4,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),14,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,鄰域解圖：一臺(tái)機(jī)器的交貨期最小遲延排序問(wèn)題,1234,1243,點(diǎn)與解一一對(duì)應(yīng),6,6,7,7,5,4,3,5,7,7,10,8,7,8,6,6,8,5,5,4,6,10,目標(biāo)函數(shù)值,2134,1324,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),15,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,局部探索法的探索路徑,鄰域解圖的枝 (x,y): f

8、(x)f(y),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),16,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,局部探索法的局限性,目標(biāo)函數(shù),難以跳離局部最優(yōu)解,3,4,5,6,7,8,9,10,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),17,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,局部最優(yōu)解的脫出,局部探索法的探索 在局部?jī)?yōu)解處停止 有必要從局部最優(yōu)解處脫出 改變初期解，再次應(yīng)用局部探索法 (multiple start local search，iterated local search) 可變近鄰局部探索法 (variable neighborhood local search) 隨機(jī)局部探索法

9、 (接受惡化解) （stochastic local search） 誘導(dǎo)局部探索法 (guided local search),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),18,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形1,Multiple Start Local Search iterated local search,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),19,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search 的改進(jìn)形1：,Iterated local Search (迭代局部 探索法),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)

10、形態(tài),20,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形1,Iterated local search (迭代局部探索法)的特點(diǎn) 內(nèi)循環(huán)總是返回一個(gè)局部最優(yōu)解； 外循環(huán)通過(guò)從一個(gè)新的位置開(kāi)始另一次新的探索，來(lái)試圖跳離前一個(gè)局部最優(yōu)解； 總共嘗試MAX次（終止條件）。,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),21,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形2,可變近鄰法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),22,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形2,從局部最優(yōu)解處，漸漸擴(kuò)大近鄰的探索范圍，以從現(xiàn)行局部最優(yōu)解處

11、脫出。,可變近鄰局部探索法Variable neighborhood local search,即：,滿足：,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),23,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形2,Variable neighborhood local search algorithm,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),24,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形3,(概率接受惡化解),概率接受 惡化解,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),25,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的

12、改進(jìn)形3,Stochastic local search 隨機(jī)局部探索法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),26,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形3,Stochastic local search 隨機(jī)局部探索法的特點(diǎn),差,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),27,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,關(guān)于接受概率函數(shù),Stochastic local search 隨機(jī)局部探索法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),28,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,關(guān)于接受概率p 與溫度T的關(guān)系,Stochastic local se

13、arch 隨機(jī)局部探索法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),29,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,關(guān)于接受概率與新點(diǎn)評(píng)價(jià)值的關(guān)系,Stochastic local search 隨機(jī)局部探索法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),30,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形3,問(wèn)題： 上述隨機(jī)局部探索法的接受概率是針對(duì)目標(biāo)函數(shù)為求最大值的場(chǎng)合，如為求最小值的場(chǎng)合，如何設(shè)計(jì)其接受概率？并寫(xiě)出相應(yīng)的算法。,Stochastic local search 隨機(jī)局部探索法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),31,傳統(tǒng)啟發(fā)式

14、算法之改進(jìn)形,Local Search的改進(jìn)形4 誘導(dǎo)局部探索法 Guided Local Search(GLS),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),32,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形4 誘導(dǎo)局部探索法 Guided Local Search(GLS),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),33,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形4 誘導(dǎo)局部探索法 Guided Local Search(GLS),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第7講：傳統(tǒng)啟發(fā)式算法之改進(jìn)形態(tài),34,傳統(tǒng)啟發(fā)式算法之改進(jìn)形,Local Search的改進(jìn)形4 誘導(dǎo)局部探索法 Guided Local Search(GLS),Penalty (long term memory) p: U R,Modified Cost Function