大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法

1、大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,1,現(xiàn)代優(yōu)化技術(shù),第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,2,主要內(nèi)容,啟發(fā)式算法含義 啟發(fā)式算法的宿命論 啟發(fā)式算法求解問(wèn)題的一般程序 啟發(fā)式算法策略 幾種典型的構(gòu)筑法 （1）背包問(wèn)題的構(gòu)筑法 （2）旅行商問(wèn)題的構(gòu)筑法 （3）配送問(wèn)題的構(gòu)筑法,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,3,啟發(fā)式算法（heuristics）,含義：?jiǎn)l(fā)性算法是一種優(yōu)化技術(shù)，可以在可接 受計(jì)算時(shí)間下給出待求解問(wèn)題每一個(gè)實(shí)例的近似最優(yōu)解，但無(wú)法保證所得解的精確度。 目標(biāo)：求得“滿意解”，而非最優(yōu)解

2、 1）精確解無(wú)法找到； 2）過(guò)高精度的解無(wú)實(shí)際意義； 3）求最優(yōu)解代價(jià)太高。,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,4,啟發(fā)式方法的概念圖,全局最優(yōu)解,可行解集合,目標(biāo)函數(shù),局部最優(yōu)解,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,5,啟發(fā)式算法的宿命論例：Traveling Salesman Problem (TSP),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,6,啟發(fā)式算法的宿命論：計(jì)算復(fù)雜性例：Traveling Salesman Problem (TSP),個(gè)客戶的TSP問(wèn)題 ( 30! 1030 ) 高性能計(jì)算機(jī)求解最優(yōu)解需要日 (n-1)(

3、n-2)321=(n-1)! 1 PIPS (Peta Instruction Per Second)=1015 30!/1015 （秒） 1015 （秒） 105 （世紀(jì)） （窮舉法）,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,7,啟發(fā)式算法的宿命論：?jiǎn)栴}復(fù)雜性例：TSP的各種擴(kuò)展問(wèn)題及其現(xiàn)實(shí)應(yīng)用,VRP問(wèn)題:(vehicle routing problems） VRPTW問(wèn)題: （vehicle routing problem with time windows） VRPPD問(wèn)題： (VRP with pickup 相反，如wikw*, 則 zik=0,Step 3. 如 k

4、n-1, 則 k=k+1, 返回 step 2. 如 k=n, 輸出最終解z.,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,20,構(gòu)筑法,nearest neighbor for TSP,TSP的最近近鄰法：從某一個(gè)客戶出發(fā)，選擇尚未訪問(wèn)的客戶中距現(xiàn)在的客戶最近的作為下一個(gè)要訪問(wèn)的客戶，反復(fù)這一步驟，直到所有訪問(wèn)完畢。,V: 客戶的集合 SV: 尚未訪問(wèn)的客戶的集合,構(gòu)筑中的部分巡回路,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,21,構(gòu)筑法,nearest neighbor 法圖示,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,22,構(gòu)筑法,Nearest

5、neighbor algorithm for TSP,Step 1. 令 k=1，S=V. 從 iV 任選一客戶,Step 2. 設(shè),Step 3. 令 返回 step 2.,此時(shí)若,則輸出巡回路,探索終了。,以及,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,23,構(gòu)筑法,Random nearest neighbor 法,將對(duì)目標(biāo)函數(shù)值的貢獻(xiàn)度（如巡回路增加值）作為評(píng)價(jià)指標(biāo)，以評(píng)價(jià)值從大到小的順序（距現(xiàn)行出發(fā)點(diǎn)從近到遠(yuǎn)的順序），作為幾個(gè)可行的部分解，然后，從中隨機(jī)選取一個(gè)作為下一個(gè)出發(fā)點(diǎn)，,反復(fù)這一步驟直到得到完整的可行解。 與單純的nearest neighbor 法對(duì)比，加入

6、了隨機(jī)選擇性，使解具有多樣性。,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,24,構(gòu)筑法,Random nearest neighbor 法,Random nearest 法圖示,1,2,a,b,c,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,25,構(gòu)筑法,Random nearest neighbor algorithm for TSP,Step 1. 令 k=1，S=V. 從 iV 任選一客戶,Step 2. 設(shè),Step 3. 對(duì)于現(xiàn)在的 i, 從集合S中按dij的從小到大的順序選擇候補(bǔ)客戶 j, 其集合為 . Step 4. 從集合 中隨機(jī)選取一個(gè) ，作為 i

7、, , 返回 step 2.,此時(shí)若,則輸出巡回路,探索終了。,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,26,構(gòu)筑法,Multiple fragment method for TSP,Multiple fragment method 多部分巡回路法 思路：首先生成多個(gè)部分巡回路（subtour)， 然后連接這些部分，形成完整的巡回路。 條件：在生成部分巡回路的過(guò)程中， 1.與各都市相連的枝的個(gè)數(shù)不超過(guò)2個(gè)； 2.不能出現(xiàn)部分閉巡回路。 過(guò)程：在滿足上述2條件的前提下，按dij 的從小到大的順序多個(gè)生成部分巡回路，最后形成完整的巡回路。,Greedy 性,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)

8、第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,27,構(gòu)筑法,Closed subtours,部分閉巡回路（closed subtour） 圖示例,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,28,構(gòu)筑法,多部分巡回路算法用符號(hào),點(diǎn)（dot）：各個(gè)都市 枝 (edge)：連接兩個(gè)客戶的部分巡回路 通路 (path)：非閉的部分巡回路 現(xiàn)階段部分巡回路中包含的枝的集合 現(xiàn)階段部分巡回路中尚未包含的枝的集合 當(dāng)中與客戶i相連接的枝的個(gè)數(shù) 通路一端的端點(diǎn)i所對(duì)應(yīng)的另一端端點(diǎn)（客戶）號(hào)。,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,29,構(gòu)筑法,多部分巡回路算法（1）,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)

9、第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,30,構(gòu)筑法,多部分巡回路算法（2）,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,31,構(gòu)筑法,多部分巡回路法的實(shí)行例,(1).途中的多個(gè)部分巡回路,(2). 最終得到的完整巡回路,1,2,3,4,5,6,7,8,9,10,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,32,構(gòu)筑法,VRP (vehicle routing problem),配送 中心,顧客,總費(fèi)用或總距離最小化 route內(nèi)的顧客需要量不能超過(guò)車的載重量 工作時(shí)間的上限 不能超過(guò),大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,33,構(gòu)筑法,配送 中心,配送 中心

10、,Saving value Sij 的計(jì)算 （移動(dòng)費(fèi)用対稱 cij=cji）,所有客戶都從庫(kù)存點(diǎn)的 之間的直行運(yùn)輸開(kāi)始！,根據(jù)客戶i,j連續(xù)運(yùn)輸時(shí)的節(jié)約量 （saving value）的從大到小順序來(lái)連續(xù)運(yùn)輸！,Saving algorithm for VRP,大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第5講：傳統(tǒng)啟發(fā)式算法之構(gòu)筑法,34,構(gòu)筑法,Saving algorithm for VRP,Step1. 計(jì)算所有的顧客對(duì)（ i,j）的saving value Sij Step2. saving value Sij的從大到小的順序重新排列 得到新的顧客對(duì)順序list Step3. 重復(fù)以下的操作直到list變空為止： (1). 按list的順序，調(diào)查將顧客 i,j 間直接運(yùn)輸?shù)膶g行可能性 (2).如果這種実行可能性存在，則連接 i與 j。 (3).如果不存在這