趙新超，陳 敏，鞏敦衛(wèi)

(1.北京郵電大學(xué)理學(xué)院，北京 100876;2.中國(guó)礦業(yè)大學(xué)信息與控制工程學(xué)院，江蘇 徐州 221116)

0 引言

遺傳算法是由Holland[1]于1975年提出，它是一類借鑒生物界自然選擇和適者生存機(jī)制的隨機(jī)搜索算法[2-4]。遺傳算法在迭代過程中保留一組候選解，利用交叉、變異等遺傳操作產(chǎn)生新的候選解群體，按照適應(yīng)值指標(biāo)從解群體中選擇較優(yōu)個(gè)體進(jìn)入下一代，重復(fù)此過程，直到滿足某種收斂指標(biāo)。遺傳算子僅僅利用適應(yīng)值作為度量指標(biāo)進(jìn)行隨機(jī)操作，降低了一般優(yōu)化算法在搜索過程中對(duì)問題信息和人機(jī)交互的依賴[5]。與傳統(tǒng)的優(yōu)化算法[6]相比，遺傳算法的主要特征在于不依賴于問題的梯度信息與群體搜索策略，群體搜索使得遺傳算法得以突破鄰域搜索[7]的限制，可以實(shí)現(xiàn)整個(gè)解空間上的分布式信息采集和探索。

在遺傳算法中，交叉算子通過模擬自然界生物的雜交過程對(duì)個(gè)體進(jìn)行交叉操作，不斷產(chǎn)生新個(gè)體，增加種群的多樣性，擴(kuò)大尋優(yōu)范圍，從而使得遺傳算法具有較強(qiáng)的全局搜索能力。因此，交叉算子在遺傳算法擴(kuò)展求解空間和搜索全局最優(yōu)解的過程中發(fā)揮著重要作用[8]。對(duì)實(shí)數(shù)編碼的交叉策略[9]，兩個(gè)父體經(jīng)交叉操作后得到的子個(gè)體往往限定于兩父體圍成的某個(gè)區(qū)域，使整個(gè)群體搜索范圍和路徑探測(cè)受到了一定的限制，并有早熟收斂于局部鄰域的可能。子個(gè)體若要跳出父體圍成的區(qū)域，一般只能借助于變異操作，但若單純地加大變異概率或增大搜索步長(zhǎng)，遺傳算法就有退化成一般隨機(jī)搜索算法的趨勢(shì)[10-11]。針對(duì)這一不足，文獻(xiàn)[12]提出了幾種新的交叉算子，對(duì)傳統(tǒng)的交叉操作進(jìn)行了相應(yīng)的改進(jìn)，使得子代個(gè)體始終有跳出父體所圍成區(qū)域的可能，一定程度上擴(kuò)大了遺傳算法交叉算子的搜索區(qū)域，使算法始終保持探測(cè)新區(qū)域的可能。但是，該文獻(xiàn)只是給出每組交叉操作搜索區(qū)域大小比較的定性結(jié)果，并沒有任何定量的理論分析和數(shù)據(jù)支撐。本文對(duì)文獻(xiàn)[12]中6種實(shí)數(shù)編碼的交叉操作的相對(duì)搜索區(qū)域和潛在的覆蓋范圍進(jìn)行了定量分析和理論探討，為交叉算子和遺傳算法的算法設(shè)計(jì)[13]以及問題求解提供了理論支持。

1 6種實(shí)數(shù)編碼的交叉操作

序列投影尋蹤是揭示隱藏在高維數(shù)據(jù)中有趣結(jié)構(gòu)的有用工具[12]，并有序地構(gòu)造了低維空間的基底。遺傳算法是發(fā)現(xiàn)這些基底的有力工具，但是它的表現(xiàn)取決于對(duì)遺傳算法交叉操作的選擇。Espezua等[12]對(duì)8種交叉操作進(jìn)行了介紹和比較分析，多組測(cè)試結(jié)果表明，新提出的超圓錐交叉操作在尋找適應(yīng)度最高的投影方面表現(xiàn)最好。

下面對(duì)其中的6種(3組)實(shí)數(shù)編碼的交叉操作進(jìn)行介紹，詳細(xì)的操作參見文獻(xiàn)[12]。下面都假定a1與a2是兩父代個(gè)體，b1與b2是兩個(gè)子代個(gè)體。

1.1 算術(shù)內(nèi)部交叉(交叉1)

算術(shù)交叉操作產(chǎn)生子代的過程如下：

b1=Normalize(ra1+(1-r)a2)，b2=Normalize((1-r)a1+ra2),

(1)

1.2 算術(shù)內(nèi)外交叉(交叉2)

該算子是對(duì)交叉操作1的拓展，子代產(chǎn)生方式同交叉操作1，唯一的區(qū)別是隨機(jī)數(shù)r的產(chǎn)生范圍由[0,0.5]變成[-0.5,0.5]。因此，子代向量有較大可能位于父代向量圍成的扇形區(qū)域之外，并依然對(duì)稱地分布在父代等分線的兩側(cè)，操作如圖1b所示。相比于交叉操作1，交叉操作2的子代可以產(chǎn)生在由父代個(gè)體向量形成的扇形區(qū)域之外，在這個(gè)擴(kuò)展的扇形區(qū)域中，子代和對(duì)稱軸形成的最大角為2θ，θ是父代個(gè)體和對(duì)稱軸之間的夾角，該操作的探測(cè)范圍和新解的生成過程如圖1b所示。

1.3 內(nèi)部超圓錐交叉(交叉5)

1.4 內(nèi)外超圓錐交叉(交叉6)

該交叉操作是交叉操作5的擴(kuò)展，產(chǎn)生子代的步驟類似于交叉5，唯一的區(qū)別是此時(shí)θr∈[0,2θ]。對(duì)比于交叉操作5，通過父代個(gè)體圍繞等分線進(jìn)行旋轉(zhuǎn)產(chǎn)生的子代可以在超圓錐體的外部，因此，子代個(gè)體產(chǎn)生了相對(duì)更廣泛的超圓錐搜索鄰域。

交叉操作5和交叉操作6的鄰域探測(cè)范圍和子代產(chǎn)生的過程如圖2a和圖2b所示，θ是父代向量a1或a2與其夾角平分線m的夾角，θb1，θb2是子代個(gè)體b1和b2與對(duì)稱軸的夾角，urand[a,b]是均勻分布在區(qū)間[a,b]的一個(gè)隨機(jī)數(shù)。

1.5 適應(yīng)度偏向的內(nèi)部交叉(交叉7)

(2)

1.6 適應(yīng)度偏向的內(nèi)外交叉(交叉8)

2 3對(duì)交叉操作搜索區(qū)域?qū)Ρ鹊亩糠治?/h2>

2.1 交叉操作1和交叉操作2

由于交叉操作1和交叉操作2中子代產(chǎn)生的范圍由父代個(gè)體形成的扇形區(qū)域所界定，又因?yàn)樯刃蚊娣e公式為S=αr2/2，其中r為扇形半徑，α為扇形圓心角，并且由相同的兩個(gè)個(gè)體在交叉操作1和交叉操作2中所圍成扇形的半徑相同，而交叉操作2產(chǎn)生的子代個(gè)體探測(cè)扇形區(qū)域的圓心角是交叉操作1產(chǎn)生子代的2倍，所以子代個(gè)體搜索區(qū)域的面積也是交叉操作1中的兩倍，即交叉操作2產(chǎn)生子代的搜索探測(cè)范圍較交叉操作1更廣泛，子代樣本能保持較好的探測(cè)空間多樣性，尤其是算法搜索的后期，更有利于保持群體多樣性，從而更有可能跳出當(dāng)前鄰域，更好地尋求全局最優(yōu)解。

2.2 交叉操作5和交叉操作6

由于交叉操作5和交叉操作6產(chǎn)生的子代覆蓋區(qū)域是其兩父代個(gè)體繞其中心線旋轉(zhuǎn)形成的圓錐和圓錐所對(duì)應(yīng)的球冠內(nèi)部，即為圓錐體頂角所對(duì)應(yīng)的包含于球體內(nèi)部的那一部分球體體積，所以兩種交叉操作對(duì)應(yīng)的搜索區(qū)域之比就是它們子代個(gè)體所可能張成的圓錐和球冠的體積之比。如圖4所示，其中藍(lán)色陰影部分代表交叉操作5產(chǎn)生子代個(gè)體所可能覆蓋的區(qū)域體積V5，藍(lán)色和紅色陰影部分之和代表交叉操作6產(chǎn)生子代個(gè)體所可能覆蓋的區(qū)域V6。

2.3 交叉操作7和交叉操作8

由于交叉操作7、交叉操作8與交叉操作1、交叉操作2類似，區(qū)別在于交叉操作1和交叉操作2是在可能的探測(cè)范圍內(nèi)均勻地產(chǎn)生子代，而交叉操作7和交叉操作8是以依賴于個(gè)體適應(yīng)值的非均勻方式產(chǎn)生子代個(gè)體，因此若只是考慮探測(cè)范圍的區(qū)別，這兩組操作有相同的探測(cè)范圍的對(duì)比分析，因而僅僅考慮探測(cè)范圍顯示不出交叉操作7、交叉操作8與交叉操作1交叉操作2的區(qū)別。根據(jù)交叉操作7和交叉操作8的特點(diǎn)分析可知，這組交叉操作的更重要特征是子代個(gè)體在允許的探測(cè)范圍上的非均勻分布。由于較優(yōu)父代個(gè)體與中心線夾角為負(fù)，因此該組交叉操作對(duì)比的重點(diǎn)在于考察操作8產(chǎn)生的子代個(gè)體是否有更趨向于較優(yōu)父代個(gè)體鄰域的趨勢(shì)，如果有該趨勢(shì)，可否分析出這種趨于較優(yōu)個(gè)體趨勢(shì)的大小。

通過以上對(duì)遺傳算法中的6種交叉操作的兩兩定量對(duì)比分析，給出了兩兩搜索區(qū)域和覆蓋范圍大小比較的解析結(jié)果，證明了新的交叉操作比相應(yīng)的原有操作具有相對(duì)的廣鄰域性，從而對(duì)新的交叉操作具有相對(duì)的優(yōu)異性能給出可靠的理論分析基礎(chǔ)。不僅加深了對(duì)遺傳算法的執(zhí)行機(jī)理的理解，還在一定程度上給遺傳算法概率型搜索的黑箱搜索機(jī)制提供了理論支持。

3 結(jié)論

對(duì)文獻(xiàn)[12]中6種(3組)實(shí)數(shù)編碼的交叉算子的探測(cè)區(qū)域進(jìn)行了定量對(duì)比分析。通過對(duì)每一對(duì)交叉算子所可能的搜索區(qū)域和覆蓋范圍進(jìn)行理論上的對(duì)比分析發(fā)現(xiàn)，每一對(duì)交叉算子中的后者對(duì)應(yīng)的搜索區(qū)域都比前者更加廣泛，即后者的交叉操作有效擴(kuò)大了種群多樣性和尋優(yōu)范圍，體現(xiàn)了擴(kuò)展的交叉操作具有內(nèi)在的群體多樣性保持機(jī)制和搜索的寬鄰域特性，從而使得遺傳算法具有更加平衡的搜索能力，有效減少了交叉操作在求解過程中陷入局部最優(yōu)解的概率，而這種性能對(duì)群體優(yōu)化算法具有重要影響，尤其是算法搜索后期。綜合本文對(duì)不同組交叉操作探測(cè)范圍的理論對(duì)比分析和文獻(xiàn)[12]中對(duì)不同交叉操作的實(shí)驗(yàn)對(duì)比分析，證明了本文中對(duì)6種(3組)交叉操兩兩作對(duì)比分析的正確性和必要性，從而為遺傳算法搜索性能的差異表現(xiàn)提供了理論上的支持。