分布式遺傳算法性能優(yōu)化及其應(yīng)用.pdf

1、分布式遺傳算法 (Distributed Genetic Algorithms，DGAs)不但繼承了傳統(tǒng)遺傳算法的優(yōu)點(diǎn)，更具備了分布并行的特色。遺傳進(jìn)化過程中各臺計(jì)算機(jī)雖然相互獨(dú)立，但又可通過網(wǎng)絡(luò)交換遺傳信息，相互影響，增加彼此個(gè)體基因的多樣性，從而可以有效避免傳統(tǒng)遺傳算法的“早熟(prematuration)”問題。 實(shí)際上，隨著硬件技術(shù)的發(fā)展和個(gè)人計(jì)算機(jī)PC價(jià)格的不斷下跌，目前許多企業(yè)、學(xué)術(shù)研究機(jī)構(gòu)以及個(gè)人利用高性價(jià)比的個(gè)人

2、PC來構(gòu)建它們自己的分布式系統(tǒng)已成為可能，因此基于此系統(tǒng)的分布式遺傳算法得到了廣泛的應(yīng)用。 那么如何提高分布式遺傳算法的性能，就成為了一個(gè)值得深入探討的問題。因此，本文選擇以分析影響算法性能的控制參數(shù)作為切入點(diǎn)，來研究如何提升分布式遺傳算法的性能，使其更加有效地應(yīng)用于NP難問題的求解。 本文首先研究了影響分布式遺傳算法運(yùn)算性能的參數(shù)：種群規(guī)模和遷移相關(guān)參數(shù)，接著分析了目前的研究現(xiàn)狀及存在的問題，然后依據(jù)參數(shù)動、靜態(tài)特征再

3、進(jìn)行分類研究，并分別提出了相應(yīng)的優(yōu)化策略。 一方面，為了避免種群規(guī)模的固定不變對算法性能負(fù)面影響，本文提出了基于模糊選擇的種群規(guī)模動態(tài)調(diào)整策略，此策略著重解決如何在進(jìn)化過程中動態(tài)地為種群選取適當(dāng)?shù)倪M(jìn)化規(guī)模。具體地，依據(jù)子種群當(dāng)前的進(jìn)化效果來選擇進(jìn)入基因池的個(gè)體的數(shù)目，這樣有利于優(yōu)勢基因被有效繼承和擴(kuò)散，不但增強(qiáng)了算法的搜索能力，還提高了算法的搜索效率。 另一方面，為了避免盲目的參數(shù)設(shè)置導(dǎo)致算法性能不可預(yù)見的起伏，本文提出

4、了基于數(shù)據(jù)挖掘技術(shù)(Data Mining)的參數(shù)優(yōu)化方法，此方法有助于解決參數(shù)設(shè)置對算法性能的影響難以預(yù)測的問題。具體地，本文首先針對三個(gè)經(jīng)典的優(yōu)化問題進(jìn)行了參數(shù)組合實(shí)驗(yàn)，然后利用數(shù)據(jù)挖掘技術(shù)尋找參數(shù)組合與算法最終解之間的一些必然聯(lián)系或規(guī)則，進(jìn)而建立了參數(shù)設(shè)置對算法性能影響的預(yù)測模型，為參數(shù)合理設(shè)置提供指導(dǎo)和依據(jù)，以求達(dá)到優(yōu)化算法性能的目的。 最后在基于 PVM(Parallel Virtual Machine)的仿真平臺上所