遺傳算法的改進(jìn)

1、 遺傳算法的改進(jìn)王晶北京工業(yè)大學(xué)應(yīng)用數(shù)理學(xué)院(100022E-mail:wangjing820617摘要: 標(biāo)準(zhǔn)的遺傳算法對(duì)種群的進(jìn)化實(shí)施統(tǒng)一的交叉變異操作。本文引入了生物進(jìn)化過程中的漸變與突變機(jī)制,提出按適應(yīng)度大小將種群分為適應(yīng)度高的漸變種群和適應(yīng)度低的突變種群的方法,對(duì)不同種群采用不同交叉變異算子,使得種群的進(jìn)化能達(dá)到全局最優(yōu)解而不陷入局部極值;同時(shí)改進(jìn)的子代種群生成的方法保證了每代種群的多樣性。數(shù)值實(shí)驗(yàn)表明改進(jìn)的遺傳算法可以減少種群進(jìn)化的代數(shù),提高算法的效率,保證了算法的全局收斂性。關(guān)鍵詞:標(biāo)準(zhǔn)遺傳算法(SGA,漸變種群,突變種群中圖分類號(hào): TP183文獻(xiàn)標(biāo)識(shí)碼: A1. 引言遺傳算法

2、最初是由美國(guó)的J.Holland教授于1975年在他的專著自然界和人工系統(tǒng)的適應(yīng)性1中提出的,它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。遺傳算法通過模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因變異的現(xiàn)象2,在每次迭代中都保留一組候選解,并按一定的指標(biāo)從種群中選取較優(yōu)的個(gè)體,并利用遺傳算子3(選擇、交叉和變異對(duì)這些個(gè)體進(jìn)行組合,產(chǎn)生新一代的候選種群,重復(fù)此過程,直到滿足某種收斂指標(biāo)為止。遺傳算法由于其操作簡(jiǎn)單,目前已在復(fù)雜函數(shù)優(yōu)化、生產(chǎn)調(diào)度、圖像識(shí)別、機(jī)器學(xué)習(xí)等眾多領(lǐng)域都獲得了成功的應(yīng)用。然而標(biāo)準(zhǔn)的遺傳算法又有很多弊端:如部分個(gè)體過分早熟使種群陷入局部極值點(diǎn);局部搜索能力差

3、;若干步迭代之后由于種群過分相似而降低了交叉算子的效率;降低了收斂的速度等。本文針對(duì)標(biāo)準(zhǔn)遺傳算法6中存在的一些缺點(diǎn)提出了采用模擬自然界進(jìn)化過程中同時(shí)存在漸變和突變的機(jī)制,將種群按適應(yīng)度的高低分為適應(yīng)度高的漸變種群和適應(yīng)度低的突變種群,對(duì)于漸變種群其可能已經(jīng)接近局部最優(yōu)解,因此我們控制交叉和變異算子使個(gè)體做較小改變,加強(qiáng)局部搜索,以保證目標(biāo)函數(shù)在局部達(dá)到最優(yōu)值;而對(duì)于突變種群的交叉變異算子使個(gè)體進(jìn)行較大的改變,不斷引入新的優(yōu)秀個(gè)體,保證種群的多樣性,從而避免個(gè)別個(gè)體早熟使算法陷入局部極值而收斂不到全局最優(yōu)值。2. 改進(jìn)的遺傳算法標(biāo)準(zhǔn)的遺傳算法應(yīng)有如下幾部分組成:(1編碼(產(chǎn)生初始種群(2適應(yīng)度函

4、數(shù)(3遺傳算子(選擇、交叉、變異(4運(yùn)行參數(shù)。以下分別介紹本文對(duì)標(biāo)準(zhǔn)遺傳算法各部分的改進(jìn)。1.編碼與初始種群的產(chǎn)生:常用的遺傳算法采用的是二進(jìn)制編碼,由于二進(jìn)制編碼具有容易進(jìn)行交叉變異操作的特點(diǎn),編碼的原則是二進(jìn)制碼通過解碼函數(shù)解碼后能與實(shí)值的取值范圍相對(duì)應(yīng)。初始種群的構(gòu)造就是利用隨機(jī)數(shù)發(fā)生器隨機(jī)地產(chǎn)生一系列方案,然后以此為基礎(chǔ)進(jìn)行迭代。-1- 2. 選擇算子:遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰的操作,適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大;適應(yīng)度低的個(gè)體,被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代種群中選取一些個(gè)體,遺傳到下一代群體。標(biāo)準(zhǔn)遺傳算法中

5、選擇算子采用輪盤賭選擇方法,個(gè)體適應(yīng)度越大,其被選中的概率就越高,反之亦然。按(F =n i i i i F F P 1/i為第i 個(gè)個(gè)體的適應(yīng)度計(jì)算出群體中各個(gè)個(gè)體選擇概率后,就可以決定那些個(gè)體被選出。但是,由于該方法是基于概率的選擇,存在統(tǒng)計(jì)誤差。同時(shí)在種群進(jìn)化過程中,有時(shí)會(huì)產(chǎn)生一些超常的個(gè)體,這些個(gè)體因競(jìng)爭(zhēng)力太突出而控制了選擇運(yùn)算過程,從而影響算法的全局優(yōu)化性能,導(dǎo)致算法獲得某個(gè)局部最優(yōu)解。本文所提出的選擇算子是直接通過不同的父代種群來構(gòu)造子代種群的過程。方法如下:父代的部分最佳個(gè)體及經(jīng)過漸變進(jìn)化的優(yōu)秀個(gè)體可以直接進(jìn)入下一代;部分次優(yōu)個(gè)體和突變進(jìn)化后的優(yōu)秀個(gè)體可以進(jìn)入下一代。這樣的種群構(gòu)

6、造方式不僅保證了優(yōu)秀個(gè)體可以保留同時(shí)保證了各代種群的多樣性,降低了種群之間的相似性,提高了交叉操作了效率。適應(yīng)度高低排序高 低 -2-適應(yīng)度排序圖1 種群進(jìn)化結(jié)構(gòu)圖 3. 交叉操作:所謂交叉運(yùn)算4,是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率Pc 按某種方式相互交換其部分基因,從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征,它在遺傳算法中起關(guān)鍵作用,是產(chǎn)生新個(gè)體的主要方法。常用的交叉算子有單點(diǎn)交叉,兩點(diǎn)交叉等。 單點(diǎn)交叉:兩點(diǎn)交叉交叉前:交叉前:00000|01110000000010000 00000|0111000000001|000011100|0000011111100

7、0101 11100|0000011111100|0101 交叉后:交叉后:00000|00000111111000101 00000|0000011111100|000011100|01110000000010000 11100|0111000000001|0101由于我們將種群分為了漸變種群和突變種群,為了使?jié)u變種群能夠達(dá)到局部最優(yōu),因此我們依據(jù)交叉概率Pc對(duì)漸變種群做兩點(diǎn)交叉的交叉操作,以減小其改變量,使其在最優(yōu)解鄰域內(nèi)做局部搜索;對(duì)于突變種群為保證其能在整體范圍內(nèi)尋優(yōu),我們可以采用再次隨機(jī)產(chǎn)生新個(gè)體的方法,使其以大概率與突變種群的個(gè)體做交叉操作,通過不斷引入新個(gè)體,使種群做較大的改變。

8、4.變異算子:所謂變異運(yùn)算,是指依據(jù)變異概率Pm將個(gè)體編碼串中的某些基因值用其它基因值來替換,從而形成一個(gè)新的個(gè)體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法,它決定了遺傳算法的局部搜索能力,同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合,共同完成對(duì)搜索空間的全局搜索和局部搜索。標(biāo)準(zhǔn)遺傳算法中變異算子采用基本位變異算子。如二進(jìn)制編碼符號(hào)串所表示的個(gè)體若需要進(jìn)行變異操作方法如下:即某一基因座上的原有基因值為0,則變異操作將其變?yōu)?;反之,若原有基因值為1,則變異操作將其變?yōu)?。0000001110000000010000變異后0000000110000000010000通過如上變異我們發(fā)現(xiàn),

9、二進(jìn)制各基因位所表現(xiàn)出的位權(quán)重不一樣,導(dǎo)致變異后解增量的是不同的,如二進(jìn)制串0110,若第一位變異(為0111,串值改變量是1,而第四位變異后(為1110,串值改變量是8,變異越往高位,串值的改變量越大,結(jié)果可能導(dǎo)致接近最優(yōu)點(diǎn)的個(gè)體遺漏。因此在變異操作時(shí)我們要求漸變種群以變異概率做較少的基本位變異,且控制變異區(qū)的權(quán)重較小,避免串值的改變量太大,導(dǎo)致接近最優(yōu)點(diǎn)的個(gè)體遺漏;對(duì)于突變種群,我們?cè)试S多個(gè)基因位以變異概率同時(shí)變異且變異位不受限制。5.參數(shù)控制:遺傳算法的運(yùn)行需要很多參數(shù)進(jìn)行控制,參數(shù)的不同可能導(dǎo)致收斂的速度與效率,尤其是本算法中有更多的可控因素。M:種群規(guī)模;T:遺傳運(yùn)算的終止進(jìn)化代數(shù);

10、Pc:交叉概率;Pm:變異概率等。Schaffer建議的最優(yōu)參數(shù)范圍是:M = 20-100,T = 100-500,Pc = 0.4-0.9,Pm = 0.001-0.01。本文所提出的漸變種群與突變種群的交叉變異概率可根據(jù)具體問題做適當(dāng)調(diào)整。如使突變種群的變異概率為漸變種群變異概率的2倍。3. 改進(jìn)的遺傳算法收斂性分析遺傳算法本質(zhì)上是對(duì)染色體模式所進(jìn)行的一系列運(yùn)算,即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中,利用交叉算子進(jìn)行模式重組,利用變異算子進(jìn)行模式變異。通過這些遺傳操作,模式逐步向較好的方向進(jìn)化,最終得到問題的最優(yōu)解。本文所提出的針-3- -4-對(duì)漸變和突變種群實(shí)施不同的

11、交叉變異操作的方法提高了算法的效率,加快了全局最優(yōu)解收斂的速率5,具體分析如下:(1 選擇操作對(duì)收斂性的影響改進(jìn)的選擇操作保證了每代種群的多樣性,降低了個(gè)體之間的相似度,使高適應(yīng)度的父代個(gè)體能夠從直接進(jìn)入子代,進(jìn)化后的較優(yōu)個(gè)體也可以進(jìn)入子代,解決了標(biāo)準(zhǔn)遺傳算法中經(jīng)過若干代后種群內(nèi)個(gè)體高度相似缺點(diǎn);使種群可以收斂到的全局最優(yōu)解。本方法對(duì)于復(fù)雜的多峰多谷的函數(shù)求最值具有較好的效果。(2 交叉操作對(duì)收斂性的影響交叉操作用于個(gè)體對(duì),產(chǎn)生新的個(gè)體,實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。漸變種群的交叉操作保證了種群中個(gè)體不至于更新很快,不會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉;突變種群的交叉操作,保證了交叉的有效性

12、,從而不會(huì)使搜索停滯不前,造成算法的不收斂,或陷入局部最優(yōu)解。(3 變異操作對(duì)收斂性的影響變異操作是對(duì)種群模式的擾動(dòng),有利于增加種群的多樣性。漸變種群的變異保證了最佳個(gè)體漸進(jìn)達(dá)到局部最就解,增強(qiáng)了個(gè)體的局部搜索能力;突變種群的變異保證了新模式的產(chǎn)生,保證種群的多樣性。從而保證了最終達(dá)到全局最優(yōu)解。 4. 數(shù)值實(shí)驗(yàn)為驗(yàn)證本文所提出的改進(jìn)的遺傳算法的有效性,下面給出與標(biāo)準(zhǔn)遺傳算法對(duì)比的實(shí)驗(yàn)結(jié)果。本實(shí)驗(yàn)測(cè)試程序是作者用C +編程語(yǔ)言開發(fā)的。(1 測(cè)試函數(shù):max f (x 1,x 2=100(x 12-x 22+(1-x 12-2.048<=x 1,x 2<=2.048(2 采用二進(jìn)制編

13、碼,x 1,x 2對(duì)應(yīng)的染色體長(zhǎng)度均為10(3 解碼函數(shù):4.096*CodeValue/1023.0-2.048(4 測(cè)試中的參數(shù) 交叉概率:pc =0.8,變異概率:pm =0.08(5 測(cè)試函數(shù)的性質(zhì):此函數(shù)有兩個(gè)局部極大點(diǎn),分別是f (2.0048,-2.048=3897.734227對(duì)應(yīng)的編碼為11111111110000000000;f (-2.0048,-2.048=3905.926227 對(duì)應(yīng)的編碼為00000000000000000000 ;后者為全局極大點(diǎn)。一般的遺傳算法常常陷入前者局部極值點(diǎn),但改進(jìn)后的算法明顯提高了全局極值點(diǎn)的收斂概率,降低了種群進(jìn)化的代數(shù)表1 標(biāo)準(zhǔn)遺傳

14、算法與改進(jìn)遺傳算法比較標(biāo)準(zhǔn)遺傳算法(SGA 改進(jìn)的遺傳算法 種群大小 收斂全局極值概率平均進(jìn)化代數(shù) 收斂全局極值概率平均進(jìn)化代數(shù)80 31% 205 53% 81150 55% 103 90% 51 200 80% 49 98% 23 5. 結(jié)束語(yǔ)通過數(shù)值實(shí)驗(yàn)可以發(fā)現(xiàn)本文所提出的方法,使得漸變種群在局部最優(yōu)解附近做逼近搜索,突變種群通過不斷引入新個(gè)體,在全局范圍內(nèi)搜索最優(yōu)值。與標(biāo)準(zhǔn)遺傳算法相比本方法可以減少種群進(jìn)化的代數(shù);增強(qiáng)了個(gè)體的局部搜索能力;提高了算法的效率;保證了算法達(dá)到全局最優(yōu)解;對(duì)于復(fù)雜的多峰多谷函數(shù)尋求最優(yōu)值具有良好的效果。參考文獻(xiàn)1J.Holland. 自然界和人工系統(tǒng)的適應(yīng)性

15、.19752Srinivas M,Patnaik L M. 遺傳算法中的自適應(yīng)交叉和變異概率J IEEE系統(tǒng). 人和控制論學(xué)報(bào),1994, 24(4:656667(英文版3鄭金華,葉正華,蒙祖強(qiáng)等. 基于空間交配的遺傳算法J. 模式識(shí)別與人工智能,2003,16(4:4824854陳小平,于盛林. 實(shí)數(shù)遺傳算法交叉策略的改進(jìn). 電子學(xué)報(bào),2003:31(15李茂軍,童調(diào)生. 單親遺傳算法的全局收斂性分析. 自動(dòng)化學(xué)報(bào),1999,25(1:2680.6焦李成,保錚. 進(jìn)化計(jì)算與遺傳算法-計(jì)算智能的新方向. 系統(tǒng)工程與電子技術(shù),1995(6:2032The improvement of genet

16、ic algorithmWang JingBeijing University Of Technology (100022AbstractThe standard genetic algorithm carried out uniform cross - mutation implementation on populations. This paper introduces an improved genetic algorithm. According to the difference of fitness of the population, we carry out different cross - mutation implementation on populations. Numerical expe