最優(yōu)化方法-遺傳算法

主要內(nèi)容遺傳算法模擬退火算法粒子群算法智能優(yōu)化算法

智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借

經(jīng)驗(yàn)（盲目式），理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。常用的智能優(yōu)化算法（1）遺傳算法（Genetic

Algorithm，簡(jiǎn)稱GA）（2）模擬退火算法（Simulated

Annealing，簡(jiǎn)稱SA）（3）

搜索算法（Tabu

Search，簡(jiǎn)稱TS）……智能優(yōu)化算法的特點(diǎn)

它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問(wèn)題空間，因而具有全局優(yōu)化性能。5.1

遺傳算法教學(xué)內(nèi)容：遺傳算法的基本機(jī)理和求解步驟；進(jìn)化策略的算法模型、進(jìn)化策略和遺傳算法的區(qū)別；進(jìn)化編程的機(jī)理與表示和算法步驟；教學(xué)重點(diǎn)：遺傳算法的基本機(jī)理和求解步驟；進(jìn)化策略的算法模型；進(jìn)化編程表示和算法步驟；教學(xué)難點(diǎn)：遺傳算法的交叉和變異機(jī)制；進(jìn)化編程的表示。教學(xué)要求：通過(guò)對(duì)本章的學(xué)習(xí)，使學(xué)生了解三種進(jìn)化算法，并初步了解這些算法研究的進(jìn)展和應(yīng)用情況，以及它們的研究意義，掌握主要算法的求解步驟。遺傳算法遺傳算法是由

的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。自適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法的搜索機(jī)制遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和

突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的子(選擇、交叉和變異)對(duì)這些，利用遺傳算進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。5.1

遺傳算法遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過(guò)人工方式構(gòu)造的一類優(yōu)化搜索算法，是對(duì)生物進(jìn)化過(guò)程的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算中最重要的形式之一遺傳算法為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題了一個(gè)可行的解決方法進(jìn)化計(jì)算和遺傳算法借鑒了生物科學(xué)中的某些知識(shí)，體現(xiàn)了人工智能這一交叉學(xué)科的特點(diǎn)。5.1

遺傳算法(Holland)

遺傳算法通常稱為簡(jiǎn)單遺傳算法（SGA）。其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)?，F(xiàn)以此作為

主要對(duì)象，加上適應(yīng)的改進(jìn)，來(lái)分析遺傳算法的結(jié)構(gòu)和機(jī)理。基本遺傳算法的組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)編碼與GA是通過(guò)某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。正如是從

著手，而

則是由物遺傳排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。將問(wèn)題結(jié)構(gòu)變換為位串形式編碼表示的過(guò)程叫編碼；而相反將位串形式編碼表示變換為原問(wèn)題結(jié)構(gòu)的過(guò)程叫

或譯碼。把位串形式編碼表示叫，有時(shí)也叫。函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：f

(x)

x

sin(10

x)

2.0x∈[-1,2]

，求解結(jié)果精確到6位小數(shù)。SGA對(duì)于本例的編碼由于區(qū)間長(zhǎng)度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為

3×106等份。又因?yàn)?21

<3×106

<222

，所以本例的二進(jìn)制編碼長(zhǎng)度至少需要22位，本例的編碼過(guò)程實(shí)質(zhì)上是將區(qū)間[-1，2]內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20…b0）。幾個(gè)術(shù)語(yǔ)型000111（）缺點(diǎn)是什么？?jī)?yōu)化如何編碼？編碼表現(xiàn)型：0.637197初始種群GA可采用隨機(jī)方法生成若干個(gè)的集合，該集合稱為初始種群。初始種群中

的數(shù)量稱為種群規(guī)模。如何隨機(jī)生成？適應(yīng)度函數(shù)遺傳算法對(duì)一個(gè)（解）的好壞用適應(yīng)度函數(shù)值（通常為正實(shí)數(shù)）來(lái)評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過(guò)程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問(wèn)題本身的要求而定。適應(yīng)度函數(shù)的編制影響求解效果遺傳操作遺傳操作選擇操作也叫

（reproduction）操作，根據(jù)的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。交叉操作的簡(jiǎn)單方式是將被選擇出的兩個(gè)

P1和P2作為父母

，將兩者的部分碼值進(jìn)行交換。變異操作的簡(jiǎn)單方式是改變數(shù)碼串的某個(gè)位置上的數(shù)碼。二進(jìn)制編碼表示的簡(jiǎn)單變異操作是將0與1互換：0變異為1，1變異為0。選擇算子遺傳算法使用選擇運(yùn)算來(lái)實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的

下一代群體中的概率大；適應(yīng)度低的被遺傳到，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就，遺傳賭選擇是按某種方法從父代群體中選取一些到下一代群體。SGA中選擇算子采用方法。賭選擇方法賭選擇又稱比例選擇算子，它的基本思想是：各個(gè)

被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n

，

i

的適應(yīng)度為Fi，則

i

被選中遺傳到下一代群體的概率為：nPi

Fi

/

Fii

1賭選擇方法的實(shí)現(xiàn)步驟（1）

計(jì)算群體中所有

的適應(yīng)度函數(shù)值（需要

）；（2）利用比例選擇算子的公式，計(jì)算每個(gè)被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個(gè)遺傳到下一代群體的概率進(jìn)行匹配）來(lái)確定各個(gè)是否遺傳到下一代群體中。1、被選擇概率的計(jì)算被選擇概率110

0.144234各0.636

0.691被分配的區(qū)間110

0.1442

342、

賭選擇方法（或

比例選擇算子）各

區(qū)間有序隨機(jī)數(shù)產(chǎn)生隨機(jī)

0

6068 0

48

023110.636

0.6910.4860

0.6068

0.95010.2311<0.14是是2入選

0.4806<0.636是0.6068<0.636?

2入選0.9501<0.636

?否2落選0.9501<0.691

?否3落選0.9501<1

?是4入選最終選擇了3個(gè)

2，1個(gè)

4交叉算子所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率Pc

按某種方式相互交換其部分，從而形成兩個(gè)新的。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新的主要方法。

SGA

叉算子采用單點(diǎn)交叉算子。單點(diǎn)交叉運(yùn)算示例11100|01

0

00

0000交叉點(diǎn)交叉前：00000|011100000

111100|000交叉后如：何決定哪對(duì)00000應(yīng)交叉？變異算子

所謂變異運(yùn)算，是指依據(jù)變異概率Pm

將編碼串中的某些 值用其它 值來(lái)替換，從而形成一個(gè)新的 。遺傳算法中的變異運(yùn)算是產(chǎn)生新 的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。SGA中變異算子采用基本位變異算子?；疚蛔儺愃阕踊疚蛔儺愃阕邮侵笇?duì)隨機(jī)指定的某一位或某幾位編碼串作變異運(yùn)算。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的

，若需要進(jìn)行變異操作的某一基因座上的原有 值為0，則變異操作將其變?yōu)?；反之，若原有 值為1，則變異操作將其變?yōu)?

?；疚蛔儺愃阕拥膱?zhí)行過(guò)程變異點(diǎn)變異前：0000011變異后?

如何決定哪個(gè)

變異？000運(yùn)行參數(shù)（1）M

：種群規(guī)模（

20-100

）（2）T

：遺傳運(yùn)算的終止進(jìn)化代數(shù)（100～500）（3）Pc

：交叉概率

（0.4～0.9）（4）Pm

：變異概率

（0.001～0.01）SGA的框圖產(chǎn)生初始群體是否滿足停止準(zhǔn)則是輸出結(jié)果并結(jié)束計(jì)算 適應(yīng)度值比例選擇運(yùn)算單點(diǎn)交叉運(yùn)算基本位變異運(yùn)算否產(chǎn)生新一代群體遺傳算法的特點(diǎn)（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；(3)遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來(lái)指導(dǎo)搜索；適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。(4)遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(jī)操作。以決策變量的某種形式的編碼為運(yùn)算對(duì)象（5）遺傳算法使用概率搜索技術(shù)，增加了其搜索過(guò)程的靈活性。在一定條件下遺傳算法總是以概率

1收斂于問(wèn)題的最優(yōu)解。遺傳算法的特點(diǎn)遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。組合優(yōu)化；生產(chǎn)調(diào)度問(wèn)題；自動(dòng)控制；機(jī)器人學(xué)；圖象處理（使提取誤差最?。?；；機(jī)器學(xué)習(xí)（例如基于遺傳算法的機(jī)器學(xué)習(xí)可用來(lái)調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可以用于人工神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)）。如果只對(duì)幾個(gè)變量作微小的改動(dòng)就能進(jìn)一步

改進(jìn)解,則最好使用一些更普通的方法,來(lái)為遺傳算法助

（求解簡(jiǎn)單問(wèn)題時(shí)效率并不高）一般遺傳算法的主要步驟如下：(1)隨機(jī)產(chǎn)生一個(gè)由確定長(zhǎng)度的特征字符串組成的初始群體。(2)對(duì)該字符串群體迭代執(zhí)行下面的步(a)和(b)，直到滿足停止標(biāo)準(zhǔn)：(a)

計(jì)算群體中每個(gè)

字符串的適應(yīng)值；、交叉和變異等遺傳算子產(chǎn)生下一代群(b)

應(yīng)用體。(3)

把在后代中出現(xiàn)的最好的字符串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問(wèn)題的一個(gè)解。GA算法遺傳算法問(wèn)題求解舉例：遺傳算法歸納為五個(gè)基本組成部分方案表示群體初始化適應(yīng)度函數(shù)遺傳操作算法參數(shù)1、遺傳算法的數(shù)學(xué)基礎(chǔ)（1）模式定理（2）積木塊假設(shè)2遺傳算法的數(shù)學(xué)原理模式的

念編碼01101011100

5111001

50平均適應(yīng)度35.75第1代群體第2代群體編碼串適應(yīng)度011101?34111111981110015011101053平均適應(yīng)度58.75模式是指種群串中的相似樣板111***模式H中確定位置的個(gè)數(shù)稱為模式H的階，記作O(H)。例如O(10**1)=3

。模式

H

中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式

H

的定義距，記作δ(H)。例如δ(10**1)=4

。模式的階與定義距模式的階和定義距的含義模式階用來(lái)反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。模式定理

模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng)。

模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。模式定理的含義

從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長(zhǎng)的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有

的

，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長(zhǎng)的模式，而一般突變概率又相當(dāng)小，因而它對(duì)這些重要的模式幾乎沒(méi)有影響。積木塊假設(shè)

積木塊假設(shè)：遺傳算法通過(guò)短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。

模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則了在遺傳算子的作用下，能生成全局最優(yōu)解。三