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

1、遺傳算法原理與應(yīng)用遺傳算法原理與應(yīng)用郭學(xué)會郭學(xué)會20082008年年 10 10 月月報告提綱報告提綱一、遺傳算法概述一、遺傳算法概述 二、遺傳算法原理二、遺傳算法原理三、遺傳算法的應(yīng)用三、遺傳算法的應(yīng)用一、遺傳算法概述1 1、智能優(yōu)化算法智能優(yōu)化算法2 2、基本遺傳算法基本遺傳算法3 3、遺傳算法的特點遺傳算法的特點返回返回返回返回0 . 2)10sin()(xxxf基因型：基因型：1000101110110101000111編碼解碼個體（染色體）基因niiiiFFP1/交叉點交叉點突變點突變點產(chǎn)生初始群體產(chǎn)生初始群體是否滿足停止準則是否滿足停止準則是是輸出結(jié)果并結(jié)束輸出結(jié)果并結(jié)束計算個體適

2、應(yīng)度值計算個體適應(yīng)度值比例選擇運算比例選擇運算單點交叉運算單點交叉運算基本位突變運算基本位突變運算否否產(chǎn)生新一代群體產(chǎn)生新一代群體執(zhí)行執(zhí)行M/2M/2次次返回返回返回返回二、遺傳算法原理1 1、遺傳算法的數(shù)學(xué)基礎(chǔ)遺傳算法的數(shù)學(xué)基礎(chǔ)2 2、遺傳算法的收斂性分析遺傳算法的收斂性分析3 3、遺傳算法的改進遺傳算法的改進返回返回1 1、遺傳算法的數(shù)學(xué)基礎(chǔ)遺傳算法的數(shù)學(xué)基礎(chǔ)返回返回模式的階和定義距的含義模式的階和定義距的含義 模式階用來反映不同模式間確定性模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺就越高，所匹配的樣

3、本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。了這種性質(zhì)的差異。模式定理模式定理返回返回返回返回2 2、遺傳算法的收斂性分析遺傳算法的收斂性分析收斂性的影響收斂性的影響收斂性的影響收斂性的影響收斂性的影響收斂性的影響收斂性的影響收斂性的影響返回返回3 3、遺傳算法的改進遺傳算法的改進遺傳算法的改進途徑遺傳算法的改進途徑（1 1） 對群體中的所有個體對群體中的所有個體按其適應(yīng)度大小進行降序排按其適應(yīng)度大小進行降序排序；序；（2 2） 根據(jù)具體求解問題，根據(jù)具體求解問題，設(shè)計

4、一個概率分配表，將各設(shè)計一個概率分配表，將各個概率值按上述排列次序分個概率值按上述排列次序分配給各個個體；配給各個個體；（3 3） 以各個個體所分配到以各個個體所分配到的概率值作為其遺傳到下一的概率值作為其遺傳到下一代的概率，基于這些概率用代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群賭盤選擇法來產(chǎn)生下一代群體。體。 （1 1） 隨機產(chǎn)生一個與個體隨機產(chǎn)生一個與個體編碼長度相同的二進制屏蔽編碼長度相同的二進制屏蔽字字P = WP = W1 1W W2 2W Wn n ；（2 2） 按下列規(guī)則從按下列規(guī)則從A A、B B兩兩個父代個體中產(chǎn)生兩個新個個父代個體中產(chǎn)生兩個新個體體X X、Y Y：若

5、：若W Wi i = 0 = 0，則，則X X的第的第i i個基因繼承個基因繼承A A的對應(yīng)基因，的對應(yīng)基因，Y Y的第的第i i個基因繼承個基因繼承B B的對應(yīng)基的對應(yīng)基因；若因；若W Wi i = 1 = 1，則，則A A、B B的第的第i i個基因相互交換，從而生成個基因相互交換，從而生成X X、Y Y的第的第i i個基因。個基因。 突變前：突變前：3 4 8 | 7 9 6 5 | 2 13 4 8 | 7 9 6 5 | 2 1突變后：突變后：3 4 8 | 5 6 9 7 | 2 13 4 8 | 5 6 9 7 | 2 1返回返回三、遺傳算法的應(yīng)用1 1、遺傳算法的應(yīng)用領(lǐng)域遺傳算

6、法的應(yīng)用領(lǐng)域2 2、遺傳算法的應(yīng)用示例遺傳算法的應(yīng)用示例3 3、我的研究、我的研究1 1、遺傳算法的應(yīng)用領(lǐng)域遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化）組合優(yōu)化（4）圖像處理）圖像處理返回返回遺傳算法應(yīng)用于組合優(yōu)化遺傳算法應(yīng)用于組合優(yōu)化返回返回返回返回返回返回圖像處理圖像處理返回返回返回返回返回返回2 2、遺傳算法的應(yīng)用示例遺傳算法的應(yīng)用示例 彈藥裝載問題（彈藥裝載問題（Ammunition Loading Problem，簡稱，簡稱ALP），就是在），就是在滿足各類通用彈藥運輸規(guī)程和安全性的滿足各類通用彈藥運輸規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍前提下，如何將一批通用彈藥箱裝入軍用運輸工具

7、，使得通用彈藥的裝載效率用運輸工具，使得通用彈藥的裝載效率達到最大值的問題。達到最大值的問題。AGSAA的基本原理的基本原理在彈藥裝載中，考慮到模擬退火算法在彈藥裝載中，考慮到模擬退火算法的基本思想是跳出局部最優(yōu)解，將模擬退的基本思想是跳出局部最優(yōu)解，將模擬退火思想引入遺傳算法，應(yīng)用改進型遺傳算火思想引入遺傳算法，應(yīng)用改進型遺傳算法和模擬退火算法相結(jié)合，構(gòu)建自適應(yīng)遺法和模擬退火算法相結(jié)合，構(gòu)建自適應(yīng)遺傳模擬退火算法（傳模擬退火算法（AGSAAAGSAA），從而綜合了全），從而綜合了全局優(yōu)化和局部搜索的特點，為解決彈藥裝局優(yōu)化和局部搜索的特點，為解決彈藥裝載這一組合優(yōu)化問題提供了新的思路。載這一

8、組合優(yōu)化問題提供了新的思路。AGSAA的編碼方式的編碼方式AGSAAAGSAA采用二進制編碼方式，每一個二采用二進制編碼方式，每一個二進制位對應(yīng)一個待裝彈藥箱，若為，表進制位對應(yīng)一個待裝彈藥箱，若為，表示該彈藥箱裝入運輸工具，為則不裝。示該彈藥箱裝入運輸工具，為則不裝。AGSAA的解碼和適應(yīng)度函數(shù)的解碼和適應(yīng)度函數(shù)AGSAAAGSAA采用彈藥裝載的啟發(fā)式算法來解采用彈藥裝載的啟發(fā)式算法來解碼，解碼后最終確定裝入運輸工具的彈藥碼，解碼后最終確定裝入運輸工具的彈藥箱。適應(yīng)度函數(shù)主要考慮兩個方面，即載箱。適應(yīng)度函數(shù)主要考慮兩個方面，即載重率和積載率，對這兩個因素加權(quán)，來計重率和積載率，對這兩個因素加

9、權(quán)，來計算適應(yīng)度函數(shù)值。算適應(yīng)度函數(shù)值。彈藥裝載的啟發(fā)式算法彈藥裝載的啟發(fā)式算法（1 1）定位規(guī)則（）定位規(guī)則（Locating ruleLocating rule） 定位規(guī)則是指用來確定當前待裝彈藥箱在定位規(guī)則是指用來確定當前待裝彈藥箱在運輸工具剩余裝載空間中擺放位置的規(guī)則。運輸工具剩余裝載空間中擺放位置的規(guī)則。 （2 2）定序規(guī)則（）定序規(guī)則（Ordering ruleOrdering rule） 定序規(guī)則是指用來確定彈藥箱放入運輸工定序規(guī)則是指用來確定彈藥箱放入運輸工具裝載空間先后順序的規(guī)則。具裝載空間先后順序的規(guī)則。遺傳算子的選擇遺傳算子的選擇AGSAAAGSAA的選擇算子采用輪盤賭選

10、擇算的選擇算子采用輪盤賭選擇算子，并結(jié)合最優(yōu)保存策略；突變算子采子，并結(jié)合最優(yōu)保存策略；突變算子采用基本位突變算子；同時，在突變運算用基本位突變算子；同時，在突變運算之后，增加退火算子，以增強算法的局之后，增加退火算子，以增強算法的局部搜索能力；交叉概率和突變概率為自部搜索能力；交叉概率和突變概率為自適應(yīng)概率，以提高種群的進化效率。適應(yīng)概率，以提高種群的進化效率。交叉算子的選擇交叉算子的選擇 由于由于AGSAAAGSAA是采用將彈藥箱的編號排列成是采用將彈藥箱的編號排列成串來進行編碼的，如果個體交叉采用串來進行編碼的，如果個體交叉采用傳統(tǒng)方式傳統(tǒng)方式進行，就有可能使個體的編碼產(chǎn)生進行，就有可能

11、使個體的編碼產(chǎn)生重復(fù)基因重復(fù)基因（即（即一個彈藥箱編號在一個個體中出現(xiàn)兩次以一個彈藥箱編號在一個個體中出現(xiàn)兩次以上上），從而產(chǎn)生），從而產(chǎn)生不符合條件的個體不符合條件的個體，因此，因此，AGSAAAGSAA采用的是采用的是部分映射交叉算子部分映射交叉算子。部分映射交叉算子部分映射交叉算子交叉前：交叉前： 8 7 | 4 3 | 1 2 6 58 7 | 4 3 | 1 2 6 5交叉后：交叉后： 8 3 | 6 7 | 1 2 4 58 3 | 6 7 | 1 2 4 5返回返回返回返回適應(yīng)性函數(shù)適應(yīng)性函數(shù)是計算出每條染色體的適應(yīng)值。在本研究中，染色體若其適應(yīng)值較大者，表示該排課結(jié)果擁有較多較佳授課時段，將會被給予較大的生存概率于下一代演化中。首先建立每位教師的授課時段優(yōu)先度，如表1所示，可由教師填入自己較喜歡的時段及其喜好程度，該表格將提供做適應(yīng)性使用，其中3代表最喜歡的授課時段，2代表較喜歡的授課時段，1代表