遺傳算法學(xué)習(xí)課件

遺傳算法原理與應(yīng)用報(bào)告提綱一、遺傳算法概述二、遺傳算法原理三、遺傳算法的應(yīng)用一、遺傳算法概述1、智能優(yōu)化算法

2、基本遺傳算法

3、遺傳算法的特點(diǎn)

1、智能優(yōu)化算法

智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。常用的智能優(yōu)化算法（1）遺傳算法（GeneticAlgorithm，簡稱GA）（2）模擬退火算法（SimulatedAnnealing，簡稱SA）（3）禁忌搜索算法（TabuSearch，簡稱TS）

……智能優(yōu)化算法的特點(diǎn)

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

遺傳算法是由美國的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。遺傳算法的搜索機(jī)制

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

2、基本遺傳算法

基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)?；具z傳算法的組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)

編碼GA是通過某種編碼機(jī)制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：

x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。SGA對于本例的編碼

由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因?yàn)?21<3×106<222

，所以本例的二進(jìn)制編碼長度至少需要22位，本例的編碼過程實(shí)質(zhì)上是將區(qū)間[-1，2]內(nèi)對應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個二進(jìn)制串（b21b20…b0）。二進(jìn)制串（b21b20b19…b1b0）與[a,b]

內(nèi)實(shí)數(shù)的一一映射：二進(jìn)制串[a,b]

內(nèi)實(shí)數(shù)b21b20b19…b1b0幾個術(shù)語基因型：1000101110110101000111

表現(xiàn)型：0.637197編碼解碼個體（染色體）基因初始種群SGA采用隨機(jī)方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。

適應(yīng)度函數(shù)

遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。選擇算子

遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對群體中的個體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。輪盤賭選擇方法

輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個體i的適應(yīng)度為Fi，則個體i被選中遺傳到下一代群體的概率為：輪盤賭選擇方法的實(shí)現(xiàn)步驟（1）計(jì)算群體中所有個體的適應(yīng)度函數(shù)值（需要解碼）；（2）利用比例選擇算子的公式，計(jì)算每個個體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個個體遺傳到下一代群體的概率進(jìn)行匹配）來確定各個個體是否遺傳到下一代群體中。交叉算子

所謂交叉運(yùn)算，是指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。SGA中交叉算子采用單點(diǎn)交叉算子。單點(diǎn)交叉運(yùn)算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點(diǎn)變異算子

所謂變異運(yùn)算，是指依據(jù)變異概率Pm將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。SGA中變異算子采用基本位變異算子?；疚蛔儺愃阕?/p>

基本位變異算子是指對個體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對于基本遺傳算法中用二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)??；疚蛔儺愃阕拥膱?zhí)行過程變異前：000001110000000010000變異后：000001110001000010000變異點(diǎn)運(yùn)行參數(shù)（1）M：種群規(guī)模（2）T：遺傳運(yùn)算的終止進(jìn)化代數(shù)（3）Pc：交叉概率（4）Pm：變異概率SGA的框圖產(chǎn)生初始群體是否滿足停止準(zhǔn)則是輸出結(jié)果并結(jié)束計(jì)算個體適應(yīng)度值比例選擇運(yùn)算單點(diǎn)交叉運(yùn)算基本位變異運(yùn)算否產(chǎn)生新一代群體執(zhí)行M/2次3、遺傳算法的特點(diǎn)（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。二、遺傳算法原理1、遺傳算法的收斂性分析

2、遺傳算法的改進(jìn)

1、遺傳算法的收斂性分析

遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。種群規(guī)模對收斂性的影響

通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計(jì)算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。選擇操作對收斂性的影響

選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。交叉概率對收斂性的影響

交叉操作用于個體對，產(chǎn)生新的個體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。變異概率對收斂性的影響

變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。遺傳算法的本質(zhì)

遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。Schaffer建議的最優(yōu)參數(shù)范圍是：

M=20-100，

T=100-500，

Pc=0.4-0.9，

Pm=0.001-0.01。

遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）自動控制（4