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

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

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