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

IntroductiontoSystemsEngineering

石英

武漢理工大學(xué)自動化學(xué)院E-mail:a_laly@163.com系統(tǒng)工程概論IntroductiontoSystemsE1教學(xué)內(nèi)容第一章

緒論

（1學(xué)時）

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

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

第四章

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

第五章

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

教學(xué)內(nèi)容第一章緒論

（1學(xué)時）2系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述3§4-1系統(tǒng)優(yōu)化方法概述系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法系統(tǒng)優(yōu)化問題的應(yīng)用場合：工程設(shè)計中參數(shù)的選擇（既滿足設(shè)計要求，又能降低成本）生產(chǎn)計劃安排（采用合理的方案，提高產(chǎn)值和利潤）城市建設(shè)規(guī)劃（工廠、學(xué)校、醫(yī)院、機(jī)關(guān)、商店、住宅和其他公共設(shè)施的安排，方便群眾）§4-1系統(tǒng)優(yōu)化方法概述系統(tǒng)工程概論E-mail:a4系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法傳統(tǒng)優(yōu)化算法：必須定義被優(yōu)化系統(tǒng)的性能指標(biāo)和約束條件；必須選擇代表優(yōu)化因素的獨(dú)立變量；寫出表示個變量之間關(guān)系的數(shù)學(xué)模型?，F(xiàn)代優(yōu)化算法：用來解決優(yōu)化問題中的難解問題，對系統(tǒng)模型復(fù)雜而無法用明確解析方程來描述的問題有效。系統(tǒng)工程概論E-mail:a_laly@163.com5系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(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ù)，它在可接受的計算代價內(nèi)去尋找最好的解，但不能保證所得的解是最優(yōu)的，所以有必要對算法進(jìn)行評價。系統(tǒng)工程概論E-mail:a_laly@163.com6系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述7系統(tǒng)工程概論E-mail:a_laly@163.com

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

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法§4-2遺傳算法一．遺傳算法中相關(guān)的遺傳學(xué)基礎(chǔ)

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com9系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com10系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法二．遺傳算法的原理和特點(diǎn)

遺傳算法的基本思想：

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com11系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(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:a_laly@163.com12系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com13系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法三．遺傳算法的基本操作

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

1．復(fù)制（Reproduction）

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

系統(tǒng)工程概論E-mail:a_laly@163.com14系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法例如，設(shè)有一個優(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個數(shù)的初始種群如下：

01101

11000

01000

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

位串1：0110113

位串2：1100024

位串3：010008

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

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

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

系統(tǒng)工程概論遺傳算法概述遺傳算法復(fù)17系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com18系統(tǒng)工程概論E-mail:a_laly@163.com

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

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法2．交叉（Crossover）

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

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

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com20系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法下面舉例說明交叉實現(xiàn)過程。

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com21系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法A1=01101A2=11000A’1=01100A’2=11001對兩個隨機(jī)配對的位串個體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)工程概論E-mail:a_laly@163.com22系統(tǒng)工程概論遺傳算法概述遺傳算法在進(jìn)行交叉時，如果交叉的位置只有一個稱為單點(diǎn)交叉，對于位串長度為l的種群，單點(diǎn)交叉可能有l(wèi)－1個不同的交叉。

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

系統(tǒng)工程概論遺傳算法概述遺傳算法在進(jìn)23系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法3．變異（Mutation）

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

在簡單遺傳算法中，變異就是指某個字符串中某一位的值偶然的（概率很小的）隨機(jī)的改變，也就是說在某些特定位置上簡單地把1變?yōu)?，或把0變?yōu)?。當(dāng)有限制地將變異和交叉一起使用時，可以防止一些重要的遺漏。例如，對于上述例子，如果隨機(jī)產(chǎn)生的種群為：01101110010010111100系統(tǒng)工程概論E-mail:a_laly@163.com24系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法在交叉過程中，無論如何在第4位上都不可能得到有1的位串。因此最終所得到的解只能是局部最優(yōu)解。但結(jié)合變異操作就可以解決這個問題。

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com25系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法四．簡單遺傳算法的算法描述

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

系統(tǒng)工程概論E-mail:a_laly@163.com26系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法1．簡單遺傳算法的構(gòu)成要素

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

如：X=100101011010001110這個個體的染色體長度為n＝18。

系統(tǒng)工程概論E-mail:a_laly@163.com27系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(2)個體適應(yīng)度評價――適值（fitness）

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com28系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(3)遺傳算子

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com29系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(4)簡單遺傳算法的運(yùn)行參數(shù)

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com30系統(tǒng)工程概論遺傳算法概述遺傳算法2．簡單遺傳算法描述

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

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

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

E--個體適值評價函數(shù)；

P0--初始種群；

M--種群大小;

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

г—交叉算子；

ψ—變異算子；

T—遺傳運(yùn)算終止條件。系統(tǒng)工程概論遺傳算法概述遺傳算法2．簡單遺31系統(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)工程概論遺傳算法概述遺傳算法Proce32系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法fori=1toMdoP(t+1)=P(t)endfort=t+1endwhileend系統(tǒng)工程概論E-mail:a_laly@163.com33系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法五．簡單遺傳算法舉例

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com34系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com35系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

下圖是應(yīng)用遺傳算法解決實際問題的流程。系統(tǒng)工程概論E-mail:a_laly@163.com36系統(tǒng)工程概論遺傳算法概述遺傳算法實際問題參數(shù)集編碼成位串形式種群1計算適值選擇和遺傳統(tǒng)計結(jié)果種群2經(jīng)過優(yōu)化的一個或多個參數(shù)值改善或解決實際問題隨機(jī)算子種群1<-種群2復(fù)制.交叉.變異系統(tǒng)工程概論遺傳算法概述遺傳算法實際問題參37系統(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)工程概論遺傳算法概述遺傳算法2．簡單遺38系統(tǒng)工程概論E-mail:a_laly@163.com

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

系統(tǒng)工程概論E-mail:a_laly@163.com39系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

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

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

第三步：確定編碼方法。

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

系統(tǒng)工程概論E-mail:a_laly@163.com40系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com41系統(tǒng)工程概論遺傳算法概述遺傳算法第四步：確定解碼方法。

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

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

（6-1-3）

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

y1＝55，y2＝881

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

x1＝－1.828，x2＝1.476E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)工程概論遺傳算法概述遺傳算法第四步：確42系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法第五步：確定個體評價方法。

由于Rosenbrock函數(shù)的值域為非負(fù)值，并且優(yōu)化目標(biāo)是求函數(shù)的最大值。因此該例子中將個體的適值直接取為對應(yīng)的目標(biāo)函數(shù)值。

即有：

f(x)=f(x1,x2)

第六步：設(shè)計遺傳算子。

使用復(fù)制算子、交叉算子和基本變異算子。

系統(tǒng)工程概論E-mail:a_laly@163.com43系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法第七步：確定遺傳算法的運(yùn)行參數(shù)。

在本例中，設(shè)定的簡單遺傳算法運(yùn)行參數(shù)如下：

種群大?。篗=80終止代數(shù)：T=200交叉概率：Pc＝0.6變異概率：Pm=0.001通過上述七個步驟就可構(gòu)成用于Rosenbrock函數(shù)優(yōu)化計算的簡單遺傳算法。系統(tǒng)工程概論E-mail:a_laly@163.com44系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法遺傳算法的應(yīng)用控制：瓦斯管道控制，防避導(dǎo)彈控制，機(jī)器人控制

規(guī)劃：生產(chǎn)規(guī)劃，并行機(jī)任務(wù)分配設(shè)計：VLSI布局，通信網(wǎng)絡(luò)設(shè)計，噴氣發(fā)動機(jī)設(shè)計組合優(yōu)化：TSP問題，背包問題，圖劃分問題圖像處理：模式識別，特征抽取信號處理：濾波器設(shè)計機(jī)器人：路徑規(guī)劃人工生命：生命的遺傳進(jìn)化知識發(fā)現(xiàn)：規(guī)則提取，數(shù)據(jù)挖掘系統(tǒng)工程概論E-mail:a_laly@163.com45系統(tǒng)工程概論系統(tǒng)優(yōu)化概述遺傳算法遺傳算法常用詞匯E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英個體individual群體population位串

bitString染色體Chromosome基因

gene位串結(jié)構(gòu)空間bitStringSpace參數(shù)空間ParametersSpace適應(yīng)度值fitness復(fù)制、選擇reproductionorselection系統(tǒng)工程概論系統(tǒng)優(yōu)化概述遺傳算法遺傳算法常46系統(tǒng)工程概論系統(tǒng)優(yōu)化概述遺傳算法遺傳算法常用詞匯TheEndofGA交叉、交換、重組crossoverorrecombination變異mutation逆轉(zhuǎn)或倒位inversion遺傳算法GeneticAlgorithms系統(tǒng)工程概論系統(tǒng)優(yōu)化概述遺傳算法遺傳算法常47

IntroductiontoSystemsEngineering

石英

武漢理工大學(xué)自動化學(xué)院E-mail:a_laly@163.com系統(tǒng)工程概論IntroductiontoSystemsE48教學(xué)內(nèi)容第一章

緒論

（1學(xué)時）

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

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

第四章

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

第五章

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

教學(xué)內(nèi)容第一章緒論

（1學(xué)時）49系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述50§4-1系統(tǒng)優(yōu)化方法概述系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法系統(tǒng)優(yōu)化問題的應(yīng)用場合：工程設(shè)計中參數(shù)的選擇（既滿足設(shè)計要求，又能降低成本）生產(chǎn)計劃安排（采用合理的方案，提高產(chǎn)值和利潤）城市建設(shè)規(guī)劃（工廠、學(xué)校、醫(yī)院、機(jī)關(guān)、商店、住宅和其他公共設(shè)施的安排，方便群眾）§4-1系統(tǒng)優(yōu)化方法概述系統(tǒng)工程概論E-mail:a51系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法傳統(tǒng)優(yōu)化算法：必須定義被優(yōu)化系統(tǒng)的性能指標(biāo)和約束條件；必須選擇代表優(yōu)化因素的獨(dú)立變量；寫出表示個變量之間關(guān)系的數(shù)學(xué)模型。現(xiàn)代優(yōu)化算法：用來解決優(yōu)化問題中的難解問題，對系統(tǒng)模型復(fù)雜而無法用明確解析方程來描述的問題有效。系統(tǒng)工程概論E-mail:a_laly@163.com52系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(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ù)，它在可接受的計算代價內(nèi)去尋找最好的解，但不能保證所得的解是最優(yōu)的，所以有必要對算法進(jìn)行評價。系統(tǒng)工程概論E-mail:a_laly@163.com53系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述54系統(tǒng)工程概論E-mail:a_laly@163.com

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

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法§4-2遺傳算法一．遺傳算法中相關(guān)的遺傳學(xué)基礎(chǔ)

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com56系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com57系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法二．遺傳算法的原理和特點(diǎn)

遺傳算法的基本思想：

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com58系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(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:a_laly@163.com59系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com60系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法三．遺傳算法的基本操作

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

1．復(fù)制（Reproduction）

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

系統(tǒng)工程概論E-mail:a_laly@163.com61系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法例如，設(shè)有一個優(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個數(shù)的初始種群如下：

01101

11000

01000

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

位串1：0110113

位串2：1100024

位串3：010008

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

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

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

系統(tǒng)工程概論遺傳算法概述遺傳算法復(fù)64系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com65系統(tǒng)工程概論E-mail:a_laly@163.com

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

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法2．交叉（Crossover）

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

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

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com67系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法下面舉例說明交叉實現(xiàn)過程。

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com68系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法A1=01101A2=11000A’1=01100A’2=11001對兩個隨機(jī)配對的位串個體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)工程概論E-mail:a_laly@163.com69系統(tǒng)工程概論遺傳算法概述遺傳算法在進(jìn)行交叉時，如果交叉的位置只有一個稱為單點(diǎn)交叉，對于位串長度為l的種群，單點(diǎn)交叉可能有l(wèi)－1個不同的交叉。

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

系統(tǒng)工程概論遺傳算法概述遺傳算法在進(jìn)70系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法3．變異（Mutation）

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

在簡單遺傳算法中，變異就是指某個字符串中某一位的值偶然的（概率很小的）隨機(jī)的改變，也就是說在某些特定位置上簡單地把1變?yōu)?，或把0變?yōu)?。當(dāng)有限制地將變異和交叉一起使用時，可以防止一些重要的遺漏。例如，對于上述例子，如果隨機(jī)產(chǎn)生的種群為：01101110010010111100系統(tǒng)工程概論E-mail:a_laly@163.com71系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法在交叉過程中，無論如何在第4位上都不可能得到有1的位串。因此最終所得到的解只能是局部最優(yōu)解。但結(jié)合變異操作就可以解決這個問題。

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com72系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法四．簡單遺傳算法的算法描述

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

系統(tǒng)工程概論E-mail:a_laly@163.com73系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法1．簡單遺傳算法的構(gòu)成要素

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

如：X=100101011010001110這個個體的染色體長度為n＝18。

系統(tǒng)工程概論E-mail:a_laly@163.com74系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(2)個體適應(yīng)度評價――適值（fitness）

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com75系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(3)遺傳算子

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com76系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法(4)簡單遺傳算法的運(yùn)行參數(shù)

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com77系統(tǒng)工程概論遺傳算法概述遺傳算法2．簡單遺傳算法描述

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

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

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

E--個體適值評價函數(shù)；

P0--初始種群；

M--種群大小;

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

г—交叉算子；

ψ—變異算子；

T—遺傳運(yùn)算終止條件。系統(tǒng)工程概論遺傳算法概述遺傳算法2．簡單遺78系統(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)工程概論遺傳算法概述遺傳算法Proce79系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法fori=1toMdoP(t+1)=P(t)endfort=t+1endwhileend系統(tǒng)工程概論E-mail:a_laly@163.com80系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學(xué)自動化學(xué)院石英遺傳算法概述遺傳算法五．簡單遺傳算法舉例

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com81系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

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

系統(tǒng)工程概論E-mail:a_laly@163.com82系統(tǒng)工程概論E-mail:a_laly@163.com

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

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

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

下圖是應(yīng)用遺傳算法解決實際問題的流程。系統(tǒng)工程概論E-mail:a_laly@163.com83系統(tǒng)工程概論遺傳算法概述遺傳算法實際問題參數(shù)集編碼成位串形式種群1計算適值選擇和遺傳統(tǒng)計結(jié)果種群2經(jīng)過優(yōu)化的一個或多個參數(shù)值改善或解決實際問題隨機(jī)算子種群1<-種群2復(fù)制.交叉.變異系統(tǒng)工程概論遺傳算法概述遺傳算法實際問題參84系統(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)工程概論遺傳算法概述遺傳算