遺傳進(jìn)化算法課件

1、第5章 遺傳進(jìn)化算法基本概念、基本原理、基本算法第1頁(yè)，共41頁(yè)。達(dá)爾文的生物進(jìn)化論與遺傳算法遺傳生命之特征或性狀的傳承 染色體（chromosome) DNA (deoxyribonucleic acid) RNA (ribonucleic acid) 雙螺旋結(jié)構(gòu) 基因(gene) 四進(jìn)制編碼（A,T,C,G) 復(fù)制(reproduction) 交叉(crossover) 變異(mutation)第2頁(yè)，共41頁(yè)。達(dá)爾文的生物進(jìn)化論與遺傳算法 進(jìn)化“物競(jìng)天擇，優(yōu)勝劣汰，適者生存”遺傳信息（基因）寓于染色體，染色體決定生物特征，特征決定對(duì)環(huán)境的適應(yīng)度。遺傳與進(jìn)化之過(guò)程均發(fā)生在DNA之上。遺傳通

2、過(guò)繁殖完成，繁殖由基因復(fù)制實(shí)現(xiàn)，復(fù)制的基本方式是交叉重組。交叉與變異產(chǎn)生新的物種，變異是物種進(jìn)化的保證。適應(yīng)度決定物種的存活，適應(yīng)性強(qiáng)者遺傳機(jī)會(huì)更大。競(jìng)爭(zhēng)是物種進(jìn)化的促進(jìn)劑。有競(jìng)爭(zhēng)就有選擇，自然選擇是進(jìn)化的基本規(guī)律第3頁(yè)，共41頁(yè)。遺傳進(jìn)化算法的基本概念編碼、個(gè)體與種群 (encoding, individual and population)適應(yīng)度函數(shù) (fitness function)選擇算子 (selection operator) 交叉算子 (crossover operator) 變異算子 (mutation operator)第4頁(yè)，共41頁(yè)。遺傳編碼 (genetic enco

3、ding)二進(jìn)制編碼灰度編碼可拼接/可分解編碼實(shí)數(shù)編碼可變精度實(shí)數(shù)編碼符號(hào)編碼混亂編碼混合編碼第5頁(yè)，共41頁(yè)。編碼(encoding)與解碼(decoding)式中A 所表示的有限字符串稱(chēng)為優(yōu)化變量X 的遺傳（染色體）編碼，記為 ,A 中的字符稱(chēng)為基因，字符所有可能的取值稱(chēng)為等位基因，L 稱(chēng)為編碼長(zhǎng)度；X 稱(chēng)為A 的解碼，記為 。編碼的重要性： 1）基因的排列決定遺傳操作的作用方式； 2）決定搜索的難度與復(fù)雜性； 3）決定問(wèn)題求解的精度。第6頁(yè)，共41頁(yè)。個(gè)體空間與種群空間一個(gè)問(wèn)題可行解的遺傳編碼稱(chēng)為個(gè)體，或者說(shuō)一群染色體的組合稱(chēng)為個(gè)體設(shè) 表示等位基因， 為給定的編碼長(zhǎng)度，則所有基因可能排列

4、成的編碼構(gòu)成整個(gè)個(gè)體空間對(duì)任何正整數(shù) m，乘積 稱(chēng)為m 階種群空間，其中的元素稱(chēng)為 m 階種群個(gè)體空間中的一群個(gè)體稱(chēng)為一個(gè)種群第7頁(yè)，共41頁(yè)。與編碼相關(guān)的定義1）編碼格式 e 是從HL 到 的一個(gè)映射，且對(duì)任何 ， 存在唯一 與之對(duì)應(yīng)的解碼 ；2）當(dāng)且僅當(dāng)任何 唯一對(duì)應(yīng)一個(gè)個(gè)體A，則稱(chēng)編碼格式是正則的；3）如果一個(gè)L 編碼 和一個(gè)K 編碼 的拼接 有意義且是一個(gè)L+K碼，則稱(chēng)其為是可拼接的；反之則稱(chēng)之為是可分解的 設(shè)個(gè)體空間為：其可行解空間為：第8頁(yè)，共41頁(yè)。二進(jìn)制編碼二進(jìn)制編碼：以字符0和1為等位基因的定長(zhǎng)字符串編碼。對(duì)實(shí)數(shù)xi 給定編碼精度 ，取 mi 為滿足 的最小整數(shù)，則 mi 長(zhǎng)

5、的0-1字符串唯一對(duì)應(yīng)實(shí)數(shù)xi ，定義為：設(shè)且第9頁(yè)，共41頁(yè)。二進(jìn)制編碼示例Xi 的 二進(jìn)制編碼個(gè)體： 0000000000000 0 0000000000001 0.0009767 0001000100010 1.0880438 1111111111111 8.0001497設(shè) 則mi =13，從中任選n個(gè)個(gè)體可構(gòu)成一個(gè)種群,任選m次就可構(gòu)成m個(gè)種群第10頁(yè)，共41頁(yè)。二進(jìn)制編碼的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：二進(jìn)制編碼簡(jiǎn)明、通用、易于各種進(jìn)化操作。缺點(diǎn)：不具備正則性，可能破壞可行解空間的拓?fù)溥B續(xù)性。 對(duì)于高維、連續(xù)優(yōu)化問(wèn)題存在離散化誤差，高精度要求 將產(chǎn)生很長(zhǎng)的編碼；不便于表達(dá)反映所求問(wèn)題的特定知識(shí)。例如

6、:在整數(shù)集0,10中的數(shù)7和8最鄰近，但它們的二進(jìn)制編碼0111和1000的海明距離為4，最遠(yuǎn).海明距離：兩染色體編碼所有相應(yīng)位置中取不同數(shù)值的位置數(shù)第11頁(yè)，共41頁(yè)?；叶染幋a假定已有二進(jìn)制編碼： 其修正（灰度）編碼：兩者相互轉(zhuǎn)換公式：即：其中 表示異或運(yùn)算，即：第12頁(yè)，共41頁(yè)。二進(jìn)制與灰度編碼轉(zhuǎn)換示例二進(jìn)制編碼 0 1 1 1 (7), 1 0 0 0 (8), 1 0 1 1 (11), 1 1 0 0 (12), 前兩個(gè)編碼的海明距離為4, 后兩個(gè)編碼海明距離為3.其相應(yīng)灰度編碼為0 0 1 1, 1 0 1 1, 1 0 0 1, 1 1 0 1, 顯然前后兩個(gè)編碼的海明距離均為

7、1, 新編碼保持了原空間的連續(xù)性.其灰度變換計(jì)算: 其逆變換計(jì)算:第13頁(yè)，共41頁(yè)。個(gè)基因，和分別表示第表示染色體，這里表示染色體的第個(gè)基因解空間的上限和下限。實(shí)數(shù)與二進(jìn)制的混合編碼設(shè)第14頁(yè)，共41頁(yè)。采用混合編碼產(chǎn)生初始種群的算法如下：隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù) ，實(shí)數(shù)與二進(jìn)制的混合編碼 ；(2) ,重復(fù) N 次，就產(chǎn)生一個(gè)染色體(3)重復(fù)步驟(1)、(2)M次，就產(chǎn)生一個(gè)包含 M 個(gè)染色 體的初始種群。第15頁(yè)，共41頁(yè)。適應(yīng)度函數(shù)(fitness function)1）對(duì)應(yīng)某種生物群體在給定環(huán)境下的適應(yīng)性度量；2）優(yōu)化變量X對(duì)應(yīng)生物群體中的個(gè)體；3）遺傳進(jìn)化對(duì)應(yīng)于實(shí)現(xiàn)該優(yōu)化過(guò)程的演化過(guò)程。

8、適應(yīng)度函數(shù)是評(píng)價(jià)群體中個(gè)體好壞的標(biāo)準(zhǔn)，是模擬自然選擇的唯一依據(jù)。從而適應(yīng)度函數(shù)選取的優(yōu)劣直接影響遺傳算法的收斂速度及能否找到最優(yōu)解。第16頁(yè)，共41頁(yè)。適應(yīng)度函數(shù)的設(shè)計(jì)原則早熟現(xiàn)象：遺傳算法運(yùn)行初期階段，群體中或許會(huì)出現(xiàn)適應(yīng)度極好的個(gè)體，最終這些個(gè)體可能會(huì)充斥整個(gè)群體，使用于產(chǎn)生新個(gè)體作用較大的交叉操作失去作用，從而使得群體的多樣性降低，遺傳算法提前收斂到某個(gè)局部最優(yōu)解。適應(yīng)度函數(shù)的選取應(yīng)盡量的避免早熟現(xiàn)象，即縮小適應(yīng)度較高的個(gè)體與其他個(gè)體適應(yīng)度之間的差異，限制其復(fù)制數(shù)量以維護(hù)群體的多樣性 第17頁(yè)，共41頁(yè)。適應(yīng)度函數(shù)的設(shè)計(jì)原則退化現(xiàn)象：遺傳算法運(yùn)行后期階段，群體越來(lái)越集中，個(gè)體之間的差異減

9、小，相互之間的競(jìng)爭(zhēng)力也隨即減弱。這必然造成個(gè)體被選擇到下一代中的概率接近，使進(jìn)化過(guò)程失去競(jìng)爭(zhēng)力，退化為隨機(jī)選擇過(guò)程。適應(yīng)度函數(shù)的選取應(yīng)該克服這種退化現(xiàn)象，使算法在運(yùn)行后期階段能夠擴(kuò)大最佳個(gè)體適應(yīng)度與其它個(gè)體適應(yīng)度之間的差異，提高個(gè)體之間的競(jìng)爭(zhēng)性。第18頁(yè)，共41頁(yè)。適應(yīng)度函數(shù)的常用變換線性尺度變換乘冪尺度變換指數(shù)尺度變換第19頁(yè)，共41頁(yè)。適應(yīng)度函數(shù)設(shè)計(jì)舉例 設(shè)計(jì)一個(gè)分段的非線性變換的適應(yīng)度函數(shù) 這里 , 表示變換過(guò)后的適應(yīng)度函數(shù)； 表示種群的適應(yīng)度比例值 、 、 和 均為常數(shù)。其中 的主要作用一方面用于保證 恒為正，另一方面調(diào)控不同個(gè)體被選擇的概率； 為冪指數(shù)，可在1-1.2之間選擇； 、

10、為0-1的實(shí)數(shù)，是不同函數(shù)的切換條件。第20頁(yè)，共41頁(yè)。選擇算子 (selection operator)模擬“優(yōu)勝劣汰、適者生存”自然進(jìn)化原理決定父代種群中個(gè)體以多大可能被選中遺傳到下一代的進(jìn)化操作。選擇原則：1）依據(jù)適應(yīng)度評(píng)價(jià)； 2）選擇最優(yōu)個(gè)體； 3）避免無(wú)效搜索； 4）快速搜索到最優(yōu)解。定義：選擇算子 S 是一個(gè)隨機(jī)映射，它滿足： 第21頁(yè)，共41頁(yè)。選擇算子 (selection operator)比例選擇（輪盤(pán)賭選擇）變尺度比例選擇杰出者選擇期望生存數(shù)選擇確定式采樣選擇排序選擇Boltzmann局部退火選擇種群偏差度選擇排除算子選擇基于正交表的選擇第22頁(yè)，共41頁(yè)。比例選擇第2

11、3頁(yè)，共41頁(yè)。輪盤(pán)賭選擇（Roulette Wheel Selection） 每一個(gè)染色體適應(yīng)度函數(shù)值決定其在輪盤(pán)上面積的大小。此面積大小與輪盤(pán)總面積的比率就染色體被挑選至下一代之概率，也就是在輪盤(pán)上任意取n點(diǎn)，面積比率較大者，選擇并復(fù)制至交叉池（Mating Pool）的個(gè)體數(shù)相對(duì)較多。 P1P2PNPN-1第24頁(yè)，共41頁(yè)。輪盤(pán)賭選擇示例設(shè)有四個(gè)染色體Cll，C24，C310，C415，其適應(yīng)度函數(shù)（Fitness Function）為 F（X）X ，相應(yīng)之適應(yīng)函數(shù)值為f11，f24，f310，f415，占據(jù)輪盤(pán)的面積，Pcl1/300.03，Pc24/300.13， Pc310/30

12、0.33，Pc415/300.51，其中Cl與C2所占比率較小，可能在下一代被C3及C4所取代。第25頁(yè)，共41頁(yè)。交叉算子 (crossover operator)定義：模擬生物的自然進(jìn)化過(guò)程中，兩個(gè)同源染色體通過(guò)交配重組形成新染色體，產(chǎn)生新個(gè)體和物種的進(jìn)化操作，稱(chēng)為交叉算子。交叉操作步驟：1. 從種群個(gè)體中分別任意選取兩個(gè)個(gè)體組成母體對(duì)。2. 對(duì)任一母體對(duì)獨(dú)立重復(fù)實(shí)施交叉操作生成子代個(gè)體。第26頁(yè)，共41頁(yè)。交叉算子 (crossover operator)單點(diǎn)交叉多點(diǎn)交叉均勻交叉洗牌交叉部分匹配交叉順序交叉循環(huán)交叉第27頁(yè)，共41頁(yè)。單點(diǎn)交叉在母體個(gè)體變量排序中任選一交叉點(diǎn)，并以該點(diǎn)為分

13、界相互交換交叉點(diǎn)后的變量，形成新的子代個(gè)體。例如： 母?jìng)€(gè)體對(duì)： 1 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 子代個(gè)體對(duì)： 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 1第28頁(yè)，共41頁(yè)。順序交叉兩個(gè)母體交叉時(shí)，通過(guò)選擇母體1的一部分，并保留母體2中相應(yīng)碼位的相對(duì)順序，而生成子個(gè)體。順序交叉操作能保留母體的排列并融合不同排列的有序結(jié)構(gòu)單元。 母?jìng)€(gè)體對(duì)： 1 2 3 4 5 6 7 8 9 4 5 2 1 8 7 6 9 3 子代個(gè)體對(duì)的兩個(gè)交叉點(diǎn)之間的中間段保持不變： X X X|4 5 6 7|X X X X X|1 8 7

14、 6|X X 子個(gè)體1由2的排序93-452-1876中去掉中間段4567獲得 2 1 8|4 5 6 7|9 3 子個(gè)體2由1的排序89-1234-567之間去掉中間段1876獲得 3 4 5|1 8 7 6|9 2 第29頁(yè)，共41頁(yè)?？勺兙鹊慕徊嬖趯?shí)數(shù)編碼的兩個(gè)母體交叉時(shí)，首先選擇一個(gè)交換點(diǎn)，然后將母體兩個(gè)染色體交叉點(diǎn)右邊的部分交換，接著再計(jì)算交換點(diǎn)的線性組合，這樣產(chǎn)生兩個(gè)新的子代個(gè)體。即： 母體對(duì)： 子代個(gè)體對(duì)： 其中： 分別表示第個(gè)基因解空間的上限和下限， 是一個(gè)隨機(jī)數(shù)， 新的基因由隨機(jī)變量和產(chǎn)生，由于在不同的代中，它的值是不同的，所以基因取值精度就可以擴(kuò)展。 第30頁(yè)，共41頁(yè)。

15、變異算子 (mutation operator)定義：模擬種群內(nèi)部分個(gè)體染色體中基因發(fā)生突變，產(chǎn)生新的個(gè)體和物種的進(jìn)化操作，稱(chēng)為變異（突變）算子。變異的作用是可以恢復(fù)一些在遺傳進(jìn)化過(guò)程中丟失的部分基因，增加種群內(nèi)個(gè)體的多樣性，避免進(jìn)化的早熟和局部收斂。操作步驟： 1）在母體經(jīng)過(guò)交叉產(chǎn)生的子代個(gè)體中按一定（極小的）概率挑選出少量的個(gè)體； 2）對(duì)挑選出的個(gè)體中的部分基因，按一定的方式進(jìn)行變異，產(chǎn)生新的物種。第31頁(yè)，共41頁(yè)。變異算子 (mutation operator)點(diǎn)變異均勻變異正態(tài)變異非一致變異大規(guī)模反饋式突變第32頁(yè)，共41頁(yè)。二進(jìn)制編碼的點(diǎn)變異按某一概率獨(dú)立地改變個(gè)體的某幾位基因的進(jìn)

16、化操作 變異前的個(gè)體 1 1 0 0 1 0 1 1 1 0 1 1 變異后的個(gè)體 1 1 1 1 1 1 1 1 0 0 1 0 種群中選擇進(jìn)行變異的個(gè)體的概率一般很小大約0.01-0.001,因此對(duì)優(yōu)秀的個(gè)體的影響較小. 第33頁(yè)，共41頁(yè)。實(shí)數(shù)編碼的高精細(xì)變異變異時(shí)，單個(gè)染色體的兩個(gè)基因被隨機(jī)地選擇進(jìn)行凸組合的變異。假設(shè)染色體: 的第i個(gè)基因和第k個(gè)基因被選擇進(jìn)行變異，變異生成新的染色體為: 其中 ， 兩個(gè)基因分別為： 這里 為隨機(jī)數(shù)， 。 這種變異方式的目的就是為了增強(qiáng)變異的精細(xì)調(diào)節(jié)能力。第34頁(yè)，共41頁(yè)。大規(guī)模反饋式突變采用輪盤(pán)賭選擇和最優(yōu)個(gè)體保存策略，隨著進(jìn)化的進(jìn)行，某些好的個(gè)體

17、產(chǎn)生的后代越來(lái)越多，整個(gè)種群適應(yīng)度也越來(lái)越高，這時(shí)種群中基因的多樣性變得越來(lái)越差,以至于進(jìn)化進(jìn)行非常緩慢甚至完全停滯，種群陷入早熟。大規(guī)模反饋式突變,就是用隨機(jī)生成的新的個(gè)體代替通過(guò)突變被消滅的個(gè)體，可以大大提高種群的多樣性，同時(shí)保持了種群大小的穩(wěn)定。 假設(shè)通過(guò)反饋式突變的產(chǎn)生的新的染色體的數(shù)目為L(zhǎng)，那么就利用混合編碼的方式隨機(jī)產(chǎn)生L個(gè)新的染色體，代替種群中原來(lái)適應(yīng)度值排在最后的L個(gè)染色體。第35頁(yè)，共41頁(yè)。Step1.（編碼與初始化）確定種群規(guī)模，交叉與變異概率，初始種群隨機(jī)生成；Step2.（個(gè)體評(píng)價(jià)）估計(jì)種群中各個(gè)體的適應(yīng)度；Step3.（種群進(jìn)化） 3.1 選擇（母體） 3.2 交叉

18、 依交叉概率形成中間個(gè)體； 3.3 變異 對(duì)中間個(gè)體依變異概率執(zhí)行變異，形成候選個(gè)體； 3.4 選擇（子代）從候選個(gè)體中依適應(yīng)度選擇合適個(gè)體組成新種群；Step4. （終止校驗(yàn)）滿足終止準(zhǔn)則，輸出最優(yōu)解，否則繼續(xù)轉(zhuǎn)步3。標(biāo)準(zhǔn)遺傳進(jìn)化算法的基本運(yùn)算過(guò)程(Holland1969, De Jong1975, Goldberg1989)第36頁(yè)，共41頁(yè)。計(jì)算的典型執(zhí)行技巧研究：搜索機(jī)理研究：收斂性理論研究：復(fù)雜性理論研究；有效性理論研究。遺傳進(jìn)化算法的基本理論研究在原始的遺傳算法中存在著早熟收斂、收斂速度慢、計(jì)算效率低、精度不高、搜索能力弱、容易陷入局部最優(yōu)等問(wèn)題，因此展開(kāi)如下眾多基本理論研究。第37頁(yè)，共41頁(yè)。遺傳計(jì)算的典型執(zhí)行技巧適應(yīng)值共享策略并行（群體分組、搜索空間分解）實(shí)現(xiàn)策略混合（神經(jīng)網(wǎng)絡(luò)、梯度下降、列表尋優(yōu)、貪婪變換）策略自適應(yīng)（穩(wěn)態(tài)、動(dòng)態(tài)、混合編碼、選擇）策略；第38頁(yè)，共41