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

1、現(xiàn)代優(yōu)化算法課程內(nèi)容課程內(nèi)容第一部分第一部分 現(xiàn)代機(jī)械設(shè)計(jì)概述現(xiàn)代機(jī)械設(shè)計(jì)概述第二部分第二部分 機(jī)械優(yōu)化設(shè)計(jì)機(jī)械優(yōu)化設(shè)計(jì)第三部分第三部分 創(chuàng)新設(shè)計(jì)創(chuàng)新設(shè)計(jì)TRIZ 第四部分第四部分 綠色設(shè)計(jì)綠色設(shè)計(jì)第五部分第五部分 逆向設(shè)計(jì)逆向設(shè)計(jì)現(xiàn)代優(yōu)化算法第七章第七章 現(xiàn)代優(yōu)化算法現(xiàn)代優(yōu)化算法第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 20 20世紀(jì)世紀(jì)8080年代初期，開(kāi)始研究另一類不同于常規(guī)確定性優(yōu)化年代初期，開(kāi)始研究另一類不同于常規(guī)確定性優(yōu)化算法的所謂啟發(fā)式算法。這類算法在求解高線性、多約束、多算法的所謂啟發(fā)式算法。這類算法在求解高線性、多約束

2、、多極值的問(wèn)題中顯示了它的有效性。通過(guò)揭示和模擬自然現(xiàn)象和極值的問(wèn)題中顯示了它的有效性。通過(guò)揭示和模擬自然現(xiàn)象和過(guò)程、并綜合利用數(shù)學(xué)、物理學(xué)、生物進(jìn)化、人工智能、神經(jīng)過(guò)程、并綜合利用數(shù)學(xué)、物理學(xué)、生物進(jìn)化、人工智能、神經(jīng)科學(xué)和統(tǒng)計(jì)學(xué)等所構(gòu)造的算法?？茖W(xué)和統(tǒng)計(jì)學(xué)等所構(gòu)造的算法。1.1.陳立周，陳立周，機(jī)械優(yōu)化設(shè)計(jì)方法機(jī)械優(yōu)化設(shè)計(jì)方法（第三版），冶金工業(yè)出版社（第三版），冶金工業(yè)出版社2.2.邢文訓(xùn)，邢文訓(xùn)，現(xiàn)代優(yōu)化計(jì)算方法現(xiàn)代優(yōu)化計(jì)算方法，清華大學(xué)出版社，清華大學(xué)出版社現(xiàn)代優(yōu)化算法第七章第七章 練習(xí)練習(xí)現(xiàn)代優(yōu)化算法第七章第七章 重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容1. 基本遺傳算法的計(jì)算步驟?；具z傳算法的計(jì)算步驟

3、。2. 基本遺傳算法的編碼與解碼方法?；具z傳算法的編碼與解碼方法。3. 基本遺傳算法有哪三個(gè)遺傳算子，都是如何定義的？基本遺傳算法有哪三個(gè)遺傳算子，都是如何定義的？4. 輪盤選擇的計(jì)算步驟。輪盤選擇的計(jì)算步驟。5.模擬退火算法的新?tīng)顟B(tài)產(chǎn)生函數(shù)是怎樣的？模擬退火算法的新?tīng)顟B(tài)產(chǎn)生函數(shù)是怎樣的？6.模擬退火算法的抽樣穩(wěn)定準(zhǔn)則可以寫成怎樣的表達(dá)式？模擬退火算法的抽樣穩(wěn)定準(zhǔn)則可以寫成怎樣的表達(dá)式？7.模擬退火算法的退溫函數(shù)有哪兩種？模擬退火算法的退溫函數(shù)有哪兩種？現(xiàn)代優(yōu)化算法現(xiàn)代優(yōu)化算法第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 從代表可能潛在的解集的一個(gè)種群開(kāi)始，借助選擇、復(fù)制、從代表可能潛在的解

4、集的一個(gè)種群開(kāi)始，借助選擇、復(fù)制、交叉，變異等遺傳操作，依據(jù)交叉，變異等遺傳操作，依據(jù)“適者生存適者生存”原則，指導(dǎo)在不斷改原則，指導(dǎo)在不斷改進(jìn)的解區(qū)域中進(jìn)行搜索，最后以末代種群的最優(yōu)個(gè)體作為問(wèn)題的進(jìn)的解區(qū)域中進(jìn)行搜索，最后以末代種群的最優(yōu)個(gè)體作為問(wèn)題的近似最優(yōu)解。近似最優(yōu)解。 （Genetic Algorithm） 源于達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)源于達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō) 生物遺傳進(jìn)化的過(guò)程生物遺傳進(jìn)化的過(guò)程: :生物循環(huán)進(jìn)化的過(guò)程圖生物循環(huán)進(jìn)化的過(guò)程圖算法基本思想：算法基本思想：第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法3.3.遺傳算法有較大的可能性可得到全

5、局最優(yōu)解遺傳算法有較大的可能性可得到全局最優(yōu)解. . 4.4.遺傳算法具有良好的可操作性遺傳算法具有良好的可操作性. . 遺傳算法的處理對(duì)象通常不是參數(shù)本身，而是對(duì)參數(shù)進(jìn)行遺傳算法的處理對(duì)象通常不是參數(shù)本身，而是對(duì)參數(shù)進(jìn)行了編碼的個(gè)體，目標(biāo)函數(shù)可解釋為編碼化個(gè)體（可行解）的適了編碼的個(gè)體，目標(biāo)函數(shù)可解釋為編碼化個(gè)體（可行解）的適應(yīng)值，這使遺傳算法不受函數(shù)連續(xù)性、可導(dǎo)性等約束條件的限應(yīng)值，這使遺傳算法不受函數(shù)連續(xù)性、可導(dǎo)性等約束條件的限制。制。 2.2.遺傳算法只需目標(biāo)函數(shù)的取值信息，無(wú)需梯度等其他信息，具遺傳算法只需目標(biāo)函數(shù)的取值信息，無(wú)需梯度等其他信息，具有很強(qiáng)的通用性有很強(qiáng)的通用性. .

6、適合：大規(guī)模、高度非線性的不連續(xù)多峰函數(shù)的優(yōu)化適合：大規(guī)模、高度非線性的不連續(xù)多峰函數(shù)的優(yōu)化 和無(wú)解析表達(dá)式的目標(biāo)函數(shù)的優(yōu)化和無(wú)解析表達(dá)式的目標(biāo)函數(shù)的優(yōu)化1. 1. 并行特點(diǎn)并行特點(diǎn) 操作對(duì)象是一組可行解，而非單個(gè)可行解操作對(duì)象是一組可行解，而非單個(gè)可行解 搜索軌道有多條，而非單條搜索軌道有多條，而非單條. .算法特點(diǎn)算法特點(diǎn): : 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 1.1 1.1 基本遺傳算法的構(gòu)成要素基本遺傳算法的構(gòu)成要素1.4 1.4 遺傳算法基本流程遺傳算法基本流程 1.6 1.6 遺傳算法的展望遺傳算法的展望 第一

7、節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法1.1 基本遺傳算法的構(gòu)成要素基本遺傳算法的構(gòu)成要素 (1) 染色體編碼方法染色體編碼方法 基本遺傳算法使用基本遺傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)串固定長(zhǎng)度的二進(jìn)制符號(hào)串來(lái)來(lái)表示群體中的個(gè)體，其等位基因由二值符號(hào)集表示群體中的個(gè)體，其等位基因由二值符號(hào)集0，1組成。組成。 初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來(lái)生成。如：機(jī)數(shù)來(lái)生成。如： x；1001 1100 1000 1011 01 就可表示一個(gè)個(gè)體，其染色體長(zhǎng)度是就可表示一個(gè)個(gè)體，其染色體長(zhǎng)度是 l18第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GA

8、GA） 現(xiàn)代優(yōu)化算法 基本遺傳算法基本遺傳算法為正確計(jì)為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問(wèn)題，必須預(yù)先確定好由目標(biāo)函數(shù)這樣，根據(jù)不同種類的問(wèn)題，必須預(yù)先確定好由目標(biāo)函數(shù) 值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。 基本遺傳算法使用下述三種遺傳算子：基本遺傳算法使用下述三種遺傳算子： 選擇運(yùn)算：使用選擇運(yùn)算：使用； 交叉運(yùn)算：使用交叉運(yùn)算：使用； 變異運(yùn)算：使用變異運(yùn)算：使用。 第一

9、節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 基本遺傳算法有下述基本遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：個(gè)運(yùn)行參數(shù)需要提前設(shè)定： ：群體大小，群體中所含個(gè)體的數(shù)量，一般?。喝后w大小，群體中所含個(gè)體的數(shù)量，一般取20 100 ：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為50 500 ：交叉概率，一般取為：交叉概率，一般取為0.4 0.99 ：變異概率，一般取為：變異概率，一般取為 0.0001 0.1 這這4個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無(wú)合理選擇它們的理論依據(jù)。在遺一定的影響，但

10、目前尚無(wú)合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過(guò)多次試算后才能確定傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過(guò)多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。出這些參數(shù)合理的取值大小或取值范圍。太大太大: :可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但增加計(jì)可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但增加計(jì)算量，使收斂時(shí)間太長(zhǎng)算量，使收斂時(shí)間太長(zhǎng) 太小太小: :不能提供足夠的采樣點(diǎn)，以致算法性能很差不能提供足夠的采樣點(diǎn)，以致算法性能很差, ,甚至甚至得不到問(wèn)題的可行解得不到問(wèn)題的可行解 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 基本遺傳算法可定義為一個(gè)基本遺傳算法可定義為一

11、個(gè)7元組：元組： M群體大小；群體大?。?F個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)； s選擇操作算子；選擇操作算子； c交叉操作算子：交叉操作算子： m變異操作算子；變異操作算子； pc交叉概率；交叉概率； pm變異概率；變異概率；第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 遺傳算法的尋優(yōu)過(guò)程就是通過(guò)染色體的結(jié)合，即通過(guò)雙親的遺傳算法的尋優(yōu)過(guò)程就是通過(guò)染色體的結(jié)合，即通過(guò)雙親的基因遺傳基因遺傳( (復(fù)制）、變異和交叉等，使解的編碼發(fā)生變化，從而復(fù)制）、變異和交叉等，使解的編碼發(fā)生變化，從而可根據(jù)可根據(jù)“適者生存適者生存”的規(guī)律，最終找出最好的解。的規(guī)律，最終找出最好的解。 遺傳

12、算法中的解空間和編碼空間的映射關(guān)系遺傳算法中的解空間和編碼空間的映射關(guān)系由設(shè)計(jì)空間向遺傳算法編碼空間的映射稱為由設(shè)計(jì)空間向遺傳算法編碼空間的映射稱為編碼編碼；而由編碼空間向設(shè)計(jì)空間的映射稱為而由編碼空間向設(shè)計(jì)空間的映射稱為解碼解碼。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 假設(shè)某一參數(shù)的取值范圍是假設(shè)某一參數(shù)的取值范圍是umin , umax，用長(zhǎng)度為，用長(zhǎng)度為l的二進(jìn)的二進(jìn)制編碼符號(hào)串來(lái)表示該參數(shù)，則它總共能夠產(chǎn)生制編碼符號(hào)串來(lái)表示該參數(shù)，則它總共能夠產(chǎn)生 2l種不同的種不同的編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下：編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下： 0000000000000000

13、0 umin 00000000000000011 umin + 00000000000000102 umin + 2 1111111111111111=2l1 umax 其中，其中， 為二進(jìn)制編碼的編碼精度，其公式為：為二進(jìn)制編碼的編碼精度，其公式為： = umax umin2l 1 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 假設(shè)某一個(gè)體的編碼是：假設(shè)某一個(gè)體的編碼是： x： bl bl-1 bl-2b2b1 則對(duì)應(yīng)的解碼公式為：則對(duì)應(yīng)的解碼公式為：第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 122minmax11minlliiiuubux現(xiàn)代優(yōu)化算法例例 設(shè)設(shè) -3.0

14、x 12.1 , 精度要求精度要求 =0.0001，求：二進(jìn)制編，求：二進(jìn)制編碼的長(zhǎng)度至少為多少？碼的長(zhǎng)度至少為多少？ Umax umin2l + 10.000112.1 + 3.0+ 1 151001151001 即：即： 217 151001 00 if f(X)+Cmin 0式中，式中，minC)(xF為可調(diào)參數(shù)，所取的值應(yīng)使適應(yīng)函數(shù)為可調(diào)參數(shù)，所取的值應(yīng)使適應(yīng)函數(shù)恒大于恒大于0 0。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 ：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，變換方法為：，變換方法為： 其中，其中，Cmax是一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可

15、用下面幾種是一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可用下面幾種方法求得：方法求得： 預(yù)先指定的一個(gè)較大的數(shù)。預(yù)先指定的一個(gè)較大的數(shù)。 進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。 當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。F(X) =Cmax - f(X) if f(X) Cmax0 if f(X) Cmax 式中，式中，maxC)(xF為可調(diào)參數(shù)，所取的值應(yīng)使適應(yīng)函數(shù)為可調(diào)參數(shù)，所取的值應(yīng)使適應(yīng)函數(shù)恒大于恒大于0 0。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制從當(dāng)前代群體中

16、選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。到下一代群體中。 ： 比例選擇算子。比例選擇算子。 指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。適應(yīng)度大小成正比。 輪盤法的基本精神是：個(gè)體被選中的概率取決于個(gè)體的輪盤法的基本精神是：個(gè)體被選中的概率取決于個(gè)體的相對(duì)適應(yīng)度。相對(duì)適應(yīng)度。 復(fù)制體現(xiàn)了復(fù)制體現(xiàn)了“適者生存適者生存”的自然法則。一般都采用適應(yīng)度成的自然法則。一般都采用適應(yīng)度成比例的概率方法，使高性能的個(gè)體得以更大的概率生存，從而比例的概率方法，使高性能的個(gè)體得以更大的概率生存，從而提高全局收斂性和計(jì)算效率。提高全

17、局收斂性和計(jì)算效率。 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 輪盤法的基本思路：個(gè)體被選中的概率取決于個(gè)體的相對(duì)輪盤法的基本思路：個(gè)體被選中的概率取決于個(gè)體的相對(duì)適應(yīng)度：適應(yīng)度： pi = fi / fi ( i=1,2,M ) 式中式中 pi個(gè)體個(gè)體i被選中的概率；被選中的概率； fi個(gè)體個(gè)體i的適應(yīng)度；的適應(yīng)度； fi群體的累加適應(yīng)度。群體的累加適應(yīng)度。 顯然，個(gè)體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)顯然，個(gè)體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)度小的個(gè)體也有可度小的個(gè)體也有可 能被選中，以便增加下一代群體的多樣性。能被選中，以便增加下一代群體的多樣性。第一節(jié)第

18、一節(jié) 遺傳算法（遺傳算法（GAGA） 從統(tǒng)計(jì)意義講，適應(yīng)度大的從統(tǒng)計(jì)意義講，適應(yīng)度大的個(gè)體，其刻度長(zhǎng)，被選中的可能個(gè)體，其刻度長(zhǎng)，被選中的可能性大；反之，適性大；反之，適 應(yīng)度小的個(gè)體被應(yīng)度小的個(gè)體被選中的可能性小，但有時(shí)也會(huì)被選中的可能性小，但有時(shí)也會(huì)被“破格破格”選中。選中?，F(xiàn)代優(yōu)化算法 上述輪盤選擇過(guò)程，可描述如下：上述輪盤選擇過(guò)程，可描述如下： . 順序累計(jì)群體內(nèi)各個(gè)體的適應(yīng)度，得相應(yīng)的累計(jì)值順序累計(jì)群體內(nèi)各個(gè)體的適應(yīng)度，得相應(yīng)的累計(jì)值Si，最后一個(gè)累計(jì)值為最后一個(gè)累計(jì)值為Sn； . 在在0, Sn區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)r； . 依次用依次用Si與與r比較

19、比較，第一個(gè)出現(xiàn)，第一個(gè)出現(xiàn)Si大于或等于大于或等于r的個(gè)體的個(gè)體j被被選為復(fù)制對(duì)象；選為復(fù)制對(duì)象； . 重復(fù)重復(fù) 、 項(xiàng)，直至新群體的個(gè)體數(shù)目等于父代群體項(xiàng)，直至新群體的個(gè)體數(shù)目等于父代群體的規(guī)模。的規(guī)模。輪盤選擇示例輪盤選擇示例個(gè)體序號(hào)個(gè)體序號(hào)12345678910適應(yīng)度適應(yīng)度f(wàn)i8217721211737適應(yīng)度累計(jì)值適應(yīng)度累計(jì)值Si8102734364859666976隨機(jī)數(shù)隨機(jī)數(shù)r2349761312757被選中的個(gè)體號(hào)被選中的個(gè)體號(hào)37103137第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 通過(guò)交叉，子代的基因值不同于父代。交換是遺傳算法產(chǎn)生新通過(guò)交叉，子代的基因值不

20、同于父代。交換是遺傳算法產(chǎn)生新個(gè)體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。個(gè)體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。單點(diǎn)交叉算子。單點(diǎn)交叉算子。 . 對(duì)群體中的個(gè)體進(jìn)行兩兩對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)隨機(jī)配對(duì)。配對(duì)。 若群體大小為若群體大小為M，則共有，則共有 M/2 對(duì)相互配對(duì)的個(gè)體組。對(duì)相互配對(duì)的個(gè)體組。 . 每對(duì)相互配對(duì)的個(gè)體，每對(duì)相互配對(duì)的個(gè)體，隨機(jī)隨機(jī)設(shè)置某設(shè)置某基因座基因座為為交叉點(diǎn)，其后的部交叉點(diǎn)，其后的部分交換。染色體的長(zhǎng)度為分交換。染色體的長(zhǎng)度為l ，則共有，則共有(l-1)個(gè)可能的交叉點(diǎn)位置。個(gè)可能的交叉點(diǎn)位置。 . 對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的

21、交叉概率對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法單點(diǎn)交叉單點(diǎn)交叉A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00 pc = McM 式中式中 M群體中個(gè)體的數(shù)目；群體中個(gè)體的數(shù)目； Mc群體中被交換個(gè)體的數(shù)目。群體中被交換個(gè)體的數(shù)目。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法交叉操作示例交叉操作示例 交叉的個(gè)體是隨機(jī)確定的，如

22、下表所示。某群體有交叉的個(gè)體是隨機(jī)確定的，如下表所示。某群體有n個(gè)個(gè)體，個(gè)個(gè)體，每個(gè)個(gè)體含每個(gè)個(gè)體含8個(gè)等位基因。針對(duì)每個(gè)個(gè)體產(chǎn)生一個(gè)個(gè)等位基因。針對(duì)每個(gè)個(gè)體產(chǎn)生一個(gè)0, 1 區(qū)間的均區(qū)間的均勻隨機(jī)數(shù)。假設(shè)交叉概率勻隨機(jī)數(shù)。假設(shè)交叉概率pc = 0.6，則隨機(jī)數(shù)小于，則隨機(jī)數(shù)小于0.6的對(duì)應(yīng)個(gè)體的對(duì)應(yīng)個(gè)體與其隨機(jī)確定的另一個(gè)個(gè)體交叉，交叉點(diǎn)隨機(jī)確定。與其隨機(jī)確定的另一個(gè)個(gè)體交叉，交叉點(diǎn)隨機(jī)確定。個(gè)體編號(hào)個(gè)體編號(hào)個(gè)體個(gè)體隨機(jī)數(shù)隨機(jī)數(shù)交叉操作交叉操作新個(gè)體新個(gè)體10.72820.589101010 11101010 0130.67840.801100011 01100011 11第一節(jié)第一節(jié) 遺傳

23、算法（遺傳算法（GAGA） 概率太大概率太大: : 群中串的更新很快，使高適配值的個(gè)體很快被群中串的更新很快，使高適配值的個(gè)體很快被破壞掉；破壞掉； 概率太小概率太小: :交叉操作很少進(jìn)行，從而使搜索停滯不前。交叉操作很少進(jìn)行，從而使搜索停滯不前。 p pc c的取值范圍一般的取值范圍一般0.40.4 0.90.9?，F(xiàn)代優(yōu)化算法 對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作需要進(jìn)行變異操作 的某一基因座上的原有基因值為的某一基因座上的原有基因值為0，則變異，則變異操作將該基因值變?yōu)椴僮鲗⒃摶蛑底優(yōu)?，反之，若原有，反

24、之，若原有 基因值為基因值為1，則變異操，則變異操作將其變?yōu)樽鲗⑵渥優(yōu)?。 . 對(duì)個(gè)體的每一個(gè)基因座，依變異概率對(duì)個(gè)體的每一個(gè)基因座，依變異概率pm指定其為變異點(diǎn)。指定其為變異點(diǎn)。 . 對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來(lái)代替，等位基因值來(lái)代替， 從而產(chǎn)生出一個(gè)新的個(gè)體。從而產(chǎn)生出一個(gè)新的個(gè)體。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 基本位變異運(yùn)算的示例如下所示：基本位變異運(yùn)算的示例如下所示： A：1010 1 01010 A：1010 0 01010 變異點(diǎn)變異點(diǎn)基本位變異基本位變異 現(xiàn)代優(yōu)化算法 變異是針對(duì)個(gè)

25、體的某一個(gè)或某一些基因座上的基因值執(zhí)行的，變異是針對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值執(zhí)行的，因此變異概率因此變異概率pm 也是針對(duì)基因而言，即：也是針對(duì)基因而言，即：式中式中 B每代中變異的基因數(shù)目；每代中變異的基因數(shù)目； M每代中群體擁有的個(gè)體數(shù)目每代中群體擁有的個(gè)體數(shù)目 l個(gè)體中基因串長(zhǎng)度。個(gè)體中基因串長(zhǎng)度。Pm = B M l 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 通常取一個(gè)較小的變異概率通常取一個(gè)較小的變異概率0.10.1 0.0010.001。較低的變異率。較低的變異率足以防止整個(gè)群體中任一位置的基因一直保持不變。變異足以防止整個(gè)群體中任一位置的基因一直保持不變。變異概率

26、太大概率太大: :則使遺傳算法退化為隨機(jī)搜索則使遺傳算法退化為隨機(jī)搜索. . 變異起到恢復(fù)丟失或生成遺傳信息的作用，從而保持群變異起到恢復(fù)丟失或生成遺傳信息的作用，從而保持群體中個(gè)體的多樣性，有效地防止算法早熟收斂體中個(gè)體的多樣性，有效地防止算法早熟收斂. . 現(xiàn)代優(yōu)化算法變異操作示例變異操作示例 變異字符的位置是隨機(jī)確定的，如下表所示。某群體有變異字符的位置是隨機(jī)確定的，如下表所示。某群體有3個(gè)個(gè)體，每個(gè)體含個(gè)個(gè)體，每個(gè)體含4 個(gè)基因。針對(duì)每個(gè)個(gè)體的每個(gè)基因產(chǎn)生一個(gè)基因。針對(duì)每個(gè)個(gè)體的每個(gè)基因產(chǎn)生一個(gè)個(gè)0, 1 區(qū)間具有區(qū)間具有3位有效數(shù)字的均勻隨機(jī)數(shù)。假設(shè)變異概率位有效數(shù)字的均勻隨機(jī)數(shù)。假

27、設(shè)變異概率 pm = 0.01，則隨機(jī)數(shù)小于，則隨機(jī)數(shù)小于0.01的對(duì)應(yīng)基因值產(chǎn)生變異。表中的對(duì)應(yīng)基因值產(chǎn)生變異。表中3號(hào)個(gè)體的第號(hào)個(gè)體的第4位的隨機(jī)數(shù)為位的隨機(jī)數(shù)為0.001，小于，小于0.01，該基因產(chǎn)生變異，該基因產(chǎn)生變異，使使3號(hào)個(gè)體由號(hào)個(gè)體由 0010 變?yōu)樽優(yōu)?0011 。其余基因的隨機(jī)數(shù)均大于。其余基因的隨機(jī)數(shù)均大于0.01，不產(chǎn)生變異。不產(chǎn)生變異。個(gè)體編號(hào)個(gè)體編號(hào)10個(gè)體個(gè)體隨機(jī)數(shù)隨機(jī)數(shù)新個(gè)體新個(gè)體110100.801 0.102 0.266 0.373211000.120 0.796 0.105 0.840300100.760 0.473 0.894 0.0010011第一節(jié)

28、第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法1.3.6 1.3.6 確定算法的終止條件確定算法的終止條件 （1 1）GAGA已找到能接受的優(yōu)秀個(gè)體已找到能接受的優(yōu)秀個(gè)體（2 2）GAGA已進(jìn)化了預(yù)定的最大迭代數(shù)已進(jìn)化了預(yù)定的最大迭代數(shù)（3 3）在預(yù)定迭代數(shù)內(nèi)最適應(yīng)個(gè)體的適應(yīng)度無(wú)改進(jìn)）在預(yù)定迭代數(shù)內(nèi)最適應(yīng)個(gè)體的適應(yīng)度無(wú)改進(jìn)（4 4）最適應(yīng)個(gè)體占群體的比例已達(dá)到規(guī)定的比例）最適應(yīng)個(gè)體占群體的比例已達(dá)到規(guī)定的比例 1.3.7 1.3.7 約束條件的處理約束條件的處理 2.2.罰函數(shù)法的基本思想：罰函數(shù)法的基本思想： 對(duì)于在解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體，計(jì)算其適應(yīng)對(duì)于在解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體

29、，計(jì)算其適應(yīng)度時(shí)，用罰函數(shù)降低該個(gè)體的適應(yīng)度，使該個(gè)體被遺傳度時(shí)，用罰函數(shù)降低該個(gè)體的適應(yīng)度，使該個(gè)體被遺傳到下一代群體中的機(jī)會(huì)減少。到下一代群體中的機(jī)會(huì)減少。 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 1.1.拒絕方法的基本思想拒絕方法的基本思想 ：在算法的運(yùn)行過(guò)程中通過(guò)檢查在算法的運(yùn)行過(guò)程中通過(guò)檢查解解 的可行性來(lái)決定解的保留或棄用的可行性來(lái)決定解的保留或棄用. . 現(xiàn)代優(yōu)化算法罰函數(shù)通過(guò)將懲罰不可行解將約束問(wèn)題罰函數(shù)通過(guò)將懲罰不可行解將約束問(wèn)題無(wú)約束問(wèn)題無(wú)約束問(wèn)題 第一種方法：采用加法的形式第一種方法：采用加法的形式 eval（x）=f（x）+ p（x） x x 染色體染色體f f（

30、x x） 問(wèn)題的目標(biāo)函數(shù)問(wèn)題的目標(biāo)函數(shù)p p（x x） 懲罰項(xiàng)懲罰項(xiàng) 對(duì)于最小化問(wèn)題，要求：對(duì)于最小化問(wèn)題，要求：p p（x x）= 0 = 0 ， if x if x 可行可行p p（x x） 0 0 ， if x if x 不可行不可行 第二種方法：采用乘法的形式第二種方法：采用乘法的形式 eval（x）=f（x）p（x） 最小化問(wèn)題，則要求最小化問(wèn)題，則要求p p（x x）= 1 = 1 ，if x if x 可行可行p p（x x） 1 1 ，if x if x 不可行不可行 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法例例2 用遺傳算法求解用遺傳算法求解 2,031,f

31、 xxxxx x為整數(shù)的最大值。為整數(shù)的最大值。一個(gè)簡(jiǎn)單的表示解的編碼是二進(jìn)制編碼，即一個(gè)簡(jiǎn)單的表示解的編碼是二進(jìn)制編碼，即0 0，1 1字符串。由于字符串。由于變量的最大值是變量的最大值是3131，因此可以采用，因此可以采用5 5位數(shù)的二進(jìn)制碼。可以隨機(jī)位數(shù)的二進(jìn)制碼?？梢噪S機(jī)取取4 4個(gè)染色體組成一個(gè)初始群體，如個(gè)染色體組成一個(gè)初始群體，如 x1=0,x2=25,x3=15,x4=8123400000 ,11001 ,01111 ,01000 xxxx第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 適應(yīng)函數(shù)可以依據(jù)目標(biāo)函數(shù)而定，如適應(yīng)函數(shù)可以依據(jù)目標(biāo)函數(shù)而定，如2xxfxfitness)()

32、(01)(xfitness2225)(xfitness2315)(xfitness248)(xfitness定義第定義第i i個(gè)個(gè)體入選種群的概率為個(gè)個(gè)體入選種群的概率為iijjfitness xp xfitness x現(xiàn)代優(yōu)化算法 若群體中選若群體中選4 4個(gè)個(gè)體成為種群，則極有可能競(jìng)爭(zhēng)上的是個(gè)個(gè)體成為種群，則極有可能競(jìng)爭(zhēng)上的是223411001 ,11001 ,01111 ,01000 xxxx若它們交叉，采用如下的交叉方式，稱為簡(jiǎn)單交叉若它們交叉，采用如下的交叉方式，稱為簡(jiǎn)單交叉2132234411 001111110111101 00111 00111 00001 00001 001x

33、yxyxyxy 244233222118)(, 8 ;15)(,1525)(,25 ; 0)(, 0 xfxxfxxfxxfx 于是，適應(yīng)函數(shù)值大的染色體個(gè)體的生存概率自然較大。于是，適應(yīng)函數(shù)值大的染色體個(gè)體的生存概率自然較大。變異變異411001y 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 一次遺傳優(yōu)化迭代完成。一次遺傳優(yōu)化迭代完成。現(xiàn)代優(yōu)化算法1.4 1.4 遺傳算法基本流程遺傳算法基本流程 隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成初始種群，并評(píng)價(jià)每一個(gè)體的初始種群，并評(píng)價(jià)每一個(gè)體的適配值（適配值（fitness valuefitness value）; ;判斷算法收準(zhǔn)則是否滿

34、足判斷算法收準(zhǔn)則是否滿足; ; 根據(jù)適應(yīng)值大小以一定根據(jù)適應(yīng)值大小以一定方式執(zhí)行復(fù)制操作；方式執(zhí)行復(fù)制操作；按交叉概率按交叉概率p pc c執(zhí)行交叉操作；執(zhí)行交叉操作；按變異概率按變異概率p pm m執(zhí)行變異操作；執(zhí)行變異操作；返回步驟。返回步驟。（randomrandom（0 0，1 1）為）為00，11間均間均勻分布隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)勻分布隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)數(shù)值。）數(shù)值。） 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 例例 Rosenbrock函數(shù)的全局最大值計(jì)算。函數(shù)的全局最大值計(jì)算。 max f(x1,x2) = 100 (x2-x12)2 + (1-x1)2

35、s.t. -2.048 xi 2.048 (xi=1,2)如圖所示：如圖所示：該函數(shù)有兩個(gè)局部極大點(diǎn)，該函數(shù)有兩個(gè)局部極大點(diǎn)，分別是分別是: f(2.048, -2048)=3897.7342 和和 f(-2.048,-2.048)=3905.9262其中后者為全局最大點(diǎn)。其中后者為全局最大點(diǎn)。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 3897.73423905.9262現(xiàn)代優(yōu)化算法：確定設(shè)計(jì)變量及其取值范圍：確定設(shè)計(jì)變量及其取值范圍 s.t. -2.048 xi 2.048 (xi=1,2)建立優(yōu)化模型建立優(yōu)化模型 max f(x1,x2) = 100 (x2-x12)2 + (1-x1

36、)2確定編碼方法確定編碼方法 用長(zhǎng)度為用長(zhǎng)度為l0l0位的二進(jìn)制編碼串來(lái)分別表示二個(gè)設(shè)計(jì)變量位的二進(jìn)制編碼串來(lái)分別表示二個(gè)設(shè)計(jì)變量x x1 1,x,x2 2 第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 從離散點(diǎn)從離散點(diǎn)-2.048-2.048到離散點(diǎn)到離散點(diǎn)2.0482.048，依次讓它們分別，依次讓它們分別對(duì)應(yīng)于從對(duì)應(yīng)于從00000 00000(0) 到到11111 11111(1023)之間的二進(jìn)制編碼。再將分之間的二進(jìn)制編碼。再將分別表示別表示x x1 1和和x x2 2的二個(gè)的二個(gè)10位長(zhǎng)的二進(jìn)制編碼串連接在一起，組成位長(zhǎng)的二進(jìn)制編碼串連接在一起，組成一個(gè)一個(gè)20位長(zhǎng)的二進(jìn)制編碼串，

37、它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的位長(zhǎng)的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。例如染色體編碼方法。例如 X：0000110111 11011 10001 就表示一個(gè)個(gè)體的基因型就表示一個(gè)個(gè)體的基因型現(xiàn)代優(yōu)化算法確定解碼方法。確定解碼方法。 解碼時(shí)先將解碼時(shí)先將20位長(zhǎng)的二進(jìn)制編碼串切斷為二個(gè)位長(zhǎng)的二進(jìn)制編碼串切斷為二個(gè)10位長(zhǎng)的二位長(zhǎng)的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為分別記為y1和和y2。 依據(jù)前述個(gè)體編碼方法相對(duì)定義域的離散化方法可知，將依據(jù)前述個(gè)體編碼方法相對(duì)定義域的離散化方法可知，將代碼代

38、碼yi轉(zhuǎn)換為變量轉(zhuǎn)換為變量xi的解碼公式為：的解碼公式為：例如，對(duì)前述個(gè)體例如，對(duì)前述個(gè)體 X： 0000110111 1101110001 它由這樣的兩個(gè)代碼所組成：它由這樣的兩個(gè)代碼所組成： y1= 55 y2 = 881 經(jīng)上式的解碼處理后，得到：經(jīng)上式的解碼處理后，得到： x1= -1.828 x2= 1.476 xi = 4.096 yi 1023 2.048 ( i = 1,2)第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 確定個(gè)體評(píng)價(jià)方法。確定個(gè)體評(píng)價(jià)方法。 由式由式 f(x1,x2) = 100 (x2-x12)2 + (1-x1)2 可知，可知， Rosenbr

39、ock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故這里可將個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函的最大值，故這里可將個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，并且不再對(duì)它作其他變換處理，即有：數(shù)值，并且不再對(duì)它作其他變換處理，即有： F(x) = f(x1,x2)設(shè)計(jì)遺傳算子。設(shè)計(jì)遺傳算子。 選擇運(yùn)算使用比例選擇算子；選擇運(yùn)算使用比例選擇算子； 交叉運(yùn)算使用單點(diǎn)交叉算子；交叉運(yùn)算使用單點(diǎn)交叉算子； 變異運(yùn)算使用基本位變異算子。變異運(yùn)算使用基本位變異算子。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 確定遺傳算法的運(yùn)行參數(shù)。確定遺傳算法的運(yùn)行參數(shù)。 群體

40、大小群體大小: M80 終止代數(shù)終止代數(shù): T200 交叉概率：交叉概率：pc0.6 變異概率：變異概率：pm0.001現(xiàn)代優(yōu)化算法 下圖為其進(jìn)化過(guò)程示例及運(yùn)行結(jié)果。下圖為其進(jìn)化過(guò)程示例及運(yùn)行結(jié)果。 圖中兩條曲線分別為各代群體中個(gè)體適應(yīng)度的最大值和平均值。圖中兩條曲線分別為各代群體中個(gè)體適應(yīng)度的最大值和平均值。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法(a)下圖所示分別為初始群體、第下圖所示分別為初始群體、第5代群體、第代群體、第10代群體和第代群體和第100代群代群體中個(gè)體的分布情況。體中個(gè)體的分布情況。 在圖在圖(a)中初始群體各個(gè)個(gè)體分布得比較均勻。中初始群體各個(gè)個(gè)體分布

41、得比較均勻。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 在圖在圖(b)中中第第5代群體代群體大量的個(gè)體分布在最優(yōu)點(diǎn)和次最優(yōu)點(diǎn)附近。大量的個(gè)體分布在最優(yōu)點(diǎn)和次最優(yōu)點(diǎn)附近。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法從圖從圖(c) 中可以看出，中可以看出，第第10代群體中代群體中次最優(yōu)點(diǎn)也被淘汰。次最優(yōu)點(diǎn)也被淘汰。(c)第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法從圖從圖(d)中可以看出，中可以看出，第第100代群體代群體個(gè)體更加集中在最優(yōu)點(diǎn)附近。個(gè)體更加集中在最優(yōu)點(diǎn)附近。(d) 由該組圖我們可以看出，隨著進(jìn)化過(guò)程的進(jìn)行，群體中適由該組圖我們可以看出，隨

42、著進(jìn)化過(guò)程的進(jìn)行，群體中適應(yīng)度較低的一些個(gè)體被逐漸淘汰掉，而適應(yīng)度較高的一些個(gè)體應(yīng)度較低的一些個(gè)體被逐漸淘汰掉，而適應(yīng)度較高的一些個(gè)體會(huì)越來(lái)越多并且它們都集中在所求問(wèn)題的最優(yōu)點(diǎn)附近，從而會(huì)越來(lái)越多并且它們都集中在所求問(wèn)題的最優(yōu)點(diǎn)附近，從而最終就可搜索到問(wèn)題的最優(yōu)解。最終就可搜索到問(wèn)題的最優(yōu)解。第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法例：例：三桿桁架三桿桁架 MpL2000Mpy1500材料許用拉應(yīng)力材料許用拉應(yīng)力 材料許用壓應(yīng)力材料許用壓應(yīng)力 容重（容重（單位體積的重量單位體積的重量） 7.87.8克克/立方厘米立方厘米 工況工況1: 1: 0,200021PNP工況工況2:

43、 2: NPP2000, 021工況是對(duì)稱的，結(jié)構(gòu)也對(duì)稱，取工況是對(duì)稱的，結(jié)構(gòu)也對(duì)稱，取左右兩桿的截面積左右兩桿的截面積A A1 1，中，中間間桿的截面積桿的截面積A A2 2為自變量，求為自變量，求整個(gè)桁架的最輕質(zhì)量整個(gè)桁架的最輕質(zhì)量2122AAW滿足條件滿足條件 102 . 02A102 . 01A150022200022220002222121213212111221211211AAAAPAAAAPAAAAAP第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法三個(gè)應(yīng)力約束改為：三個(gè)應(yīng)力約束改為：對(duì)約束采用罰函數(shù)法，加在目標(biāo)函數(shù)中，罰函數(shù)定義如下對(duì)約束采用罰函數(shù)法，加在目標(biāo)函數(shù)中，

44、罰函數(shù)定義如下 M M 較大的數(shù)，本例取較大的數(shù)，本例取M=150.0 M=150.0 適應(yīng)度函數(shù)適應(yīng)度函數(shù) 312122liBAAF022150002222000022220002121213212111221211211AAAAPgAAAAPgAAAAAPg 0 )3 , 2 , 1( 0 . 10 0 . 1g 1111211gMigggB第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 由于由于GAGA尋求目標(biāo)函數(shù)的最大值，故上式進(jìn)一步變換為：尋求目標(biāo)函數(shù)的最大值，故上式進(jìn)一步變換為： 312122liBAACFCF設(shè)計(jì)變量設(shè)計(jì)變量A A1 1，A A2 2分別用兩個(gè)分別用兩

45、個(gè)8 8字節(jié)二進(jìn)制串表示字節(jié)二進(jìn)制串表示參數(shù)：種群大小取參數(shù)：種群大小取1010，染色體長(zhǎng)度取，染色體長(zhǎng)度取1616，最大，最大遺傳遺傳代數(shù)取代數(shù)取7070，交叉率取，交叉率取0.70.7，變異率取，變異率取0.125 0.125 如：如：代表兩整型量代表兩整型量176176與與106106，對(duì)應(yīng)的設(shè)計(jì)變量，對(duì)應(yīng)的設(shè)計(jì)變量A A1 1，A A2 2為為 75215702001255176201.).(.A53254902001255106202.).(.A第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法 從從6464代里得到代里得到 6069.696maxF對(duì)比如下對(duì)比如下: : A

46、 A1 1=0.78667 =0.78667 A A2 2 =0.416471 =0.416471 1A2AW精確解精確解0.78820.78820.40820.408226392639復(fù)合形法復(fù)合形法0.7800.7800.4550.45526422642GAGA0.7870.7870.4160.41626412641第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） 現(xiàn)代優(yōu)化算法第一節(jié)第一節(jié) 遺傳算法（遺傳算法（GAGA） （1 1）對(duì)于大型復(fù)雜的或高度非線性的優(yōu)化問(wèn)題）對(duì)于大型復(fù)雜的或高度非線性的優(yōu)化問(wèn)題 ，是一種，是一種有效的優(yōu)化方法。有效的優(yōu)化方法。 （2 2）和傳統(tǒng)的優(yōu)化方法相結(jié)合）和傳

47、統(tǒng)的優(yōu)化方法相結(jié)合, , 發(fā)揮各自的優(yōu)勢(shì)發(fā)揮各自的優(yōu)勢(shì), ,進(jìn)一步加進(jìn)一步加快搜索效率及收斂速度快搜索效率及收斂速度, ,拓寬應(yīng)用范圍。拓寬應(yīng)用范圍。 （3 3）和進(jìn)化策略）和進(jìn)化策略(Evolution Strategy,(Evolution Strategy,簡(jiǎn)稱簡(jiǎn)稱ES)ES)、進(jìn)化規(guī)劃、進(jìn)化規(guī)劃(Evolution Programming,(Evolution Programming,簡(jiǎn)稱簡(jiǎn)稱EP)EP)相互滲透、相互結(jié)合相互滲透、相互結(jié)合, , 提高的智能性搜索。提高的智能性搜索。 （4 4）的控制參數(shù)很多）的控制參數(shù)很多, ,其不同選取對(duì)的性能產(chǎn)生較大的其不同選取對(duì)的性能產(chǎn)生較大的

48、影響影響, ,如何選取這些參數(shù)以及如何使參數(shù)在中自適應(yīng)調(diào)如何選取這些參數(shù)以及如何使參數(shù)在中自適應(yīng)調(diào)節(jié)節(jié), ,需進(jìn)一步研究和探討。需進(jìn)一步研究和探討。（5 5）目前）目前, ,用遺傳算法求解約束優(yōu)化問(wèn)題時(shí)用遺傳算法求解約束優(yōu)化問(wèn)題時(shí), ,一般采用一般采用 懲罰函數(shù)懲罰函數(shù)法法, ,如何確定合理的罰函數(shù)是難點(diǎn)。如何確定合理的罰函數(shù)是難點(diǎn)。 1.6 1.6 遺傳算法的展望遺傳算法的展望 現(xiàn)代優(yōu)化算法第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） （Simulated Annealing） MetropolisMetropolis最早在最早在19531953年提出模擬退火算法（簡(jiǎn)稱年提出模擬退火

49、算法（簡(jiǎn)稱SASA）的思）的思想的想的; ;在在19831983年年KirkpatrickKirkpatrick成功地應(yīng)用于組合優(yōu)化問(wèn)題中成功地應(yīng)用于組合優(yōu)化問(wèn)題中; ;后來(lái)后來(lái)又推廣應(yīng)用到函數(shù)優(yōu)化問(wèn)題中，成為一種通用的優(yōu)化算法，目前又推廣應(yīng)用到函數(shù)優(yōu)化問(wèn)題中，成為一種通用的優(yōu)化算法，目前已在工程中得到了應(yīng)用。已在工程中得到了應(yīng)用。第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） 模擬退火法是一種非導(dǎo)數(shù)優(yōu)化方法，來(lái)源于拉絲玻璃的物理特模擬退火法是一種非導(dǎo)數(shù)優(yōu)化方法，來(lái)源于拉絲玻璃的物理特性，原理類似于以一定的速率冷卻金屬時(shí)發(fā)生的現(xiàn)象。緩慢下降性，原理類似于以一定的速率冷卻金屬時(shí)發(fā)生的現(xiàn)象。

50、緩慢下降的溫度使融化金屬中的原子排成行，形成具有高密度低能量的有的溫度使融化金屬中的原子排成行，形成具有高密度低能量的有規(guī)則的晶體結(jié)構(gòu)。規(guī)則的晶體結(jié)構(gòu)。在模擬退火中，最優(yōu)化目標(biāo)函數(shù)類似于熱力學(xué)系統(tǒng)中的能量。在模擬退火中，最優(yōu)化目標(biāo)函數(shù)類似于熱力學(xué)系統(tǒng)中的能量。溫度高時(shí)，模擬退火算法允許對(duì)遠(yuǎn)處的點(diǎn)求函數(shù)值，并且有可能溫度高時(shí)，模擬退火算法允許對(duì)遠(yuǎn)處的點(diǎn)求函數(shù)值，并且有可能接受一個(gè)具有較高能量的新點(diǎn)，溫度低時(shí)，模擬退火算法只能在接受一個(gè)具有較高能量的新點(diǎn)，溫度低時(shí)，模擬退火算法只能在局部處求目標(biāo)函數(shù)，它接受較高能量新點(diǎn)的可能性小。局部處求目標(biāo)函數(shù)，它接受較高能量新點(diǎn)的可能性小?，F(xiàn)代優(yōu)化算法第二節(jié)第

51、二節(jié) 模擬退火算法（模擬退火算法（SASA） 2.1 模擬退火算法的基本思想模擬退火算法的基本思想 基于物理中固體物質(zhì)的退火過(guò)程和統(tǒng)計(jì)性質(zhì)與一般組基于物理中固體物質(zhì)的退火過(guò)程和統(tǒng)計(jì)性質(zhì)與一般組合優(yōu)化問(wèn)題的相似性。合優(yōu)化問(wèn)題的相似性。固體退火是先將固體加熱到熔化，然后再徐徐冷卻使之固體退火是先將固體加熱到熔化，然后再徐徐冷卻使之凝固成規(guī)整晶體的一種熱力學(xué)過(guò)程。凝固成規(guī)整晶體的一種熱力學(xué)過(guò)程。 它由三部分組成它由三部分組成 : :加溫過(guò)程：即增強(qiáng)分子的熱運(yùn)動(dòng)，使其偏離平衡位置，加溫過(guò)程：即增強(qiáng)分子的熱運(yùn)動(dòng)，使其偏離平衡位置，隨著溫度的升高，粒子與其平衡位置偏離越大。隨著溫度的升高，粒子與其平衡位置

52、偏離越大。 等溫過(guò)程：溫度升至熔解溫度后，固體的規(guī)則性被徹底等溫過(guò)程：溫度升至熔解溫度后，固體的規(guī)則性被徹底破壞，固體熔解為液體，與周圍環(huán)境下進(jìn)行熱交換，破壞，固體熔解為液體，與周圍環(huán)境下進(jìn)行熱交換，但溫度不變，消除系統(tǒng)中原先可能存在的非均勻狀態(tài)。但溫度不變，消除系統(tǒng)中原先可能存在的非均勻狀態(tài)。此時(shí)是高自由能的一種平衡狀態(tài)，是下一過(guò)程即冷卻此時(shí)是高自由能的一種平衡狀態(tài)，是下一過(guò)程即冷卻過(guò)程的起點(diǎn)。過(guò)程的起點(diǎn)。 現(xiàn)代優(yōu)化算法第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） 冷卻過(guò)程：隨著溫度的下降，使分子熱運(yùn)動(dòng)減弱，并處于冷卻過(guò)程：隨著溫度的下降，使分子熱運(yùn)動(dòng)減弱，并處于不同的狀態(tài)，當(dāng)溫度最

53、低時(shí)，分子重新以一定結(jié)構(gòu)排列，不同的狀態(tài)，當(dāng)溫度最低時(shí)，分子重新以一定結(jié)構(gòu)排列，從而得到能量最小的晶體結(jié)構(gòu)。從而得到能量最小的晶體結(jié)構(gòu)。系統(tǒng)將達(dá)到本身的最低能系統(tǒng)將達(dá)到本身的最低能量狀態(tài)，即基態(tài)，這相當(dāng)于能量函數(shù)的全局極小點(diǎn)。量狀態(tài)，即基態(tài)，這相當(dāng)于能量函數(shù)的全局極小點(diǎn)。 根據(jù)統(tǒng)計(jì)力學(xué)的研究表明，在溫度根據(jù)統(tǒng)計(jì)力學(xué)的研究表明，在溫度t t，分子停留在狀態(tài)，分子停留在狀態(tài)r r滿滿足足BolztmannBolztmann概率分布概率分布: :ktrEtzrEEP)(exp)()(1式中式中 )(rE狀態(tài)狀態(tài)r r的能量；的能量；k0k常數(shù)，常數(shù)，； E分子能量的一個(gè)隨機(jī)變量；分子能量的一個(gè)隨機(jī)變

54、量； )(tz概率分布的標(biāo)準(zhǔn)化因子。概率分布的標(biāo)準(zhǔn)化因子。 現(xiàn)代優(yōu)化算法（2 2）在相同溫度下，分子停留在能量小狀態(tài)的概率要比停留）在相同溫度下，分子停留在能量小狀態(tài)的概率要比停留在能量大狀態(tài)的概率要大，當(dāng)溫度相當(dāng)高時(shí)，每個(gè)狀態(tài)的在能量大狀態(tài)的概率要大，當(dāng)溫度相當(dāng)高時(shí)，每個(gè)狀態(tài)的概率基本相同，接近于平均值。概率基本相同，接近于平均值。 第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） BolztmannBolztmann函數(shù)曲線：函數(shù)曲線： ktrEtzrEEP)(exp)(1)(（1 1）分子停留在狀態(tài)）分子停留在狀態(tài)r r的概率的概率P P對(duì)溫度對(duì)溫度t t是單調(diào)下降的，且當(dāng)是單調(diào)下降

55、的，且當(dāng)t t趨近于零時(shí)趨近于零時(shí), ,分子停留在最低能量狀態(tài)的概率值最高。分子停留在最低能量狀態(tài)的概率值最高?，F(xiàn)代優(yōu)化算法第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） 物理退火過(guò)程與求解優(yōu)化問(wèn)題過(guò)程對(duì)照表物理退火過(guò)程與求解優(yōu)化問(wèn)題過(guò)程對(duì)照表 為了使物理系統(tǒng)趨于能量最低狀態(tài)，為了使物理系統(tǒng)趨于能量最低狀態(tài)，MetropolisMetropolis于于19531953年提年提出一種狀態(tài)遷移（固體狀態(tài)的變換）的準(zhǔn)則出一種狀態(tài)遷移（固體狀態(tài)的變換）的準(zhǔn)則-Metropolis-Metropolis抽樣抽樣穩(wěn)定性條件穩(wěn)定性條件: :若若) 1 , 0(exprandomktEEji則以新?tīng)顟B(tài)則

56、以新?tīng)顟B(tài)j j 代替原狀態(tài)代替原狀態(tài)i;i;若不成立則保留狀態(tài)若不成立則保留狀態(tài)i i為當(dāng)前狀態(tài)為當(dāng)前狀態(tài)。 物理退火物理退火優(yōu)化問(wèn)題優(yōu)化問(wèn)題能量能量E(r)目標(biāo)函數(shù)值目標(biāo)函數(shù)值f(x)不同溫度的狀態(tài)不同溫度的狀態(tài)問(wèn)題的解域問(wèn)題的解域能量最低的狀態(tài)能量最低的狀態(tài)E(rmin)最優(yōu)解（目標(biāo)函數(shù)值極小點(diǎn)）最優(yōu)解（目標(biāo)函數(shù)值極小點(diǎn)）f(x*)iE固體當(dāng)前狀態(tài)的能量固體當(dāng)前狀態(tài)的能量randomrandom（0 0，1 1） 00，11間均勻分布的隨機(jī)數(shù)間均勻分布的隨機(jī)數(shù)jE通過(guò)攝動(dòng)產(chǎn)生新?tīng)顟B(tài)的能量通過(guò)攝動(dòng)產(chǎn)生新?tīng)顟B(tài)的能量現(xiàn)代優(yōu)化算法第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） ),(exp1

57、0randomktEEji由式由式可知可知: 高溫下，接受能量差較大的新?tīng)顟B(tài)；高溫下，接受能量差較大的新?tīng)顟B(tài)； 低溫下，接受能量差較小的新?tīng)顟B(tài)。低溫下，接受能量差較小的新?tīng)顟B(tài)。模擬退火算法的基本思想：模擬退火算法的基本思想： 由某一較高的初始溫度開(kāi)始（在解空間中選擇某個(gè)具有由某一較高的初始溫度開(kāi)始（在解空間中選擇某個(gè)具有大目標(biāo)函數(shù)值的一點(diǎn)），利用上式在解域內(nèi)隨機(jī)搜索采樣，大目標(biāo)函數(shù)值的一點(diǎn)），利用上式在解域內(nèi)隨機(jī)搜索采樣，伴隨溫度的不斷下降，并重復(fù)抽樣過(guò)程，使系統(tǒng)的能量達(dá)伴隨溫度的不斷下降，并重復(fù)抽樣過(guò)程，使系統(tǒng)的能量達(dá)到最低狀態(tài)，即相當(dāng)于能量函數(shù)的全局最優(yōu)解。到最低狀態(tài)，即相當(dāng)于能量函數(shù)的全

58、局最優(yōu)解?，F(xiàn)代優(yōu)化算法第二節(jié)第二節(jié) 模擬退火算法（模擬退火算法（SASA） 2.2 算法的基本步驟算法的基本步驟nRxxf )(min（1 1）任選一個(gè)初始解（初始狀態(tài)）任選一個(gè)初始解（初始狀態(tài)）x x（0 0），并令，并令 )()(,00 xxkkmaxttk（初始退火溫度（初始退火溫度tmax應(yīng)取較高的值），計(jì)算應(yīng)取較高的值），計(jì)算)()0(xf（2 2）在溫度）在溫度t tk k下做以下的循環(huán)下做以下的循環(huán)在當(dāng)前的在當(dāng)前的t tk k下隨機(jī)產(chǎn)生新?tīng)顟B(tài)（候選解）下隨機(jī)產(chǎn)生新?tīng)顟B(tài)（候選解）)()(kxgenetex )(xf)()()(kxfxff 計(jì)算計(jì)算值和值和。),()/exp(,mi

59、n101randomtfk xxk)(若若則令則令轉(zhuǎn)到轉(zhuǎn)到(3);(3);否則轉(zhuǎn)。否則轉(zhuǎn)。 0f xxk)(若若則令則令，轉(zhuǎn)，轉(zhuǎn)(3)(3)；否則執(zhí)行下一步。；否則執(zhí)行下一步。新?tīng)顟B(tài)產(chǎn)生函數(shù)新?tīng)顟B(tài)產(chǎn)生函數(shù)狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)（3 3）若滿足算法收斂（退火結(jié)束）準(zhǔn)則，轉(zhuǎn)）若滿足算法收斂（退火結(jié)束）準(zhǔn)則，轉(zhuǎn)(4)(4)；否則令下一循；否則令下一循環(huán)的退火溫度環(huán)的退火溫度 并并 ，轉(zhuǎn)向，轉(zhuǎn)向(2)(kktupdatt11 kk退溫函數(shù)退溫函數(shù)xx)()(xfxf（4 4）終止計(jì)算，輸出結(jié)果，即取）終止計(jì)算，輸出結(jié)果，即取和和內(nèi)內(nèi)循循環(huán)環(huán)外外循循環(huán)環(huán)現(xiàn)代優(yōu)化算法第二節(jié)第二節(jié) 模擬退火算法（模擬退火

60、算法（SASA） 在模擬退火算法中，包含內(nèi)循環(huán)和外循環(huán)：在模擬退火算法中，包含內(nèi)循環(huán)和外循環(huán)：內(nèi)循環(huán)內(nèi)循環(huán)在同一溫度在同一溫度t tk k下不斷隨機(jī)產(chǎn)生候選解，且下不斷隨機(jī)產(chǎn)生候選解，且使它不斷向好解方向移動(dòng)。使它不斷向好解方向移動(dòng)。目標(biāo)函數(shù)的均值已相當(dāng)穩(wěn)定。目標(biāo)函數(shù)的均值已相當(dāng)穩(wěn)定。 規(guī)定產(chǎn)生有限個(gè)候選解規(guī)定產(chǎn)生有限個(gè)候選解; ;連續(xù)若干步候選解的目標(biāo)函數(shù)值變化很小連續(xù)若干步候選解的目標(biāo)函數(shù)值變化很小; ;內(nèi)循環(huán)終止條件：內(nèi)循環(huán)終止條件： 設(shè)置一個(gè)終止溫度設(shè)置一個(gè)終止溫度t te e; ; 規(guī)定外循環(huán)的最大迭代次數(shù)規(guī)定外循環(huán)的最大迭代次數(shù)k kmaxmax; ; 算法在每個(gè)溫度值搜索到的最優(yōu)