基本介紹
- 中文名：並行遺傳算法
- 外文名：Parallel Genetic Algorithm
- 簡稱：PGA
- 具體：對遺傳算法進行並行設計後的算法
- 模型分類：主從式、粗粒度、細粒度、混合
- 屬於：遺傳算法
簡介,遺傳算法的並行形式,遺傳算法並行模型,主從式模型,粗粒度模型,細粒度模型,混合模型,評價並行遺傳算法,
簡介
遺傳算法是一類基於自然選擇和遺傳學原理的有效搜尋方法，許多領域成功地套用遺傳算法得到了問題的滿意解 。雖然遺傳算法通常能在合理的時間內找到滿意解，但隨著求解問題的複雜性及難度的增加，提高遺傳算法的運行速度便顯得尤為突出 。遺傳算法具有天然的並行性，非常適合於在大規模並行計算機上實現，而大規模並行計算機的日益普及，為並行遺傳算法奠定了物質基礎。實現並行遺傳算法，不僅要把串列遺傳算法等價地變換成一種並行方案，更重要的是要將遺傳算法的結構修改成易於並行化實現的形式，形成並行群體模型。
並行遺傳算法將並行計算機的高速並行性和遺傳算法的天然並行性相結合，並行處理的引入不僅提高了求解速度，而且由於種群規模的擴大和各子種群的隔離，使種群的多樣性得以豐富和保持，減少了未成熟收斂的可能性，提高了求解質量。
遺傳算法的並行形式
遺傳算法具有天然的並行性，其並行形式有以下4類：
(1)個體適應度評價內部的並行性;
(2)種群中每個個體適應度評價的並行性;
(3)算法基本操作內部的並行性;
(4)基於種群分組的並行性
遺傳算法並行模型
實現並行遺傳算法，不僅要把串列遺傳算法等價地變成一種並行方案，更重要的是要將遺傳算法的結構修改成易於並行化的形式，形成並行模型。目前遺傳算法並行模型共分為四類：主從式模型 ，粗粒度模型，細粒度模型和混合模型。以下作詳細介紹：
主從式模型
主從式模型是遺傳算法的直接並行化方案，不改變遺傳算法的基本結構特點，它只有一個群體，選擇、交叉和變異等全局操作由主節點機(或主處理器)串列進行，而適應度的評價和計算由各從節點機(或從處理器)並行執行主節點機(或主處理器)和從節點機(或從處理器)的通信表現在兩個方面，一方面主節點機(或主處理器)把選擇的群體部分個體傳送給從節點機(或從處理器)；另一方面從節點機(或從處理器)把適應度的評價結果傳送給主節點(或主處理器)。
粗粒度模型
粗粒度模型又被稱作分散式模型或孤島模型 ,是適應性最強和套用最廣的遺傳算法的並行模型.它將群體依照節點機(或處理器)的個數分成若干個子群體,各個子群體在各自的節點機(或處理器)上並發獨自運行遺傳算法，每經過一定的進化代，各個子群體間將交換若干個個體， 一方面用來引入更優良的個體，另一方面豐富了種群的多樣性，達到了防止未成熟早收斂現象[ 4] 。對於粗粒度模型，可以看出何時交換個體，交換哪些個體，採用什麼方式交換是關鍵問題，因此目前對粗粒度模型的研究，主要是解決這幾個方面的問題，也就是我們常說的如何確定遷移規模、遷移策略和遷移拓撲等問題。
細粒度模型
細粒度模型又稱作鄰域模型, 在整個進化過程中雖然保持一個群體, 但要求子群體的劃分要非常細小 ,最理想狀態是每個節點機(或處理器)只有一個個體,要求各節點機(或處理器)具有極強的通信能力 ,對於每個染色體,選擇和交叉操作都只在所處的節點機(或處理器)及其鄰域中進行。 由於整個進行過程中 ,不需要或者需要很少的全局操作, 因此充分發揮了遺傳算法並行特性。
混合模型
混合模型是近些年快速發展起來的模型結構, 主要是通過把前面三種基本模型混合形成層次結構。目前混合模型組合關係主要有三種:粗粒度—細粒度、粗粒度—粗粒度和粗粒度—主從式。在形成的層次結構中,在下層的並行模型中,子群體的規模是真實的 ,即為一個處理進程所處理的個體數量。而對於上層模型，將每個下層的並結構都視為一個‘’集合子群體”，而“集合子群體”之間按上層的並行模型協調運行。對於此混合模型，無論在下層還是在上層，都是子群體內部信息互動量大，之間信息互動量小。
對於此四種模型, 哪種模型更好沒有一個明確的標準 ,甚至對於不同問題往往得出互相矛盾的答案. 對於主從式模型,由於僅適用計算時間主要集中在適應度評估的問題 , 因此適用的範圍受到了極大的限制 ;對於細粒度模型 , 是採用大範圍的鄰域模型 ,還是採用小範圍直徑也有爭議,特別是由於對節點機(或處理器)的數量和通信能力要求很高 ,所以細粒度模型的套用範圍也不廣;對於粗粒度模型 ,雖然採用什麼樣的遷移拓撲 、遷移規模和遷移策略還需深入研究 ,但由於通信開銷較小,可獲得接近線性的加速比,而且非常適合運行在通信頻寬較低的集群系統上[ 16], 因此得到了廣泛的套用;混合模型是在前三種模型的基礎上建立起來的, 由於具有很好的並行性特點,已成為人們研究的主流,但從套用效果看,目前只有粗粒度 —主從式模型套用較好
評價並行遺傳算法
為更好和更實用地評價並行遺傳算法，文獻1和文獻2結合實際給出了兩條評價並行遺傳算法的指標：
(1) 確定一個適應度指標，分別利用串列遺傳算法和並行遺傳算法計算達到某一個個體適用度高於指定適用度指標的時間，然後讓串列搜尋時間除以並行搜尋時間，作為並行遺傳算法的加速比指標。
(2) 給定一定時間，利用 PGAs 進行最佳化，測量能夠得到的最高適用度比利用串列遺傳算法搜尋到的最高適應度高出多少。
對於上面兩條評價指標， 不難發現，第二條評價指標更具有實用價值。對於不同問題， 由於問題差異、群體大小及採用不同的局部搜尋方法等等因素不同 ，評價模型得出的結果也會有差異，因此對於並行遺傳算法評價模型仍需深一步研究。
