第五章 系統(tǒng)優(yōu)化

第五章系統(tǒng)優(yōu)化15.1系統(tǒng)優(yōu)化方法概述

優(yōu)化問題是一個(gè)古老的課題。

系統(tǒng)優(yōu)化問題：在一定制約條件下，選擇最合理的、達(dá)到目標(biāo)（準(zhǔn)則）解的最優(yōu)，即在制約條件下選擇準(zhǔn)則函數(shù)最優(yōu)解的問題。2傳統(tǒng)的優(yōu)化算法:

為了將系統(tǒng)優(yōu)化的方法應(yīng)用于具體系統(tǒng)中，傳統(tǒng)的優(yōu)化算法必須定義被優(yōu)化系統(tǒng)的性能指標(biāo)和約束條件；必須選擇代表優(yōu)化因素的獨(dú)立變量；寫出表示各種變量之間關(guān)系的數(shù)學(xué)模型。3優(yōu)點(diǎn)：梯度為基礎(chǔ)的傳統(tǒng)優(yōu)化算法具有較高的計(jì)算效率、較強(qiáng)的可靠性、比較成熟等優(yōu)點(diǎn)，是一類最重要的、應(yīng)用最廣泛的優(yōu)化算法。4弱點(diǎn)：

傳統(tǒng)優(yōu)化方法往往要求目標(biāo)函數(shù)是凸的、連續(xù)可微的，可行域是凸集等條件，而且處理非確定性信息的能力較差。這些弱點(diǎn)使傳統(tǒng)優(yōu)化方法在解決許多實(shí)際問題時(shí)受到了限制。5傳統(tǒng)優(yōu)化方法線性規(guī)劃：?jiǎn)渭冃畏蔷€性規(guī)劃：最速下降法、共扼梯度法、罰函數(shù)法、Kun-Tucker條件動(dòng)態(tài)規(guī)劃圖論6現(xiàn)代優(yōu)化算法:要解決優(yōu)化問題中的難解問題，或者說是系統(tǒng)模型過于復(fù)雜無法用明確的解析方程來描述的問題。它是一種多學(xué)科綜合性的解決問題方法。7優(yōu)化問題的復(fù)雜，通常是指具有下列特征之一：（1）目標(biāo)函數(shù)沒有明確解析表達(dá)；（2）目標(biāo)函數(shù)雖有明確表達(dá)，但不可能恰好估值；（3）目標(biāo)函數(shù)為多峰函數(shù)；（4）目標(biāo)函數(shù)有多個(gè)，即多目標(biāo)優(yōu)化。一個(gè)優(yōu)化問題稱為是困難的，通常是指：目標(biāo)函數(shù)或約束條件不連續(xù)、不可微、高度非線性，或者問題本身是困難的組合問題。8智能優(yōu)化算法主要包括：進(jìn)化算法、模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)方法、免疫算法、禁忌搜索算法、差分演化算法、蟻群算法、微粒群算法等。這類新的優(yōu)化算法一般都是建立在生物智能或物理現(xiàn)象基礎(chǔ)上的隨機(jī)搜索算法，9優(yōu)點(diǎn)：

這類新算法一般不要求目標(biāo)函數(shù)和約束的連續(xù)性與凸性，甚至有時(shí)連有沒有解析表達(dá)式都不要求，對(duì)計(jì)算中數(shù)據(jù)的不確定性也有很強(qiáng)的適應(yīng)能力。105.2啟發(fā)式算法和現(xiàn)代優(yōu)化算法

現(xiàn)代優(yōu)化算法:

隨著20世紀(jì)80年代初期模擬退火、遺傳算法和人工神經(jīng)元網(wǎng)絡(luò)算法的興起，科學(xué)工作者對(duì)一些復(fù)雜問題的優(yōu)化問題和各種新的算法進(jìn)行了深入的分析和研究，并將這些算法稱為現(xiàn)代優(yōu)化算法?，F(xiàn)代優(yōu)化算法的主要應(yīng)用對(duì)象是優(yōu)化問題中的難解問題，或者是系統(tǒng)模型過于復(fù)雜無法用明確的解析方程來描述的問題。

11這些算法包括：禁忌搜索（tabusearch），模擬退火（simulatedannealing），遺傳算法（geneticalgorithms），人工神經(jīng)網(wǎng)絡(luò)（neuralnetworks）。主要用于解決大量的實(shí)際應(yīng)用問題。目前，這些算法在理論和實(shí)際應(yīng)用方面都得到了較大的發(fā)展。實(shí)際中大量的組合優(yōu)化問題是采用大規(guī)模數(shù)值計(jì)算方法。12啟發(fā)式算法:

現(xiàn)代優(yōu)化算法涉及多學(xué)科的知識(shí)，如生物進(jìn)化、人工智能、數(shù)學(xué)和物理科學(xué)、神經(jīng)系統(tǒng)和統(tǒng)計(jì)力學(xué)等概念。它們都是一定的直觀基礎(chǔ)構(gòu)造的算法，稱之為啟發(fā)式算法。啟發(fā)式算法是相對(duì)于最優(yōu)化算法提出的。啟發(fā)式算法的特點(diǎn)是不考慮算法所得解與最優(yōu)解的偏離程度。13如果采用分析最壞情況的誤差界限的概念來評(píng)價(jià)啟發(fā)式算法，則可以將近似算法定義如下：

定義5.1設(shè)A是一個(gè)問題。記問題A的任何一個(gè)實(shí)例I的最優(yōu)解和啟發(fā)式算法H的解的目標(biāo)值分別為和。于是對(duì)于某個(gè)，稱H是A的近似算法，當(dāng)且僅當(dāng)

上面的定義給出啟發(fā)式算法和近似算法兩個(gè)概念的聯(lián)系和區(qū)別。14

啟發(fā)式算法定義的算法集合包含了近似算法概念定義的算法集合。近似算法強(qiáng)調(diào)給出算法最壞情況的誤差界限，而啟發(fā)式算法不需考慮偏差程度。由于很多組合優(yōu)化問題算法的最壞情況誤差估計(jì)需要很強(qiáng)的數(shù)學(xué)基礎(chǔ)和較強(qiáng)的技巧，甚至一些問題很難或無法給出最壞情況誤差界，而實(shí)際問題又迫切需要求解的方法，因此，只能通過啟發(fā)式算法解決問題。15[例5．1]背包問題的貪婪算法（greedyalgorithm）有一個(gè)容積為b的背包，n個(gè)體積分別為(i=1，2，…，n），價(jià)值分別為(i=1，2，…，n)的物品，如何以最大的價(jià)值裝包？這個(gè)問題稱為背包問題。對(duì)背包問題可以構(gòu)造下面的貪婪算法:

16STEP1對(duì)物品以從大到小排列，不妨把排列記成{d1，d2,…dn｝，k＝1；STEP2若，則＝1；否則，＝0。k＝k＋1;當(dāng)k＝n1時(shí)，停止；否則，重復(fù)STEP2。(，，…，)為貪婪算法所得解。單位體積價(jià)值比越大越先裝包是貪婪算法的原則。這樣的算法非常直觀，非常容易操作。

17給定組合優(yōu)化問題，假設(shè)其領(lǐng)域結(jié)構(gòu)已確定，設(shè)S為解集合，f為S上的費(fèi)用函數(shù)，N為領(lǐng)域結(jié)構(gòu)，算法為：STEP1任選一個(gè)初始解；STEP2在N()中按某一規(guī)則選一s；若f(s)＜f()，則＝s；否則N()＝N()-s;若N()=，停止；否則，返回STEP2。［例5．2］簡(jiǎn)單的領(lǐng)域搜索（localsearch）算法18

簡(jiǎn)單的領(lǐng)域搜索從任何一點(diǎn)出發(fā)，達(dá)到一個(gè)局部最優(yōu)值點(diǎn)。從算法中可以看出，算法停止時(shí)得到點(diǎn)的性質(zhì)依賴算法初始解的選取、領(lǐng)域的結(jié)構(gòu)和領(lǐng)域選點(diǎn)的規(guī)則。

啟發(fā)算法的優(yōu)點(diǎn)：

一些啟發(fā)式算法可以用在最優(yōu)算法中，如在分枝定界算法中，可以用啟發(fā)式算法估界:簡(jiǎn)單易行;比較直觀；易被使用者接受；速度快，在適時(shí)管理中非常重要；多數(shù)情況下，程序簡(jiǎn)單，因此易于修改。

19啟發(fā)算法的缺點(diǎn)：

雖然有諸多好處，但它有其短處，這些不足往往成為爭(zhēng)論的焦點(diǎn)：不能保證求得最優(yōu)解；表現(xiàn)不穩(wěn)定，啟發(fā)式算法在同一問題的不同實(shí)例計(jì)算中會(huì)有不同的效果。有些解很好，而有些則很差。在實(shí)際應(yīng)用中，這種不穩(wěn)定性造成計(jì)算結(jié)果不可信。20啟發(fā)式算法的分類：

啟發(fā)式算法由多種算法構(gòu)成，可以將其簡(jiǎn)單的分類為：1．一步算法一步算法的一個(gè)典型實(shí)例是背包問題的貪婪算法。2．改進(jìn)算法（也可以稱之為迭代算法）3．?dāng)?shù)學(xué)規(guī)劃算法數(shù)學(xué)規(guī)劃算法主要指用線性規(guī)劃的方法求解組合優(yōu)化問題，其中包括一些啟發(fā)式規(guī)劃。215.3遺傳算法

遺傳算法主要借用生物進(jìn)化中“適者生存”的規(guī)律。“適者生存”揭示了大自然生物進(jìn)化過程中的一個(gè)規(guī)律：最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群體。22先簡(jiǎn)單了解生物進(jìn)化的基本過程，見下圖。23

以這個(gè)循環(huán)圈的群體（population）為起點(diǎn)，經(jīng)過競(jìng)爭(zhēng)后，一部分群體被淘汰而無法進(jìn)入這個(gè)循環(huán)圈。而另一部分則成為種群（reproduction）。優(yōu)勝劣汰在這個(gè)過程中起著非常重要的作用，這在自然界顯得更加突出。因?yàn)樽匀惶鞖獾膼毫雍吞鞌车那趾?。大自然中的很多?dòng)物的成活率是非常低的。即使在成活群體，還要通過競(jìng)爭(zhēng)產(chǎn)生種群，種群通過婚配的作用產(chǎn)生子代群體（簡(jiǎn)稱子群）。24進(jìn)化的過程中，可能會(huì)因?yàn)樽儺惗a(chǎn)生新的個(gè)體。綜合變異（mutation）的作用，子群成長(zhǎng)為新的群體而取代舊群體，在新的一個(gè)循環(huán)過程中，新的群體將替代舊的群體而成為循環(huán)的開始。25

遺傳算法主要借鑒了生物進(jìn)化的一些特征，其主要特征體現(xiàn)為：進(jìn)化發(fā)生在解的編碼上。這些編碼按生物學(xué)的術(shù)語稱為染色體。26

遺傳算法主要處理步驟：首先是對(duì)優(yōu)化問題的解進(jìn)行編碼，此外，稱一個(gè)解的編碼為一個(gè)染色體，組成編碼的元素稱為基因。第二是適應(yīng)函數(shù)的構(gòu)造和應(yīng)用。第三是染色體的結(jié)合。最后是變異，新解產(chǎn)生過程中可能發(fā)生基因變異，變異使某些解的編碼發(fā)生變化，使解有更大的遍歷性。27下表列出了生物遺傳基本概念在遺傳算法中作用的對(duì)應(yīng)關(guān)系。28

[例5.3]用遺傳算法maxf(x)=，,x為整數(shù)的最大值。一個(gè)簡(jiǎn)單的表示解的編碼是二進(jìn)制編碼，即0，1字符串。由于變量的最大值是31，因此可以采用5位數(shù)的二進(jìn)制碼，如10000161111131010019000102，以上的5位字符串稱為染色體。每一個(gè)分量稱為基因，每個(gè)基因有兩種狀態(tài)0或1。模擬生物進(jìn)化，首先要產(chǎn)生一個(gè)群體，可以隨機(jī)取4個(gè)染色體組成一個(gè)群體，如=（00000），29=（11001)，＝（01111），＝（01000）。群體有4個(gè)個(gè)體，適應(yīng)函數(shù)可以依據(jù)目標(biāo)函數(shù)而定，如適應(yīng)函數(shù)fitness（x）＝f(x)＝，于是fitness()＝0，fitness()＝，fitness()＝，fitness()＝．30定義第i個(gè)個(gè)體入選種群的概率為于是，適應(yīng)函數(shù)值大的染色體個(gè)體的生存概率自然較大，若群體中選4個(gè)個(gè)體成為種群，則極有可能競(jìng)爭(zhēng)上的是＝(11001)，＝（11001），＝（01111），＝（01000）。31若它們結(jié)合，采用如下的交配方式，稱為簡(jiǎn)單交配即交換第二個(gè)位置以后的基因，得到。若的第一個(gè)基因發(fā)生變異，則變成，＝（11001）。32

可以將求解組合優(yōu)化問題的遺傳算法簡(jiǎn)化地描述為：遺傳算法

STEP1選擇問題的一個(gè)編碼，給出一個(gè)有N個(gè)染色體的初始群體pop(1)，t＝1；

STEP2對(duì)群體pop(t)中的每一個(gè)染色體計(jì)算它的適應(yīng)函數(shù)33

STEP3若停止規(guī)則滿足，則算法停止；否則，計(jì)算概率

并以概率分布從pop（t）中隨機(jī)選一些染色體。構(gòu)成一個(gè)種群newpop(t+1)={|j=1,2,…,N};［注］newpop(t+1)集中可能重復(fù)選(pop)(t)中的一個(gè)元素，如例5.3中的就選取兩次。34STEP4通過交配，交配概率為，得到一個(gè)有N個(gè)染色體的crosspop(t+1)；

STEP5以一個(gè)較小的概率p，使得一個(gè)染色體的一個(gè)基因發(fā)生變異，形成mutpop(t+1)；t＝t+1，一個(gè)新的群體pop(t)＝mutpop(t)，返回STEP2。種群的選取方式每次都可能不同，在計(jì)算過程中無法預(yù)測(cè)哪一次的選擇會(huì)獲得好的結(jié)果，因而在某種程度上稱為輪盤賭。35[例5．4]用遺傳算法求maxf(x)=1-,x[0,1]由于對(duì)連續(xù)變量求解，要解決的一個(gè)問題是如何編碼，假設(shè)對(duì)解的誤差要求是1/16，則可以采用4位二進(jìn)制編碼，對(duì)應(yīng)關(guān)系為若計(jì)算一步如表5－2。3637

在表5-2中，newpop只選擇4個(gè)染色體，交配方法采用隨機(jī)選擇一對(duì)染色個(gè)體按交配位進(jìn)行交叉，如0001和0100的交配位隨機(jī)選在位置2，經(jīng)過交配產(chǎn)生0000和0101兩個(gè)個(gè)體。在算法中，0001和0011的交配位隨機(jī)選在位置3，經(jīng)過交配產(chǎn)生0001和0011兩個(gè)個(gè)體，這樣的交配稱為簡(jiǎn)單交配。交配后的染色體組成crosspop。在crosspop中可能有些染色體會(huì)產(chǎn)生變異，簡(jiǎn)單的變異是crosspop中每一個(gè)基因都以同樣一個(gè)概率變異。如0101第一位的基因發(fā)生變異。變異后，得到mutpop，也就是新的群體。38簡(jiǎn)單遺傳算法可以理解為：求解的問題是極大目標(biāo)函數(shù)的優(yōu)化問題；采用0－l二進(jìn)制編碼；pop(t)中的染色體個(gè)數(shù)是一個(gè)常數(shù)；初始群體隨機(jī)選取；適應(yīng)函數(shù)為目標(biāo)函數(shù)；按輪盤賭方法選取色體個(gè)數(shù)同pop(t)相同的種群；交配按常規(guī)交配方法——一對(duì)染色體按隨機(jī)位交換后的基因，染色體中的每一個(gè)基因都以相同的概率變異。39

以上只對(duì)遺傳算法有一個(gè)直觀的了解，但對(duì)遺傳算法的應(yīng)用來說，應(yīng)該側(cè)重于如下主要因素來進(jìn)行研究。（1）解的編碼和解碼。（2）初始群體的選取和計(jì)算中群體的大小。（3）適應(yīng)函數(shù)的確定。（4）三個(gè)算子。遺傳算法的三個(gè)算子是：種群選取、交配和變異。40

遺傳算法的優(yōu)越性：

（1）遺傳算法適合數(shù)值求解那些帶有多參數(shù)、多變量、多目標(biāo)和在多區(qū)域但連續(xù)性較差的NP－h(huán)ard優(yōu)化問題。（2）遺傳算法在求解很多組合優(yōu)化問題時(shí)，不需要有很強(qiáng)的技巧和對(duì)問題有非常深人的了解。（3）遺傳算法同求解問題的其他啟發(fā)式算法有較好的兼容性。415.4模擬退火算法

一、基本思想模擬退火算法（simulatedannealingalgorithm，簡(jiǎn)稱SAA）的思想最早是由Metropolis等于1953年提出的，1983年Kirkpatrick等將其用于組合優(yōu)化。42

1、原理模擬退火算法是一種基于MenteCarlo迭代求解策略的隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理學(xué)中固體物質(zhì)的退火過程與一般組合優(yōu)化問題的相似性。模擬退火算法是在某一初溫下，結(jié)合概率突跳性的Metropolis抽樣策略在解空間中隨機(jī)搜索，伴隨溫度參數(shù)的不斷下降重復(fù)抽樣過程，最終尋找目標(biāo)函數(shù)的全局最優(yōu)解。432、優(yōu)化過程從選定的初始解開始，在借助于控制參數(shù)t遞減的一系列馬氏鏈中，利用一個(gè)新解產(chǎn)生裝置和接受準(zhǔn)則，重復(fù)進(jìn)行產(chǎn)生新解、計(jì)算目標(biāo)函數(shù)差、判斷是否接受新解、接受或舍棄新解，不斷對(duì)當(dāng)前解迭代，從而得到目標(biāo)函數(shù)最優(yōu)的欲求參數(shù)。44二、Metropolis準(zhǔn)則Metropolis于1953年提出了重要性采樣法，即以概率接受新狀態(tài)：在溫度t，由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為Ei和Ej，如果Ej<Ei

，則接受新狀態(tài)j為當(dāng)前狀態(tài)；否則，若概率大于[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)則仍然接受新狀態(tài)j為當(dāng)前狀態(tài)，若不成立則保留狀態(tài)i為當(dāng)前狀態(tài)。45當(dāng)這種過程重復(fù)多次后，系統(tǒng)將趨于能量較低的平衡態(tài)，各狀態(tài)的概率分布將趨于某種正則分布，如Gibbs正則分布?？梢钥吹?，這種重要性采樣過程在高溫下可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)，而在低溫下基本只接受與當(dāng)前能量差較小的新狀態(tài)，這與不同溫度下熱運(yùn)動(dòng)的影響完全一致，而當(dāng)前溫度趨于零時(shí)，就不能接受比當(dāng)前狀態(tài)能量高的新狀態(tài)。這種接受準(zhǔn)則就是Metropolis準(zhǔn)則。46三、模擬退火算法的步驟標(biāo)準(zhǔn)模擬退火算法的一般步驟可描述如下：①給定初始溫度，隨機(jī)產(chǎn)生初始狀態(tài)。②判斷是否滿足算法收斂準(zhǔn)則，若是，輸出結(jié)果；否則，轉(zhuǎn)入下一步。③判斷是否滿足Metropolis抽樣穩(wěn)定準(zhǔn)則，若是，降溫后轉(zhuǎn)入②；否則，由當(dāng)前狀態(tài)Si產(chǎn)生新狀態(tài)Sj。④判斷新狀態(tài)是否滿足抽樣穩(wěn)定準(zhǔn)則，若是，新狀態(tài)Sj為當(dāng)前狀態(tài)；否則，保持當(dāng)前狀態(tài)不變轉(zhuǎn)入③。47四、模擬退火算法的程序框圖

48五、關(guān)鍵參數(shù)和設(shè)計(jì)從算法的流程上看，模擬退火算法包括三函數(shù)準(zhǔn)則：狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則。這些環(huán)節(jié)的設(shè)計(jì)將決定SAA算法的優(yōu)化性能。49（1）狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)一般以概率的方式給出，這里通常采用作為狀態(tài)接受函數(shù)。

（2）初始溫度實(shí)驗(yàn)表明，初溫越大，獲得高質(zhì)量的解的概率越大，但是相應(yīng)的計(jì)算量也越大。因此，初溫的確定應(yīng)著重考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用的方法有：①均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。②利用經(jīng)驗(yàn)公式給出。50（3）溫度更新函數(shù)溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。目前最常用的溫度更新函數(shù)為指數(shù)退溫，即，其中，一般可取。（4）內(nèi)循環(huán)終止準(zhǔn)則

內(nèi)循環(huán)終止準(zhǔn)則即Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。常用的抽樣穩(wěn)定準(zhǔn)則有：①檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定。②連續(xù)若干步的目標(biāo)值變化較小。③按一定的步數(shù)抽樣。51

（5）外循環(huán)終止準(zhǔn)則外循環(huán)終止準(zhǔn)則即算法終止準(zhǔn)則，用于決定算法何時(shí)結(jié)束。設(shè)置溫度終值是一種簡(jiǎn)單的方法，通常還可設(shè)置外循環(huán)迭代次數(shù)或是檢驗(yàn)算法搜索到的最優(yōu)值連續(xù)若干步保持不變時(shí)結(jié)束尋優(yōu)。模擬退火算法的通用性很強(qiáng)，算法易于實(shí)現(xiàn)，但是計(jì)算時(shí)間較長(zhǎng)、效率較低。525.5大系統(tǒng)的分解與協(xié)調(diào)

按一般理解是，系統(tǒng)的變量、階次及約束條件的規(guī)模大一些就稱其大系統(tǒng)。處理大系統(tǒng)優(yōu)化問題就稱其為“大系統(tǒng)理論”。處理大系統(tǒng)優(yōu)化的思路:就是對(duì)大系統(tǒng)進(jìn)行分解(Decomposition)，使被處理的系統(tǒng)降階、降維，達(dá)到易于處理的目的。53大系統(tǒng)分解成若干個(gè)子系統(tǒng)之后，優(yōu)化的困難在于各子系統(tǒng)之間存在的耦合。正是這些關(guān)聯(lián)，在分解后必須在總體目標(biāo)和約束下進(jìn)行協(xié)調(diào)（Coordination）。所以大系統(tǒng)優(yōu)化中的核心概念是大系統(tǒng)的分解／協(xié)調(diào)。54

［例5．5］某總公司下屬兩個(gè)分公司，它們分別生產(chǎn)兩種產(chǎn)品，第一個(gè)子公司產(chǎn)量為，第二個(gè)子公司產(chǎn)量為，每種產(chǎn)品單位產(chǎn)量的產(chǎn)值均為10個(gè)單位，兩個(gè)子公司的生產(chǎn)能力限制分別為4