網格平臺下并行遺傳算法的設計

（電子科技大學 計算機科學與工程學院， 四川 成都 610054）

摘 要：并行遺傳算法是遺傳算法研究中的一個重要課題，提出了一種在網格平臺下實現遺傳算法的設計和一些關于遺傳算法本身的改進，以及需要進一步研究的課題。

關鍵詞：遺傳算法； 粗粒度并行遺傳算法； 網格計算

中圖法分類號：TP301．6文獻標識碼：A

文章編號：1001-3695(2006)08-0083-02



Design of Parallel Genetic Algorithm on Grid Computing Platform

LI Lei， CAI Hong bin， WU Yue

（College of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu Sichuan 610054， China）

Abstract:Parallel genetic algorithm is one of the main research fields of genetic algorithms. A design of the parallel genetic algorithm on grid computing platform and the improvement of the coarse grained parallel algorithm have been brought out in this paper. The further research work which should be given more attention has also been pointed out.

Key words:Genetic Algorithm; Coarse grained Parallel Genetic Algorithm; Grid Computing



1引言



美國Michigan大學的J.H.Holland[1]教授創立的遺傳算法（Genetic Algorithms，GAs）是模仿自然界生物進化過程中“物競天擇，適者生存”的原則而進行的一種多參數、多群體同時優化的方法。經過二十多年的發展，遺傳算法已經在貨郎擔問題（TSP）的求解、生產調度、函數優化、機器學習等領域得到成功的應用，并顯示出其良好的性能。串行遺傳算法在解決實際問題時，由于需要較多的個體數量和大量計算，使得進化過程緩慢，難以達到實際要求。因此并行遺傳算法（Parallel Genetic Algorithm，PGA）成為了遺傳算法研究的一個熱點。當前并行遺傳算法大多是用分布式并行計算的方法實現，由于分布式并行計算要求高度可控的特點，實現并行算法不夠靈活。本文提出了一種在網格平臺下實現的并行遺傳算法，能充分利用網絡上閑置的計算資源，大大地提升了遺傳算法的效率。

計算機科學計算的發展對計算機的計算能力要求是永無止境的，因為計算機硬件的物理特性，要從硬件上提高計算機的計算速度將越來越困難。網格計算系統又稱為計算網格，它是可以作為虛擬的整體而使用在地理上分布的異構計算資源[2，3]，這些資源包括高速互連的異構計算機、數據庫、科學儀器、文件和超級計算機系統等。這些資源有機地結合在一起，有效地利用了網絡上閑置的資源，使用戶在較少的投資下能夠獲得超級計算機的計算能力。

2網格計算平臺的設計

本文中設計的網格計算平臺如圖1所示，由客戶端、Web服務器、計算網格服務器、工作機組成。該平臺的工作流程大致如下：用戶通過客戶端Web瀏覽器登錄Web服務器，提交要計算的任務。Web服務器把原始數據提交該計算網格服務器。假設網絡中有n臺工作機，計算網格服務器把計算任務分割成n片送到工作機上，工作機完成各自的計算任務后，把計算結果回送到計算網格服務器，計算網格服務器再將結果回送至Web服務器，用戶可以在客戶端通過Web瀏覽器瀏覽Web服務器上的計算結果。另外，在Web服務器上還可以提供工作機的安裝程序下載，網絡上任何感興趣的人都可以把自己的計算機作為工作機協同完成計算任務，充分利用了網絡上閑置的計算資源。本平臺是一個很典型的計算網格平臺，很適合并行遺傳算法的設計。

3粗粒度并行遺傳算法在網格平臺上的改進

在分布式并行計算中，粗粒度并行遺傳算法[6]的基本思想是將整個種群劃分為幾個子種群，各個子種群分配在各自的處理機上獨立地并行簡單的遺傳算法操作，在適當的時候各個子種群間互相交換一些信息。其基本出發點是從全局的角度開發種群進化并行性。

在本文的模型中，可對粗粒度并行遺傳算法進行一些改進。用戶將整個群體提交到計算網格服務器后，計算網格服務器將整個種群分割為若干個子種群，各個子種群分配到各自所在的工作機上獨立進行串行的遺傳算法的進化操作；每進化一段時間后，各個工作機選取一個個體發送給計算網格服務器，計算網格服務器統一把這些個體發送給其他工作機上的子種群；工作機接收到這些個體后，繼續進化，直到下一個交換個體的時間到達或者算法達到終止條件。所以，本文模型中的遺傳算法描述如圖2所示。

針對本文網格計算平臺的特點，粗粒度并行遺傳算法還應該從以下幾個方面進行改進：

（1）種群的分割的改進

在本文的模型中，網格計算平臺具有動態變化性，工作機的數量不固定，種群分割的大小也不固定。如果把整個群體均勻地分配到各個工作機上，一種情況是工作機數量過多，這會導致各子種群規模過小，影響算法的搜索范圍，從而得不到最優解。在此可以設定一個最小種群個體數S_min，當分割后每個工作機上的子種群中的個體數量小于S_min，服務器就嘗試重新分割整個種群到更少的工作機上，直到每個工作機分配的種群中個體數量大于S_min為止。另外一種極端的情況是工作機數過少，最壞的情況是整個網絡只有一臺工作機，這個時候該模型的算法退化為串行遺傳算法。

（2）變異概率和交叉概率的改進

在遺傳算法中，變異概率p_c和交叉概率p_m對算法的性能有重要的影響[4，5]。一般說來，如果變異概率p_c和交叉概率p_m越大，算法的探測能力就越強，越容易探測到新的超平面，而個體的平均適應度波動較大；相反，如果變異概率p_c 和交叉概率p_m越小，則算法的開發能力越強，使得較優的個體不易被破壞，個體的平均適應度平穩，但是容易導致群體過早收斂，造成“早熟”現象。

正如上文所述，本文模型中在工作機上的子種群規模并不固定，變異概率p_c和交叉概率p_m也應該隨實際情況變化，采用自適應的變異概率和交叉概率能很好地解決遺傳算法參數選擇的問題。

在各個工作機的種群中，令f_max代表種群中最優的個體適應度，F代表該種群的平均適應度，令Δ=f_max -F，Δ可以近似地反映種群的收斂程度。如果Δ越小，表示種群個體適應度之間的差別較小，種群達到局部最優的可能性就越大，“早熟”現象出現的可能性也就越大；相反，Δ越大，表示個體的分布比較分散，適應度差別較大。根據這個思想，各工作機上的變異概率p_c和交叉概率p_m可以根據Δ的大小來實時調整，當Δ較小時，增大p_c和p_m，從而克服過早收斂；相反，當Δ較大時，減小p_c和p_m。這樣，實際上p_c，p_m的值應該與Δ成反比。表示如下：

p_c= k₁/Δ (1)

p_m= k₂/Δ (2)

在工作機上開始進行種群進化時，先確定一個初始的p_c和p_m，在進化出新的子種群時根據式(1)和式(2)來修正p_c和p_m，常數k₁和k₂的取值需要根據具體問題適當選取。

采用遺傳算法自適應參數雖然增大了算法的時間復雜度，但是能夠使算法更合理地進行，有效地克服了“早熟”問題。

（3）工作機子種群個體遷移的改進

為了讓每個工作機上的種群保持其多樣性，使其能夠探測出更優的結果，避免“早熟”現象，每隔一段時間，工作機上的子種群之間需要交換一些個體[6]。

當算法進行一定時間t后，計算網格服務器通知各個工作機提交各自子種群中當前適應度=f_max的個體（最優個體）到計算網格服務器，再由計算網格服務器將這些個體送到與發送這些個體不同的工作機子種群中去。工作機接收這些個體后，繼續開始各自的進化。

假設網絡上有n臺工作機：w₁，w₂，w₃，…，w_n。當算法運行時間t后，工作機選出各自的最優個體i₁， i₂， i ₃，…，i_n，并將它們發送到計算網格服務器。計算網格服務器接收到這些最優秀的個體后，將i₁發送到w₂，i₂發送到w₃，…，將i _n發送到w₁，當個體的交換完成后，工作機繼續自己的進化。為了防止死鎖，所有的工作機發送和接收個體都是先發后收。

4結論

如何獲得更好的性能是遺傳算法研究中的一個重要課題。目前很多并行遺傳算法的研究都針對這一目標做了很多工作，傳統的并行遺傳算法主要利用了分布式并行計算的思想，而網格計算相對分布式并行計算有靈活、投資小的優勢。本文描述的模型能夠在網絡上征集免費的計算資源進行并行遺傳算法的計算，是一個不錯的選擇。同時，針對具體問題如何尋找優化的并行策略和種群劃分策略是有待解決的問題。

參考文獻：

[1]J H Holland. Adaptation in Natural and Artificial Systems[M]. Michigan: The Univ. Michigan Press， 1975.

[2]Murata T. Petri Nets: Properties， Analysis and Application[C]. Proceedings of the IEEE， 1989.541-570.

[3]王耀南，童調生.基于模糊Petri網絡的獲取知識的方法[C]. 中國機器學習會議.北京：電子工業出版社，1993.245-252.

[4]Goldberg D E. Genetic Alogrithms in Search， Optimization Machine Learning[M]. Boston: Addison Wesley Publishing Company， 1989.

[5]Srinivas M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J]. IEEE Trans. SMC， 1994，24(4):655-677.

[6]周明，孫樹棟，彭炎午.并行遺傳算法的研究評述[J]. 南昌航空工業學院學報，1998，(2):84-88.

作者簡介：李鐳（1979-），男，碩士研究生，主要研究方向為網格計算和P2P網絡；蔡洪斌（1966-），男，副教授，博士，主要研究方向為計算機網絡；吳躍（1958-），教授，博導，主要研究方向為數據挖掘、移動代理技術。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。