6種交叉操作兩兩搜索區(qū)域大小的定量分析

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

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

0 引言

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

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

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

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

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

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)

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

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

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

3 結(jié)論

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