多種群混合并行遺傳算法的研究.pdf

1、遺傳算法(Genetic Algorithms，簡稱GA)是一種建立在自然演化系統(tǒng)理論研究基礎(chǔ)上，通過模擬自然進(jìn)化過程搜索最優(yōu)解的優(yōu)化方法，可用于復(fù)雜的系統(tǒng)優(yōu)化，是有效的全局優(yōu)化搜索算法，具有眾多無可比擬的優(yōu)點(diǎn)。但是標(biāo)準(zhǔn)的遺傳算法(Standard Genetic Algorithms,簡稱SGA)也存在不少缺點(diǎn)，主要有以下兩個方面：(1)容易過早收斂；(2)局部搜索能力差。這兩個缺點(diǎn)是GA在對問題進(jìn)行高質(zhì)量求解的主要障礙。
　　

2、 遺傳算法的局部搜索能力不強(qiáng)，因此即便其全局收斂性很強(qiáng)，可以很快到達(dá)最優(yōu)解的附近，但也要花很長時間才能搜索到最優(yōu)解。若想合理的避開其缺陷，達(dá)到充分利用其優(yōu)勢，加快整體收斂速度的目的，除了選取適合的參數(shù)以及設(shè)計科學(xué)的基本操作算子之外，比較有效的方法就是在遺傳進(jìn)化的過程中引入快速收斂的局部尋優(yōu)算法，也就是采用混合策略，使其構(gòu)成混合遺傳算法。本文的主要工作之一就是針對GA存在的缺陷，在標(biāo)準(zhǔn)的遺傳算法中引入小生境技術(shù)，對進(jìn)化的每一代個體進(jìn)行分

3、類，使種群以類的方式持續(xù)進(jìn)化，這樣有效維持了種群的多樣性，從而防止種群早熟。同時，通過將GA與模擬退火算法(Simulated Annealing Algorithms，簡稱SAA)相結(jié)合，利用SAA較強(qiáng)的局部搜索能力，改進(jìn)SGA在這方面的缺陷，從而提高GA對問題的求解質(zhì)量與效率。
　　 遺傳算法是一種高效智能的搜索方法。由于它一般具有較大的群體規(guī)模，不僅需要對大量的個體進(jìn)行遺傳和進(jìn)化操作，而且還要進(jìn)行適應(yīng)度計算或評價，導(dǎo)致算法

4、的進(jìn)化過程難以達(dá)到計算速度上的要求，因而GA的并行計算問題就顯得十分重要。本文的主要工作之二就是根據(jù)GA易于并行實(shí)現(xiàn)的特點(diǎn)，利用多個種群對問題進(jìn)行并行求解，進(jìn)一步提高了求解速度。
　　 與此同時，考慮到集群環(huán)境的優(yōu)勢及多核計算平臺發(fā)展的趨勢，本文在最后分別設(shè)計與實(shí)現(xiàn)了基于此兩種環(huán)境下的改進(jìn)遺傳算法，提高了遺傳算法的運(yùn)行效率。
　　 綜上所述，本文的主要工作包括兩部分：
　　 (1)提出了一個改進(jìn)的多種群算法。首先

5、基于小生境技術(shù)，引入具有較強(qiáng)局部搜索能力的模擬退火操作，有效提高了遺傳算法的收斂速度，抑制了算法局部早熟，改善了算法的優(yōu)化質(zhì)量。然后基于此改進(jìn)的遺傳算法，構(gòu)造具有更強(qiáng)搜索能力的多種群算法，即對每個種群獨(dú)立執(zhí)行改進(jìn)的遺傳算法，運(yùn)行過程則通過多種群的交換策略進(jìn)行信息的交流。最后通過對一組典型的函數(shù)優(yōu)化求解來驗(yàn)證該改進(jìn)算法的有效性。
　　 (2)在改進(jìn)的多種群遺傳算法的基礎(chǔ)上，設(shè)計了基于并行虛擬機(jī)(PVM)環(huán)境與多核CPU計算平臺的并