算法合集之《遺傳算法的特點(diǎn)及其應(yīng)用》

1、遺傳算法的特點(diǎn)及其應(yīng)用 省、市： 學(xué) 校：復(fù)旦附中 姓 名： 張 寧 IOI2002集訓(xùn)隊(duì)論文1目 錄 遺傳算法的基本概念簡單的遺傳算法 選擇、交換、變異遺傳算法應(yīng)用舉例 子集和問題 TSP(旅行商)問題結(jié)束語2遺傳算法的基本概念遺傳算法（Genetic Algorithms，簡稱GA）根據(jù)適者生存，優(yōu)勝劣汰等自然進(jìn)化規(guī)則來進(jìn)行搜索計(jì)算和問題求解。 對(duì)許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的復(fù)雜問題，特別是優(yōu)化問題，GA提供了一個(gè)行之有效的新途徑。 3簡單的遺傳算法GA把每一個(gè)可能的解編碼為一個(gè)向量，稱為一個(gè)染色體，向量的每一個(gè)元素稱為基因。所有染色體組成群體。并按預(yù)定的目標(biāo)函數(shù)對(duì)每個(gè)染色提進(jìn)行評(píng)價(jià)

2、，根據(jù)其結(jié)果給出一個(gè)適應(yīng)度的值。算法開始時(shí)先隨機(jī)地產(chǎn)生一些染色體，計(jì)算其適應(yīng)度，根據(jù)適應(yīng)度對(duì)諸染色體進(jìn)行選擇、交換、變異等遺傳操作，剔除適應(yīng)度低的染色體，留下適應(yīng)度高的染色體。由于新群體的成員是上一代群體的優(yōu)秀者，因而在總體上優(yōu)于上一代。GA就這樣反復(fù)迭代，直至滿足某種預(yù)定的優(yōu)化指標(biāo)。上述GA的工作過程可用圖1簡要描述。 4選 擇 選擇運(yùn)算使用比較普遍的一種是適應(yīng)度比例法。其實(shí)就是將適應(yīng)度值視為其權(quán)值，權(quán)值大的被選中的概率也大。它與各染色體適應(yīng)度成比例。某一染色體被選中的概率為 式中xi為種群中第i個(gè)染色體對(duì)應(yīng)的數(shù)字串，f(xi)是第i個(gè)染色體的適應(yīng)度值， 是種群中所有染色體的適應(yīng)度值之和。顯

3、然，此法要求染色體的適應(yīng)度應(yīng)為正值。 5交 換 復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體，因此，遺傳算法的開創(chuàng)者提出了交換操作。即：在匹配集中任選兩個(gè)染色體，隨機(jī)選擇一點(diǎn)或多點(diǎn)交換點(diǎn)位置，交換雙親染色體交換點(diǎn)右邊的部分，即可得到兩個(gè)新的染色體數(shù)字串。6變 異 變異運(yùn)算用來模擬生物在自然界的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小概率隨機(jī)地改變遺傳基因的值。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由1變成0，或由0變成1。通過變異操作，可以使搜索能在盡可能大的空間中進(jìn)行，獲得質(zhì)量較高的優(yōu)化解答。 7遺傳算法應(yīng)用舉例子集和問題TSP(旅行商)問題8子

4、集和問題 GA在子集和問題上的應(yīng)用子集和問題SUBSET_SUM：給定正整數(shù)集合S和一個(gè)整數(shù)t，判定是否存在S的一個(gè)子集使得S中整數(shù)的和為t。我們已知道該問題是一個(gè)NP-完全問題。在實(shí)際應(yīng)用中，我們常遇到的是最優(yōu)化子集和問題。在這種情況下，我們要找出S的一個(gè)子集S，使得其和不超過t，但又盡可能接近于t。9子集和問題下面用遺傳算法來解決：我們可以用n位二進(jìn)制數(shù)來表示每個(gè)染色體。每一位，用0、1表示是否屬于子集。 我們將染色體所表示的子集的元素和與所給t的差異記為適應(yīng)度，即令染色體x的每一位為xi，所表示元素的值為Si則 但是經(jīng)過實(shí)踐后發(fā)現(xiàn)由于適應(yīng)度相對(duì)差異較小，使得適應(yīng)度非常接近，難以區(qū)分染色體

5、的優(yōu)劣，使得遺傳進(jìn)化變得非常緩慢，且f(x)可能為負(fù)值，因此還需對(duì)適應(yīng)度函數(shù)做一下變換，才可以適合本題的要求。 令f(k)為當(dāng)前群體中所有染色體適應(yīng)度的最大值 f(x)=|f(k)-f(x)| 所以適應(yīng)度為f (x)。 10子集和問題選擇時(shí)可以用前面所介紹的適應(yīng)度比例法，但可能會(huì)因?yàn)榕既磺闆r使得優(yōu)秀的染色體沒有子孫。因此，我在這里采用確定性選擇法，先計(jì)算群體中每個(gè)串的生存概率 ，1=j=n，然后計(jì)算期望復(fù)制數(shù)ei=Ps*n，式中：n為群體中染色體的數(shù)目。根據(jù)ei的值給每個(gè)染色體串分配一個(gè)復(fù)制數(shù)。交換運(yùn)算與前述相同，不過若進(jìn)行單點(diǎn)交換有可能使得兩個(gè)染色體在交換時(shí)產(chǎn)生的差異過大，使得遺傳變得不穩(wěn)定

6、，優(yōu)秀的染色體不能遺傳到下一代。因此可以采用多點(diǎn)交換。變異運(yùn)算時(shí)，只需注意變異概率的取值，至于具體算法如前面所述。11子集和問題在本題中的一些數(shù)值不妨取值如下：種群長度（染色體個(gè)數(shù)）：20選擇概率：0.9變異概率：0.1結(jié)束條件：當(dāng)前最優(yōu)解在100代遺傳后仍未改變，或已取到最優(yōu)解12TSP(旅行商)問題 GA在TSP（旅行商）問題求解中的應(yīng)用設(shè)存在N個(gè)城市， Dij表示城i與城j之間的距離， Dij=Dji，現(xiàn)在要求一條遍歷所有N個(gè)城市，且不走重復(fù)路的最短路徑（最短哈密爾頓圈）。這是一個(gè)典型NP-完全問題。傳統(tǒng)解法對(duì)此都并不太奏效下面我們?cè)囍眠z傳算法來解決這道題目。13TSP(旅行商)問題我

7、們先采用十進(jìn)制編碼，每個(gè)染色體由按一定順序排列的N個(gè)城市的序號(hào)組成，表示一條可能的旅行路徑。適應(yīng)度為一條旅行路徑對(duì)應(yīng)的距離，路徑越短的染色體適應(yīng)度越高。例如，取N=10，城市代號(hào)為1至10。 例如種群中的染色體：2 8 4 10 5 1 7 3 6 9 表示一條旅行路徑284105173692 其總路徑長 我們可以采用非負(fù)變換，把最小化優(yōu)化目標(biāo)函數(shù)變換為以最大值為目標(biāo)的適應(yīng)度函數(shù)，可以如下定義： 其中cmax為可以取為進(jìn)化過程中路徑長度的最大值，或者為了保證f(x)為正而預(yù)先設(shè)定為一個(gè)與種群無關(guān)的常數(shù)。14TSP(旅行商)問題關(guān)于選擇運(yùn)算，可以考慮前面介紹的確定性選擇法。此處的交換運(yùn)算不同于前

8、，因?yàn)閮蓚€(gè)染色體，若進(jìn)行簡單的交換運(yùn)算，可能會(huì)使得染色體所表示路徑中會(huì)重復(fù)經(jīng)過同一城市，即同一染色體中的兩個(gè)基因有著相同的城市編號(hào)。因此須改進(jìn)交換運(yùn)算。我們可以采用部分匹配交換運(yùn)算（PMX）。 當(dāng)然也可以不進(jìn)行交換運(yùn)算，而直接進(jìn)行變異運(yùn)算，因?yàn)楸纠械淖儺愡\(yùn)算本就隱含了交換的含義。變異操作與二進(jìn)制編碼時(shí)不同，從群體中隨機(jī)抽取一個(gè)染色體，隨機(jī)抽取兩個(gè)基因，將兩者交換，即顛倒城市次序。算法的主要部分已經(jīng)討論完了，但是還有一點(diǎn)值得提出的，由于遺傳算法是一種不斷優(yōu)化的搜索算法，因此，我們可以用貪心算法構(gòu)造初始群。 15TSP(旅行商)問題題目中的一些數(shù)值不妨取值如下：種群長度（染色體個(gè)數(shù)）：20變異概

9、率：0.1結(jié)束條件：當(dāng)前最優(yōu)解在100代遺傳后仍未改變。16遺傳算法應(yīng)用舉例通過兩道例題，我們?cè)谶z傳算法原有簡單定義上，加以擴(kuò)充，介紹了若干高級(jí)遺傳算法在具體實(shí)例中的應(yīng)用，旨在打開思想的局限性，不僅僅在原有簡單定義下做文章，而是充分發(fā)揮想象，對(duì)于不同問題，采取不同對(duì)策，在遺傳算法的框架下，安排使用合理的算法，改進(jìn)原有算法，或與原有算法相結(jié)合。這樣，才能充分發(fā)揮遺傳算法的長處解決問題。 17結(jié) 束 語遺傳算法的原理是簡單的，但是如何熟練運(yùn)用遺傳算法卻并不是一個(gè)簡單的問題，理論要切合實(shí)際，對(duì)于不同問題，遺傳算法要稍加變化，就如同畫龍點(diǎn)睛一般，切忌不可生搬硬套。我認(rèn)為遺傳算法應(yīng)當(dāng)與現(xiàn)有優(yōu)化算法結(jié)合，

10、可產(chǎn)生比單獨(dú)使用遺傳算法或現(xiàn)有優(yōu)化算法更好，更實(shí)用的算法。本文的主要目的還是讓大家對(duì)遺傳算法能夠有一個(gè)初步的了解，這樣對(duì)大家進(jìn)行深入的實(shí)踐是有幫助的。希望大家通過本文的指導(dǎo)，能夠?qū)⑦z傳算法熟練應(yīng)用在各個(gè)方面。 18圖 一 Y問題的初始（侯選）解種群滿足預(yù)定指標(biāo)編碼為染色體（向量）種群P（t）計(jì)算各染色體適應(yīng)度通過遺傳運(yùn)算存優(yōu)去劣種群P（t+1）復(fù)制交換變異種群P（t）種群P（t+1）解碼染色體問題解答空間N圖1 遺傳算法工作原理示意圖19多點(diǎn)交換不過在本例中使用多點(diǎn)交換，只需進(jìn)行兩點(diǎn)交換即可，其實(shí)兩點(diǎn)交換與單點(diǎn)交換是類似的。設(shè)有兩個(gè)父輩染色體A和B： A：110 B：001 設(shè)兩個(gè)交換點(diǎn)選擇如下： A：10100|10010|1110 B：01001|11011|0001 則兩點(diǎn)交換運(yùn)算就是交換染色體A和染色體B，兩個(gè)交換點(diǎn)之間的部分，則交換結(jié)果如下： A：110 B：00120部分匹配交換運(yùn)算部分匹配交換運(yùn)算先在兩父染色體串中各產(chǎn)生兩個(gè)交換點(diǎn)，把這兩點(diǎn)之間的區(qū)域定義為匹配區(qū)域，再對(duì)兩個(gè)匹配區(qū)域中的基因通過對(duì)應(yīng)匹配置換。例如，兩父染色體串為： A： 2 8 4 10 * 5 1 7 3 * 6 9 B： 5 6 7 1 * 10 2 8 3 * 9 4 符號(hào)“*”表示交換點(diǎn)。