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

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

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

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

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

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