多父輩遺傳算法交叉算子研究

《多父輩遺傳算法交叉算子研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、多父輩遺傳算法交叉算子研究[日期：2006-05-31]來源：?作者：[字體：大中小]羅治情?戴光明?詹煒?鄭蔚??摘要:通過對遺傳算子和多父輩交叉遺傳算法的研究，提出了多父輩循環(huán)移位的交叉算子。新的交叉算子能夠讓多父體之間實現(xiàn)基因互補(bǔ)，達(dá)到保持種群個體多樣性的目的。仿真測試結(jié)果表明：新的算子改進(jìn)了多父輩遺傳算法對全局最優(yōu)解的搜索能力和收斂速度。在此基礎(chǔ)上可以進(jìn)一步改善多父輩遺傳算法的性能，從而使遺傳算法獲得更廣泛的應(yīng)用。關(guān)鍵詞:多父輩；遺傳算法；遺傳算子；循環(huán)交叉1?引言傳統(tǒng)的遺傳算法作為一種通用的自適應(yīng)隨機(jī)搜索算法，存在著局部收斂和收斂速度慢這兩個問題。而多父輩交叉

2、(Multi-parentRecombination)遺傳算法在近年來逐漸引起了研究者的注意。由于隨著在交叉操作中多父輩的引入，降低了一些個體將自身復(fù)制到子代中的可能性，這就意味著多父輩交叉有利于提高遺傳算法的性能。但是，研究發(fā)現(xiàn)，對于不同的測試函數(shù)，不知道在何種情況下或者說對于具有何種特點的測試函數(shù)，應(yīng)該采用何種交叉算子才能獲得最優(yōu)的結(jié)果。本文在對遺傳算子和多父輩交叉遺傳算法的研究的基礎(chǔ)上，提出了多父輩循環(huán)移位的交叉算子，算子改進(jìn)了多父輩遺傳算法的性能。2?多父輩遺傳算法的算子在多父輩遺傳算法的研究中，其遺傳算子一直都是被研究的熱點。曾經(jīng)也有很多學(xué)者進(jìn)行了相關(guān)方面的研

3、究。如：多父輩交叉的基因池重組算子(Genepoolrecombination)、、二值編碼遺傳算法的多父輩掃描交叉(scanningcrossover)算子和對角線交叉(diagonalcrossover)算子以及采用邊界鏡像延拓(BoundaryExtensionbyMirroring,BEM)的實數(shù)編碼的質(zhì)心交叉(CenterofMassCrossover,CMX)算子和單純形交叉(SimplexCrossover,SPX)算子。另外還有多父輩的單峰均勻分布交叉算子(UnimodalNormalDistributionCrossover,UNDX-m)。通過對以上

4、研究的總結(jié)可以知道：多父輩交叉有利于提高遺傳算法的性能，但是同時也發(fā)現(xiàn)多父輩交叉遺傳算法的性能依賴于測試函數(shù)和交叉操作的父輩數(shù)量。3?循環(huán)移位交叉算子的設(shè)計循環(huán)移位交叉算子的思想實質(zhì)上就是基本遺傳算法中的交叉算子，只是在本文中處理方式不一樣而以，由于是多個父體進(jìn)行交叉，產(chǎn)生的后代也不是只有一個后代個體。因此，需要在交叉過程中進(jìn)行有效的處理，以便得到同樣數(shù)目的個體?；具z傳算法的交叉操作一般是在交配池中選擇兩個個體之后，然后隨機(jī)選擇一個交叉點n，然后將兩個個體基因位數(shù)n后面的基因交換而得到下一代個體。如圖1所示。圖1基本遺傳算法中的交叉操作本文的多父輩交叉操作思想來自于基

5、本的交叉操作，但是在處理上有些不同之處。在交配池中隨機(jī)選擇一定數(shù)目（一般≥3）的參入交叉的父輩個體之后，將這些父輩個體的染色體連接在一起，形成一個長的染色體C。然后，產(chǎn)生一個隨機(jī)數(shù)P（1≤P≤單個染色體長度-1），將C循環(huán)左移P位，即讓左端移出的基因填補(bǔ)到C的右端，得到C。如圖2所示。交叉完之后，再按照單個個體染色體的長度將C’“分割還原”為后代子個體。?圖2循環(huán)移位交叉操作另外，在算法的實際實現(xiàn)過程中，我們引入了自適應(yīng)的概念。當(dāng)進(jìn)化到群體中最壞個體和最好個體的適應(yīng)度相差很小的時候，我們可以減小父輩的數(shù)目，從而加快算法的收斂速度。4?算法模擬測試為了檢驗本文交叉算子對多

6、父輩遺傳算法的搜索能力的影響，選取平均收斂次數(shù)作為評價標(biāo)準(zhǔn)。平均收斂次數(shù)是指對于同一目標(biāo)函數(shù)做多次測試(本文對同一目標(biāo)函數(shù)統(tǒng)一都做30次)而得到的停機(jī)代數(shù)的平均值。算法的停機(jī)條件也是采用一般常用的方法，適應(yīng)度值與當(dāng)前理論結(jié)果的差值（e）很小則認(rèn)為算法收斂并停機(jī)；另外如果進(jìn)化代數(shù)大于某一指定的值時則認(rèn)為不收斂并停機(jī)。本文中選取的測試函數(shù)：F1：六駝峰函數(shù)f(x,y)=(4-2.1x2+x4/3)x2+xy+(-4+4y2)y2的最小值，-100≤x,y≤100。函數(shù)在兩個不同點：(-0.089860,0.712657)和(0.089860,-0.712657)為全局最小，

7、最小值為-1.031628。F2：DeJong函數(shù)f(x,y)=100*(x2-y)2+(1-x)2的最大值，-2.048≤x,y≤2.048。該函數(shù)有兩個局部最大點(f(-2.048,-2.048)=3905.926227和f(2.048,-2.048)=3897.722309，其中第一個點為全局最大點。F3：函數(shù)f(x,y)=(a÷(b+(x2+y2)))2+(x2+y2)的最大值,-5.12≤x,y≤5.12。其中設(shè)a=3.0，b=0.05，maxf(0,0)=3600，同時存在4個局部極值點。測試結(jié)果如表1所示：表1函數(shù)優(yōu)化測試結(jié)