組合優(yōu)化問(wèn)題及算法

MATHEMATICAMODEL制作:龔劬組合優(yōu)化問(wèn)題及其算法1組合最優(yōu)化（combinatorialoptimization)是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，是運(yùn)籌學(xué)(operationsresearch)中的一個(gè)重要分支。所研究的問(wèn)題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通信網(wǎng)絡(luò)等領(lǐng)域。該問(wèn)題可用數(shù)學(xué)模型描述為：引言其中D表示有限個(gè)點(diǎn)組成的集合。21.0-1背包問(wèn)題設(shè)有一個(gè)容積為b的背包，n個(gè)體積分別為ai(i=1,2,…,n),價(jià)值分別為ci(i=1,2,…,n)的物品，如何以最大的價(jià)值裝包？一些例子32.旅行商問(wèn)題(TSP，travelingsalesmanproblem)一個(gè)商人欲到n個(gè)城市推銷(xiāo)商品，每?jī)蓚€(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市正好走一遍后回到起點(diǎn)且所走路徑最短。一些例子4

3.有約束的機(jī)器調(diào)度問(wèn)題(capacitatedmachinescheduling)n個(gè)加工量為{di|i=1,2,…,n}的產(chǎn)品在一臺(tái)機(jī)器上加工，機(jī)器在第t個(gè)時(shí)段的工作能力為ct,求完成所有產(chǎn)品加工所需時(shí)段數(shù)最少的調(diào)度方案一些例子

其中xit,T為決策變量,xit=1表示產(chǎn)品i在第t時(shí)段加工5

4.裝箱問(wèn)題(binpacking)如何把n個(gè)尺寸不超過(guò)1的物品裝入尺寸為1的箱子，并使所用的箱子個(gè)數(shù)最少。5.二維裝箱問(wèn)題（平面上的套裁問(wèn)題）原料的尺寸大于需求的尺寸，需求的品種尺寸可以不同，最終的目標(biāo)是在滿(mǎn)足需求的前提下，使邊角余料最小。6.車(chē)間作業(yè)調(diào)度問(wèn)題(jobshopscheduling)n個(gè)工件，J1,…,Jn在m臺(tái)機(jī)器M1,M2,…,Mm上加工。每個(gè)工件Ji有ni個(gè)工序，Oi1,…,Oini,第Oij工序的加工時(shí)間為pij，必須按工序進(jìn)行加工且每一工序必須一次加工完成。一臺(tái)機(jī)器在任何時(shí)刻最多只能加工一個(gè)產(chǎn)品，一個(gè)工件不能同時(shí)在兩臺(tái)機(jī)器上加工，如何安排才能使最后一個(gè)完工的工件完工時(shí)間最??？一些例子6

7.最大截問(wèn)題(MCP,MaxCutProblem)8.圖的頂點(diǎn)著色問(wèn)題（GCP,GraphColouringProblem)9.獨(dú)立集問(wèn)題（ISP,IndependentSetProblem)10.調(diào)度問(wèn)題(SCP,SchedulingProblem)11.劃分問(wèn)題(PAP,PartitionProblem)12.布局問(wèn)題（PLP,PlacementProblem)……上述問(wèn)題都是NP-hard問(wèn)題，目前人們認(rèn)為它們不存在求解最優(yōu)解的多項(xiàng)式時(shí)間算法，大規(guī)模情形只有嘗試用一些近似算法或啟發(fā)式算法求解。一些例子7鄰域概念

對(duì)于組合優(yōu)化問(wèn)題(D,F,f),D上的一個(gè)映射：N:SDN(S)2D稱(chēng)為一個(gè)鄰域映射，其中2D表示D的所有子集構(gòu)成的集合，N(S)稱(chēng)為S的鄰域。鄰域的構(gòu)造依賴(lài)于問(wèn)題決策變量的表示，鄰域的結(jié)構(gòu)在現(xiàn)代化優(yōu)化算法中起重要作用。啟發(fā)式算法8鄰域概念例如，前面例子2給出的TSP問(wèn)題模型。由解空間D={x{0,1}n(n-1)}，可以定義它的一種鄰域?yàn)椋簡(jiǎn)l(fā)式算法k為一個(gè)正整數(shù)。TSP問(wèn)題解的另一種表示法為D={S=(i1,i2,…,in)是1,2,…,n的一個(gè)排列}9鄰域概念啟發(fā)式算法TSP問(wèn)題解的另一種表示法為D={S=(i1,i2,…,in)是1,2,…,n的一個(gè)排列}可以定義它的鄰域映射為2-opt，即S中的兩個(gè)元素對(duì)換。如4個(gè)城市的TSP問(wèn)題，當(dāng)S=(1,2,3,4)時(shí)，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)}.類(lèi)似可定義k-opt(k2)10局部最優(yōu)與全局最優(yōu)啟發(fā)式算法

若s*滿(mǎn)足f(s*)()f(s),其中sN(s*)F,則稱(chēng)s*為f在F上的局部(local)最?。ㄗ畲螅┙狻Ｈ魋*滿(mǎn)足f(s*)()f(s),其中sF,則稱(chēng)s*為f在F上的全局(global)最?。ㄗ畲螅┙狻?1

啟發(fā)式算法定義

一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（計(jì)算時(shí)間、占用空間等）下給出待解決問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解，該解與最優(yōu)解的偏離程度不一定能預(yù)計(jì)。啟發(fā)式算法是一種技術(shù)，使在可接受的計(jì)算開(kāi)銷(xiāo)內(nèi)尋找最好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至多數(shù)情況下，無(wú)法給出所得解同最優(yōu)解的近似程度。啟發(fā)式算法12近似算法定義

記問(wèn)題A的任何一個(gè)實(shí)例I的最優(yōu)解和啟發(fā)式算法H解的目標(biāo)值分別為zopt(I)和zH(I),若對(duì)某個(gè)正數(shù)0，有|zH(I)-zopt(I)|

|zopt(I)|，IA則稱(chēng)H是A的近似算法。啟發(fā)式算法13

背包問(wèn)題的貪婪算法1）將物品以ci/ai（單位體積的價(jià)值）由大到小的順序排列，不妨把排列記為{1,2,…,n},k:=1;2）若，則xk=1;否則xk=0,k:=k+1;3)當(dāng)k=n+1時(shí)，停止；否則，轉(zhuǎn)2).(x1,x2,…,xn)為貪婪算法所得解，單位體積的價(jià)值越大越先放入是貪婪算法的原則。啟發(fā)式算法14

簡(jiǎn)單的鄰域搜索算法給定組合優(yōu)化問(wèn)題，假設(shè)其鄰域結(jié)構(gòu)已確定，算法為1）任選一個(gè)初始解s0F;2)在N(s0)中按某一規(guī)則選一s；若f(s)<f(s0),則s0s；否則，N(s0)N(s0)-s;3)若N(s0)=,停止；否則，返回2).啟發(fā)式算法15算法停止時(shí)得到點(diǎn)的性質(zhì)依賴(lài)算法初始解的選取、鄰域的結(jié)構(gòu).只要選好初始點(diǎn)，就一定可以求到最優(yōu)解。對(duì)NP-hard的組合最優(yōu)化問(wèn)題，確定這樣的初始點(diǎn)非常困難。如何選初始點(diǎn)和如何跳出局部最優(yōu)值點(diǎn)以達(dá)到全局最優(yōu)點(diǎn)是許多算法的關(guān)鍵。啟發(fā)式算法16啟發(fā)式算法的類(lèi)型1.一步算法（構(gòu)造型算法）2.改進(jìn)型算法3.數(shù)學(xué)規(guī)劃算法4.解空間松弛算法5.現(xiàn)代化優(yōu)化算法禁忌搜索（tabusearch),模擬退火（simulatedannealing),遺傳算法（geneticalgorithms),人工神經(jīng)網(wǎng)絡(luò)(neuralnetworks),螞蟻算法(antalgorithm).17模擬退火算法1982年，Kirkpatric等將退火思想引入組合優(yōu)化領(lǐng)域，提出一種解大規(guī)模組合優(yōu)化問(wèn)題，特別是NP-hard的組合優(yōu)化問(wèn)題的有效近似算法——模擬退火算法。它源于對(duì)固體退火過(guò)程的模擬；采用Metropolis接受準(zhǔn)則；并用一組稱(chēng)為冷卻進(jìn)度表的參數(shù)控制算法進(jìn)程，使算法在多項(xiàng)式時(shí)間里給出一個(gè)近似最優(yōu)解。固體退火過(guò)程的物理圖象和統(tǒng)計(jì)性質(zhì)是模擬退火算法的物理背景；Metropolis接受準(zhǔn)則使算法跳離局部最優(yōu)的“陷阱”，而冷卻進(jìn)度表的合理選擇是算法應(yīng)用的前提。18模擬退火算法模擬退火算法的思路：從選定的初始解開(kāi)始，在借助于控制參數(shù)t遞減時(shí)產(chǎn)生的一系列Markov鏈中，利用一個(gè)新解產(chǎn)生方案和接受準(zhǔn)則，重復(fù)進(jìn)行包括“產(chǎn)生新解-計(jì)算目標(biāo)函數(shù)差-判斷是否接受新解-接受（或舍棄）新解”這四個(gè)任務(wù)的試驗(yàn)，不斷對(duì)當(dāng)前解迭代，使目標(biāo)函數(shù)逼近最優(yōu)。

19模擬退火算法任選一個(gè)初始解x0,xix0,k0,t0

tmax(初始溫度）,LkL0(內(nèi)循環(huán)次數(shù)初值）；2)l0;3)若l>Lk，則到4）；否則，從鄰域N(xi)中隨機(jī)選一xj,計(jì)算fij=f(xj)-f(xi);ll+1;若fij0，則xixj;否則,若exp(-

fij/tk)>random（[0,1)）時(shí)，xixj；重復(fù)3）；4）tk+1

T(tk);kk+1；計(jì)算Lk，若滿(mǎn)足停止條件，終止計(jì)算，否則，回到2).20模擬退火算法的漸近收斂性已證明，模擬退火算法以1的概率收斂到整體最優(yōu)解集，但漸近收斂到最優(yōu)解集須經(jīng)歷無(wú)限多次變換。對(duì)最優(yōu)解任意近似的逼近，對(duì)多數(shù)組合優(yōu)化問(wèn)題都導(dǎo)致比解空間規(guī)模大的變換數(shù)，從而導(dǎo)致算法的指數(shù)時(shí)間執(zhí)行。解決辦法：犧牲保證得到最優(yōu)解為代價(jià)，在多項(xiàng)式時(shí)間里，逼近模擬退火算法的漸近收斂狀態(tài)，返回一個(gè)近似最優(yōu)解。21模擬退火算法應(yīng)用的一般要求數(shù)學(xué)模型解空間、目標(biāo)函數(shù)和初始解2）新解的產(chǎn)生和接受機(jī)制新解產(chǎn)生:當(dāng)前解經(jīng)簡(jiǎn)單變換產(chǎn)生新解（決定了當(dāng)前解的鄰域結(jié)構(gòu)），如對(duì)當(dāng)前解的全部或部分元素進(jìn)行置換、互換或反演等。Metropolis接受準(zhǔn)則:

3）冷卻進(jìn)度表的設(shè)定22冷卻進(jìn)度表冷卻進(jìn)度表是一組控制算法進(jìn)程的參數(shù)，它包括：1.初始溫度t0

=tmax2.溫度衰減函數(shù)T(t)3.Markov鏈的長(zhǎng)度