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

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