組合優(yōu)化問題及算法.pptVIP

,MATHEMATICA MODEL,制作: 龔劬,組合優(yōu)化問題及其算法,-2-,組合最優(yōu)化（combinatorial optimization)是通過對數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，是運籌學(xué)(operations research)中的一個重要分支。所研究的問題涉及信息技術(shù)、經(jīng)濟管理、工業(yè)工程、交通運輸、通信網(wǎng)絡(luò)等領(lǐng)域。該問題可用數(shù)學(xué)模型描述為：,引言,其中D表示有限個點組成的集合。,-3-,1. 0-1背包問題 設(shè)有一個容積為b的背包，n個體積分別為 ai(i=1,2,n),價值分別為ci (i=1,2,n)的物品，如何以最大的價值裝包？,一些例子,-4-,2. 旅行商問題(TSP，traveling salesman problem) 一個商人欲到n個城市推銷商品，每兩個城市i和j之間的距離為dij，如何選擇一條道路使得商人每個城市正好走一遍后回到起點且所走路徑最短。,一些例子,-5-,3.有約束的機器調(diào)度問題(capacitated machine scheduling) n個加工量為di|i=1,2,n的產(chǎn)品在一臺機器上加工，機器在第t個時段的工作能力為ct,求完成所有產(chǎn)品加工所需時段數(shù)最少的調(diào)度方案,一些例子,其中xit,T為決策變量,xit=1表示產(chǎn)品i在第t時段加工,-6-,4. 裝箱問題(bin packing) 如何把n個尺寸不超過1的物品裝入尺寸為1的箱子，并使所用的箱子個數(shù)最少。 5. 二維裝箱問題（平面上的套裁問題） 原料的尺寸大于需求的尺寸，需求的品種尺寸可以不同，最終的目標是在滿足需求的前提下，使邊角余料最小。 6. 車間作業(yè)調(diào)度問題(job shop scheduling) n個工件，J1,Jn在m臺機器M1,M2,Mm上加工。每個工件Ji有ni個工序，Oi1,Oini,第Oij工序的加工時間為pij，必須按工序進行加工且每一工序必須一次加工完成。一臺機器在任何時刻最多只能加工一個產(chǎn)品，一個工件不能同時在兩臺機器上加工，如何安排才能使最后一個完工的工件完工時間最??？,一些例子,-7-,7. 最大截問題(MCP,Max Cut Problem) 8. 圖的頂點著色問題（GCP,Graph Colouring Problem) 9. 獨立集問題（ISP,Independent Set Problem) 10.調(diào)度問題(SCP,Scheduling Problem) 11.劃分問題(PAP,Partition Problem) 12.布局問題（PLP, Placement Problem) 上述問題都是NP-hard問題，目前人們認為它們不存在求解最優(yōu)解的多項式時間算法，大規(guī)模情形只有嘗試用一些近似算法或啟發(fā)式算法求解。,一些例子,-8-,鄰域概念 對于組合優(yōu)化問題(D,F,f),D上的一個映射： N:SD N(S)2D 稱為一個鄰域映射，其中2D表示D的所有子集構(gòu)成的集合，N(S)稱為S的鄰域。 鄰域的構(gòu)造依賴于問題決策變量的表示，鄰域的結(jié)構(gòu)在現(xiàn)代化優(yōu)化算法中起重要作用。,啟發(fā)式算法,-9-,鄰域概念 例如，前面例子2給出的TSP問題模型。由解空間 D=x0,1n(n-1)，可以定義它的一種鄰域為：,啟發(fā)式算法,k為一個正整數(shù)。 TSP問題解的另一種表示法為 D=S=(i1,i2,in)是1,2,n的一個排列,-10-,鄰域概念,啟發(fā)式算法,TSP問題解的另一種表示法為 D=S=(i1,i2,in)是1,2,n的一個排列 可以定義它的鄰域映射為2-opt，即S中的兩個元素對換。 如4個城市的TSP問題，當(dāng)S=(1,2,3,4)時，N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3). 類似可定義k-opt(k2),-11-,局部最優(yōu)與全局最優(yōu),啟發(fā)式算法,若s*滿足 f(s*)()f(s),其中sN(s*)F, 則稱s*為f在F上的局部(local)最?。ㄗ畲螅┙狻?若s*滿足 f(s*)()f(s),其中sF, 則稱s*為f在F上的全局(global)最?。ㄗ畲螅┙?。,-12-,啟發(fā)式算法,-13-,啟發(fā)式算法,-14-,背包問題的貪婪算法 1）將物品以ci/ai（單位體積的價值）由大到小的順序排列，不妨把排列記為1,2,n,k:=1; 2）若 ，則xk=1;否則xk=0,k:=k+1; 3) 當(dāng)k=n+1時，停止；否則，轉(zhuǎn)2). (x1,x2,xn)為貪婪算法所得解，單位體積的價值越大越先放入是貪婪算法的原則。,啟發(fā)式算法,-15-,簡單的鄰域搜索算法 給定組合優(yōu)化問題，假設(shè)其鄰域結(jié)構(gòu)已確定，算法為 1）任選一個初始解s0F; 2) 在N(s0)中按某一規(guī)則選一s；若f(s)f(s0),則s0s；否則，N(s0) N(s0)-s; 3) 若N(s0)=,停止；否則，返回2).,啟發(fā)式算法,-16-,算法停止時得到點的性質(zhì)依賴算法初始解的選取、鄰域的結(jié)構(gòu). 只要選好初始點，就一定可以求到最優(yōu)解。對NP-hard的組合最優(yōu)化問題，確定這樣的初始點非常困難。如何選初始點和如何跳出局部最優(yōu)值點以達到全局最優(yōu)點是許多算法的關(guān)鍵。,啟發(fā)式算法,-17-,啟發(fā)式算法的類型,1.一步算法（構(gòu)造型算法） 2.改進型算法 3.數(shù)學(xué)規(guī)劃算法 4.解空間松弛算法 5.現(xiàn)代化優(yōu)化算法 禁忌搜索（tabu search),模擬退火（simulated annealing),遺傳算法（genetic algorithms),人工神經(jīng)網(wǎng)絡(luò)(neural networks),螞蟻算法(ant algorithm).,-18-,模擬退火算法,1982年，Kirkpatric等將退火思想引入組合優(yōu)化領(lǐng)域，提出一種解大規(guī)模組合優(yōu)化問題，特別是NP-hard的組合優(yōu)化問題的有效近似算法模擬退火算法。它源于對固體退火過程的模擬；采用Metropolis接受準則；并用一組稱為冷卻進度表的參數(shù)控制算法進程，使算法在多項式時間里給出一個近似最優(yōu)解。 固體退火過程的物理圖象和統(tǒng)計性質(zhì)是模擬退火算法的物理背景；Metropolis接受準則使算法跳離局部最優(yōu)的“陷阱”，而冷卻進度表的合理選擇是算法應(yīng)用的前提。,-19-,模擬退火算法,模擬退火算法的思路：從選定的初始解開始，在借助于控制參數(shù)t遞減時產(chǎn)生的一系列Markov鏈中，利用一個新解產(chǎn)生方案和接受準則，重復(fù)進行包括“產(chǎn)生新解-計算目標函數(shù)差-判斷是否接受新解-接受（或舍棄）新解”這四個任務(wù)的試驗，不斷對當(dāng)前解迭代，使目標函數(shù)逼近最優(yōu)。,-20-,模擬退火算法,任選一個初始解x0,xix0,k 0,t0 tmax(初始溫度）,LkL0(內(nèi)循環(huán)次數(shù)初值）； 2) l0; 3) 若lLk，則到4）；否則，從鄰域N(xi)中隨機選一xj,計算fij=f(xj)-f(xi); ll+1;若fij0，則xixj; 否則,若exp(- fij/tk)random（0,1)）時，xixj；重復(fù)3）； 4）tk+1T(tk);k k+1；計算Lk，若滿足停止條件，終止計算，否則，回到2).,-21-,模擬退火算法的漸近收斂性,已證明，模擬退火算法以1的概率收斂到整體最優(yōu)解集，但漸近收斂到最優(yōu)解集須經(jīng)歷無限多次變換。 對最優(yōu)解任意近似的逼近，對多數(shù)組合優(yōu)化問題都導(dǎo)致比解空間規(guī)模大的變換數(shù)，從而導(dǎo)致算法的指數(shù)時間執(zhí)行。 解決辦法：犧牲保證得到最優(yōu)解為代價，在多項式時間里，逼近模擬退火算法的漸近收斂狀態(tài)，返回一個近似最優(yōu)解。,-22-,模擬退火算法應(yīng)用的一般要求,數(shù)學(xué)模型 解空間、目標函數(shù)和初始解 2）新解的產(chǎn)生和接受機制 新解產(chǎn)生:當(dāng)前解經(jīng)簡單變換產(chǎn)生新解（決定了當(dāng)前解的鄰域結(jié)構(gòu)），如對當(dāng)前解的全部或部分元素進行置換、互換或反演等。 Metropolis接受準則: 3）冷卻進度表的設(shè)定,-23-,冷卻進度表,冷卻進度表是一組控制算法進程的參數(shù)，它包括： 1.初始溫度t0 =tmax 2.溫度衰減函數(shù)T(t) 3.Markov鏈的長度Lk 4.終止溫度tf（停止準則） 。,-24-,冷卻進度表,雖然已經(jīng)證明模擬退火算法在一定條件下的漸近收斂性。但這并不意味著任意冷卻進度表都能確保算法收斂，不合理的冷卻進度表會使算法在某些解間“振蕩”而不能收斂于某一近似解。 模擬退火算法的最終解質(zhì)量和CPU時間呈反向關(guān)系，很難兩全其美，妥善解決辦法只有：折中，即在合理的CPU時間里盡量提高最終解的質(zhì)量。這涉及到冷卻進度表所有參數(shù)的合理選取。,-25-,冷卻進度表的參數(shù)設(shè)置,1.初始溫度t0 的選取 t0 要取得足夠大，Johnson等建議通過計算若干次隨機變換目標函數(shù)平均增量的方法來確定t0的值。,其中， 為上述平均增量， 為初始接受率，一般取0.81之間的數(shù)。,-26-,冷卻進度表的參數(shù)設(shè)置,-27-,冷卻進度表的參數(shù)設(shè)置,3.Markov鏈的長度Lk的選取 1）固定長度 Lk通常取為問題規(guī)模 n的一個多項式函數(shù)。如，Kirkpatric等 Lk=n或100n, Aars等 Lk=鄰域規(guī)模 2）由接受和拒絕的比率來控制Lk 當(dāng)溫度很高時，Lk應(yīng)盡量小，隨著溫度的漸漸下降，Lk逐步增大。,-28-,冷卻進度表的參數(shù)設(shè)置,3.Markov鏈的長度Lk的選取 2）由接受和拒絕的比率來控制Lk 實現(xiàn)的第一種方法是：給定一個充分大的長度上限U和一個接受次數(shù)指標R,當(dāng)接受次數(shù)等于R時，此溫度不再迭代而使溫度下降。 實現(xiàn)的第二種方法是：給定一個接受比率指標R,長度上限U和下限L,當(dāng)?shù)螖?shù)超過L時，若接受次數(shù)與迭代次數(shù)的比率不小于R時，此溫度不再迭代而使溫度下降，否則，一直迭代到上限步數(shù)U。,-29-,冷卻進度表的參數(shù)設(shè)置,4.終止溫度tf（停止準則）的選取 1）零度法 2）循環(huán)總數(shù)控制法 3）基于不改進規(guī)則的控制法 4）接受概率控制法 3）和4）的實現(xiàn)：在一個溫度和給定的迭代次數(shù)內(nèi)，沒有改進當(dāng)前的局部最優(yōu)解或接受概率都小于一個給定的比較小的數(shù)f,則停止運算. 5）鄰域法 當(dāng) 時，停止計算。f0,f1分別為一個鄰域內(nèi)的局部最優(yōu)和次最優(yōu)，N為鄰域的大小。,-30-,模擬退火算法的優(yōu)點,高效、健壯、通用、靈活 1）高效性 與局部搜索算法相比，模擬退火算法可望在較短時間里求得更優(yōu)近似解；允許任意選取初始解，且能得出較優(yōu)近似解，因此應(yīng)用該算法解組合優(yōu)化問題的前期工作量大大減少。 2）健壯性 該算法的實驗性能不因組合優(yōu)化問題實例的不同而蛻變；解的質(zhì)量和CPU時間均隨n的增大而趨于穩(wěn)定，且不受初始解和隨機數(shù)序列的影響。,-31-,模擬退火算法的優(yōu)點,3）通用性和靈活性 該算法能應(yīng)用于多種組合優(yōu)化問題，為一個問題編制的程序可有效地用于其他問題。解的質(zhì)量與CPU時間呈反向關(guān)系，針對不同的實例以及不同的解質(zhì)要求，適當(dāng)調(diào)整冷卻進度表的參數(shù)值可使算法執(zhí)行獲得最佳的解時關(guān)系。,-32-,模擬退火算法的不足和改進途徑,主要不足是：返回一個高質(zhì)近似解的時間花費較多。有如下途徑改進算法的實驗性能、提高算法的執(zhí)行效率。 1）增加一個記憶器 給算法增加一個記憶器，使之能記住搜索過程中遇到過的最好結(jié)果，當(dāng)結(jié)束時，