遺傳算法原理與應(yīng)用專題知識專家講座

遺傳算法原理與應(yīng)用唐慧豐年5月遺傳算法原理與應(yīng)用專題知識專家講座第1頁匯報提要一、遺傳算法概述二、遺傳算法原理三、遺傳算法應(yīng)用遺傳算法原理與應(yīng)用專題知識專家講座第2頁一、遺傳算法概述1、智能優(yōu)化算法2、基本遺傳算法3、遺傳算法特點遺傳算法原理與應(yīng)用專題知識專家講座第3頁1、智能優(yōu)化算法智能優(yōu)化算法又稱為當(dāng)代啟發(fā)式算法，是一個含有全局優(yōu)化性能、通用性強、且適合于并行處理算法。這種算法普通含有嚴(yán)密理論依據(jù)，而不是單純憑借教授經(jīng)驗，理論上能夠在一定時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。遺傳算法原理與應(yīng)用專題知識專家講座第4頁慣用智能優(yōu)化算法（1）遺傳算法（GeneticAlgorithm，簡稱GA）（2）模擬退火算法（SimulatedAnnealing，簡稱SA）（3）禁忌搜索算法（TabuSearch，簡稱TS）……遺傳算法原理與應(yīng)用專題知識專家講座第5頁智能優(yōu)化算法特點它們共同特點：都是從任一解出發(fā)，按照某種機制，以一定概率在整個求解空間中探索最優(yōu)解。因為它們能夠把搜索空間擴展到整個問題空間，因而含有全局優(yōu)化性能。遺傳算法原理與應(yīng)用專題知識專家講座第6頁遺傳算法起源遺傳算法是由美國J.Holland教授于1975年在他專著《自然界和人工系統(tǒng)適應(yīng)性》中首先提出，它是一類借鑒生物界自然選擇和自然遺傳機制隨機化搜索算法。遺傳算法原理與應(yīng)用專題知識專家講座第7頁遺傳算法搜索機制遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)個體，利用遺傳算子(選擇、交叉和變異)對這些個體進(jìn)行組合，產(chǎn)生新一代候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。

遺傳算法原理與應(yīng)用專題知識專家講座第8頁2、基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出一個最基本遺傳算法，其遺傳進(jìn)化操作過程簡單，輕易了解，是其它一些遺傳算法雛形和基礎(chǔ)。遺傳算法原理與應(yīng)用專題知識專家講座第9頁基本遺傳算法組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運行參數(shù)遺傳算法原理與應(yīng)用專題知識專家講座第10頁編碼GA是經(jīng)過某種編碼機制把對象抽象為由特定符號按一定次序排成串。正如碩士物遺傳是從染色體著手，而染色體則是由基因排成串。SGA使用二進(jìn)制串進(jìn)行編碼。遺傳算法原理與應(yīng)用專題知識專家講座第11頁函數(shù)優(yōu)化示例求以下一元函數(shù)最大值：

x∈[-1,2]，求解結(jié)果準(zhǔn)確到6位小數(shù)。遺傳算法原理與應(yīng)用專題知識專家講座第12頁SGA對于本例編碼

因為區(qū)間長度為3，求解結(jié)果準(zhǔn)確到6位小數(shù)，所以可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222，所以本例二進(jìn)制編碼長度最少需要22位，本例編碼過程實質(zhì)上是將區(qū)間[-1，2]內(nèi)對應(yīng)實數(shù)值轉(zhuǎn)化為一個二進(jìn)制串（b21b20…b0）。遺傳算法原理與應(yīng)用專題知識專家講座第13頁幾個術(shù)語基因型：1000101110110101000111表現(xiàn)型：0.637197編碼解碼個體（染色體）基因遺傳算法原理與應(yīng)用專題知識專家講座第14頁初始種群SGA采取隨機方法生成若干個個體集合，該集合稱為初始種群。初始種群中個體數(shù)量稱為種群規(guī)模。遺傳算法原理與應(yīng)用專題知識專家講座第15頁適應(yīng)度函數(shù)

遺傳算法對一個個體（解）好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程驅(qū)動力，也是進(jìn)行自然選擇唯一標(biāo)準(zhǔn)，它設(shè)計應(yīng)結(jié)合求解問題本身要求而定。遺傳算法原理與應(yīng)用專題知識專家講座第16頁選擇算子遺傳算法使用選擇運算來實現(xiàn)對群體中個體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高個體被遺傳到下一代群體中概率大；適應(yīng)度低個體，被遺傳到下一代群體中概率小。選擇操作任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采取輪盤賭選擇方法。遺傳算法原理與應(yīng)用專題知識專家講座第17頁輪盤賭選擇方法輪盤賭選擇又稱百分比選擇算子，它基本思想是：各個個體被選中概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個體i適應(yīng)度為Fi，則個體i被選中遺傳到下一代群體概率為：遺傳算法原理與應(yīng)用專題知識專家講座第18頁輪盤賭選擇方法實現(xiàn)步驟（1）計算群體中全部個體適應(yīng)度函數(shù)值（需要解碼）；（2）利用百分比選擇算子公式，計算每個個體被選中遺傳到下一代群體概率；（3）采取模擬賭盤操作（即生成0到1之間隨機數(shù)與每個個體遺傳到下一代群體概率進(jìn)行匹配）來確定各個個體是否遺傳到下一代群體中。遺傳算法原理與應(yīng)用專題知識專家講座第19頁交叉算子所謂交叉運算，是指對兩個相互配正確染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新個體。交叉運算是遺傳算法區(qū)分于其它進(jìn)化算法主要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體主要方法。SGA中交叉算子采取單點交叉算子。遺傳算法原理與應(yīng)用專題知識專家講座第20頁單點交叉運算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點遺傳算法原理與應(yīng)用專題知識專家講座第21頁變異算子所謂變異運算，是指依據(jù)變異概率Pm將個體編碼串中一些基因值用其它基因值來替換，從而形成一個新個體。遺傳算法中變異運算是產(chǎn)生新個體輔助方法，它決定了遺傳算法局部搜索能力，同時保持種群多樣性。交叉運算和變異運算相互配合，共同完成對搜索空間全局搜索和局部搜索。SGA中變異算子采取基本位變異算子。遺傳算法原理與應(yīng)用專題知識專家講座第22頁基本位變異算子基本位變異算子是指對個體編碼串隨機指定某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進(jìn)制編碼符號串所表示個體，若需要進(jìn)行變異操作某一基因座上原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。遺傳算法原理與應(yīng)用專題知識專家講座第23頁基本位變異算子執(zhí)行過程變異前：000001110000000010000變異后：000001110001000010000變異點遺傳算法原理與應(yīng)用專題知識專家講座第24頁運行參數(shù)（1）M：種群規(guī)模（2）T：遺傳運算終止進(jìn)化代數(shù)（3）Pc：交叉概率（4）Pm：變異概率遺傳算法原理與應(yīng)用專題知識專家講座第25頁SGA框圖產(chǎn)生初始群體是否滿足停頓準(zhǔn)則是輸出結(jié)果并結(jié)束計算個體適應(yīng)度值百分比選擇運算單點交叉運算基本位變異運算否產(chǎn)生新一代群體執(zhí)行M/2次遺傳算法原理與應(yīng)用專題知識專家講座第26頁3、遺傳算法特點（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件約束，適用范圍很廣。遺傳算法原理與應(yīng)用專題知識專家講座第27頁二、遺傳算法原理1、遺傳算法數(shù)學(xué)基礎(chǔ)2、遺傳算法收斂性分析3、遺傳算法改進(jìn)遺傳算法原理與應(yīng)用專題知識專家講座第28頁1、遺傳算法數(shù)學(xué)基礎(chǔ)（1）模式定理（2）積木塊假設(shè)遺傳算法原理與應(yīng)用專題知識專家講座第29頁模式模式是指種群個體基因串中相同樣板，它用來描述基因串中一些特征位相同結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個字符集(0,1,*)字符串，符號*代表任意字符，即0或者1。

模式示例：10**1遺傳算法原理與應(yīng)用專題知識專家講座第30頁兩個定義定義1：模式H中確定位置個數(shù)稱為模式H階，記作O(H)。比如O(10**1)=3。定義2：模式H中第一個確定位置和最終一個確定位置之間距離稱為模式H定義距，記作δ(H)。比如δ(10**1)=4。遺傳算法原理與應(yīng)用專題知識專家講座第31頁模式階和定義距含義模式階用來反應(yīng)不一樣模式間確定性差異，模式階數(shù)越高，模式確實定性就越高，所匹配樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同模式，也會有不一樣性質(zhì)，而模式定義距就反應(yīng)了這種性質(zhì)差異。遺傳算法原理與應(yīng)用專題知識專家講座第32頁模式定理模式定理：含有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度模式在子代中呈指數(shù)增加。模式定理確保了較優(yōu)模式（遺傳算法較優(yōu)解）數(shù)目呈指數(shù)增加，為解釋遺傳算法機理提供了數(shù)學(xué)基礎(chǔ)。遺傳算法原理與應(yīng)用專題知識專家講座第33頁模式定理從模式定理可看出，有高平均適應(yīng)度、短定義距、低階模式，在連續(xù)后代里取得最少以指數(shù)增加串?dāng)?shù)目，這主要是因為選擇使最好模式有更多復(fù)制，交叉算子不輕易破壞高頻率出現(xiàn)、短定義長模式，而普通突變概率又相當(dāng)小，因而它對這些主要模式幾乎沒有影響。遺傳算法原理與應(yīng)用專題知識專家講座第34頁積木塊假設(shè)積木塊假設(shè)：遺傳算法經(jīng)過短定義距、低階以及高平均適應(yīng)度模式（積木塊），在遺傳操作下相互結(jié)合，最終靠近全局最優(yōu)解。模式定理確保了較優(yōu)模式樣本數(shù)呈指數(shù)增加，從而使遺傳算法找到全局最優(yōu)解可能性存在；而積木塊假設(shè)則指出了在遺傳算子作用下，能生成全局最優(yōu)解。遺傳算法原理與應(yīng)用專題知識專家講座第35頁2、遺傳算法收斂性分析遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能抵達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來預(yù)防最優(yōu)解遺失。與算法收斂性相關(guān)原因主要包含種群規(guī)模、選擇操作、交叉概率和變異概率。遺傳算法原理與應(yīng)用專題知識專家講座第36頁種群規(guī)模對收斂性影響通常，種群太小則不能提供足夠采樣點，以致算法性能很差；種群太大，盡管能夠增加優(yōu)化信息，阻止早熟收斂發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度遲緩。遺傳算法原理與應(yīng)用專題知識專家講座第37頁選擇操作對收斂性影響選擇操作使高適應(yīng)度個體能夠以更大概率生存，從而提升了遺傳算法全局收斂性。假如在算法中采取最優(yōu)保留策略，即將父代群體中最正確個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。遺傳算法原理與應(yīng)用專題知識專家講座第38頁交叉概率對收斂性影響交叉操作用于個體對，產(chǎn)生新個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值個體很快被破壞掉；概率太小時，交叉操作極少進(jìn)行，從而會使搜索停滯不前，造成算法不收斂。遺傳算法原理與應(yīng)用專題知識專家講座第39頁變異概率對收斂性影響變異操作是對種群模式擾動，有利于增加種群多樣性。不過，變異概率太小則極難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。遺傳算法原理與應(yīng)用專題知識專家講座第40頁遺傳算法本質(zhì)遺傳算法本質(zhì)上是對染色體模式所進(jìn)行一系列運算，即經(jīng)過選擇算子將當(dāng)前種群中優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。經(jīng)過這些遺傳操作，模式逐步向很好方向進(jìn)化，最終得到問題最優(yōu)解。遺傳算法原理與應(yīng)用專題知識專家講座第41頁3、遺傳算法改進(jìn)遺傳坑騙問題：在遺傳算法進(jìn)化過程中，有時會產(chǎn)生一些超常個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法全局優(yōu)化性能，造成算法取得某個局部最優(yōu)解。遺傳算法原理與應(yīng)用專題知識專家講座第42頁遺傳算法改進(jìn)路徑（1）對編碼方式改進(jìn)（2）對遺傳算子改進(jìn)（3）對控制參數(shù)改進(jìn)（4）對執(zhí)行策略改進(jìn)遺傳算法原理與應(yīng)用專題知識專家講座第43頁對編碼方式改進(jìn)二進(jìn)制編碼優(yōu)點在于編碼、解碼操作簡單，交叉、變異等操作便于實現(xiàn)，缺點在于精度要求較高時，個體編碼串較長，使算法搜索空間急劇擴大，遺傳算法性能降低。格雷編碼克服了二進(jìn)制編碼不連續(xù)問題，浮點數(shù)編碼改進(jìn)了遺傳算法計算復(fù)雜性。遺傳算法原理與應(yīng)用專題知識專家講座第44頁對遺傳算子改進(jìn)排序選擇均勻交叉逆序變異（1）對群體中全部個體按其適應(yīng)度大小進(jìn)行降序排序；（2）依據(jù)詳細(xì)求解問題，設(shè)計一個概率分配表，將各個概率值按上述排列次序分配給各個個體；（3）以各個個體所分配到概率值作為其遺傳到下一代概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。遺傳算法原理與應(yīng)用專題知識專家講座第45頁對遺傳算子改進(jìn)排序選擇均勻交叉逆序變異（1）隨機產(chǎn)生一個與個體編碼長度相同二進(jìn)制屏蔽字P=W1W2…Wn；（2）按以下規(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個基因。

遺傳算法原理與應(yīng)用專題知識專家講座第46頁對遺傳算子改進(jìn)排序選擇均勻交叉逆序變異變異前：348|7965|21變異前：348|5697|21遺傳算法原理與應(yīng)用專題知識專家講座第47頁對控制參數(shù)改進(jìn)Schaffer提議最優(yōu)參數(shù)范圍是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

遺傳算法原理與應(yīng)用專題知識專家講座第48頁對控制參數(shù)改進(jìn)Srinvivas等人提出自適應(yīng)遺傳算法，即PC和Pm能夠隨適應(yīng)度自動改變，當(dāng)種群各個個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，使二者增加，而當(dāng)種群適應(yīng)度比較分散時，使二者減小，同時對適應(yīng)值高于群體平均適應(yīng)值個體，采取較低PC和Pm，使性能優(yōu)良個體進(jìn)入下一代，而低于平均適應(yīng)值個體，采取較高PC和Pm，使性能較差個體被淘汰。遺傳算法原理與應(yīng)用專題知識專家講座第49頁對執(zhí)行策略改進(jìn)混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法遺傳算法原理與應(yīng)用專題知識專家講座第50頁三、遺傳算法應(yīng)用1、遺傳算法應(yīng)用領(lǐng)域2、遺傳算法應(yīng)用示例遺傳算法原理與應(yīng)用專題知識專家講座第51頁1、遺傳算法應(yīng)用領(lǐng)域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）自動控制（4）生產(chǎn)調(diào)度（5）圖像處理（6）機器學(xué)習(xí)（7）人工生命（8）數(shù)據(jù)挖掘遺傳算法原理與應(yīng)用專題知識專家講座第52頁遺傳算法應(yīng)用于組合優(yōu)化伴隨問題規(guī)模增大，組合優(yōu)化問題搜索空間也急劇擴大，有時在計算機上用枚舉法極難甚至不可能求出其最優(yōu)解。實踐證實，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、網(wǎng)絡(luò)路由等含有NP難度組合優(yōu)化問題上取得了成功應(yīng)用。遺傳算法原理與應(yīng)用專題知識專家講座第53頁2、遺傳算法應(yīng)用示例彈藥裝載問題（AmmunitionLoadingProblem，簡稱ALP），就是在滿足各類通用彈藥運輸規(guī)程和安全性前提下，怎樣將一批通用彈藥箱裝入軍用運輸工具，使得通用彈藥裝載效率到達(dá)最大值問題。遺傳算法原理與應(yīng)用專題知識專家講座第54頁AGSAA基本原理在彈藥裝載中，考慮到模擬退火算法基本思想是跳出局部最優(yōu)解，將模擬退火思想引入遺傳算法，應(yīng)用改進(jìn)型遺傳算法和模擬退火算法相結(jié)合，構(gòu)建自適應(yīng)遺傳模擬退火算法（AGSAA），從而綜合了全局優(yōu)化和局部搜索特點，為處理彈藥裝載這一組合優(yōu)化問題提供了新思緒。遺傳算法原理與應(yīng)用專題知識專家講座第55頁AGSAA編碼方式AGSAA采取二進(jìn)制編碼方式，每一個二進(jìn)制位對應(yīng)一個待裝彈藥箱，若為１，表示該彈藥箱裝入運輸工具，為０則不裝。遺傳算法原理與應(yīng)用專題知識專家講座第56頁AGSAA解碼和適應(yīng)度函數(shù)AGSAA采取彈藥裝載啟發(fā)式算法來解碼，解碼后最終確定裝入運輸工具彈藥箱。適應(yīng)度函數(shù)主要考慮兩個方面，即載重率和積載率，對這兩個原因加權(quán)，來計算適應(yīng)度函數(shù)值。遺傳算法原理與應(yīng)用專題知識專家講座第57頁彈藥裝載啟發(fā)式算法（1）定位規(guī)則（Locatingrule）定位規(guī)則是指用來確定當(dāng)前待裝彈藥箱在運輸工具剩下裝載空間中擺放位置規(guī)則。（2）定序規(guī)則（Orderingrule）定序規(guī)則是指用來確定彈藥箱放入運輸工具裝載空間先后次序規(guī)則。遺傳算法原理與應(yīng)用專題知識專家講座第58頁遺傳算子選擇AGSAA選擇算子采取輪盤賭選擇算子，并結(jié)合最優(yōu)保留策略；變異算子采取基本位變異算子；同時，在變異運算之后，增加退火算子，以增強算法局部搜索能力；交叉概率和變異概率為自適應(yīng)概率，以提升種群進(jìn)化效率。遺傳算法原理與應(yīng)用專題知識專家講座第59頁交叉算子選擇因為AGSAA是采取將彈藥箱編號排列成串來進(jìn)行編碼，假如個體交叉采取傳統(tǒng)方式進(jìn)行，就有可能使個體編碼產(chǎn)生重復(fù)基因（即一個彈藥箱編號在一個個體中出現(xiàn)兩次以上），從而產(chǎn)生不符合條件個體，所以，AGSAA采取是部分映射交叉算子。遺傳算法原理與應(yīng)用專題知識專家講座第60頁部分映射交叉算子交叉前：87|43|126512|57|8346交叉后：83|67|124517|62|8345遺傳算法原理與應(yīng)用專題知識專家講座第61頁參考文件1張偉，李守智，高峰等.幾個智能最優(yōu)化算法比較研究.Proceedingsofthe24thChineseControlConference,Guangzhou,P.R.ChinaJuly15-18,:1316～13202馬玉明,賀愛玲,李愛民.遺傳算法理論研究綜述.山東輕工業(yè)學(xué)院學(xué)報,,18(3):77～803AndreasBortfeldt,HermannGehring.AHybridGeneticAlgorithmforTheContainerLoadingProblem.EuropeanJournalofOperationalResearch,(131):143～161.4D.Y.He,J.Z.Cha.ResearchonSolutiontoComplexContainerLoadingProblemBasedonGeneticAlgorithm.TheFirstInternationalCon