組合最優(yōu)化問(wèn)題

參考書(shū):１．《現(xiàn)代優(yōu)化計(jì)算方法》—邢文訓(xùn)謝金星２．《非數(shù)值并行算法第一冊(cè)—模擬退火算法》—康立山謝云等

組合最優(yōu)化是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，該問(wèn)題可用數(shù)學(xué)模型描述為：其中，f(x)為目標(biāo)函數(shù)，

g(x)為約束函數(shù)，x為決策變量，

D表示有限個(gè)點(diǎn)組成的集合．1.1組合最優(yōu)化問(wèn)題一個(gè)組合最優(yōu)化問(wèn)題可用三參數(shù)(D,F,f)表示，其中D表示決策變量的定義域，F(xiàn)表示可行解集合F

x

x

D,g(x)0，F(xiàn)中的任何一個(gè)元素稱為該問(wèn)題的可行解，f表示目標(biāo)函數(shù)．滿足f(x

)minf(x)x

F

的可行解x

稱為該問(wèn)題的最優(yōu)解．組合最優(yōu)化的特點(diǎn)是可行解集合為有限點(diǎn)集．例1.1

o-1背包問(wèn)題(knapsackproblem)設(shè)有一個(gè)容積為b的背包，n個(gè)體積分別為ai(i1,2,,n)，價(jià)值分別為ci(i1,2,,n)的物品，如何以最大的價(jià)值裝包？這個(gè)問(wèn)題稱為o-1背包問(wèn)題．用數(shù)學(xué)模型表示為：其中xi

1表示裝第i個(gè)物品，xi

0表示不裝．此時(shí)，D

0,1n，F(xiàn)為D中滿足(1.2)的可行解集．例1.2

旅行商問(wèn)題(TSP,travelingsalesmanproblem)當(dāng)

dij=dji,

i,j

時(shí)，稱為對(duì)稱距離TSP，否則稱為非對(duì)稱距離TSP．對(duì)一般的TSP，它的一種數(shù)學(xué)模型描述為：一個(gè)商人欲到n個(gè)城市推銷商品，每?jī)蓚€(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短．

TSP可分為對(duì)稱和非對(duì)稱距離兩大類問(wèn)題．其中(1.8)中的決策變量

xij=1表示商人行走的路線包含從城市i到城市j路徑，xij=0表示商人沒(méi)有選擇走這條路．i

j的約束可以減少變量的個(gè)數(shù)，使得共有n

(n

1)個(gè)決策變量.(1.5)要求商人從城市i

出來(lái)一次，(1.6)要求商人走入城市j只有一次.

(1.5)和(1.6)表示每個(gè)城市經(jīng)過(guò)一次．僅有(1.5)和(1.6)的約束無(wú)法避免回路的產(chǎn)生，(1.7)約束商人在任何一個(gè)城市子集中不形成回路．此時(shí)

D

0,1n

n1．TSP問(wèn)題解的另一種表示法為循環(huán)排列數(shù)學(xué)模型為：(記in

1

i1)1.2計(jì)算復(fù)雜性的概念

由于有些優(yōu)化算法所需的計(jì)算時(shí)間和存儲(chǔ)空間難以承受，因此算法可解的問(wèn)題在實(shí)踐中并不一定可解。由組合最優(yōu)化問(wèn)題的定義可知，每一個(gè)組合最優(yōu)化問(wèn)題都可以通過(guò)枚舉的方法求得最優(yōu)解。枚舉是以時(shí)間為代價(jià)的，有的枚舉時(shí)間還可以接受，有的則不可能接受。

例如對(duì)非對(duì)稱距離TSP問(wèn)題，可以用另一個(gè)方法來(lái)表示它的可行解：用n個(gè)城市的一個(gè)排列表示商人按這個(gè)排列序推銷并返回起點(diǎn)。若固定一個(gè)城市為起點(diǎn)，則需要

n

個(gè)枚舉。以計(jì)算機(jī)

秒可以完成

個(gè)城市所有枚舉為單位，則枚舉時(shí)城市數(shù)與計(jì)算時(shí)間的關(guān)系如表所示。通過(guò)表可以看出，隨著城市數(shù)的增多，計(jì)算時(shí)間增加非常之快，當(dāng)城市數(shù)增加到

時(shí)，計(jì)算時(shí)間約.年，已無(wú)法接受。所以，我們必須對(duì)計(jì)算復(fù)雜性理論有所了解，這也是最優(yōu)化的理論基礎(chǔ)。只有了解所研究問(wèn)題的復(fù)雜性，才能有針對(duì)性地設(shè)計(jì)算法，進(jìn)而提高優(yōu)化效率。主要簡(jiǎn)單介紹一下多項(xiàng)式時(shí)間算法和指數(shù)時(shí)間算法。一個(gè)算法常常是針對(duì)一個(gè)問(wèn)題來(lái)設(shè)計(jì)的，而若用計(jì)算機(jī)求解，則必須對(duì)問(wèn)題中的參數(shù)賦予具體值．問(wèn)題中的參數(shù)賦予了具體值的例子稱為問(wèn)題的實(shí)例．一個(gè)問(wèn)題通過(guò)它的所有實(shí)例表現(xiàn)．衡量一個(gè)算法的好壞通常是用算法中的加，減，乘，除和比較等基本運(yùn)算的總次數(shù)同實(shí)例在計(jì)算機(jī)計(jì)算時(shí)的二進(jìn)制輸入數(shù)據(jù)的大小關(guān)系來(lái)度量．我們對(duì)實(shí)例的二進(jìn)制輸入長(zhǎng)度和算法的基本計(jì)算總次數(shù)是粗略估計(jì)的，一般是給予一個(gè)上限．一個(gè)求解實(shí)例I的算法的基本計(jì)算總次數(shù)C(I)同實(shí)例I的計(jì)算機(jī)二進(jìn)制輸入長(zhǎng)度d(I)的關(guān)系常用符號(hào)C(I)

f(d(I))

O(g(d(I)))表示，它的含義是：求解實(shí)例I的算法的基本計(jì)算總次數(shù)C(I)是實(shí)例輸入長(zhǎng)度d(I)的一個(gè)函數(shù)，這個(gè)函數(shù)被另一個(gè)函數(shù)g(x)控制，即存在一個(gè)函數(shù)g(x)和一個(gè)正常數(shù)

，使得C(I)

g(d(I))

．其中g(shù)(x)的函數(shù)特性決定了基本計(jì)算總次數(shù)的性能．定義1.1假設(shè)問(wèn)題和解決該問(wèn)題的一個(gè)算法已經(jīng)給定，若給定該問(wèn)題的一個(gè)實(shí)例I，存在多項(xiàng)式函數(shù)g(x)，使得

成立，我們稱該算法對(duì)實(shí)例I是多項(xiàng)式時(shí)間算法；若存在g(x)為多項(xiàng)式函數(shù)且對(duì)該問(wèn)題任意的一個(gè)實(shí)例I，都有

成立．則稱該算法為解決該問(wèn)題的多項(xiàng)式時(shí)間算法．當(dāng)不存在多項(xiàng)式函數(shù)g(x)

使

成立時(shí)，稱相應(yīng)的算法是指數(shù)時(shí)間算法．相比較而言，隨著變量的增加，多項(xiàng)式函數(shù)增長(zhǎng)的速度比指數(shù)函數(shù)增長(zhǎng)的速度要慢得多，因此，我們更喜歡多項(xiàng)式函數(shù)。例如，隨著n的增加，nk

k

的整數(shù)

的增長(zhǎng)速度遠(yuǎn)比an

a1為實(shí)數(shù)

增長(zhǎng)的速度慢。

復(fù)雜性分析的一個(gè)研究方向是對(duì)算法進(jìn)行評(píng)價(jià)。對(duì)于解決一個(gè)問(wèn)題的算法，如何評(píng)估這個(gè)算法的性能？復(fù)雜性分析是評(píng)價(jià)算法的一個(gè)指標(biāo)。復(fù)雜性分析是通過(guò)

從最壞實(shí)例的條件下，確定是否存在多項(xiàng)式函數(shù)g(x)，即可以敘述為：對(duì)一個(gè)求解問(wèn)題的算法，是否存在多項(xiàng)式函數(shù)g(x)和常數(shù)

，使得對(duì)問(wèn)題的任意一個(gè)實(shí)例I，都有

成立。

復(fù)雜性分析的另一個(gè)研究方向是對(duì)組合優(yōu)化問(wèn)題歸類。定義1.3例1.41.3鄰域的概念對(duì)于組合優(yōu)化問(wèn)題(D,F,f)，D上的一個(gè)映射：N:S

D

N(S)2D稱為一個(gè)鄰域映射，其中2D表示D的所有子集組成的集合，N(S)稱為S的鄰域，S'

N(S)稱為S的一個(gè)鄰居．例1.2已給出TSP的一種數(shù)學(xué)模型，由模型D

x

x0,1n(n1)

，可以定義它的一種鄰域?yàn)椋簁為一個(gè)正整數(shù)．這個(gè)鄰域定義使得x最多有k個(gè)位置的值可以發(fā)生變化．x的鄰居有的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)}.

例1.5TSP問(wèn)題解的另一種表示法為定義它的鄰域映射為2-opt，即S中的兩個(gè)元素進(jìn)行對(duì)換，N(S)中共包含S的個(gè)鄰居．如四個(gè)城市定義1.4

若S*滿足f(S*)()f(S)，其中，S

N(S*)F，則稱S*為f在F上的局部最小(大)解．若f(S*)()f(S)，S

F，則稱S*為f在F上的全局最小(大)解．例1.6對(duì)o-1背包問(wèn)題，由模型D

x

x0,1n

，可以定義它的一種鄰域?yàn)椋哼@個(gè)鄰域定義使得x最多有2個(gè)位置的值可以發(fā)生變化．x的鄰居有啟發(fā)式算法是相對(duì)于最優(yōu)算法提出的．一個(gè)問(wèn)題的最優(yōu)算法求得該問(wèn)題每個(gè)實(shí)例的最優(yōu)解．啟發(fā)式算法可以這樣定義：

一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算