遺傳算法原理和應(yīng)用

1、關(guān)于遺傳算法原理與應(yīng)用第一張，PPT共六十五頁，創(chuàng)作于2022年6月報告提綱一、遺傳算法概述 二、遺傳算法原理三、遺傳算法的應(yīng)用第二張，PPT共六十五頁，創(chuàng)作于2022年6月一、遺傳算法概述1、智能優(yōu)化算法 2、基本遺傳算法 3、遺傳算法的特點 第三張，PPT共六十五頁，創(chuàng)作于2022年6月1、智能優(yōu)化算法 智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。這種算法一般具有嚴密的理論依據(jù)，而不是單純憑借專家經(jīng)驗，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。 第四張，PPT共六十五頁，創(chuàng)作于2022年6月常用的智能優(yōu)化算法 （1）遺傳算法 （Gene

2、tic Algorithm， 簡稱GA） （2）模擬退火算法（Simulated Annealing， 簡稱SA） （3）禁忌搜索算法（Tabu Search， 簡稱TS） 第五張，PPT共六十五頁，創(chuàng)作于2022年6月智能優(yōu)化算法的特點 它們的共同特點：都是從任一解出發(fā)，按照某種機制，以一定的概率在整個求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴展到整個問題空間，因而具有全局優(yōu)化性能。第六張，PPT共六十五頁，創(chuàng)作于2022年6月遺傳算法起源 遺傳算法是由美國的J. Holland教授于1975年在他的專著自然界和人工系統(tǒng)的適應(yīng)性中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機

3、化搜索算法 。 第七張，PPT共六十五頁，創(chuàng)作于2022年6月遺傳算法的搜索機制 遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標為止。 第八張，PPT共六十五頁，創(chuàng)作于2022年6月2、基本遺傳算法 基本遺傳算法（Simple Genetic Algorithms，簡稱SGA，又稱簡單遺傳算法或標準遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進化操作過程簡單，容易理解，是其它一些

4、遺傳算法的雛形和基礎(chǔ)。 第九張，PPT共六十五頁，創(chuàng)作于2022年6月基本遺傳算法的組成 （1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運行參數(shù)第十張，PPT共六十五頁，創(chuàng)作于2022年6月 編碼 GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進制串進行編碼。 第十一張，PPT共六十五頁，創(chuàng)作于2022年6月函數(shù)優(yōu)化示例 求下列一元函數(shù)的最大值： x-1,2 ，求解結(jié)果精確到6位小數(shù)。第十二張，PPT共六十五頁，創(chuàng)作于2022年6月SGA對于本例的編碼 由于區(qū)間長度為3

5、，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3106等份。又因為221 3106 222 ，所以本例的二進制編碼長度至少需要22位，本例的編碼過程實質(zhì)上是將區(qū)間-1，2內(nèi)對應(yīng)的實數(shù)值轉(zhuǎn)化為一個二進制串（b21b20b0）。第十三張，PPT共六十五頁，創(chuàng)作于2022年6月幾個術(shù)語 基因型：1000101110110101000111 表現(xiàn)型：0.637197 編碼解碼個體（染色體）基因第十四張，PPT共六十五頁，創(chuàng)作于2022年6月初始種群 SGA采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。 第十五張，PPT共六十五頁，創(chuàng)作于2022年6月

6、適應(yīng)度函數(shù) 遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。 第十六張，PPT共六十五頁，創(chuàng)作于2022年6月選擇算子 遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。 第十七張，PPT共六十五頁，創(chuàng)作于2022年6月輪盤賭選擇方法 輪盤賭選擇又稱比例

7、選擇算子，它的基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n ，個體i 的適應(yīng)度為 Fi，則個體i 被選中遺傳到下一代群體的概率為： 第十八張，PPT共六十五頁，創(chuàng)作于2022年6月輪盤賭選擇方法的實現(xiàn)步驟（1） 計算群體中所有個體的適應(yīng)度函數(shù)值（需要解碼）；（2） 利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3） 采用模擬賭盤操作（即生成0到1之間的隨機數(shù)與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。第十九張，PPT共六十五頁，創(chuàng)作于2022年6月交叉算子 所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概

8、率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。 SGA中交叉算子采用單點交叉算子。 第二十張，PPT共六十五頁，創(chuàng)作于2022年6月單點交叉運算 交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點第二十一張，PPT共六十五頁，創(chuàng)作于2022年6月變異算子 所謂變異運算，是指依據(jù)變異概率 Pm 將個體編碼串中的某些基因值用其它基因

9、值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。 SGA中變異算子采用基本位變異算子。 第二十二張，PPT共六十五頁，創(chuàng)作于2022年6月基本位變異算子 基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)? 。 第二十三張，PPT共六十五頁，創(chuàng)作于2022年6月基

10、本位變異算子的執(zhí)行過程 變異前：000001110000000010000變異后：000001110001000010000變異點第二十四張，PPT共六十五頁，創(chuàng)作于2022年6月運行參數(shù) （1）M ： 種群規(guī)模 （2）T ： 遺傳運算的終止進化代數(shù) （3）Pc ： 交叉概率 （4）Pm ： 變異概率 第二十五張，PPT共六十五頁，創(chuàng)作于2022年6月SGA的框圖 產(chǎn)生初始群體是否滿足停止準則是輸出結(jié)果并結(jié)束計算個體適應(yīng)度值比例選擇運算單點交叉運算基本位變異運算否產(chǎn)生新一代群體執(zhí)行M/2次第二十六張，PPT共六十五頁，創(chuàng)作于2022年6月3、遺傳算法的特點 （1）群體搜索，易于并行化處理； （

11、2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。第二十七張，PPT共六十五頁，創(chuàng)作于2022年6月二、遺傳算法原理1、遺傳算法的數(shù)學(xué)基礎(chǔ) 2、遺傳算法的收斂性分析 3、遺傳算法的改進 第二十八張，PPT共六十五頁，創(chuàng)作于2022年6月1、遺傳算法的數(shù)學(xué)基礎(chǔ)（1）模式定理 （2）積木塊假設(shè) 第二十九張，PPT共六十五頁，創(chuàng)作于2022年6月模式 模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，即 0 或者 1。 模式示例：10*1第三十張，PPT

12、共六十五頁，創(chuàng)作于2022年6月兩個定義定義1：模式 H 中確定位置的個數(shù)稱為模式 H 的階，記作O(H)。例如O(10*1)=3 。定義2：模式 H 中第一個確定位置和最后一個確定位置之間的距離稱為模式 H 的定義距，記作(H)。例如(10*1)=4 。 第三十一張，PPT共六十五頁，創(chuàng)作于2022年6月模式的階和定義距的含義 模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 第三十二張，PPT共六十五頁，創(chuàng)作于2022年6月模式定理 模式定理：具有低階、短

13、定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學(xué)基礎(chǔ)。 第三十三張，PPT共六十五頁，創(chuàng)作于2022年6月模式定理 從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串數(shù)目，這主要是因為選擇使最好的模式有更多的復(fù)制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當小，因而它對這些重要的模式幾乎沒有影響。 第三十四張，PPT共六十五頁，創(chuàng)作于2022年6月積木塊假設(shè) 積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積

14、木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。 第三十五張，PPT共六十五頁，創(chuàng)作于2022年6月2、遺傳算法的收斂性分析 遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。 第三十六張，PPT共六十五頁，創(chuàng)作于2022年6月種群規(guī)模對收斂性的影響 通常，種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡

15、管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。第三十七張，PPT共六十五頁，創(chuàng)作于2022年6月選擇操作對收斂性的影響 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。第三十八張，PPT共六十五頁，創(chuàng)作于2022年6月交叉概率對收斂性的影響 交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破

16、壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。 第三十九張，PPT共六十五頁，創(chuàng)作于2022年6月變異概率對收斂性的影響 變異操作是對種群模式的擾動，有利于增加種群的多樣性 。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。 第四十張，PPT共六十五頁，創(chuàng)作于2022年6月遺傳算法的本質(zhì) 遺傳算法本質(zhì)上是對染色體模式所進行的一系列運算，即通過選擇算子將當前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進行模式重組，利用變異算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，最終得到問題的最優(yōu)解。 第四十一張，PPT共六十

17、五頁，創(chuàng)作于2022年6月3、遺傳算法的改進 遺傳欺騙問題：在遺傳算法進化過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個局部最優(yōu)解。 第四十二張，PPT共六十五頁，創(chuàng)作于2022年6月遺傳算法的改進途徑（1）對編碼方式的改進 （2）對遺傳算子 的改進（3）對控制參數(shù)的改進 （4）對執(zhí)行策略的改進 第四十三張，PPT共六十五頁，創(chuàng)作于2022年6月對編碼方式的改進 二進制編碼優(yōu)點在于編碼、解碼操作簡單，交叉、變異等操作便于實現(xiàn)，缺點在于精度要求較高時，個體編碼串較長，使算法的搜索空間急劇擴大，遺傳算法的性能降低。格雷編碼

18、克服了二進制編碼的不連續(xù)問題 ，浮點數(shù)編碼改善了遺傳算法的計算復(fù)雜性 。 第四十四張，PPT共六十五頁，創(chuàng)作于2022年6月對遺傳算子 的改進排序選擇 均勻交叉 逆序變異（1） 對群體中的所有個體按其適應(yīng)度大小進行降序排序；（2） 根據(jù)具體求解問題，設(shè)計一個概率分配表，將各個概率值按上述排列次序分配給各個個體；（3） 以各個個體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。 第四十五張，PPT共六十五頁，創(chuàng)作于2022年6月對遺傳算子 的改進排序選擇 均勻交叉 逆序變異（1） 隨機產(chǎn)生一個與個體編碼長度相同的二進制屏蔽字P = W1W2Wn ；（2） 按下

19、列規(guī)則從A、B兩個父代個體中產(chǎn)生兩個新個體X、Y：若Wi = 0，則X的第i個基因繼承A的對應(yīng)基因，Y的第i個基因繼承B的對應(yīng)基因；若Wi = 1，則A、B的第i個基因相互交換，從而生成X、Y的第i個基因。 第四十六張，PPT共六十五頁，創(chuàng)作于2022年6月對遺傳算子 的改進排序選擇 均勻交叉 逆序變異變異前：3 4 8 | 7 9 6 5 | 2 1變異前：3 4 8 | 5 6 9 7 | 2 1第四十七張，PPT共六十五頁，創(chuàng)作于2022年6月對控制參數(shù)的改進 Schaffer建議的最優(yōu)參數(shù)范圍是： M = 20-100， T = 100-500， Pc = 0.4-0.9， Pm =

20、0.001-0.01。 第四十八張，PPT共六十五頁，創(chuàng)作于2022年6月對控制參數(shù)的改進 Srinvivas等人提出自適應(yīng)遺傳算法，即PC和Pm能夠隨適應(yīng)度自動改變，當種群的各個個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，使二者增加，而當種群適應(yīng)度比較分散時，使二者減小，同時對適應(yīng)值高于群體平均適應(yīng)值的個體，采用較低的PC和Pm，使性能優(yōu)良的個體進入下一代，而低于平均適應(yīng)值的個體，采用較高的PC和Pm，使性能較差的個體被淘汰 。第四十九張，PPT共六十五頁，創(chuàng)作于2022年6月對執(zhí)行策略的改進混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法第五十張，PPT共六十五頁，創(chuàng)作于2022年6

21、月三、遺傳算法的應(yīng)用1、遺傳算法的應(yīng)用領(lǐng)域 2、遺傳算法的應(yīng)用示例 第五十一張，PPT共六十五頁，創(chuàng)作于2022年6月1、遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化 （2）函數(shù)優(yōu)化 （3）自動控制 （4）生產(chǎn)調(diào)度 （5）圖像處理 （6）機器學(xué)習 （7）人工生命 （8）數(shù)據(jù)挖掘 第五十二張，PPT共六十五頁，創(chuàng)作于2022年6月遺傳算法應(yīng)用于組合優(yōu)化 隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在計算機上用枚舉法很難甚至不可能求出其最優(yōu)解。實踐證明，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、網(wǎng)絡(luò)路由等具有NP難度的組合優(yōu)化問題上取得了成功的應(yīng)用。 第五十三張，PPT共六十五

22、頁，創(chuàng)作于2022年6月2、遺傳算法的應(yīng)用示例 彈藥裝載問題（Ammunition Loading Problem，簡稱ALP），就是在滿足各類通用彈藥運輸規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍用運輸工具，使得通用彈藥的裝載效率達到最大值的問題。第五十四張，PPT共六十五頁，創(chuàng)作于2022年6月AGSAA的基本原理 在彈藥裝載中，考慮到模擬退火算法的基本思想是跳出局部最優(yōu)解，將模擬退火思想引入遺傳算法，應(yīng)用改進型遺傳算法和模擬退火算法相結(jié)合，構(gòu)建自適應(yīng)遺傳模擬退火算法（AGSAA），從而綜合了全局優(yōu)化和局部搜索的特點，為解決彈藥裝載這一組合優(yōu)化問題提供了新的思路。第五十五張，PPT共

23、六十五頁，創(chuàng)作于2022年6月AGSAA的編碼方式 AGSAA采用二進制編碼方式，每一個二進制位對應(yīng)一個待裝彈藥箱，若為，表示該彈藥箱裝入運輸工具，為則不裝。第五十六張，PPT共六十五頁，創(chuàng)作于2022年6月AGSAA的解碼和適應(yīng)度函數(shù) AGSAA采用彈藥裝載的啟發(fā)式算法來解碼，解碼后最終確定裝入運輸工具的彈藥箱。適應(yīng)度函數(shù)主要考慮兩個方面，即載重率和積載率，對這兩個因素加權(quán)，來計算適應(yīng)度函數(shù)值。第五十七張，PPT共六十五頁，創(chuàng)作于2022年6月彈藥裝載的啟發(fā)式算法 （1）定位規(guī)則（Locating rule） 定位規(guī)則是指用來確定當前待裝彈藥箱在運輸工具剩余裝載空間中擺放位置的規(guī)則。 （2）

24、定序規(guī)則（Ordering rule） 定序規(guī)則是指用來確定彈藥箱放入運輸工具裝載空間先后順序的規(guī)則。第五十八張，PPT共六十五頁，創(chuàng)作于2022年6月遺傳算子的選擇AGSAA的選擇算子采用輪盤賭選擇算子，并結(jié)合最優(yōu)保存策略；變異算子采用基本位變異算子；同時，在變異運算之后，增加退火算子，以增強算法的局部搜索能力；交叉概率和變異概率為自適應(yīng)概率，以提高種群的進化效率。第五十九張，PPT共六十五頁，創(chuàng)作于2022年6月交叉算子的選擇 由于AGSAA是采用將彈藥箱的編號排列成串來進行編碼的，如果個體交叉采用傳統(tǒng)方式進行，就有可能使個體的編碼產(chǎn)生重復(fù)基因（即一個彈藥箱編號在一個個體中出現(xiàn)兩次以上），

25、從而產(chǎn)生不符合條件的個體，因此，AGSAA采用的是部分映射交叉算子。 第六十張，PPT共六十五頁，創(chuàng)作于2022年6月部分映射交叉算子交叉前： 8 7 | 4 3 | 1 2 6 5 1 2 | 5 7 | 8 3 4 6交叉后： 8 3 | 6 7 | 1 2 4 5 1 7 | 6 2 | 8 3 4 5第六十一張，PPT共六十五頁，創(chuàng)作于2022年6月參考文獻1 張偉，李守智，高峰等. 幾種智能最優(yōu)化算法的比較研究. Proceedings of the 24th Chinese Control Conference, Guangzhou, P.R. China July 15-18,

26、2005:131613202馬玉明,賀愛玲,李愛民. 遺傳算法的理論研究綜述. 山東輕工業(yè)學(xué)院學(xué)報, 2004,18(3):77803 Andreas Bortfeldt, Hermann Gehring. A Hybrid Genetic Algorithm for The Container Loading Problem. European Journal of Operational Research, 2001(131):143161.4 D.Y.He, J.Z.Cha. Research on Solution to Complex Container Loading Problem Based on Genetic Algorithm. The First International Conference on Machine Learning and Cybernetics. Beijing-China,2002:7882第六十二張，PPT共六十五