系統(tǒng)工程第四章系統(tǒng)優(yōu)化

系統(tǒng)工程第四章系統(tǒng)優(yōu)化教學(xué)內(nèi)容第一章

緒論

（1學(xué)時(shí)）

第二章系統(tǒng)分析與系統(tǒng)建模（3學(xué)時(shí)）

第三章最優(yōu)化技術(shù)（24學(xué)時(shí)）

第四章

系統(tǒng)優(yōu)化（2學(xué)時(shí)）

第五章

決策分析（2學(xué)時(shí)）

系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:武漢理工大學(xué)自動化學(xué)院石英§4-1系統(tǒng)優(yōu)化方法概述系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法系統(tǒng)優(yōu)化問題的應(yīng)用場合：工程設(shè)計(jì)中參數(shù)的選擇（既滿足設(shè)計(jì)要求，又能降低成本）生產(chǎn)計(jì)劃安排（采用合理的方案，提高產(chǎn)值和利潤）城市建設(shè)規(guī)劃（工廠、學(xué)校、醫(yī)院、機(jī)關(guān)、商店、住宅和其他公共設(shè)施的安排，方便群眾）系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法傳統(tǒng)優(yōu)化算法：必須定義被優(yōu)化系統(tǒng)的性能指標(biāo)和約束條件；必須選擇代表優(yōu)化因素的獨(dú)立變量；寫出表示個(gè)變量之間關(guān)系的數(shù)學(xué)模型?，F(xiàn)代優(yōu)化算法：用來解決優(yōu)化問題中的難解問題，對系統(tǒng)模型復(fù)雜而無法用明確解析方程來描述的問題有效。系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法現(xiàn)代優(yōu)化算法：是20世紀(jì)80年代初興起的啟發(fā)式算法，這些算法包括禁忌搜索(tabusearch)、模擬退火(simulatedannealing)、遺傳算法(geneticalgorithms)、人工神經(jīng)網(wǎng)絡(luò)(neuralnetworks)。啟發(fā)式算法是這樣一種技術(shù)，它在可接受的計(jì)算代價(jià)內(nèi)去尋找最好的解，但不能保證所得的解是最優(yōu)的，所以有必要對算法進(jìn)行評價(jià)。系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法一．遺傳算法中相關(guān)的遺傳學(xué)基礎(chǔ)二．遺傳算法的原理和特點(diǎn)三．遺傳算法的基本操作四．簡單遺傳算法的算法描述五．簡單遺傳算法舉例§4-2遺傳算法系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法§4-2遺傳算法一．遺傳算法中相關(guān)的遺傳學(xué)基礎(chǔ)

遺傳算法是根據(jù)生物進(jìn)化的模型提出的一種優(yōu)化算法。

根據(jù)達(dá)爾文的進(jìn)化論，生物的發(fā)展進(jìn)化主要有三個(gè)原因：遺傳、變異和選擇。

遺傳：指子代總是和親代相似。遺傳性是一切生物所共有的特性，它使得生物能夠把它的特性、性狀傳給后代。遺傳是生物進(jìn)化的基礎(chǔ)。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法選擇：指具有精選的能力，它決定生物進(jìn)化的方向。進(jìn)化過程中，有的要保留，有的要被淘汰，即適者生存，優(yōu)勝劣汰。

生物就是在遺傳、變異和選擇三種因素的綜合作用過程中，不斷地向前發(fā)展和進(jìn)化。變異：指子代和親代有某些不相似的現(xiàn)象，即子代不會和親代完全一樣。它是生物個(gè)體之間區(qū)別的基礎(chǔ)。生物的變異性為生物的進(jìn)化和發(fā)展創(chuàng)造了條件。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法二．遺傳算法的原理和特點(diǎn)

遺傳算法的基本思想：

首先將需要優(yōu)化的參數(shù)進(jìn)行編碼，組成一個(gè)種群;

按照一定的適值函數(shù)和一系列遺傳操作對種群中的各個(gè)個(gè)體進(jìn)行篩選，使適值(fitness也叫適應(yīng)度)高的個(gè)體被保留，組成新的種群，

新種群包含了上一代的大量信息，并且引入了新的優(yōu)于上一代的個(gè)體。

這樣周而復(fù)始，種群中個(gè)體的適值不斷提高，直至滿足一定的極限條件。此時(shí)，種群中適值最高的個(gè)體即為需要優(yōu)化參數(shù)的最優(yōu)解。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法由于遺傳算法獨(dú)具特色的工作原理，使它能夠在復(fù)雜空間進(jìn)行全局優(yōu)化搜索，并且具有較強(qiáng)的魯棒性。

同常規(guī)優(yōu)化算法比較，遺傳算法有以下優(yōu)點(diǎn)：

1．遺傳算法是對參數(shù)的編碼進(jìn)行操作，而非參數(shù)本身。這樣算法的操作信息量大，優(yōu)化效果好。

2．遺傳算法是從許多點(diǎn)開始并行操作，可以有效防止搜索過程收斂于局部最優(yōu)解問題。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法4．遺傳算法的尋優(yōu)規(guī)則是由概率決定的，而非確定性的。

5．遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而不是盲目地窮舉或完全隨機(jī)搜索。

6．遺傳算法具有并行計(jì)算的特點(diǎn)，可以借助大規(guī)模并行計(jì)算來提高計(jì)算速度。

3．遺傳算法對所要解決的優(yōu)化問題沒有太多的數(shù)學(xué)要求。它通過目標(biāo)函數(shù)來計(jì)算適值，并不需要其它推導(dǎo)和附加信息，因此對問題的依賴性較小。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法三．遺傳算法的基本操作

一般的遺傳算法都包含三個(gè)基本操作：復(fù)制、交叉和變異。

1．復(fù)制（Reproduction）

復(fù)制又稱繁殖，也叫選擇（selection），它是從一個(gè)舊種群中選擇生命力強(qiáng)的個(gè)體位串，產(chǎn)生新種群的過程。也就是說，復(fù)制是個(gè)體位串根據(jù)目標(biāo)函數(shù)（適值函數(shù)）計(jì)算適值，按照適值進(jìn)行復(fù)制，具有較高適值的位串出現(xiàn)在下一代種群中的可能性就大。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法例如，設(shè)有一個(gè)優(yōu)化問題，在整數(shù)空間[0,31]上求函數(shù)f(x)=x2的最大值。

首先把參數(shù)x編碼為有限長度的字符串，一般使用二進(jìn)制數(shù)串，設(shè)參數(shù)x的編碼長度為5。

則有：“00000”代表參數(shù)0，“11111”代表參數(shù)31，區(qū)間[0,31]上的數(shù)與編碼之間采用線性映射方法。

隨機(jī)產(chǎn)生復(fù)制操作的初始種群。

例如隨機(jī)生成的有4個(gè)數(shù)的初始種群如下：

01101

11000

01000

10011系統(tǒng)工程概論遺傳算法概述遺傳算法將初始種群中的個(gè)體視為長度為5位的無符號二進(jìn)制數(shù)，每個(gè)位串可解碼為一個(gè)十進(jìn)制數(shù)：

位串1：0110113

位串2：1100024

位串3：010008

位串4：1001119對種群的各位串根據(jù)目標(biāo)函數(shù)f(x)=x2計(jì)算相應(yīng)的適值和比例，結(jié)果如表所示。

系統(tǒng)工程概論遺傳算法概述遺傳算法復(fù)制操作可以用多種算法實(shí)現(xiàn)，其中最簡單的方法是轉(zhuǎn)輪法。

轉(zhuǎn)輪法：將種群中所有個(gè)體位串的適值的總和看作一個(gè)輪子的圓周，每個(gè)位串按照它的適值在總和中所占的比例，在圓周中用一個(gè)扇區(qū)表示。按照上表畫出的轉(zhuǎn)輪如圖所示。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法由于初始種群中的每個(gè)位串的適值不同，所占總數(shù)的百分比不一樣，因此在轉(zhuǎn)輪旋轉(zhuǎn)時(shí)，被選中的概率就不一樣。

例如，本次產(chǎn)生的4個(gè)位串中，原初始種群中，有的位串被選中一次，有的被選中多次，而有的一次也沒有選中，即該位串被淘汰。因此，適值最好的位串在新種群中就有較多的拷貝。

產(chǎn)生的新種群的情況如下表所示。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法2．交叉（Crossover）

遺傳算法的有效性主要來自復(fù)制和交叉操作。

復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造出新的個(gè)體；

交叉操作模擬了生物進(jìn)化過程中的繁殖現(xiàn)象，通過兩個(gè)個(gè)體的交換組合，來創(chuàng)造出新的優(yōu)良個(gè)體。

簡單的交叉分兩步實(shí)現(xiàn)：

（1）將新復(fù)制產(chǎn)生的位串個(gè)體隨機(jī)進(jìn)行兩兩配對；

（2）隨機(jī)選擇交叉點(diǎn)，對匹配的位串進(jìn)行交叉繁殖，產(chǎn)生一對新的位串。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法下面舉例說明交叉實(shí)現(xiàn)過程。

設(shè)位串的字符長度為l，在[1,l－1]的范圍內(nèi)，隨機(jī)選取一個(gè)整數(shù)值k作為交叉點(diǎn)。將兩個(gè)位串的第k位右邊部分的所有字符進(jìn)行交換，從而生成兩個(gè)新的位串。

b1b2b3b4b5a1a2a3a4a5b1b2b3a4a5a1a2a3b4b5新串1新串2交叉前交叉后例如，在前述表1中，l＝5，對兩個(gè)隨機(jī)配對的位串個(gè)體A1和A2，隨機(jī)選取k＝4，經(jīng)過交叉后產(chǎn)生的新串為A’1和A’2。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法A1=01101A2=11000A’1=01100A’2=11001對兩個(gè)隨機(jī)配對的位串個(gè)體A3和A4，隨機(jī)選取交叉點(diǎn)k＝2，經(jīng)過交叉后產(chǎn)生的新串為A’3、和A’4。

A3=11000A4=10011A’3=11011A’4=10000經(jīng)過交叉后的結(jié)果數(shù)據(jù)如下表所示。

系統(tǒng)工程概論遺傳算法概述遺傳算法在進(jìn)行交叉時(shí)，如果交叉的位置只有一個(gè)稱為單點(diǎn)交叉，對于位串長度為l的種群，單點(diǎn)交叉可能有l(wèi)－1個(gè)不同的交叉。

交叉時(shí)也可以選擇多點(diǎn)交叉，也稱為復(fù)點(diǎn)交叉，即允許個(gè)體的切斷點(diǎn)有多個(gè)，每個(gè)切斷點(diǎn)在兩個(gè)個(gè)體間進(jìn)行個(gè)體的交叉，生成兩個(gè)新個(gè)體。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法3．變異（Mutation）

變異也叫突變，盡管在遺傳算法中，復(fù)制和交叉操作是最重要的，但它不能保證不會遺漏一些重要的遺傳信息。

在簡單遺傳算法中，變異就是指某個(gè)字符串中某一位的值偶然的（概率很小的）隨機(jī)的改變，也就是說在某些特定位置上簡單地把1變?yōu)?，或把0變?yōu)?。當(dāng)有限制地將變異和交叉一起使用時(shí)，可以防止一些重要的遺漏。例如，對于上述例子，如果隨機(jī)產(chǎn)生的種群為：01101110010010111100系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法在交叉過程中，無論如何在第4位上都不可能得到有1的位串。因此最終所得到的解只能是局部最優(yōu)解。但結(jié)合變異操作就可以解決這個(gè)問題。

變異運(yùn)算是用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)改變位串個(gè)體中的某一位的值。

從上面的簡單例子分析中可以看出，雖然只進(jìn)行了一代遺傳操作，但所獲得的新種群的適值的平均值和最大值卻比初始種群有了很大的提高，平均值由293增到了439，最大值由576增加到729。這說明隨著遺傳運(yùn)算的進(jìn)行，種群正向著優(yōu)化的方向發(fā)展。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法四．簡單遺傳算法的算法描述

簡單遺傳算法只使用了復(fù)制算子（選擇算子）、交叉算子和變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解．是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法1．簡單遺傳算法的構(gòu)成要素

(1)染色體編碼方法簡單遺傳算法使用固定長度的二址制位串來表示種群中的個(gè)體，初始種群中各個(gè)個(gè)體的位串值可用均勻分布的隨機(jī)數(shù)來生成。

如：這個(gè)個(gè)體的染色體長度為n＝18。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(2)個(gè)體適應(yīng)度評價(jià)――適值（fitness）

基本遺傳算法按照與個(gè)體適值正比的概率，來決定當(dāng)前種群中每個(gè)個(gè)體遺傳到下一代的機(jī)會的大小。

為了正確計(jì)算這個(gè)概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題．必須預(yù)先確定好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(3)遺傳算子

簡單遺傳算法使用三種遺傳算子：

●復(fù)制運(yùn)算使用復(fù)制算子；●交叉運(yùn)算使用單點(diǎn)交叉算子；●變異運(yùn)算使用基本位變異算子或均勻變異算子。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(4)簡單遺傳算法的運(yùn)行參數(shù)

簡單遺傳算法有以下4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：

●M：種群大小，即種群中所含個(gè)體的數(shù)量，一般取為20～100?！馮：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為100～500?！馪c：交叉概率，一般取為0.4～0.99?！馪m：變異概率，一般取為0.0001～0.1。

這4個(gè)運(yùn)行參數(shù)對遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前還沒有合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后，才能確定出這些參數(shù)合理的取值大小或取值范圍。

系統(tǒng)工程概論遺傳算法概述遺傳算法2．簡單遺傳算法描述

下面給出簡單遺傳算法的偽代碼描述。

簡單遺傳算法可定義為一個(gè)8元組：

SGA＝(C，E，P0，M，Φ,г,ψ，T)式中:C--個(gè)體的編碼方法；

E--個(gè)體適值評價(jià)函數(shù)；

P0--初始種群；

M--種群大小;

Φ--復(fù)制算子；

г—交叉算子；

ψ—變異算子；

T—遺傳運(yùn)算終止條件。系統(tǒng)工程概論遺傳算法概述遺傳算法ProcedureSGABeginInitializeP(0);t=0;while(t≤T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoReproductionoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endfor系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法fori=1toMdoP(t+1)=P(t)endfort=t+1endwhileend系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法五．簡單遺傳算法舉例

簡單遺傳算法是一個(gè)迭代過程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，反復(fù)將復(fù)制算子、交叉算子子、變異算子作用于種群，最終可得到問題的最優(yōu)解或近似最優(yōu)解。

1．遺傳算法的應(yīng)用步驟

遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領(lǐng)域和種類。

對一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問題，一般可按以下步驟來構(gòu)造求解該問題的遺傳算法。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法第一步：確定決策變量及其各種約束條件，即確定出個(gè)體的表現(xiàn)型x和問題的解空間。

第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型(是求目標(biāo)函數(shù)的最大值還是求目標(biāo)函數(shù)的最小值?)及其數(shù)學(xué)描述形式或量化方法。

第三步：確定表示可行的個(gè)體編碼方法，也就是確定出個(gè)體的位串x及遺傳算法的搜索空間。

第四步：確定解碼方法，也就是確定出由個(gè)體位串x到個(gè)體表現(xiàn)型x的對應(yīng)關(guān)系或轉(zhuǎn)換方法。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法第五步；確定個(gè)體適值的量化評價(jià)方法，也就是確定出由目標(biāo)函數(shù)值g(x)到個(gè)體適應(yīng)度f(x)的轉(zhuǎn)換規(guī)則。

第六步：設(shè)計(jì)遺傳算子，即確定出復(fù)制運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法。

第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的M、T、Pc、Pm等參數(shù)。

下圖是應(yīng)用遺傳算法解決實(shí)際問題的流程。系統(tǒng)工程概論遺傳算法概述遺傳算法實(shí)際問題參數(shù)集編碼成位串形式種群1計(jì)算適值選擇和遺傳統(tǒng)計(jì)結(jié)果種群2經(jīng)過優(yōu)化的一個(gè)或多個(gè)參數(shù)值改善或解決實(shí)際問題隨機(jī)算子種群1<-種群2復(fù)制.交叉.變異系統(tǒng)工程概論遺傳算法概述遺傳算法2．簡單遺傳算法在函數(shù)優(yōu)化中的應(yīng)用舉例

例

用簡單遺傳算法求解Rosenbrock函數(shù)的全局最大值。

f(x1,x2)＝100(x12－x2)2＋(1-x1)2（6-1-1）

-2.048<xi<2.048(i=1,2)（6-1-2）

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法如圖所示，該函數(shù)有兩個(gè)局部極大點(diǎn)，分別是f(2.048,-2.048)=3897.7342和f(-2.048,-2.048)=3905.9296，其中后者為全局最大點(diǎn)。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法下面討論求解該問題的遺傳算法的構(gòu)造過程.

第一步：確定決策變量和約束條件。

式（6-1-2）就是該問題的決策變量和約束條件。

第二步：建立優(yōu)化模型。

式（6-1-1）就是該問題的數(shù)學(xué)模型。

第三步：確定編碼方法。

用長度為10位的二進(jìn)制位串來分別表示二個(gè)決策變量x1和x2。10位編碼可以表示從0～1023之間的1024個(gè)不同的數(shù)。

系統(tǒng)工程概論E-mail:武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法將x1和x2的定義域(-2.048~2.048)離散化為1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有1024個(gè)不同的離散點(diǎn)。依次讓它們對應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。

再將分別表示x1和x2的二個(gè)10位長的編碼串連接在一起，組成一個(gè)20位長的編碼，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問題的染色體（個(gè)體）編碼方法。

系統(tǒng)工程概論遺傳算法概述遺傳算法第四步：確定解碼方法。

解碼時(shí)需要先將20位長的位串分割成二個(gè)10位長的位串，然后將它們分別轉(zhuǎn)換為對應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。

根據(jù)前面介紹的個(gè)體編碼方法和對定義域的離散化方法，將代碼yi轉(zhuǎn)換為變量xi，解碼公式為：

（6-1-3）

例如，對于個(gè)體X：00001101111101110001分解成兩個(gè)代碼：

y1＝55，y2＝881

經(jīng)過式（6-1-3）解碼處理后，可得到：

x1＝－1.828，x2＝1.476E-mail:武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)工程概論E-mail: