基于MapReduce 泛型遺傳算法的機(jī)載計(jì)算機(jī)散熱器設(shè)計(jì)

劉世卿

（中航工業(yè)西安航空計(jì)算技術(shù)研究所，西安 710119）

0 引言

現(xiàn)代微電子器件高密度封裝、多種功能用途、高速工作的特點(diǎn)決定了其功率耗散密度的增大，會(huì)產(chǎn)生更多的熱量。在一定環(huán)境溫度條件下，為了使機(jī)載計(jì)算機(jī)能夠可靠、穩(wěn)定地工作，必須將設(shè)備所產(chǎn)生的大量熱量散發(fā)出去；因此，熱設(shè)計(jì)技術(shù)比起電參數(shù)設(shè)計(jì)、結(jié)構(gòu)設(shè)計(jì)的重要性會(huì)更為突出［1］。

傳統(tǒng)的應(yīng)用遺傳算法（Genetic Algorithm，GA）對(duì)箱體散熱進(jìn)行優(yōu)化設(shè)計(jì)的問題［3，7］，伴隨著應(yīng)用問題的規(guī)模增加、影響因素的增多，逐漸面臨效率低下的問題。GA 的研究從一開始就是基于并行處理，早在1960 年代初期，Holland 教授就認(rèn)識(shí)到了遺傳算法的自然并行性。近年來，人們不斷地致力于把遺傳算法應(yīng)用到各種并行計(jì)算機(jī)上，即并行遺傳算法（Parallel Genetic Algorithm，PGA）的理論和應(yīng)用研究［5］。但是這些并行遺傳算法大都采用較低的抽象框架（如MPI［8］），不但很難實(shí)現(xiàn)編程，而且也不易擴(kuò)展［6］。

在函數(shù)式語(yǔ)言兩大算子map 和reduce 基礎(chǔ)上，Google 公司開發(fā)了MapReduce 這一通用并行抽象計(jì)算模型［9，12］。MapReduce 通過把并行數(shù)據(jù)處理以及并行計(jì)算的操作抽象為map 和reduce 兩種，大大降低了分布式并行計(jì)算程序間的耦合程度，在提供高效計(jì)算的同時(shí)還具有很好的可擴(kuò)展性與易編程性特點(diǎn)。

正是基于這樣的考慮，本文擬將遺傳算法與MapReduce 相結(jié)合，克服傳統(tǒng)PGA 的不足，并應(yīng)用于箱體散熱器的算例當(dāng)中。然而遺傳算法各種群間交叉運(yùn)算的存在，使得不能簡(jiǎn)單套用傳統(tǒng)map 和reduce 算子完成遺傳算法的并行化。據(jù)此，本文設(shè)計(jì)了基于復(fù)合MapReduce 的遺傳算法（Currying MapReduce GA，CMRGA），并應(yīng)用該算法對(duì)密閉箱體散熱器進(jìn)行了結(jié)構(gòu)優(yōu)化。

1 遺傳算法求解密閉箱體散熱器參數(shù)優(yōu)化問題

1.1 優(yōu)化目標(biāo)函數(shù)

通過對(duì)散熱模型設(shè)計(jì)方案的研究，在箱體模型兩側(cè)添加散熱翹片可以使得密閉機(jī)箱能夠通過箱體達(dá)到一個(gè)快速散熱的作用。而箱體散熱器的設(shè)計(jì)必須滿足特定的設(shè)計(jì)要求，才能達(dá)到箱體散熱性能的提高和經(jīng)濟(jì)實(shí)用、便于攜帶的目的［2，13］。

圖1 表示箱體散熱器局部肋片模型，散熱性能參數(shù)有影響的包括肋片形狀Cx、肋片材料Cc、肋片數(shù)目N、長(zhǎng)度L、寬度W、高度H、肋片厚度b、氣流速度v 等。散熱器熱阻與上述變量的關(guān)系［3］為：

上述變量對(duì)散熱器熱阻的影響各有不同，優(yōu)化過程中對(duì)各變量的考慮如下：

1）通過前人的試驗(yàn)研究和概括得到的經(jīng)驗(yàn)公式對(duì)流動(dòng)和傳熱情況進(jìn)行描述，冷卻氣流通過散熱器時(shí)的方向是順著肋片長(zhǎng)度的方向。

2）散熱器的結(jié)構(gòu)形式是通過肋片的形狀決定的，不同形式的肋片有不同的流動(dòng)特性。為了減少未知的參數(shù)我們就不一一考慮，根據(jù)實(shí)際情況，本文所用的是實(shí)際應(yīng)用中最為廣泛的鋁合金型材散熱器（Cc確定），其翅片通常為矩形（Cx確定）。

3）忽略肋片厚度b（以0.5mm為界）極小的情形，因?yàn)樵趯?shí)際情況中b 很小、N 很大時(shí)屬于微通道散熱器設(shè)計(jì)的范疇，本文不做考慮。

4）氣流速度v 與散熱器熱阻成反比。氣流速度v 越大，熱阻越小，我們將v 設(shè)為定值。

本文主要考慮熱阻Rs最小為優(yōu)選目標(biāo)，依據(jù)上述變量考慮，將散熱器熱阻優(yōu)化的目標(biāo)函數(shù)寫為：

通過散熱器和冷流體的最大溫差除以熱源功率來確定散熱器的熱阻，則由相關(guān)文獻(xiàn)［4］可以得到Rs在層流和湍流下的表達(dá)式：

（1）層流，Re≤2300

其中，Re為雷諾數(shù)、s為肋片內(nèi)距、Dh為當(dāng)量直徑、Pr為普朗克常量，其余參數(shù)的詳細(xì)說明與計(jì)算見文獻(xiàn)［4］。

1.2 優(yōu)化參數(shù)限定與求解步驟

某機(jī)載計(jì)算機(jī)的箱體散熱器設(shè)計(jì)中，需要優(yōu)化的變量為：肋片數(shù)N；肋厚b；長(zhǎng)度L；寬度W；高度H。約束條件：①肋片數(shù)N 的搜索范圍：［2，50］；②肋厚b 的搜索范圍［0.5，W］，即肋厚不應(yīng)小于0.5mm，最大不應(yīng)超過散熱器寬度W；③L、W、H 的搜索范圍分別為［300，400］、［350，450］、［15，25］。

針對(duì)上述約束條件下求解最小化Rs的問題，遺傳算法計(jì)算設(shè)計(jì)如下：

1）編碼與解碼。擬抽取種群數(shù)量為M，在遺傳算法中采用二進(jìn)制編碼的方式：N 直接用其對(duì)應(yīng)的二進(jìn)制數(shù)值編碼；b、L、W、H 本身有一定的取值約束，對(duì)其的編碼舉例說明如下：H 的取值范圍為［10，20］，對(duì)H 采用5 位二進(jìn)制編碼為00001 時(shí)，其對(duì)應(yīng)的真實(shí)值為：10+（20-10）*1/2^6，當(dāng)然也可以采用n 位二進(jìn)制為H 編碼，這里的n決定了在［10，20］取值范圍內(nèi)的數(shù)值精度。解碼時(shí)N 直接轉(zhuǎn)化為十進(jìn)制值即可，b、L、W、H 需要通過上述例子的方法解碼。

3）交叉算子。交叉算子采用單點(diǎn)交叉來產(chǎn)生新一代個(gè)體，根據(jù)隨機(jī)函數(shù)隨機(jī)確定一個(gè)整數(shù)，該整數(shù)在0 到X（X為位置編號(hào)）之間，從而確定交叉位置。0.6～1.0為典型的交叉概率的取值范圍［7］。

4）變異算子。在本文采取的二進(jìn)制編碼方法下，其中每一位的變異由1 到0 或者由0 到1。變異概率Pm取值范圍一般為0.01～0.1［7］。

5）選擇策略。本算法按照熱阻大小從雜交變異后產(chǎn)生的新的種群和父種群中選取最小的若干個(gè)個(gè)體，組成下一代種群，則每代的較優(yōu)個(gè)體都保留在產(chǎn)生的新一代種群中。

6）算法的終止條件。經(jīng)過數(shù)代的迭代后，選擇最優(yōu)熱阻值，并將輸出群體中多個(gè)較優(yōu)的個(gè)體作為供決策者選擇的備選方案。

2 應(yīng)用CMRGA 求解箱體散熱器參數(shù)優(yōu)化

在優(yōu)化精度不要求很高、箱體設(shè)備數(shù)量較少的情況下，應(yīng)用傳統(tǒng)遺傳算法可以在能接受的較短時(shí)間內(nèi)完成問題的求解。然而隨著航電應(yīng)用中設(shè)備規(guī)模的不斷增大、數(shù)量不斷增多，加之設(shè)計(jì)精度的要求不斷提高，都增大了問題求解的復(fù)雜程度。越來越多的優(yōu)化過程借助了并行遺傳算法的手段。

目前PGA 的并行模型主要分為三類［10］：主從式模型、粗粒度模型和細(xì)粒度模型。但是由于遺傳迭代過程中設(shè)計(jì)的參數(shù)傳遞較多，又沒有統(tǒng)一的模式可以遵循，使得無論哪種PGA 實(shí)現(xiàn)起來都比較復(fù)雜。即便是其中最為流行和適應(yīng)性最強(qiáng)的粗粒度模型，編程過程也比較繁瑣。正是基于這樣的考慮，本文擬將遺傳算法與MapReduce 相結(jié)合克服傳統(tǒng)PGA 的不足。

2.1 基于復(fù)合機(jī)制的MapReduce 分布式并行計(jì)算模型擴(kuò)展

映射過程map 和聚集過程reduce為MapReduce 計(jì)算模型中的兩個(gè)關(guān)鍵過程。這兩個(gè)函數(shù)的輸入為一組鍵值對(duì)（key/value），通過計(jì)算得出另一組鍵值對(duì)作為輸出，即：

將鍵值對(duì)（k1，v1）輸入到用戶定義的映射函數(shù)map 中經(jīng)過處理得到一組中間的（k2，v2）鍵值對(duì)。所有相同的中間鍵k2的相應(yīng)值通過MapReduce 函數(shù)庫(kù)的聚合，得到關(guān)于k2鍵的值集合list（v2），并且發(fā)送給由用戶提供的歸并函數(shù)reduce，通過reduce 進(jìn)一步處理、合并該中間的鍵值集合，最后形成的鍵值對(duì)集合list（k3，v3）。

通過對(duì)MapReduce 泛型和GA 的研究不難發(fā)現(xiàn)：如果我們將一代進(jìn)化操作歸并到map 函數(shù)中，那么相應(yīng)的reduce 函數(shù)則可以主要處理群體評(píng)價(jià)；通過兩者的不斷迭代就可以構(gòu)造一種并行遺傳算法。然而這樣的編程抽象還不足以描述GA 算法中關(guān)于交叉的部分，需要對(duì)其進(jìn)行擴(kuò)展。

眾所周知，MapReduce 最初是受Lisp 等函數(shù)式編程語(yǔ)言的啟發(fā)。在函數(shù)式編程語(yǔ)言中，復(fù)合（Currying）算子能夠?yàn)楹瘮?shù)引入多目標(biāo)的輸出特性，即可解決遺傳過程中的交叉處理問題。通過復(fù)合算子與map 算子的結(jié)合，map 算子可以輸出多個(gè)鍵值對(duì)。這就是cmap（Currying Map）算子。這樣一來，cmap 可以輸出多個(gè)鍵值對(duì)，作為后代適應(yīng)度的鍵值對(duì)list（k2，v2）提交給reduce 算子，作為交叉的鍵值對(duì)list（k2′，v2′）提交給其他cmap 算子，如下：

2.2 基于復(fù)合MapReduce 的遺傳算法

在復(fù)合MapReduce 的基礎(chǔ)上，構(gòu)建并行GA 算法的流程如下：群體根據(jù)cmap 函數(shù)的個(gè)數(shù)分割成若干個(gè)子群體，遺傳算法通過各個(gè)子群體在不同處理器上相互獨(dú)立的并發(fā)運(yùn)行，每經(jīng)過一定的進(jìn)化代數(shù)，各子群體通過交換若干的個(gè)體從而引入其它子群體的優(yōu)秀基因；最終在reduce 函數(shù)中輸出本代最優(yōu)個(gè)體，并判斷是否進(jìn)入下一輪遺傳計(jì)算。整個(gè)處理過程中，因?yàn)橥ㄐ胖挥性诟髯尤后w交換個(gè)體時(shí)才產(chǎn)生，通信的開銷不大，可獲得近似線性的加速比。本文設(shè)計(jì)的基于復(fù)合MapReduce 的遺傳算法處理步驟（編碼解碼、選擇、復(fù)制、交叉、變異與終止方式參見1.2 節(jié)）如下：

1）初始化種群，產(chǎn)生父代遺傳群體，并產(chǎn)生鍵值對(duì)（k1，v1）。MapReduce 不能直接用來表達(dá)遺傳算法，本步驟在進(jìn)入迭代過程前對(duì)個(gè)體進(jìn)行初始化并進(jìn)入迭代過程的預(yù)備工作，產(chǎn)生不同子群作為cmap 函數(shù)的輸入鍵值對(duì)。

2）cmap 函數(shù)接收（k1，v1），接收交叉鍵值對(duì)（k2′，v2′），完成復(fù)制、選擇、交叉、變異，計(jì)算子群中每個(gè)個(gè)體的適應(yīng)度值，輸出適應(yīng)度鍵值對(duì)（k2，v2），輸出交叉鍵值對(duì)（k2′，v2′）。（k1，v1）中，k1為個(gè)體的索引號(hào)，v1為個(gè)體染色體；交叉鍵值對(duì)含義與（k1，v1）相同，但表征的為待交叉的染色體；中間件結(jié)果的適應(yīng)度鍵值對(duì)（k2，v2）中，k2為個(gè)體的適應(yīng)度值，v2為個(gè)體染色體。流程如下：

3）reduce 函數(shù)接收所有cmap 函數(shù)產(chǎn)生的鍵值對(duì)（k2，v2），在對(duì)最優(yōu)的適應(yīng)度值及對(duì)應(yīng)的個(gè)體進(jìn)行更新后，需判斷是否滿足停機(jī)條件，如滿足，那么輸出最優(yōu)個(gè)體和最優(yōu)值，否則，保存最優(yōu)個(gè)體和最優(yōu)值，并產(chǎn)生新的（key，value）對(duì)作為cmap 輸入，轉(zhuǎn)到步驟2）。具體的reduce 函數(shù)如下：

3 典型算例和結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

本文為搭建Hadoop 集群系統(tǒng)進(jìn)行分布式計(jì)算實(shí)驗(yàn)，使用了10 臺(tái)計(jì)算機(jī)，各節(jié)點(diǎn)所用操作系統(tǒng)均為紅旗linux 8.0，節(jié)點(diǎn)配置為AMD Operon64 2.2GHz CPU、4GB DDR RAM 以及1000 Mbps Ethernet；使用的Hadoop 版本為hadoop0.20.2，默認(rèn)調(diào)度策略為先來先服務(wù)（FCFS）。

3.2 結(jié)果分析

在遺傳算法中，設(shè)500為種群數(shù)量，Pc=0.8為交叉概率，Pm=0.1為變異概率，算法迭代600 步?；谄胀℅A算法與CMRGA 分別進(jìn)行計(jì)算，計(jì)算結(jié)果最小熱阻均為50.01，對(duì)應(yīng)的優(yōu)化變量值均分別為N=14、b=1.85、L=376.16、W=412.78、H=19.33。CMRGA 算法計(jì)算終止后，適應(yīng)度較優(yōu)的10 個(gè)結(jié)果輸出如表1 所示。從實(shí)驗(yàn)結(jié)果不難發(fā)現(xiàn)，CMRGA 與GA計(jì)算精度和正確性保持一致。

表1 適應(yīng)度較優(yōu)的10 對(duì)方案

圖2 10 節(jié)點(diǎn)情況下CMRGA算法與普通GA 算法的處理時(shí)間比較

3.3 性能分析

在實(shí)驗(yàn)結(jié)果正確性分析的基礎(chǔ)之上，我們得到了CMRGA的效率和可擴(kuò)展性分析如下。圖2 中，我們比較了10 節(jié)點(diǎn)情況下CMRGA 算法與普通GA 算法的處理時(shí)間，CMRGA 算法的處理時(shí)間僅為GA 算法的不到七分之一。

接著，我們對(duì)CMRGA 算法的可擴(kuò)展性進(jìn)行了測(cè)試。我們從2 到10 逐步增加參與計(jì)算節(jié)點(diǎn)個(gè)數(shù)，得到的加速比統(tǒng)計(jì)如圖3 所示，可見CMRGA 算法接近于線性加速比。

可見CMRGA 算法有很好的可擴(kuò)展性，當(dāng)處理不同規(guī)模優(yōu)化問題時(shí)，可以選取合理的計(jì)算資源參與。另外，由于CMRGA 采用cmap與reduce 編程模式，使得整個(gè)算法的編寫過程相對(duì)固定，降低了并行GA 的編程難度，有易編程的特點(diǎn)。

4 結(jié)語(yǔ)

本文針對(duì)機(jī)載計(jì)算機(jī)箱體散熱器的導(dǎo)熱性優(yōu)化問題，提出遺傳算法在MapReduce 泛型下的并行化方法，解決了傳統(tǒng)遺傳算法的效率和可擴(kuò)展性問題，對(duì)實(shí)際工程應(yīng)用具有一定的指導(dǎo)意義。當(dāng)然，僅僅使用遺傳算法對(duì)散熱器結(jié)構(gòu)進(jìn)行優(yōu)化是不夠的，如何應(yīng)用MapReduce 的易擴(kuò)展性和高性能特點(diǎn)，將CMRGA 與其它熱仿真軟件結(jié)合起來（即求解目標(biāo)的計(jì)算為仿真軟件過程）研究散熱器結(jié)構(gòu)是需要繼續(xù)研究的問題。

圖3 CMRGA 算法的加速比變化

［1］薛輝，王瑋，李志信.基于微腔自然對(duì)流的PCR 芯片的熱設(shè)計(jì)［J］.功能材料與器件學(xué)報(bào)，2008，14（2）：431-435.

［2］邱成悌，趙惇殳，蔣全興.電子設(shè)備結(jié)構(gòu)設(shè)計(jì)原理［M］.南京：東南大學(xué)出版社，2001：37-39.

［3］徐麗娜，鄧正隆.遺傳算法與最優(yōu)化［J］.黑龍江自動(dòng)化技術(shù)與應(yīng)用，1996（4）：1-4.

［4］CHEN C L，KIM P，SCOTT D.Three analysis Design Tool for Parallel Plate Heat sinks［C］//International Society Conference on Thermal Phenomenon，1998：371-377.

［5］周明，孫樹棟.遺傳算法原理及其應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，1999.

［6］GERKEY B，VAUGHAN R，HOWARD A.The player/stage project：Tools for multi-robot and distributed sensor systems.In Proc.Int.Conf.on Advanced Robotics（ICAR），2003.

［7］王小平，曹立明.遺傳算法-理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002.

［8］WEN Yang.Scalability of Dynamic Traffic Assignment［D］.Cambridge：Massachusetts Institute of Technology，2008.

［9］DEAN J，GHEMAWAT S.Mapreduce:simplified data processing on large clusters［J］.ACM，2008，51（1）：107-113.

［10］ALBA E，TOMASSINI M.Parallelism and evolutionary algorithms［J］.IEEE Transactions on Evolutionary Computation，2002，6（5）：443-462.

［11］賈瑞玉，劉范范，潘雯雯，等.基于MapReduce 模型的并行量子進(jìn)化算法［J］.計(jì)算機(jī)工程，2012，138（8）：180－182，188.

［12］王萌.高密度密閉電子設(shè)備熱設(shè)計(jì)及其結(jié)構(gòu)優(yōu)化［D］.西安：西安電子科技大學(xué)，2007.