合肥工業(yè)大學(xué)系統(tǒng)工程導(dǎo)論第5章 系統(tǒng)優(yōu)化

第5章系統(tǒng)優(yōu)化前幾章分別介紹了一些傳統(tǒng)系統(tǒng)優(yōu)化的方法，如線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論等。本章側(cè)重于介紹現(xiàn)代優(yōu)化算法和大系統(tǒng)的分解與協(xié)調(diào)。一、現(xiàn)代優(yōu)化算法傳統(tǒng)優(yōu)化算法與現(xiàn)代優(yōu)化算法在系統(tǒng)設(shè)計(jì)與規(guī)劃過程中，通常需要面臨所謂的“系統(tǒng)優(yōu)化”問題，即在一定約束條件下，選擇最合理的、達(dá)到某一（或某些）目標(biāo)的最優(yōu)解，例如生產(chǎn)計(jì)劃安排中的最大獲利問題、投資決策問題、油管鋪設(shè)中的最短路問題等。系統(tǒng)優(yōu)化問題是一個(gè)古老的課題，早在17世紀(jì)在歐洲就有人提出了各種求最大（小）值問題。直到20世紀(jì)40年代，隨著科學(xué)的發(fā)展而產(chǎn)生了一系列如線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論等傳統(tǒng)優(yōu)化算法。這些算法在應(yīng)用時(shí)，要求：Q選擇表示優(yōu)化因素的獨(dú)立??變量；Q定義要優(yōu)化的系統(tǒng)的性能指標(biāo)和約束條件；Q寫出表示各種變量之間關(guān)系的數(shù)學(xué)模型。隨著20世紀(jì)80年代初期模擬退火、遺傳算法和人工神經(jīng)元網(wǎng)絡(luò)算法的興起，人們對(duì)某些復(fù)雜的優(yōu)化問題及其算法進(jìn)行了深入研究，從而產(chǎn)生了現(xiàn)代優(yōu)化算法。這些算法是一種多學(xué)科綜合性的解決問題方法，其主要應(yīng)用對(duì)象是系統(tǒng)優(yōu)化中的難解問題，即系統(tǒng)模型過于復(fù)雜而無法用明確的解析方程來描述的問題。啟發(fā)式算法以一定的直觀基礎(chǔ)構(gòu)造成的算法，稱為啟發(fā)式算法。啟發(fā)式算法是相對(duì)于最優(yōu)化算法提出的，它是在可接受的計(jì)算費(fèi)用內(nèi)尋求最好解（但不一定是最優(yōu)解）的一種技術(shù)。在多數(shù)情況下，由于無法明確找出問題的最優(yōu)解，所以也就無法表明所得解與最優(yōu)解的近似程度。因此，啟發(fā)式算法的特點(diǎn)是不考慮算法所得的最好解與最優(yōu)解的偏離程度。例1（背包問題的貪婪算法）有一個(gè)容積為b的背包，現(xiàn)有n個(gè)體積分別為q.，價(jià)值分別為c（i=1,2,…,n）的物品待裝包，試問如何使裝包物品的價(jià)值達(dá)到最大？'解'對(duì)于該背包問題可構(gòu)造以下貪婪算法：（1）對(duì)物品按“單位體積價(jià)值最大的優(yōu)先裝包”的原則，以c,/a.從大到小進(jìn)行排列，不妨把排列記成｛1,2,…,n｝，并令k=1；（2）若勇1ax+ax<b，則xk=1（裝包）；否則，xk=0（不裝包）；iikki=1（3）k=k+1，若k=n±1時(shí)，算法停止；否則，返回（2）。故（X],x2，…,xn）為該貪婪算法的所得解?？梢姡@種啟發(fā)式算法非常直觀，且易操作。啟發(fā)式算法的優(yōu)點(diǎn)：Q數(shù)學(xué)模型簡(jiǎn)單；Q直觀且簡(jiǎn)單易行；Q速度快；Q程序易于修改等。啟發(fā)式算法的缺點(diǎn)：Q不能確保求得最優(yōu)解；Q計(jì)算結(jié)果表現(xiàn)不穩(wěn)定而造成不可信。啟發(fā)式算法的分類（參見P99）：Q一步算法；Q改進(jìn)的迭代算法；Q數(shù)學(xué)規(guī)劃算法；????????Q現(xiàn)代優(yōu)化算法。遺傳算法遺傳算法是根據(jù)生物進(jìn)化的模型而提出的一種現(xiàn)代優(yōu)化算法。由于最優(yōu)化問題的求解過程是從眾多的可行解中選出的最優(yōu)解，而生物進(jìn)化中的“適者生存”規(guī)律是使最有生存能力的染色體以最大的可能生存下來，這種相似性就使得遺傳算法可以在優(yōu)化問題中得以應(yīng)用。遺傳算法的生物進(jìn)化特征遺傳算法主要借鑒了生物進(jìn)化的以下特征：.????????????????.Q生物進(jìn)化實(shí)質(zhì)上是發(fā)生在染色體上；Q選擇：按自然選擇規(guī)律確定染色體的生存或淘汰，即適者生存、優(yōu)勝劣汰；Q遺傳：當(dāng)染色體結(jié)合時(shí)，雙親遺傳基因的結(jié)合會(huì)使子代保持父代的特征；Q變異：當(dāng)染色體結(jié)合后，隨機(jī)的變異會(huì)造成子代與父代的特征又有所不同。遺傳算法的主要步驟仿照生物遺傳的概念，可以得到遺傳算法的主要步驟如下：Q首先，對(duì)優(yōu)化問題的解進(jìn)行編碼為了便于表達(dá)優(yōu)化問題的解和進(jìn)行遺傳運(yùn)算，就必須對(duì)優(yōu)化問題的解進(jìn)行編碼，且一個(gè)解的編碼稱為一個(gè)染色體，組成編碼的元素稱為基因。Q其次，構(gòu)造和應(yīng)用適應(yīng)函數(shù)適應(yīng)函數(shù)通常是依據(jù)優(yōu)化問題的目標(biāo)函數(shù)來決定的。適應(yīng)函數(shù)確定后，由適應(yīng)函數(shù)值所決定的概率分布進(jìn)而確定生存或淘汰的染色體(即解的編碼)，生存下來的染色體組成一個(gè)可以繁衍下一代的群體一一種群(即一組解)。Q再次，進(jìn)行編碼的交叉通過編碼的交叉來實(shí)現(xiàn)染色體的結(jié)合(即編碼的組合)，從而繁衍出新的下一代(即產(chǎn)生新的解)。Q最后，產(chǎn)生變異通過基因變異(即編碼的某個(gè)元素分量發(fā)生變化)使某些解的編碼發(fā)生變化，從而使這些解具有更大的遍歷性(適應(yīng)性)。遺傳算法與生物遺傳概念的對(duì)應(yīng)關(guān)系參見P101表5-1所示。例2用遺傳算法求解maxf(x)=x2,0<x<31且x為整數(shù)。解第一步，選擇解的編碼，并選取初始群體以及群體中的個(gè)體數(shù)量(即群體維數(shù))通常，表示解的簡(jiǎn)單編碼是二進(jìn)制編碼，即0或1組成的字符串。由于變量x的最大值是31<32=25，因此可以采用5位二進(jìn)制編碼來表示優(yōu)化問題的解，例如10000—16，11111—31，01001—9，00010—2上述編碼就稱為染色體。編碼中的每個(gè)分量稱為基因，且每個(gè)基因只有兩種狀態(tài)0或1。注意：若本例是對(duì)連續(xù)變量求解，如x￡[0,1]且對(duì)解的誤差要求是1/32=1/25,則可采用5位二進(jìn)制編碼，而該編碼與十進(jìn)制的對(duì)應(yīng)關(guān)系為(參見P103例5.4)(abcde)(abcde)^|+—+—|I863JJ。模擬生物進(jìn)化來構(gòu)造一個(gè)初始群體，這里隨機(jī)取4個(gè)染色體(即編碼)組成一個(gè)群體，如x1=(00000)、x2=(11001)、x3=(01111)、x4=(01000)，且群體的個(gè)體數(shù)為4。第二步，確定適應(yīng)函數(shù)一般可依據(jù)目標(biāo)函數(shù)來確定適應(yīng)函數(shù)，如適應(yīng)函數(shù)fitness(x)=f(x)=x2,于是初始群體中各編碼的適應(yīng)函數(shù)值分別為fitness(x1)=0，fitness(x2)=252=625，fitness(x3)=152=225，fitness(x4)=82=64若定義第Z個(gè)個(gè)體(即編碼)入選種群的概率(即生存概率)為fitness(x)「Zfitness(x)j則初始群體中各編碼入選種群的概率分別為p(x1)=0,p(x2)=0.684,P(X3)=0.246,p(x4)=0.070顯然，染色體個(gè)體的適應(yīng)函數(shù)值越大，其生存概率也越大，則越有可能入選種群。若群體中選擇4個(gè)個(gè)體成為種群，則最有可能競(jìng)爭(zhēng)入選的個(gè)體(即編碼)是x2=(11001)，x2=(11001)，x3="11)，x4=(01000)種群的選取方式通常每次都可能不同，在計(jì)算過程中無法預(yù)測(cè)哪一次的選擇會(huì)獲得更好的結(jié)果，因而這種選取方式在某種程度上就稱為輪盤賭。第三步，使種群中染色體(即編碼)進(jìn)行交叉組合種群選定后，其染色體個(gè)體進(jìn)行交叉組合時(shí)，首先要考慮交叉規(guī)則，如雙親遺傳法、主個(gè)體副個(gè)體規(guī)則、單親遺傳規(guī)則等；其次還應(yīng)考慮交叉位置的選取、交叉概率等細(xì)節(jié)問題。本例中，采用以下簡(jiǎn)單交叉的方式進(jìn)行組合：X2=(11〔001)]y=(11111)X3=(01111)]y2=(01001)X2=(11*01)1y=(11I000)x=(01000)y4=(01001)用分隔符“I”表示交叉位置，即交換第二個(gè)位置以后的基因，從而得到交叉組合后的染色體y「y2、y3和y4。第四步，產(chǎn)生變異變異是擴(kuò)大染色體選擇范圍的一個(gè)重要手段。通常，遺傳算法實(shí)現(xiàn)變異的方法是賦予每個(gè)基因一個(gè)相同的相對(duì)較小的變異概率，通過隨機(jī)模擬來決定在某個(gè)基因是否發(fā)生變異。本例中，若交叉后的染色體中只有y4的第一個(gè)基因發(fā)生變異，則變成y4'=(11001)。第五步，將變異后的個(gè)體組成新的群體，重復(fù)第二~四步，直至得到滿足要求的解第六步，對(duì)最優(yōu)解進(jìn)行解碼由于解碼和編碼是相對(duì)應(yīng)的，所以可按編碼規(guī)則將所得解進(jìn)行解碼。由此可見，在應(yīng)用遺傳算法解決實(shí)際問題時(shí)應(yīng)注意的問題有(參見P103?104)：.??????????????????.Q確定解的編碼和解碼規(guī)則；Q選取初始群體和群體維數(shù)；Q確定適應(yīng)函數(shù)；Q確定種群、個(gè)體交叉和個(gè)體變異三個(gè)遺傳算子。遺傳算法小結(jié)(參見P102)簡(jiǎn)單的遺傳算法可理解為是求解目標(biāo)函數(shù)最大的優(yōu)化問題。其算法描述如下：第一步，選擇問題的一個(gè)編碼，給出一個(gè)含有N個(gè)染色體的初始群體pop(r)，并令t=1；注意：。通常采用0-1二進(jìn)制編碼，且解碼與編碼的規(guī)則相同；Q初始群體隨機(jī)選取且群體的維數(shù)為常數(shù)，該常數(shù)有時(shí)與遺傳代數(shù)有關(guān)；第二步，對(duì)群體pop(t)中的每一個(gè)染色體pop.(t)，計(jì)算其相應(yīng)的適應(yīng)函數(shù)值f.=fitness(pop.(t))注意：通常選取適應(yīng)函數(shù)與目標(biāo)函數(shù)相同。第三步，若滿足停止規(guī)則，則算法停止；否則，計(jì)算各染色體pop.(t)的生存概率P=.,i=1,2,,NiNZfjj=1并按生存概率分布，從pop(r)中隨機(jī)選一些染色體構(gòu)成一個(gè)種群newpop(r+1)={pop,(r)lj=1,2,…，N}注意：Q可重復(fù)選擇pop(￡)中的某個(gè)元素組成種群newpop(f+1)，如例2中選取兩次X2;②按輪盤賭方法選取染色體個(gè)數(shù)與初始群體pop(t)相同的種群；第四步，以交叉概率心使種群中的各染色體交叉，得到交叉群體crosspop(r+1)；注意：通常按常規(guī)交叉法進(jìn)行交叉，即一對(duì)染色體按隨機(jī)位交換其后的所有基因。第五步，以較小概率p，使交叉群體中某染色體的一個(gè)基因發(fā)生變異，并形成變異群體mutpop(r+1)；注意：通常染色體中的每個(gè)基因都以同樣相對(duì)較小的概率發(fā)生變異。第六步，令t=r+1，形成一個(gè)新的群體pop(r)=mutpop(r)，并返回第二步；第七步，重復(fù)第2?6步，直到滿足求解規(guī)則要求，則算法停止并進(jìn)行解碼。遺傳算法的特點(diǎn)與傳統(tǒng)優(yōu)化算法相比，遺傳算法的優(yōu)越性體現(xiàn)在(參見P104)：.?????????.Q遺傳算法適合于求解帶有多參數(shù)、多變量、多目標(biāo)和在多區(qū)域但連續(xù)性較差的NP-hard優(yōu)化問題，是一種具有普適性的數(shù)值求解方法；Q遺傳算法在求解許多組合優(yōu)化問題時(shí)，不需要對(duì)問題有很深入的了解和有很強(qiáng)的求解技巧，如排序、路線調(diào)度、布局等；Q遺傳算法與其他求解問題的啟發(fā)式算法之間有較好的兼容性。二、大系統(tǒng)的分解與協(xié)調(diào)所謂“大系統(tǒng)”，通常是指系統(tǒng)變量、階次及約束條件的規(guī)模都較大的系統(tǒng)。處理大系統(tǒng)優(yōu)化問題的基本思路是：對(duì)大系統(tǒng)進(jìn)行分解，即把總系統(tǒng)劃分成若干個(gè)子系統(tǒng)，從而使被處理的系統(tǒng)降階、降維，達(dá)到易于處理的目的。因?yàn)橛纱笙到y(tǒng)分解出的各子系統(tǒng)之間通常存在耦合關(guān)聯(lián)，所以在大系統(tǒng)分解后必須注意在總體目標(biāo)和約束條件下進(jìn)行協(xié)調(diào)。由此可見，大系統(tǒng)優(yōu)化的核心是大系統(tǒng)的分解/協(xié)調(diào)。其原則是：在上級(jí)系統(tǒng)對(duì)下級(jí)子系統(tǒng)的協(xié)調(diào)下，獲得總體系統(tǒng)的最優(yōu)解。大系統(tǒng)分解/協(xié)調(diào)????原理如圖1所示(參見P110圖5-5)。圖1大系統(tǒng)分解/協(xié)調(diào)示意圖(a.為協(xié)調(diào)變量，0，.為反饋?zhàn)兞?例3(生產(chǎn)管理問題)某總公司下屬兩個(gè)分公司分別生'產(chǎn)兩種產(chǎn)品，設(shè)子公司1的產(chǎn)量為氣，子公司2的產(chǎn)量為％，每種產(chǎn)品單位產(chǎn)量的產(chǎn)值均為10個(gè)單位，兩個(gè)子公司的生產(chǎn)能力限制分別為4和3。如果原材料供應(yīng)緊張，每生產(chǎn)1個(gè)單位％需要消耗1個(gè)單位的原材料，生產(chǎn)1個(gè)單位揚(yáng)消耗2個(gè)單位的原材料，總原材料限制為8個(gè)單位，試問該如何安排生產(chǎn)計(jì)劃，使全公司的產(chǎn)值最大？解該公司生產(chǎn)優(yōu)化問題的數(shù)學(xué)模型為maxZ=10x+10xfx<4x2<3|x+2x<8Ix,x>0112方法1:對(duì)耦合條件進(jìn)行分解/協(xié)調(diào)這種方法的思路是對(duì)耦合條件進(jìn)行分解與協(xié)調(diào)。既然總資源約束是8,那么就把8分成b1和b2，并將b1、b2分別分給子公司1和子公司2,這時(shí)總系統(tǒng)就分解為兩個(gè)“獨(dú)立”的子系統(tǒng)，如圖2所示（參見P106圖5-3）。圖2按耦合條件分解現(xiàn)在原問題就轉(zhuǎn)化為如何確定各子公司資源約束b]和b2，使全公司的總產(chǎn)值Z—max,其實(shí)質(zhì)就是資源優(yōu)化分配問題。由分析可知，聽、b2的可行分配方案如下：方案lb1=2,b2=6則兩個(gè)子公司生產(chǎn)優(yōu)化結(jié)果分別是x】=2，Z[=20x2=3，Z2=30可得公司總產(chǎn)值Z=Z1+Z2=50方案2b1=3,b2=5則兩個(gè)子公司生產(chǎn)優(yōu)化結(jié)果分別是了1=3,Z[=30x2=2,Z2=25可得公司總產(chǎn)值Z=Z1+Z2=55方案3b1=4,b2=4則兩個(gè)子公司生產(chǎn)優(yōu)化結(jié)果分別是x1=4,Z1=40x2=2,Z2=20可得公司總產(chǎn)值Z=Z1+Z2=60從上述方案中可以看出，增大b1的配額（b2的配額相應(yīng)減少）會(huì)使系統(tǒng)總體收益提高，那么如果繼續(xù)提高b1配額，其結(jié)果會(huì)如何呢？方案4b1=5,b2=3則兩個(gè)子公司生產(chǎn)優(yōu)化結(jié)果分別是

%=4,Z]=40x2=3/2,Z2=15可得公司總產(chǎn)值Z=Z]+Z2=55從上述方案分析可知，若在方案3的基礎(chǔ)上進(jìn)一步提高b]的配額(即同時(shí)使b2降低)，則系統(tǒng)總體收益反而會(huì)降低。因此可得出結(jié)論：方案3的資源分配方案就是最優(yōu)的方案，即「資源分配方案：b]=4,b2=4生產(chǎn)安排：x]=4,x2=2|分公司產(chǎn)值：Z]=40,Z2=20[總公司產(chǎn)值：Z=Z]+Z2=60方法2:對(duì)目標(biāo)函數(shù)進(jìn)行分解/協(xié)調(diào)這種方法是根據(jù)耦合關(guān)系，對(duì)目標(biāo)函數(shù)進(jìn)行分解/協(xié)調(diào)。其思路是：將耦合約束條件乘以待定系數(shù)k心0)，再合并到目標(biāo)函數(shù)中，即耦合約束條件移項(xiàng)，得乘以待定系數(shù)k乘以待定系數(shù)k(k^0)，得合并到目標(biāo)函數(shù)中，得由于8k是常數(shù)，則上式合并為k(8-x-2x)>0maxZ=10x]+10x2+8k-kx「2kx2maxZ=(10x]-kx〔)+(10x2-2kx2)通過上述方法將耦合約束條件合并到目標(biāo)函數(shù)中，其實(shí)就是將約束條件中耦合約束條件去掉，以便分解子系統(tǒng)。這樣原問題就轉(zhuǎn)換為：在滿足總的資源條件下，選擇待定系數(shù)k，使子系統(tǒng)達(dá)到最優(yōu)，此時(shí)子系統(tǒng)的解就是總體系統(tǒng)的最優(yōu)解，如圖3所示(參見P]07圖5-4)。圖3按目標(biāo)函數(shù)分解由圖可見，形式上分解為兩個(gè)“獨(dú)立”的子系統(tǒng)，關(guān)鍵是參數(shù)k的確定。由分析可知，確定參數(shù)k的可行方案如下：方案1k=4對(duì)于第一個(gè)子系統(tǒng)，有maxZ=]0x-4x=6xfx<4ix]>0可得，解％=4對(duì)于第二個(gè)子系統(tǒng)，有maxZ=10x-8x=2xfx<3S'IX220可得，解x2=3檢查：x1+2x2=4+2X3=10>8結(jié)論：當(dāng)選定k=4時(shí)，不能滿足約束條件，即資源不夠。方案