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

1、遺傳算法原理及應(yīng)用07計(jì)本計(jì)本張雷張雷070701010116遺傳算法是由美國(guó)的遺傳算法是由美國(guó)的J.Holl教授于教授于1975年在他的專著《自然界和人工系統(tǒng)的年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法算法。遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次遺傳算法模擬自

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

3、索，易于并行化處理；）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。遺傳算法原理：遺傳算法原理：1、遺傳算法的數(shù)學(xué)基礎(chǔ)遺傳算法的數(shù)學(xué)基礎(chǔ)（1）模式定理）模式定理模式定理：具有低階、短定義距以及平均適應(yīng)度模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指

4、數(shù)增長(zhǎng)。模式定理保證了較優(yōu)的模式（遺傳高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng)。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。算法的較優(yōu)解）的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。從模式定從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長(zhǎng)的串?dāng)?shù)目，這主要是因?yàn)檫x擇

5、使最好的模式有更多的復(fù)制，交叉算子不容易破數(shù)增長(zhǎng)的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有更多的復(fù)制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長(zhǎng)的模式，而一般突變概率又相當(dāng)小，因而它對(duì)這些重要的壞高頻率出現(xiàn)的、短定義長(zhǎng)的模式，而一般突變概率又相當(dāng)小，因而它對(duì)這些重要的模式幾乎沒有影響。模式幾乎沒有影響。（2）積木塊假設(shè)）積木塊假設(shè)積木塊假設(shè)：遺傳算法通過(guò)短定義距、低階以積木塊假設(shè)：遺傳算法通過(guò)短定義距、低階以及高平均適應(yīng)度的模式（積木塊）及

6、高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。模，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而使遺傳算法找到全局最優(yōu)解的可能式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。2、遺傳算法的收斂性分析遺傳算法的收斂性

7、分析遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來(lái)防止最優(yōu)解的遺失。與算法收斂性有能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來(lái)防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。3、遺傳算法的改進(jìn)、遺傳算法的改進(jìn)遺傳欺騙問(wèn)題：在遺傳算法進(jìn)化過(guò)程中

8、，有時(shí)會(huì)產(chǎn)生一些超常的個(gè)遺傳欺騙問(wèn)題：在遺傳算法進(jìn)化過(guò)程中，有時(shí)會(huì)產(chǎn)生一些超常的個(gè)體，這些個(gè)體因競(jìng)爭(zhēng)力太突出而控制了選擇運(yùn)算過(guò)程，從而影響算法的全局優(yōu)化性能，導(dǎo)體，這些個(gè)體因競(jìng)爭(zhēng)力太突出而控制了選擇運(yùn)算過(guò)程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個(gè)局部最優(yōu)解。致算法獲得某個(gè)局部最優(yōu)解。遺傳算法的改進(jìn)途徑遺傳算法的改進(jìn)途徑（1）對(duì)編碼方式的改進(jìn)）對(duì)編碼方式的改進(jìn)（2）對(duì)遺傳算子）對(duì)遺傳算子的改進(jìn)的改進(jìn)（3）對(duì)控制參數(shù)的改進(jìn)）對(duì)控制參數(shù)

9、的改進(jìn)（4）對(duì)執(zhí)行策略的改進(jìn)）對(duì)執(zhí)行策略的改進(jìn)遺傳算法的本質(zhì)：遺傳算法本質(zhì)上是對(duì)染色體模式所進(jìn)行的一系列運(yùn)算，即通過(guò)選擇算子遺傳算法的本質(zhì)：遺傳算法本質(zhì)上是對(duì)染色體模式所進(jìn)行的一系列運(yùn)算，即通過(guò)選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過(guò)這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問(wèn)題的最優(yōu)子進(jìn)

10、行模式突變。通過(guò)這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問(wèn)題的最優(yōu)解。解。遺傳算法的應(yīng)用領(lǐng)域遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化）組合優(yōu)化（2）函數(shù)優(yōu)化）函數(shù)優(yōu)化（3）自動(dòng)控制）自動(dòng)控制（4）生產(chǎn)調(diào)度）生產(chǎn)調(diào)度（5）圖像處理）圖像處理（6）機(jī)器學(xué)習(xí)）機(jī)器學(xué)習(xí)（7）人工生命）人工生命（8）數(shù)據(jù)挖掘）數(shù)據(jù)挖掘遺傳算法的應(yīng)用示例遺傳算法的應(yīng)用示例彈藥裝載問(wèn)題（彈藥裝載問(wèn)題（AmmunitionAmmunitionLoadingLoadin

11、gProblemProblem，簡(jiǎn)稱，簡(jiǎn)稱ALPALP），就是在滿足各類通用彈藥運(yùn)輸，就是在滿足各類通用彈藥運(yùn)輸規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍用運(yùn)輸工具，使得通用彈藥的裝載規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍用運(yùn)輸工具，使得通用彈藥的裝載效率達(dá)到最大值的問(wèn)題。效率達(dá)到最大值的問(wèn)題。AGSAAAGSAA的基本原理的基本原理：在彈藥裝載中，考慮到模擬退火算法的基本在彈藥裝載中，考慮到模擬退火算法的基本思想是跳出

12、局部最優(yōu)解，將模擬退火思想引入遺傳算法，應(yīng)用改進(jìn)型遺傳算法和模擬退火思想是跳出局部最優(yōu)解，將模擬退火思想引入遺傳算法，應(yīng)用改進(jìn)型遺傳算法和模擬退火算法相結(jié)合，構(gòu)建自適應(yīng)遺傳模擬退火算法（算法相結(jié)合，構(gòu)建自適應(yīng)遺傳模擬退火算法（AGSAAAGSAA），從而綜合了全局優(yōu)化和局部搜索的，從而綜合了全局優(yōu)化和局部搜索的特點(diǎn)，為解決彈藥裝載這一組合優(yōu)化問(wèn)題提供了新的思路。特點(diǎn)，為解決彈藥裝載這一組合優(yōu)化問(wèn)題提供了新的思路。AGSAAAGSAA采用

13、二進(jìn)制編碼方式，采用二進(jìn)制編碼方式，每一個(gè)二進(jìn)制位對(duì)應(yīng)一個(gè)待裝彈藥箱，若為１，表示該彈藥箱裝入運(yùn)輸工具，為０則不每一個(gè)二進(jìn)制位對(duì)應(yīng)一個(gè)待裝彈藥箱，若為１，表示該彈藥箱裝入運(yùn)輸工具，為０則不裝。裝。AGSAAAGSAA采用彈藥裝載的啟發(fā)式算法來(lái)解碼，解碼后最終確定裝入運(yùn)輸工具的彈藥箱。適應(yīng)采用彈藥裝載的啟發(fā)式算法來(lái)解碼，解碼后最終確定裝入運(yùn)輸工具的彈藥箱。適應(yīng)度函數(shù)主要考慮兩個(gè)方面，即載重率和積載率，對(duì)這兩個(gè)因素加權(quán)，來(lái)計(jì)算適應(yīng)度函數(shù)值。

14、度函數(shù)主要考慮兩個(gè)方面，即載重率和積載率，對(duì)這兩個(gè)因素加權(quán)，來(lái)計(jì)算適應(yīng)度函數(shù)值。（1）定位規(guī)則（）定位規(guī)則（LocatingLocatingrulerule）定位規(guī)則是指用來(lái)確定當(dāng)前待裝彈藥箱在運(yùn)輸工具剩余）定位規(guī)則是指用來(lái)確定當(dāng)前待裝彈藥箱在運(yùn)輸工具剩余裝載空間中擺放位置的規(guī)則。裝載空間中擺放位置的規(guī)則。（2）定序規(guī)則（）定序規(guī)則（deringderingrulerule）定序規(guī)則是指用來(lái)確定彈藥）定序規(guī)則是指用來(lái)確定彈藥箱放入運(yùn)輸工

15、具裝載空間先后順序的規(guī)則。箱放入運(yùn)輸工具裝載空間先后順序的規(guī)則。AGSAAAGSAA的選擇算子采用輪盤賭選擇算子，并結(jié)的選擇算子采用輪盤賭選擇算子，并結(jié)合最優(yōu)保存策略；變異算子采用基本位變異算子；同時(shí)，在變異運(yùn)算之后，增加退火算合最優(yōu)保存策略；變異算子采用基本位變異算子；同時(shí)，在變異運(yùn)算之后，增加退火算子，以增強(qiáng)算法的局部搜索能力；交叉概率和變異概率為自適應(yīng)概率，以提高種群的進(jìn)化子，以增強(qiáng)算法的局部搜索能力；交叉概率和變異概率為自適應(yīng)概

16、率，以提高種群的進(jìn)化效率。效率。由于由于AGSAAAGSAA是采用將彈藥箱的編號(hào)排列成串來(lái)進(jìn)行編碼的，如果個(gè)體交叉采用傳統(tǒng)方式進(jìn)是采用將彈藥箱的編號(hào)排列成串來(lái)進(jìn)行編碼的，如果個(gè)體交叉采用傳統(tǒng)方式進(jìn)行，就有可能使個(gè)體的編碼產(chǎn)生重復(fù)基因（即一個(gè)彈藥箱編號(hào)在一個(gè)個(gè)體中出現(xiàn)兩次以行，就有可能使個(gè)體的編碼產(chǎn)生重復(fù)基因（即一個(gè)彈藥箱編號(hào)在一個(gè)個(gè)體中出現(xiàn)兩次以上）上），從而產(chǎn)生不符合條件的個(gè)體，因此，，從而產(chǎn)生不符合條件的個(gè)體，因此，AGSAAAGS