算法骨架

算法骨架，英文全稱是：algorthmic skeleton，是一種並行編程環境。

基本介紹

• 中文名：算法骨架
• 外文名：algorthmic skeleton
• 實質：一種並行編程環境
• 內容：語言功能和套用編程接口

名稱

並行編程環境為構建並行程式提供了基本工具、語言功能和套用編程接口（API）。Murray.Cole最早引入了skeleton（algorithmic skeleton）的概念，其中skeleton是算法的抽象，是對重複出現的算法和通信模式的精確、嚴格的定義，它對一系列的套用而言是公共的，並且可以並行地實現。

並行骨架作為高層次的並行程式設計語言構件，其中包含了並行性、通信、同步以及其它相關信息。基於骨架的並行編程，具有更高級的抽象層次，隱藏運行環境內部的實現細節，從而可以簡化並行程式的開發。所以並行骨架可以作為一個並行工具包來減少編程錯誤，簡化編程細節，程式設計師可以利用工具包來針對需要解決的問題建立[2]。

一般並行程式設計可分為並行算法的設計和並行算法的實現兩個階段，然而對許多複雜的問題而言，其算法設計本身就很困難，要直接得到並行算法更加困難，因此進一步將並行算法的設計畫分為算法設計和算法並行化兩個階段，以避免在問題求解的一開始就把並行的因素考慮進來，掩蓋了問題的本質，影響問題的求解[3]。

算法設計階段完成對給定的問題確定其求解的策略的功能，在思路上不涉及並行性的考慮。對於使用某種特定算法設計方法進行求解的問題，先在並行算法骨架庫中尋求合適的並行算法骨架，如果存在，那么可以選擇使用這個並行算法骨架。算法並行化階段使用特定的並行結構骨架完成各種操作的並行。基於骨架的並行編程系統一直以並行程式開發的易用性為目標，其軟體體系結構如圖 1 所示。

圖1 基於骨架的並行編程環境的軟體體系結構

作用

通過提供算法骨架，使得用戶只需考慮問題的類型，適合哪種算法骨架，而不必顯式地去處理如並行單元間通訊、同步等低層的並行特性，同時算法骨架還是與具體問題中無關的，從具體的問題和具體的並行環境都相解脫出來。所以算法骨架的作用可以總結為：

（1）通過提高並行開發的抽象層次，簡化了並行程式設計。

（2）通過skeleton的實現細節對用戶透明，提高skeleton的可重用性和可移植性。

（3）在特定的體系結構上，skeleton的實現能夠充分利用最佳化技術，從而有效提高並行程式的性能。

skeleton的上述思想與軟體工程中許多成功的思想是相同的，如結構化的程式設計、面向對象編程和設計模式等。值得一提的是，設計模式的思想已被擴充到並行領域。由於skeleton與設計模式概念的相關性，基於skeleton的並行程式設計領域將基於skeleton與基於模式的並行研究工作很好地融合在一起，以提供一種通用的、更高層次的並行程式設計方法。

在特定的體系結構上，算法骨架能夠充分利用最佳化技術，從而有效提高並行程式的性能，而這並不是所有從事並行編程的程式設計師所具備的，或者說讓每一個並行程式設計師都編出很優秀的並行是很難的；這裡的算法骨架獨立於各種並行計算環境，與各種並行計算環境無關的，並針對不同的計算環境做出相應的調整。

當前國內外研究現狀

國內外關於算法骨架的研究也很多。

不同的組織都有各自的算法骨架，如Cole的eskel，Darlington、Rabhi、P3L等知名的骨架；

前景

並行已經成為程式設計中的一個趨勢，越來越高要求的計算，越來越多的多核處理器，都預示著未來計算機世界的並行趨勢已成必然。

並行遺傳算法骨架

並行遺傳算法骨架(PGA_Skeleton)是為了簡化遺傳算法套用問題的求解過程，並可並行實現的這一類問題求解和算法設計方法的一種抽象結構。

並行遺傳算法作為套用求解大型問題的方法，套用範圍很廣，包括函式最佳化、組合最佳化、生產調度等一系列問題，我們將其中的大部分雷同的部分形成抽象的算法骨架，這就是並行遺傳算法骨架，它可以簡化這類問題的求解過程，以及降低用戶求解難度。

PGA_Skeleton 的描述

在PGA_Skeleton中，完成了包括初始化種群、選擇、交叉、突變等幾乎所有遺傳算法套用中的計算操作以及遺傳進化過程的控制行為，只為用戶留下個體適應度評價函式作為與具體問題的互動接口。PGA_Skeleton 通過調用結構骨架來實現操作的並行，由於現存結構骨架形式多樣，並行執行流程也就不盡相同，所以需要根據問題的不同特點選擇合適的結構骨架，比如當個體適應度評價函式 (evaluate) 的複雜度較高時，使用 FARM 結構骨架並行效果就十分明顯。PGA_Skeleton 由種群初始模組和遺傳進化模組，流程圖如圖 2 所示。

圖2 PGA_Skeleton 內部流程

種群初始模組(PGACreate)負責建立初始種群，需要接收來自用戶的參數，包括染色體的編碼方式，染色體上字元串的長度和初始種群的規模。遺傳進化模組(PGARun)包括結構骨架選擇(PGAChoose)、結構骨架調用和進化終止檢查(PGACheck)3 部分組成。結構骨架選擇部分根據問題規模和適應度函式複雜度，按照選擇策略確定一個結構骨架；結構骨架調用部分將選擇、交叉、變異和個體適應度評價函式傳遞給選中的結構骨架並行執行；進化過程控制部分主要對進化循環控制和個體遷移實現。套用並行抽象程式語言 APLA+描述 PGA_Skeleton 接口，如圖 3 所示

圖3 PGA_Skeleton接口描述代碼

PGA_Skeleton的內部流程

PGA_Skeleton由種群初始模組(PGACreate)和遺傳進化模組(PGARun)組成。

(1)初始化模組

種群初始模組(PGACreate)負責建立初始種群。種群初始化包括隨機產生和確定給出兩種方式，大多數情況下都採用隨機產生，這樣可以免去輸入工作的麻煩，它適合與對問題的解無任何先驗知識的情況；在具備某些先驗知識的情況下，可以根據要求產生一組個體，這樣可以使遺傳進化更快一些收斂到最優解。初始化工作需要接收來自用戶的參數，包括染色體的編碼方式，染色體上字元串的長度和初始種群的規模，這些參數共同確定初始種群的表現。

(2)進化模組

遺傳進化模組(PGARun)包括結構骨架選擇(PGAChoose)、結構骨架調用和進化終止檢查(PGACheck)三部分組成。首先PGAChoose根據問題規模和適應度函式複雜度，按照選擇策略確定一個結構骨架；然後結構骨架調用部分將選擇、雜交、變異和個體適應度評價函式等任務傳遞給選中的結構骨架並行執行；最後進化終止檢查部分檢查進化代數和收斂程度決定是否終止進化。

PGA_Skeleton的接口描述

按照並行抽象程式語言Apla+中定義的規定的關鍵字skeleton和語法描述PGA_Skeleton接口。其中CODETYPEFLAG是關於編碼方式的枚舉類型，包括一維二進制編碼、一維整數編碼、一維實數編碼、二維二進制編碼、二維整數編碼、二維實數編碼等常見的六種染色體編碼方式；PGACreate函式根據給定參數創建大小為nPopSize，編碼方式為codeTypeFlag，上下界分別為upper和lower，碼長為nChromSize的初始種群；函式PGARun完成遺傳進化模組的功能；函式GetChorm用於獲得第i個個體的染色體上的字元串值；函式SetFitness將適應度值寫回染色體中；函式Evaluate是用戶自己編寫的個體的適應度評價方法；函式GetBest獲取最優個體。

並行遺傳算法骨架的特點

透明機制

透明的機制是對用戶而言的，指的是並行程式設計師在編寫程式時，不必關心任務時如何並行執行的。用戶在調用PGA_Skeleton尋找最優解時，只知道問題的解是如何編解碼的，而不去涉及遺傳進化的整個進程。用戶只知道自己用的是一個並行遺傳算法骨架，而不去涉及這個算法骨架是調用哪個結構骨架實現並行的。用戶只需要熟悉PGA_Skeleton的接口，知道如何獲取最優解就足夠了。

編碼方式

對於編碼方式，首先必須是正確的，即保證雜交、變異之後的子代有意義，可以解碼得到實際問題的解。適應度評價過程包括解碼和評價兩個部分，先將染色體上的字元串進行解碼，得到有實際意義的解後對解的適應度評價，所以編碼方式的選擇一定程度上決定了適應度評價函式的程式編寫方法。

編碼方式的選擇在一定程度決定了雜交和變異操作，所以為了算法骨架的自動化編程，必須將編碼方式做一定程度的固定。常見的編碼方式按照表達形式可以分成二進制、整數、實數；按照維數可以分成一維、二維。讓用戶在現有的進制和維數上進行選擇，而不是任意的編碼方式，我們也可以把我們選擇使用的編碼方式稱為固定碼。

遺傳運算元

PGA_Skeleton內部包括選擇、雜交、變異運算元。其中既可以採用一些傳統的方法，如輪盤選擇、錦標賽選擇、單點兩點雜交、換位變異等，也可以採用一些現代方法，如非均勻變異和蠕變等，這些都與實際套用問題無關。

開放原則

各遺傳運算元的修改不會影響骨架的整體結構，所以在需要對並行遺傳算法調整時，可以按照需求更換遺傳運算元，PGA_Skeleton的升級是很方便的。這些都說明並行算法骨架是開放的。

結語

並行遺傳算法骨架是解決遺傳算法並行的一種行之有效的手段。PGA_Skeleton 是開放的，其中的遺傳運算元還可以引入一些現代化的方法，如均勻交叉，蠕變等，用以達到提高更好的進化效果。由於該算法骨架的並行實現依賴於結構骨架的實現，但是目前結構骨架庫中目前僅提供了FARM和Data Parallel兩種合適的結構骨架可供選擇，所以進一步的工作將放在組合骨架設計的研究上，以便提供組合骨架的支持，從而實現混合併行遺傳算法模型。