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

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

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

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

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

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

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

6、評(píng)價(jià)標(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ù)大于某一指定的值時(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ù)在兩個(gè)不同點(diǎn)：(-0.089860,0.712657)和(0.089860,-0.712657)為全局最小，最小值為-1.031628。F2：DeJong函數(shù)f(x,y

7、)=100*(x2-y)2+(1-x)2的最大值，-2.048≤x,y≤2.048。該函數(shù)有兩個(gè)局部最大點(diǎn)(f(-2.048,-2.048)=3905.926227和f(2.048,-2.048)=3897.722309，其中第一個(gè)點(diǎn)為全局最大點(diǎn)。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，同時(shí)存在4個(gè)局部極值點(diǎn)。測試結(jié)果如表1所示：表1函數(shù)優(yōu)化測試結(jié)