龐 博

（赤峰工業(yè)職業(yè)技術(shù)學(xué)院 赤峰 024000）

1 引言

遺傳算法（Genetic Algorithm，GA）作為一種隨機(jī)仿生優(yōu)化算法，自20世紀(jì)70年代由Holland教授提出以來，經(jīng)過數(shù)十年的發(fā)展，在理論仿真與工程實(shí)際中均取得了良好表現(xiàn)［1］。遺傳算法通過對待優(yōu)化問題編碼，隨機(jī)初始化群體，模仿自然界生物進(jìn)化機(jī)制，按照“優(yōu)勝劣汰”原則對群體進(jìn)行選擇、交叉、變異操作，逐步得到問題最優(yōu)解或次優(yōu)解，從而解決用常規(guī)數(shù)學(xué)方法難以解決的問題。標(biāo)準(zhǔn)遺傳算法主要通過遺傳操作選擇與產(chǎn)生新個(gè)體進(jìn)而實(shí)現(xiàn)進(jìn)化，但各操作方式都存在隨機(jī)性大導(dǎo)致優(yōu)化速度和優(yōu)化精度較差的問題。為此，許多學(xué)者分別在編碼［2］、適應(yīng)度函數(shù)［3］、初始群體［4～5］、選擇［6］、交叉［7～9］、變異［10～11］等方面進(jìn)行改進(jìn)；有學(xué)者將其它算法與遺傳算法相結(jié)合［12］，優(yōu)勢互補(bǔ)，取得了良好效果。本文在分析了標(biāo)準(zhǔn)遺傳算法的不足及相關(guān)文獻(xiàn)之后，提出一種基于完全均勻設(shè)計(jì)的并行變異遺傳算法（Uniform Design-Parallel Mutation GA，UD-PMGA），力圖用相對簡單的思想實(shí)現(xiàn)遺傳算法的高效搜索，通過測試函數(shù)仿真與比較，驗(yàn)證了算法的有效性。

2 初始化群體

初始群體的多樣性對算法的全局收斂及尋優(yōu)速度都有重要影響，因此，產(chǎn)生均勻分布的初始群體成為眾多學(xué)者的研究內(nèi)容。正交設(shè)計(jì)與均勻設(shè)計(jì)是初始群體均勻化的主流方法［4～5］。正交設(shè)計(jì)法由于試驗(yàn)數(shù)等于水平數(shù)的平方，因此要保證較高的水平數(shù)以實(shí)現(xiàn)高精度的初始化，其群體規(guī)模必然呈平方倍增長，基于區(qū)域分解組合思想的方法也不能從本質(zhì)上降低計(jì)算量，造成計(jì)算量難以承受；如果采用較低的水平數(shù)，則初始群體的均勻性無法保證。均勻設(shè)計(jì)的水平數(shù)等于試驗(yàn)數(shù)，因此更適于遺傳算法的群體初始化。

文獻(xiàn)［13］以中心偏差作為目標(biāo)函數(shù)，用改進(jìn)的遺傳算法獲得均勻性良好的均勻設(shè)計(jì)表。但其計(jì)算量過大，且算法復(fù)雜難以實(shí)現(xiàn)普遍應(yīng)用。文獻(xiàn)［14］為均勻設(shè)計(jì)表的設(shè)計(jì)提供了簡單實(shí)用的Matlab程序，只需要輸入水平數(shù)和因素?cái)?shù)，就可得到相應(yīng)的多個(gè)中心偏差很小的均勻矩陣。本文根據(jù)文獻(xiàn)［14］的方法生成均勻設(shè)計(jì)表UM，將基因的定義域均分為size（群體規(guī)模）個(gè)區(qū)間，取每個(gè)區(qū)間的中值作為水平值，群體規(guī)模等于水平數(shù)，即均勻矩陣的行數(shù)，問題的維數(shù)即基因的個(gè)數(shù)等于均勻矩陣的列數(shù)，進(jìn)而生成均勻的初始群體。由于采用均勻設(shè)計(jì)初始化群體，同時(shí)對于連續(xù)變化的最值問題，實(shí)數(shù)編碼比二進(jìn)制編碼方式效果更好［2］，因此本文選用實(shí)數(shù)編碼方式。根據(jù)均勻設(shè)計(jì)理論［15］，一般情況下，水平數(shù)與因素?cái)?shù)的比值越大，產(chǎn)生的矩陣均勻性越好。因此，群體規(guī)模不應(yīng)太小，否則初始群體的均勻性會(huì)大大下降，對于高維優(yōu)化問題更是如此。

3 遺傳操作算子的改進(jìn)

3.1 改進(jìn)的錦標(biāo)賽選擇機(jī)制

選擇算子模仿自然界中的“優(yōu)勝劣汰”規(guī)律，按照一定的機(jī)制從父代群體中選擇適應(yīng)度較好的部分個(gè)體，經(jīng)過復(fù)制生成子代種群。選擇操作中比較常見的兩種方法是輪盤賭和錦標(biāo)賽。文獻(xiàn)［6］的研究認(rèn)為：錦標(biāo)賽選擇方法在求解精度和求解速度上整體要優(yōu)于輪盤賭選擇方法，競賽規(guī)模為種群規(guī)模的60%～80%優(yōu)化效果較好。如取種群規(guī)模為10，競賽規(guī)模為60%，則選出的個(gè)體最多涵蓋適應(yīng)度排名前5的5個(gè)個(gè)體，此5個(gè)（或小于5個(gè)）個(gè)體經(jīng)過不同數(shù)量的復(fù)制構(gòu)成下一代群體進(jìn)行交叉及變異操作。若群體規(guī)模為100，則只能選出適應(yīng)度排名前41位的個(gè)體，且適應(yīng)度越高的個(gè)體被選擇的概率越大。經(jīng)上述文獻(xiàn)方法選擇出的群體，具有一定的隨機(jī)性，其均勻性并不可靠。為此本文提出兩種改進(jìn)的錦標(biāo)賽選擇機(jī)制。一是簡單覆蓋法，取適應(yīng)度較高的一半個(gè)體覆蓋整個(gè)群體。二是不同個(gè)體覆蓋法，選擇適應(yīng)度排名靠前且各自不同的50%的個(gè)體覆蓋父代群體。對于標(biāo)準(zhǔn)遺傳算法的三個(gè)算子中，選擇操作系統(tǒng)消耗比重最大，主要緣于輪盤賭選擇或錦標(biāo)賽選擇方法的適應(yīng)度計(jì)算與比較［16］。改進(jìn)方法用一次排序和復(fù)制完成選擇，在促進(jìn)群體進(jìn)化和保證群體多樣性的同時(shí)，降低了算法的復(fù)雜性與計(jì)算量。

3.2 交叉算子

交叉算子模仿自然界生物繁衍過程中的基因重組，通過不同方式的交叉操作產(chǎn)生新個(gè)體，以期獲得適應(yīng)度更高的個(gè)體。文獻(xiàn)［7］提出選擇個(gè)體適應(yīng)值最相近且空間距離最近的兩個(gè)個(gè)體進(jìn)行交叉可以提高交叉操作的搜索效率。文獻(xiàn)［8］根據(jù)個(gè)體相似度對群體進(jìn)行劃分，之后在子種群之間和種群之內(nèi)同時(shí)進(jìn)行交叉操作，并用貪婪算法選出較優(yōu)個(gè)體。文獻(xiàn)［9］通過改進(jìn)交叉算子，將子代個(gè)體落在兩個(gè)父代個(gè)體之間及其兩側(cè)，認(rèn)為交叉后的子代將大概率地優(yōu)于父代個(gè)體，但其并沒有全面分析適應(yīng)度及空間距離對子代個(gè)體的影響?？紤]一種極端情況，兩個(gè)父代個(gè)體適應(yīng)度相等且分居極值兩側(cè)時(shí)，如圖1所示。

圖1 兩個(gè)交叉點(diǎn)在極值兩側(cè)且適應(yīng)度相等示意圖

在此情況下，采用常規(guī)交叉操作能以概率1獲得優(yōu)于兩個(gè)父代個(gè)體的子代個(gè)體。對于多峰函數(shù)，隨著進(jìn)化的進(jìn)行，多峰函數(shù)轉(zhuǎn)化為單峰特性或單調(diào)特性［9］。因此本文提出適應(yīng)度最相近且空間距離最大的兩個(gè)個(gè)體作為父代個(gè)體進(jìn)行交叉能夠以較高的概率搜索到適應(yīng)度更高的子代個(gè)體。

交叉操作具體流程如下：

1）在每一代選擇操作之后，對群體適應(yīng)度進(jìn)行排序［X1，X2……Xn］。

2）判斷Xi+1（i=1，2……n-1）與待交叉?zhèn)€體Xi（i=1，2……n）適應(yīng)度是否相同，若相同，轉(zhuǎn)入步驟2），若不同，取此個(gè)體放入配對池2，轉(zhuǎn)入步驟3）。

3）判斷Xi-1（i=2，3……n）與待交叉?zhèn)€體Xi適應(yīng)度是否相同，若相同，轉(zhuǎn)入步驟3），若不同，取此個(gè)體放入配對池2，轉(zhuǎn)入步驟4）。

4）判斷配對池1和配對池2是否為空，如果其中一個(gè)為空，則取另一個(gè)作為交叉對象；若兩個(gè)都不為空，則分別計(jì)算兩個(gè)配對池中兩個(gè)個(gè)體與待交叉?zhèn)€體的歐式距離，取距離較大者作為交叉對象；若兩個(gè)配對池均為空，則直接將待交叉?zhèn)€體放入子代群體。

5）按式（1）進(jìn)行交叉操作。

交叉完成后，用子代個(gè)體和父代個(gè)體中適應(yīng)度較高的兩個(gè)個(gè)體替換原父代個(gè)體。需要注意的是，對于個(gè)體X（i）的最佳交叉對象是個(gè)體X（j），但個(gè)體X（j）的最佳交叉對象不一定是個(gè)體X（i），因此需要對每個(gè)個(gè)體尋找其最佳交叉對象。所有個(gè)體都完成上述操作后即完成此代交叉操作。

3.3 自適應(yīng)并行變異

變異算子的思想來自生物的基因突變，標(biāo)準(zhǔn)變異算子對極少數(shù)個(gè)體進(jìn)行變異操作，產(chǎn)生新個(gè)體以保持種群的多樣性，但較低的變異概率嚴(yán)重限制了變異操作的搜索效率。許多自適應(yīng)變異方法盡管有一定改善，但搜索效率仍有提升空間。文獻(xiàn)［1］采用根據(jù)進(jìn)化代數(shù)和基因定義域的自適應(yīng)變異步長，變異操作公式較復(fù)雜，而且沒有考慮個(gè)體適應(yīng)度對搜索效率的影響。文獻(xiàn)［10］提出標(biāo)準(zhǔn)變異操作和當(dāng)前最優(yōu)解變異操作并行的變異策略。若最優(yōu)解變異得到一個(gè)更優(yōu)解，則取更優(yōu)解，否則取標(biāo)準(zhǔn)變異方法得到的隨機(jī)值。如果此次變異操作未搜索到優(yōu)于當(dāng)前最優(yōu)解的“更優(yōu)解”，可能會(huì)把適應(yīng)度低于父代個(gè)體的新個(gè)體直接放入下一代群體中，而且對于高維優(yōu)化問題意義不大。文獻(xiàn)［11］用當(dāng)前最優(yōu)解為變異操作指引方向，同時(shí)引入固定參數(shù)的按比例放縮變異，存在基因無法“過0”即正負(fù)數(shù)不能轉(zhuǎn)換的缺陷。

本文提出一種基于高斯函數(shù)的自適應(yīng)變異比例和自適應(yīng)變異步長并行的變異搜索策略。通過對高斯函數(shù)適當(dāng)變形，以進(jìn)化代數(shù)為自變量，以變異比例和變異步長參數(shù)為函數(shù)值，通過合理設(shè)置函數(shù)參數(shù)實(shí)現(xiàn)進(jìn)化初期變異比例和變異步長快速減小，以加快算法收斂；進(jìn)化后期變異比例和變異步長緩慢減小加強(qiáng)局部搜索。相關(guān)代碼如下：

miu=1；sigmaf=500；

n=exp（-（kg-miu）.^2/（2*sigmaf））*1.8+k；

%n為變異比例參數(shù)，kg為進(jìn)化代數(shù)，k為調(diào)節(jié)參數(shù)。

fisum=0；fisum=fisum+fi（i）；

%對當(dāng)前群體適應(yīng)度求和。

fiavg=fisum/size；

n1avg（i）=fiavg/（fi（i）+0.001）；

%加0.001是為防止發(fā)生除零現(xiàn)象。

n1（i）=n*n1avg（i）；

%n1（i）為考慮適應(yīng)度加權(quán)后的變異比例參數(shù)。

tem（i，j）=qunti（i，j）*（（rand+0.5）*n1（i）+1-n1（i））；

%自適應(yīng)變異比例。

km=kmu/（exp（-（kg-miu）.^2/（2*sigmaf））*1.8+k1）；

%變異步長參數(shù)，kmu=120，k1=0.01。

tem1（i，j）=qunti（i，j）+（rand*2-1）*（max-min）/km；

%自適應(yīng)變異步長。

上述代碼中，關(guān)鍵參數(shù)為 sigmaf、k、kmu、k1。對于參數(shù)k，建議前1/3進(jìn)化代數(shù)取0.1，中間1/3進(jìn)化代數(shù)取0.01，后1/3進(jìn)化代數(shù)取0.001。仿真過程中發(fā)現(xiàn)，上述四個(gè)參數(shù)在數(shù)量級范圍內(nèi)變化不會(huì)對算法的優(yōu)化結(jié)果造成明顯影響，說明算法對參數(shù)設(shè)置不敏感，這是任何優(yōu)化算法期望出現(xiàn)的特點(diǎn)。自適應(yīng)變異比例參數(shù)n1應(yīng)限定在［0.005，1.9］區(qū)間內(nèi)。如果變異操作后基因值超出定義域，則取當(dāng)前值到相近定義域端點(diǎn)之間的隨機(jī)值。兩種操作同時(shí)進(jìn)行，并與父代個(gè)體進(jìn)行適應(yīng)度比較，取適應(yīng)度最高者進(jìn)入下一代群體。

3.4 預(yù)選擇機(jī)制

預(yù)選擇機(jī)制屬于小生境遺傳算法的一種進(jìn)化機(jī)制，由Cavichio在1970年提出，其基本思想是：當(dāng)子代個(gè)體的適應(yīng)度超過其父代個(gè)體的適應(yīng)度時(shí)，所產(chǎn)生的子代個(gè)體才能替代其父代而遺傳到下一代群體中，否則父代個(gè)體仍保留在下一代群體中。由于子代個(gè)體與父代個(gè)體之間編碼結(jié)構(gòu)的相似性，所以替換掉的只是一些編碼結(jié)構(gòu)相似的個(gè)體，故能夠有效地維持群體的多樣性，并造就小生境的進(jìn)化環(huán)境［17］。本文將預(yù)選擇思想應(yīng)用在交叉與變異操作中，通過保留當(dāng)前局部最優(yōu)解，加快算法尋優(yōu)速度的同時(shí)還可以保證算法的收斂性與有效性。

4 仿真測試與分析

4.1 測試函數(shù)

為了驗(yàn)證本文算法的改進(jìn)效果，通過15個(gè)常見的函數(shù)進(jìn)行測試，函數(shù)表達(dá)式及定義域如表1所示。為避免算法對個(gè)別函數(shù)存在較好搜索效果的特殊性，選擇不同類型、不同特性的函數(shù)對UD-PMGA算法進(jìn)行測試，并與相關(guān)文獻(xiàn)算法進(jìn)行比較。測試函數(shù) f5又叫Rosenbrock's Vally函數(shù)，最優(yōu)解位于一個(gè)平坦且狹長的山谷谷底，一般算法很容易搜索到山谷底部，但由于山谷底部點(diǎn)的函數(shù)值變化很小，所以想要搜索到全局最優(yōu)解很困難，因而經(jīng)常被用來測試各種優(yōu)化算法的搜索性能［18］。表1中函數(shù)f1、f2為1維函數(shù)，f3、f4、f5、f7為2維函數(shù)，f6為10維函數(shù)，其余函數(shù)為30維。函數(shù)f1、f2、f3求最大值，其余函數(shù)求最小值。仿真環(huán)境為Matlab，在Dell Inspiron 15 5000 Series筆記本電腦運(yùn)行30次所得UD-PMGA算法優(yōu)化結(jié)果。

表1 測試函數(shù)及相關(guān)要求

4.2 仿真結(jié)果

表2為UD-PMGA算法對函數(shù)f1～f6的優(yōu)化結(jié)果及與文獻(xiàn)［18］IAGA算法和文獻(xiàn)［19］NCGA算法的比較。算法參數(shù)設(shè)置與對比文獻(xiàn)一致。函數(shù)f4、f5取群體規(guī)模分別為100和50做兩次試驗(yàn)以方便與相關(guān)文獻(xiàn)進(jìn)行比較，其余函數(shù)群體規(guī)模均為100。函數(shù)f5分別在群體規(guī)模為100、定義域?yàn)椋?5，5］和群體規(guī)模為50、定義域?yàn)椋?10，10］兩組參數(shù)下進(jìn)行兩次試驗(yàn)以方便與文獻(xiàn)［18］和文獻(xiàn)［19］進(jìn)行比較。進(jìn)化代數(shù)為1000。函數(shù)f2收斂精度要求1E-4，函數(shù)f6收斂精度要求1E-3，其它函數(shù)收斂精度要求均為1E-6。采用平均值、最優(yōu)值、最差值和平均收斂代數(shù)作為算法評價(jià)標(biāo)準(zhǔn)。

通過優(yōu)化結(jié)果比較發(fā)現(xiàn)，除函數(shù)f5以外，UD-PMGA算法對其它函數(shù)每次搜索到的最優(yōu)解均相同，說明UD-PMGA算法有著非常強(qiáng)的穩(wěn)定性。盡管UD-PMGA算法對表中個(gè)別函數(shù)收斂到指定精度的速度稍慢于IAGA、NCGA兩種算法，但其最終解的質(zhì)量及算法的穩(wěn)定性明顯優(yōu)于兩種對比算法。本文在用UD-PMGA算法對函數(shù)f5進(jìn)行仿真的過程中，首先采用前文2.1節(jié)中的第一種選擇方法進(jìn)行選擇，但最終解的質(zhì)量及算法穩(wěn)定性并不理想，因此改用第二種選擇方法進(jìn)行選擇操作。結(jié)果表明，采用第二種選擇方法可以獲得更優(yōu)解及更高的穩(wěn)定性，但算法的收斂速度明顯低于其它兩種算法。由此可以看出，第二種選擇方法是以收斂速度的下降為代價(jià)進(jìn)而獲得更高質(zhì)量的解及更高的算法穩(wěn)定性。

表3所示為UD-PMGA對函數(shù)f7～f15的優(yōu)化結(jié)果及與文獻(xiàn)［11］DMMGA算法、文獻(xiàn)［8］GACM算法的比較。算法參數(shù)設(shè)置與對比文獻(xiàn)一致。群體規(guī)模為100。f7進(jìn)化100代，其他函數(shù)進(jìn)化1000代。對函數(shù)f11、f14、f15，采用第二種選擇方法進(jìn)行選擇操作，其他函數(shù)均采用第一種選擇方法。采用平均值和標(biāo)準(zhǔn)差兩個(gè)指標(biāo)對算法進(jìn)行評價(jià)。

從表3仿真結(jié)果看出，UD-PMGA對函數(shù)f7優(yōu)化解的質(zhì)量及算法穩(wěn)定性明顯優(yōu)于GACM算法，對函數(shù)f14的優(yōu)化結(jié)果優(yōu)于GACM算法幾個(gè)數(shù)量級，雖然不及DMMGA算法，但相差不大。對于其它所有函數(shù)，UD-PMGA算法所得優(yōu)化結(jié)果相比兩種對比算法，解的平均值及標(biāo)準(zhǔn)差均有一個(gè)或幾個(gè)數(shù)量級的提高。總體來說，UD-PMGA算法在解的質(zhì)量與算法穩(wěn)定性方面要優(yōu)于DMMGA和GACM兩種算法。為了與文獻(xiàn)［19］的算法進(jìn)行全面比較，對UD-PMGA算法在參數(shù)設(shè)置為群體規(guī)模50、進(jìn)化1000代、定義域?yàn)椋?10，10］的情況下對函數(shù)f7進(jìn)行仿真測試，所得最優(yōu)解平均值為-1.03162845，標(biāo)準(zhǔn)差為0，仍然優(yōu)于文獻(xiàn)所得結(jié)果-1.03162813?？傮w來說，UD-PMGA算法的搜索性能要優(yōu)于NCGA算法。

表2 UD-PMGA與IAGA、NCGA算法的比較

表3 UD-PMGA與DMMGA、GACM算法的比較

圖2所示為函數(shù)f6用UD-PMGA算法和SGA算法優(yōu)化的仿真結(jié)果。從仿真結(jié)果可以看出，UD-PMGA算法在收斂速度及收斂精度兩個(gè)方面的表現(xiàn)均優(yōu)于SGA。在其它測試函數(shù)的仿真過程中發(fā)現(xiàn)，SGA對于部分單峰函數(shù)或低維函數(shù)的優(yōu)化效果與UD-PMGA算法的優(yōu)化效果相差并不太大，但對于多峰函數(shù)和高維函數(shù)，UD-PMGA算法的優(yōu)越性變得非常明顯，這也說明了UD-PMGA算法對于標(biāo)準(zhǔn)遺傳算法的易陷入局部最優(yōu)和局部搜索能力差的缺陷有了較大改善，驗(yàn)證了本文算法的有效性。

通過對15個(gè)測試函數(shù)的仿真結(jié)果全面比較，相比其它文獻(xiàn)所提出的算法，對于低維函數(shù)，UD-PMGA算法能以非常高的穩(wěn)定性收斂到全局最優(yōu)解附近，所得最優(yōu)解均優(yōu)于其他對比算法，體現(xiàn)出UD-PMGA算法具有較高的搜索效率。這一方面得益于遺傳操作算子的改進(jìn)對算法性能的提升，同時(shí)也說明基于全面均勻設(shè)計(jì)的初始群體能夠更加均勻地覆蓋解空間，提高了初始群體的多樣性，從而提高算法的搜索效率。相比于低維函數(shù)，UD-PMGA算法優(yōu)化高維函數(shù)的穩(wěn)定性遜色一些，這是因?yàn)楦呔S函數(shù)的解空間非常大，初始群體對解空間的覆蓋率相對較低，均勻設(shè)計(jì)方法對算法效率的提升會(huì)有折扣，因此標(biāo)準(zhǔn)差并不為0，但由于采用改進(jìn)的遺傳操作算子，UD-PMGA算法仍能到達(dá)函數(shù)最優(yōu)解附近。

圖2 函數(shù) f6用SGA和UD-PMGA算法優(yōu)化對比

5 結(jié)語

本文針對標(biāo)準(zhǔn)遺傳算法收斂速度慢和局部搜索能力不足的缺點(diǎn)，提出UD-PMGA算法。算法采用完全均勻設(shè)計(jì)方法初始化種群，提出兩種改進(jìn)的錦標(biāo)賽機(jī)制進(jìn)行選擇操作，降低算法的計(jì)算成本，同時(shí)增加種群的多樣性；提出如何選擇每個(gè)個(gè)體的最佳交叉對象，并用基于進(jìn)化代數(shù)、個(gè)體適應(yīng)度以及定義域自適應(yīng)變化的變異比例和變異步長進(jìn)行并行變異操作以提高算法的收斂速度和尋優(yōu)精度。通過多個(gè)測試函數(shù)的仿真，與相關(guān)文獻(xiàn)算法進(jìn)行比較，表明UD-PMGA算法具有較好的全局搜索能力和較高的局部搜索能力。但交叉對象的確定和并行變異操作增加了計(jì)算成本，使得UD-PMGA算法的運(yùn)行時(shí)間較長，不利于算法的實(shí)際應(yīng)用，因此如何以更低的計(jì)算成本獲得良好的搜索性能有待進(jìn)一步研究，這也是遺傳算法及其它優(yōu)化算法的改進(jìn)與發(fā)展方向。