基于初始種群對(duì)遺傳算法的收斂性探討

殷玲玲，蘇劍鋒

(六安職業(yè)技術(shù)學(xué)院，安徽 六安 237000)

0 引言

遺傳算法通過(guò)對(duì)達(dá)爾文提出的自然選擇與進(jìn)化學(xué)說(shuō)進(jìn)行模擬，同時(shí)融合計(jì)算機(jī)算法最終完成可以全局統(tǒng)籌的概率搜索算法.這種算法能夠在解決具體問(wèn)題時(shí)首先圈定一個(gè)先大致潛在解的集合作為概率搜索算法的初始種群.潛在集合一般由計(jì)算機(jī)隨機(jī)生成，數(shù)目統(tǒng)一且每一個(gè)個(gè)體代表不同的計(jì)算機(jī)編碼，其中最優(yōu)解即為初始生成的個(gè)體進(jìn)化得到的，每一個(gè)不同的生物個(gè)體依據(jù)其不同的基因特征生成代碼，以便于我們驗(yàn)證優(yōu)勝劣汰的自然選擇法則.在進(jìn)化過(guò)程中需要保持種群的多樣性使得算法更加精確、科學(xué)，同時(shí)其收斂性也相對(duì)更加準(zhǔn)確，此時(shí)需要設(shè)定小概率的變異事件，使其更加貼近自然選擇的范圍.遺傳算法的收斂性分析和收斂速度的研究一向是研究的重要方向.其中種群的初始分布是最先要考慮的問(wèn)題.林陽(yáng)等人(2017)提出運(yùn)用多種群遺傳算法的逆運(yùn)算方式，同時(shí)引用適應(yīng)度函數(shù)來(lái)提高函數(shù)的收斂速度[1].孫佳正等人(2018)提出統(tǒng)一種群中，依據(jù)缺陷這一要素將種群分為多個(gè)整體，通過(guò)交叉對(duì)比的方式提高算法搜索效率[2].薛愈潔等人(2018)提出利用遺傳算法分類器實(shí)現(xiàn)系統(tǒng)匹配，通過(guò)仿真可以提高算法的精度[3].基于此，可以看出，遺傳算法在解決高峰值和復(fù)雜的函數(shù)問(wèn)題的時(shí)候，并不能保證收斂的速度和最終能收斂到最優(yōu)解，從初始種群的選擇這一角度，能夠知道正確的初始種群構(gòu)造標(biāo)準(zhǔn).

1 初始種群模型模擬

1.1 初始種群收斂性模型

遺傳算法收斂性模擬需要考慮包括種群規(guī)模、變異率在內(nèi)很多的影響因素，這些因素均會(huì)對(duì)算法的收斂速度和概率產(chǎn)生不同的影響.初始種群對(duì)遺傳算法的收斂性的影響，前所做的研究還不多.本次測(cè)試?yán)谜业降碾S機(jī)初始種群的兩種產(chǎn)生方法，對(duì)兩者產(chǎn)生的初始種群(即隨機(jī)數(shù))進(jìn)行統(tǒng)計(jì)和分析，并對(duì)其應(yīng)用于遺傳算法的效果進(jìn)行了測(cè)試.這兩種方法，一種是經(jīng)典的系統(tǒng)自帶的隨機(jī)數(shù)發(fā)生函數(shù)，還有一種是自定義的隨機(jī)數(shù)產(chǎn)生函數(shù).

以下三個(gè)測(cè)試函數(shù)都是要求它們的最大值：

1)f(x)=xsin( 10pix)+ 2.0x=[-1.0,2.0] 最大值為3.850 274

2)f(x)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1) -2.048<=xi<=2.048最大值為3 905

1.2 遺傳算法交叉率與初始種群關(guān)系確定

初始種群產(chǎn)生過(guò)后，需要不斷多次地模擬進(jìn)化過(guò)程，最終才能得出最優(yōu)解的方案.在完成進(jìn)化操作過(guò)程中，個(gè)體在交叉操作之后產(chǎn)生了新個(gè)體，這一新個(gè)體的出現(xiàn)實(shí)際上是在整體空間上完成有效搜索的過(guò)程.交叉概率太大時(shí)，初始種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂.本次試驗(yàn)，就對(duì)交叉率和初始種群的關(guān)系進(jìn)行了分析[4].求最大值：f(x)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1)-2.048<=xi<=2.048最大值為 3 905.926.

1.3 種群規(guī)模與初始種群關(guān)系分析

種群規(guī)模是遺傳算法的一個(gè)參數(shù)，在研究過(guò)程中并沒(méi)有一定的依據(jù)，總是按照經(jīng)驗(yàn)的習(xí)慣來(lái)選取.然而一些研究表明在對(duì)遺傳算法計(jì)算的過(guò)程中需要考慮種群規(guī)模的影響，這是由于不同種群的遺傳模式不同.為了保持算法的準(zhǔn)確性，需要擴(kuò)大種群采樣點(diǎn)，從而提高算法性能，但是采樣點(diǎn)也不宜過(guò)多，如果采樣點(diǎn)過(guò)多則會(huì)增加計(jì)算量，減緩算法的收斂速度[5].因此，隨機(jī)產(chǎn)生的初始種群，需要有一個(gè)合適的種群數(shù)目，來(lái)達(dá)到最有效的利用率.本次實(shí)驗(yàn)，選擇了一個(gè)二維函數(shù)，利用不同的種群規(guī)模進(jìn)行測(cè)試，期望找到種群規(guī)模和初始種群之間的關(guān)系.求最大值：f(x)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1)-2.048<=xi<=2.048最大值為 3 905.926 227.

2 基于種群的遺傳算法數(shù)據(jù)分析

2.1 初始種群對(duì)遺傳算法收斂性數(shù)據(jù)模擬

兩種隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)比較如圖1所示.

圖1 隨機(jī)數(shù)發(fā)生器函數(shù)1的隨機(jī)比較圖

函數(shù)2的變量x1，x2在[-2.048,2.048]之間的分布如圖2所示.

圖2 隨機(jī)數(shù)發(fā)生器函數(shù)2的隨機(jī)比較圖

由圖2可知，系統(tǒng)自帶的隨機(jī)數(shù)發(fā)生器，產(chǎn)生的隨機(jī)數(shù)，在[-2， -1]，[-1 ,0]，[0 ,1]，[1 ,2]之間的分布數(shù)目分別為11,11,13,5個(gè)，計(jì)算分布方差為6，而自定義的隨機(jī)數(shù)發(fā)生器的結(jié)果為9，11，7，13，計(jì)算分布方差為3.33，點(diǎn)的分布更均勻.通過(guò)兩種隨機(jī)數(shù)生成器的比較，系統(tǒng)自帶的隨機(jī)數(shù)發(fā)生器所產(chǎn)生的隨機(jī)數(shù)分布方差過(guò)大，可見(jiàn)數(shù)字的分布并不均勻，而自定的隨機(jī)數(shù)發(fā)生器得到的隨機(jī)數(shù)明顯分布更加均勻.由上述兩種隨機(jī)初始種群產(chǎn)生法的應(yīng)用中，我們可以看出，初始種群分布的均勻性、多樣性，對(duì)遺傳算法的收斂速度有促進(jìn)作用.

2.2 遺傳算法與初始種群交叉率分析

圖3 遺傳算法與初始種群交叉率分析圖

本實(shí)驗(yàn)的進(jìn)化參數(shù)設(shè)置如下：采用二進(jìn)制編碼，適應(yīng)度函數(shù)取函數(shù)體本身.取種群大小為80，染色體長(zhǎng)度為10(精度為6位小數(shù))，初始交叉概率為0.6，變異概率為0.001，迭代100代，獨(dú)立運(yùn)行5次，取平均最大適應(yīng)度.測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果如圖3所示(圖中的橫坐標(biāo)表示進(jìn)化代數(shù)，縱坐標(biāo)表示平均最大適應(yīng)度).

我們對(duì)比圖3，可知該函數(shù)進(jìn)行遺傳操作時(shí)，交叉率較小時(shí)，個(gè)體更新緩慢，使得搜索停滯不前，造成收斂緩慢；隨著交叉概率的提高，搜索加快，個(gè)體更新較快，整體的適應(yīng)度很快提高，使得算法更加平穩(wěn)、較快地收斂于最優(yōu)解.由于交叉率取值過(guò)大，算法在運(yùn)行的過(guò)程中，個(gè)體更新過(guò)快，以至于把較優(yōu)的個(gè)體也淘汰掉，造成了算法早收斂于次優(yōu)解.由上述實(shí)驗(yàn)結(jié)果可知，遺傳算法隨機(jī)產(chǎn)生初始種群，交叉概率太小會(huì)使得算法的不收斂.交叉概率的提高增加了遺傳算法穩(wěn)定、收斂于最優(yōu)解的可能性.不過(guò)，交叉概率太大會(huì)造成收斂到次優(yōu)解.由此可見(jiàn)，隨機(jī)產(chǎn)生的初始種群，在進(jìn)化過(guò)程中，需要選取合適的交叉率，一般來(lái)說(shuō)是0.6～0.75左右，才能提高算法的收斂性.

2.3 種群規(guī)模與初始種群關(guān)系分析

種群規(guī)模與初始種群的關(guān)系函數(shù)實(shí)驗(yàn)結(jié)果：如圖4所示.

圖4 種群規(guī)模與初始種群的關(guān)系函數(shù)圖

本實(shí)驗(yàn)分別選取了種群數(shù)為80，160，320，640，由圖4可知，遺傳操作該函數(shù)時(shí)，隨著種群數(shù)目的增加，算法的收斂逐步接近于最優(yōu)解，收斂速度也提高.不過(guò)在試驗(yàn)的過(guò)程中發(fā)現(xiàn)，種群數(shù)目增加了，算法的運(yùn)算速度也變得緩慢，消耗的資源也變大了.由上述可知，對(duì)于這個(gè)二維函數(shù)，種群規(guī)模的擴(kuò)大增加了其收斂于最優(yōu)解的可能性.隨機(jī)產(chǎn)生的初始種群，有一個(gè)較大的種群規(guī)模，無(wú)疑會(huì)增加算法的收斂速度和收斂質(zhì)量.不過(guò)，種群規(guī)模較大，盡管可以增加優(yōu)化信息，阻止早收斂的發(fā)生，但是無(wú)疑會(huì)增加計(jì)算量，因此確定初始種群的大小需要根據(jù)實(shí)際情況，做適當(dāng)?shù)恼{(diào)整.

3 結(jié)論

通過(guò)對(duì)種群規(guī)模、初始種群與遺傳算法的收斂性的關(guān)系進(jìn)行對(duì)比實(shí)驗(yàn)，從中得出一些規(guī)律，為遺傳算法今后的應(yīng)用提供幫助.同時(shí)，為初始種群方面來(lái)改進(jìn)遺傳算法的收斂性奠定了基礎(chǔ).

通過(guò)研究初始種群對(duì)遺傳算法收斂性影響，我們得出以下結(jié)論：初始種群的均勻分布和多樣性，對(duì)于提高算法收斂速度和概率，有很大幫助.種群分布越均勻，就越有可能找到最優(yōu)解，使得算法更快地得到收斂.種群規(guī)模的確定，需要根據(jù)實(shí)際應(yīng)用的情況來(lái)決定.交叉概率太小，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂；交叉概率太大，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉，造成收斂到次優(yōu)解.為了有利于初始種群的進(jìn)化，有利于算法的收斂性的提高，我們需要選擇合適的交叉率.