張麗巖 ，馬 健 ，孫 焰

(1.同濟大學(xué) 交通運輸工程學(xué)院，上海 201804；2.蘇州科技學(xué)院 土木工程學(xué)院，江蘇 蘇州 215011)

近兩年來，隨著超線程處理器和多核處理器技術(shù)的出現(xiàn)及廣泛應(yīng)用，基于多核的并行計算成為新的研究熱點[1-2]。多CPU多核計算機采用稱為對稱多處理器SMP(Symmetrical Multi-Processing)的數(shù)據(jù)處理結(jié)構(gòu)，這種結(jié)構(gòu)特別適合需要大內(nèi)存、高性能CPU計算能力的應(yīng)用場合，能夠滿足大型科學(xué)計算及實時信息處理的需要。從系統(tǒng)性能來看，SMP的通信時間比Cluster大大減少。盡管今天主流計算機仍然是基于單CPU雙核的芯片技術(shù)，相信不久將來，單CPU 4核、8核乃至 16核的計算機將會到來，單機多CPU、多核高性能計算技術(shù)必將成為主流。

本文旨在提出一種基于多核SMP結(jié)構(gòu)的三層并行遺傳算法 TPGA(Three-tier Parallel Genetic Algorithm)，并基于線程構(gòu)建模塊TBB(Threading Building Blocks)，采用C++實現(xiàn)了這種算法。并采用裝箱問題來驗證TPGA的正確性及有效性，同時對TPGA進行了優(yōu)化，以加快收斂速度，提高解的質(zhì)量，充分發(fā)揮了多核SMP計算機的性能。

1 線程構(gòu)建模塊

1.1 線程構(gòu)建模塊簡介

TBB是一個開源的C++模板庫，它可將線程抽象成任務(wù)，然后創(chuàng)建可靠、可移植且可擴展的并行應(yīng)用程序。使用TBB編寫基于任務(wù)的并行應(yīng)用程序，有助于提高跨多核平臺上運行的可擴展軟件的開發(fā)效率。與本地線程和線程封裝器(wrapper)等其他線程化方法相比，它能夠充分利用多核平臺的并行性能[1-3]，是執(zhí)行并行應(yīng)用程序最高效的方式，TBB有以下三個顯著的優(yōu)點[2]：(1)TBB對線程進行抽象，將其提高到任務(wù)的高度，簡化了并行應(yīng)用程序的開發(fā)工作；(2)基于TBB開發(fā)的應(yīng)用程序的性能，可以隨著處理器內(nèi)核數(shù)量的增加而自動提升；(3)TBB能夠減少死鎖和資源競爭等常見線程錯誤，提供了一個跨平臺的并行解決方案。本文采用C++實現(xiàn)了基于TBB的 TPGA和 SGA(Sequential Genetic Algorithm)，充分利用了TBB的高效性、可靠性和可擴展性[1-5]。

1.2 TBB[1]的特性

對于開發(fā)者來說，TBB有以下明顯的好處：(1)TBB大大減少了開發(fā)多線程并行應(yīng)用程序所需的代碼行數(shù)，它的任務(wù)抽象模型節(jié)省了大量的開發(fā)時間；(2)TBB屏蔽了抽象線程管理的許多細節(jié)，大大降低了開發(fā)多線程應(yīng)用程序的復(fù)雜性；(3)基于TBB的多線程程序在運行時，其任務(wù)管理器會自動分析運行環(huán)境，并根據(jù)實際情況選擇最佳的線程數(shù)量(在程序的參數(shù)限制范圍內(nèi))，使系統(tǒng)在所有的處理器上保持最佳的負載平衡。因此，TBB多線程應(yīng)用程序能夠自動調(diào)整線程規(guī)模，充分利用一切可用的多核處理器資源，發(fā)揮多核平臺的并發(fā)優(yōu)勢，提高程序的運行效率。線程庫的功能比較如表1所示。

表1 線程庫的功能比較

2 并行化思維

2.1 串行算法并行化

一般情況下，設(shè)計并行算法有三種策略[4-5]：(1)分析現(xiàn)有串行算法中的并行性，并直接將其并行化；(2)從問題本身出發(fā)，根據(jù)問題固有的并行性，設(shè)計一個全新的并行算法；(3)借用已有的并行算法求解新的問題。

目前，串行算法的發(fā)展已經(jīng)比較成熟，在設(shè)計并行算法時要充分加以利用，并盡量在其基礎(chǔ)上直接并行化，或者將其內(nèi)嵌在其他并行算法中。本文采用第二種策略將串行遺傳算法(SGA)內(nèi)嵌于TPGA算法中，使之能更好地利用多核計算機的并行處理能力，加快算法的收斂速度，提高解的質(zhì)量。

2.2 數(shù)據(jù)并行性與任務(wù)并行性

在并行算法的具體實現(xiàn)中大多先采用劃分技術(shù)，即將一個問題劃分為許多子問題，這些子問題彼此獨立但又密切相關(guān)，然后將它們分派給不同的線程或進程，并在不同的處理器上執(zhí)行，最后，采用合并技術(shù)將不同線程或進程得到的結(jié)果進行合并。在一個具體的實際問題中，并行性的存在形式可以是并行操作的數(shù)據(jù)或者是并發(fā)執(zhí)行的任務(wù)。如果給定一個數(shù)據(jù)集合，對在此集合中的每個元素都執(zhí)行相同的操作，那么就可以并發(fā)地在每個元素上執(zhí)行相同的任務(wù)[3-5]。

圖1是數(shù)據(jù)并行性的示例圖，表明如果給定一個數(shù)據(jù)集合以及集合中的每一個元素都執(zhí)行相同的操作，利用數(shù)據(jù)并行性，就可以并發(fā)地在每個元素上執(zhí)行相同任務(wù)。圖中CAP為小寫轉(zhuǎn)大寫運算。

圖1 數(shù)據(jù)并行性的示例圖

任務(wù)并行性指的是大量通過共享數(shù)據(jù)被關(guān)聯(lián)在一起的不同任務(wù)。圖2是任務(wù)并行性的示例圖，圖中以一些數(shù)學(xué)運算為例，其中每個運算都可以應(yīng)用到相同的數(shù)據(jù)集合上以計算獨立的值。圖中AVERAGE為求平均值；MINIMUM為求最小值；BINARY OR為求二進制“或”；GEO-MEAN為求幾何平均。

圖2 任務(wù)并行性的示例圖

數(shù)據(jù)的并行性受限于所要處理的數(shù)據(jù)，包括數(shù)據(jù)規(guī)模、數(shù)據(jù)類型、數(shù)據(jù)存儲格式等，而任務(wù)的并行性是將不同的任務(wù)通過數(shù)據(jù)共享關(guān)聯(lián)在一起并發(fā)執(zhí)行。純粹的任務(wù)并行性要比純粹的數(shù)據(jù)并行性更難發(fā)現(xiàn)。本文采用三層架構(gòu)，集成了數(shù)據(jù)的并行性和任務(wù)的并行性，更易于TPGA的并行實現(xiàn)。

3 三層并行遺傳算法

3.1 并行遺傳算法

遺傳算法GA(Genetic Algorithm)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學(xué)的觀點。在計算機中，通過對自然選擇、遺傳、變異等作用機制的模擬，實現(xiàn)提高各個個體的適應(yīng)性。

遺傳算法是從代表問題可能潛在解集的一個初始種群開始的，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中個體的適應(yīng)度大小挑選個體，并借助自然遺傳學(xué)的遺傳算子進行組合交叉和變異，產(chǎn)生出代表新解集的種群。這個過程將導(dǎo)致種群像自然進化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼，可以作為問題的近似最優(yōu)解[6-7]。

雖然遺傳算法已經(jīng)成功地應(yīng)用在許多領(lǐng)域，且能在合理的時間內(nèi)找到滿意解，但隨著求解問題的復(fù)雜性及難度的增加，提高GA的運行效率顯得尤為重要，采用并行遺傳算法PGA(Parallel Genetic Algorithm)是提高運行效率的方法之一。由于GA以種群為出發(fā)點，具有天然的并行特性，非常適合并行實現(xiàn)，而多核計算機的日益普及，為PGA奠定了物質(zhì)基礎(chǔ)。GA中各個體適值計算可獨立進行且彼此間無需通信，所以并行效率很高。

實現(xiàn)PGA，重要的是對SGA的結(jié)構(gòu)進行分析，發(fā)現(xiàn)結(jié)構(gòu)中的數(shù)據(jù)并行性及任務(wù)并行性，把SGA等價地變換成一種并行方案，形成并行種群模型。并行種群模型對傳統(tǒng)SGA的修改涉及到兩個方面：一是數(shù)據(jù)并行化，即將SGA的單一種群分成多個子種群，分而治之；二是任務(wù)并行化，即控制、管理子種群之間的信息交換及種群內(nèi)部的操作。不同的分治方法產(chǎn)生不同的PGA結(jié)構(gòu)。這種結(jié)構(gòu)上的差異導(dǎo)致了不同的PGA模型，即全局并行模型、粗粒度模型、細粒度模型[8]。

3.2 TPGA的框架

為了集成數(shù)據(jù)的并行性和任務(wù)的并行性，本文采用三層架構(gòu)，實現(xiàn)了TPGA。(1)第一層是數(shù)據(jù)編碼并行化。分析輸入數(shù)據(jù)的特點，包括數(shù)據(jù)類型、存儲形式、數(shù)據(jù)規(guī)模等，找出其中的并行性，進行數(shù)據(jù)分解、數(shù)據(jù)編碼，以得到適合任務(wù)并行執(zhí)行的數(shù)據(jù)編碼及數(shù)據(jù)模塊。(2)第二層是任務(wù)處理并行化。將經(jīng)過分解的數(shù)據(jù)模塊及數(shù)據(jù)編碼傳入SGA，各個SGA并發(fā)的執(zhí)行，得到各自的適應(yīng)函數(shù)值。(3)第三層是數(shù)據(jù)解碼并行化。將各個SGA得到的值傳給數(shù)據(jù)整合模塊，經(jīng)過并行化處理，得到最優(yōu)解。圖3是TPGA的通用框架[9]。

圖3 TPGA的通用框架

4 在裝箱問題中對TPGA的驗證

裝箱問題是一個典型的組合優(yōu)化問題，其屬于NP完全問題，這類問題不存在有效時間內(nèi)求得精確解的算法，所以裝箱問題的求解極為困難。一般采用啟發(fā)式算法求解此類問題。

本算例主要研究的是抽象意義下的裝箱問題，可以描述為給定的箱子及物品(設(shè)物品的尺寸小于箱子的尺寸，且為規(guī)則物體)，目標是設(shè)計一種方案，將所有物品裝入箱子而使箱子的利用率最高。在這里，假設(shè)物品的擺放方向不受約束，穩(wěn)定性及裝載的均勻性等暫不考慮[10]，主要考慮箱子的最大載重量、承載能力等。將上述TPGA思想應(yīng)用到裝箱問題中，并利用罰函數(shù)法改造目標函數(shù)來解決裝箱問題，其模型如下：

設(shè)m為某一裝箱方案中所用箱子的數(shù)目，B(ui)為物品ui所裝入箱子的編號，sj為考慮了罰函數(shù)之后的Bj箱所裝物品的體積之和。要使所用箱子數(shù)目最少，可以取下式為優(yōu)化目標函數(shù)：

式中，α為某一箱子Bj中所裝物品的體積之和超出箱子規(guī)定容積時的懲罰因子，α＞0。

該目標函數(shù)既考慮了使所用箱子的數(shù)目最小，又考慮了使每個箱子裝完物品后所剩余的容積盡可能小。

圖4為TPGA的求解裝箱問題示意圖。

圖4 TPGA流程圖

5 TPGA與SGA的對比

5.1 TPGA的有效性驗證

在本算例中，假設(shè)箱子的體積為1(箱子長、寬、高均為 1)，箱子的數(shù)量為 18(根據(jù)物品個數(shù)而定)，初始群體大小為18，染色體長度為 18(根據(jù)物品個數(shù)決定)，算法迭代次數(shù)視具體情況而定。通過調(diào)節(jié)算法中的懲罰因子α、交叉概率pc、變異概率pm三個主要參數(shù)，確定了以懲罰因子 α=0.45，交叉概率 pc=0.8，變異概率 pm=0.001來進行遺傳算法的計算。將其迭代5 000次，不同算法的結(jié)果對比如表2所示。

表2 TPGA與SGA的裝箱方案對比

由表2可以看出，SGA總共用了10個箱子且箱子的平均利用率為70.2%；而TPGA總共用了9個箱子且箱子的平均利用率為81.3%；TPGA要明顯優(yōu)于基本遺傳算法SGA。

5.2 TPGA的效率性驗證

為了更好地比較實驗結(jié)果，應(yīng)在同一平臺下進行實驗，本文的實驗平臺具體配置為：CPU為Intel Pentium Dual-Core(Merom)T3400(2.16 GB)；內(nèi)存 2 048 MB；操作系統(tǒng)為 Windows XP(sp2)。

圖5給出了不同箱子的規(guī)模 (染色體長度規(guī)模)，不同線程數(shù)目與收斂速度的對應(yīng)關(guān)系。通過比較分析，得到此情況下的最優(yōu)線程數(shù)和全局最優(yōu)解。與此同時，分析比較TPGA與SGA的運行效率及收斂速度。

由圖5可以看出，當(dāng)線程數(shù)目為1時 (此時即為SGA)，隨著箱子規(guī)模的增大，系統(tǒng)的運行時間明顯增大很多，收斂速度較慢；當(dāng)線程數(shù)目為128時 (此時即為TPGA)，此時的子矩陣為 32，隨著箱子規(guī)模的增大，系統(tǒng)的運行時間有所增加，收斂速度較快。通過兩者對比，當(dāng)線程數(shù)目增加到一定程度時，可以明顯看出，TPGA的運行時間要明顯小于SGA的運行時間。可見，當(dāng)箱子規(guī)模較大時，TPGA要明顯優(yōu)于SGA。

圖5 線程數(shù)與收斂速度關(guān)系圖

本文提出了TPGA，并用于解決裝箱問題。經(jīng)實驗證明，TPGA明顯優(yōu)于SGA，且在解的優(yōu)化程度和收斂速度上均有顯著提高，并對TPGA進行了優(yōu)化。當(dāng)懲罰因子α=0.45，交叉概率 pc=0.8，變異概率 pm=0.001，線程數(shù)目為128，子矩陣為32時，TPGA能夠取得相對較好的解。此時收斂速度較快，并且解的優(yōu)化程度較高。

TPGA還可應(yīng)用于有大量計算機節(jié)點的分布式系統(tǒng)，及算法參數(shù)的進一步優(yōu)化等，以進一步提高解的質(zhì)量及收斂速度。同時，TPGA也可以應(yīng)用于其他領(lǐng)域，如物流的選址問題、交通路徑選擇問題等。

[1]http：//www.threadingbuildingblocks.org/[OL].

[2]REINDERS J.Intel threading building blocks outfit-ting C++for multi-core processor parallelism[M].First Edition，O′Reilly Media， Inc.， 2007.

[3]劉勇，等.非數(shù)值并行算法—遺傳算法[M].北京：科學(xué)出版社，1995.

[4]BLAKE C L，MERZ C J.UCI repository of machine learning databases[DB/OL]. http：//www.ics.uci.edu/～mlearn/MLRepository.htm，2003.

[5]LIANG J Y，CHIN K S，DANG C Y，et al.A new method for measuring uncertainty and fuzziness in rough set theory[J].International Journal of General Systems， 2002，31(4)：331-342.

[6]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M]，西安：西安交通大學(xué)出版社，2002.

[7]陳鵬.并行遺傳算法初始種群劃分建模與設(shè)計[J].計算機工程與應(yīng)用，2004(7)：78-79.

[8]崔明義.并行遺傳算法在工程智能優(yōu)化中的實現(xiàn)策略[J].計算機工程與應(yīng)用，2004(7)：90-91.

[9]Ma Jian， Li Keping， Zhang Liyan.The adaptive parallel simulated annealing algorithm based on TBB[C]，The 2nd IEEE InternationalConference on Advanced Computer Control，2010.

[10]張麗巖.裝箱問題BFD混合遺傳算法的仿真研究[D]，南京：河海大學(xué)，2006.