基于并行機(jī)制的免疫遺傳算法的研究及應(yīng)用.pdf

1、伴隨著遺傳算法應(yīng)用的深入開(kāi)展,由于遺傳算法有著其他優(yōu)化算法不可比擬的優(yōu)點(diǎn),因此,遺傳算法在優(yōu)化計(jì)算中得到了廣泛的應(yīng)用,將遺傳算法用于解決各種實(shí)際優(yōu)化問(wèn)題后,人們發(fā)現(xiàn)遺傳算法也會(huì)由于各種原因,產(chǎn)生所謂"早熟收斂"問(wèn)題,從而影響算法向全局最優(yōu)解的搜索.隨著科學(xué)技術(shù)的不斷發(fā)展,問(wèn)題規(guī)模的不斷擴(kuò)大,面對(duì)復(fù)雜程度越來(lái)越高的搜索空間,遺傳算法在優(yōu)化效率和求解質(zhì)量上都顯得"過(guò)于蒼白".為了加速?zèng)Q策的時(shí)效性和準(zhǔn)確性,在文中以無(wú)源光網(wǎng)絡(luò)中OBD與OUN位

2、置分配問(wèn)題為例,在工作站機(jī)群上對(duì)此算法進(jìn)行研究. 首先,本文研究了根據(jù)生物機(jī)體免疫系統(tǒng)的抗原識(shí)別、保持抗體的多樣性和免疫記憶的特性而提出的一種改進(jìn)遺傳算法--免疫遺傳算法,該算法將生物系統(tǒng)免疫思想引入到遺傳算法中,通過(guò)計(jì)算抗體之間的親和度來(lái)促進(jìn)和抑制抗體,既保留了全體中的較優(yōu)抗體又保證了抗體的多樣性,從而避免搜索進(jìn)化的過(guò)早收斂,得到全局最優(yōu)解.本文通過(guò)對(duì)改進(jìn)的免疫遺產(chǎn)算法和傳統(tǒng)的遺傳算法的產(chǎn)生效果進(jìn)行比較,證明了IGA的有效性和

3、優(yōu)越性. 其次,本文通過(guò)對(duì)并行遺傳算法的發(fā)展和特點(diǎn)進(jìn)行綜述,并介紹并行處理的硬件系統(tǒng)及其并行環(huán)境下的支撐軟件--工作站機(jī)群平臺(tái)上所采用的高效的編程環(huán)境MPI. 再次,論文重點(diǎn)分析遺傳算法固有的隱式并行性,結(jié)合主從并行程序設(shè)計(jì)特點(diǎn),提出了工作站機(jī)群環(huán)境下基于MPI求解最短路徑問(wèn)題的并行遺傳算法,加快算法的執(zhí)行速度和效率.在該算法并行設(shè)計(jì)中的劃分、通訊、組合和映射四個(gè)過(guò)程,提出遺傳算法初始種群的劃分原則;利用MPI消息傳遞的

4、六個(gè)基礎(chǔ)通信子集在各種群間進(jìn)行通信和傳播各子種群的最優(yōu)解;運(yùn)用組合法,以保持靈活性,減少通信開(kāi)銷(xiāo):將該算法映射為主從式工作站機(jī)群上的粗粒度并行遺傳算法,并使用靜態(tài)負(fù)載平衡任務(wù)調(diào)度技術(shù)改善映射質(zhì)量. 最后,利用MPICH進(jìn)行仿真試驗(yàn).作者通過(guò)配置工作站機(jī)群并行環(huán)境,在windows和MPI平臺(tái)上使用Visual C++6.0編程實(shí)現(xiàn)該并行算法,通過(guò)分析對(duì)比多組實(shí)驗(yàn)數(shù)據(jù),計(jì)算該算法加速比性能,結(jié)果表明:算法適應(yīng)度高,尋優(yōu)速度快.