于慧伶,崔姍姍,范德林

(1.東北林業(yè)大學(xué) 信息與計算機工程學(xué)院，黑龍江　哈爾濱150040；2.東北林業(yè)大學(xué) 經(jīng)濟管理學(xué)院，黑龍江　哈爾濱150040)

?

框架下森林分類的并行模擬退火算法*

于慧伶1,崔姍姍1,范德林2

(1.東北林業(yè)大學(xué) 信息與計算機工程學(xué)院，黑龍江哈爾濱150040；2.東北林業(yè)大學(xué) 經(jīng)濟管理學(xué)院，黑龍江哈爾濱150040)

摘要：針對傳統(tǒng)模擬退火算法存在收斂速度慢、執(zhí)行時間長的缺點，本研究提出了一種并行在線的模擬退火算法及其優(yōu)化策略，并將其運用到森林景觀分類中。研究人員運用多馬爾科夫鏈異步通信和同步通信兩種策略實現(xiàn)模擬退火算法的并行處理。在Solomon提供的標(biāo)準測試集上對并行算法性能進行測試和分析，得出并行算法時線程間的通信可以提高目標(biāo)解的搜索效率。與此同時，同步通信策略目標(biāo)解的搜索效率優(yōu)于異步通信策略，但是會增加一些通信負載的成本。通過大量實驗得出森林分類經(jīng)營代價與線程溝通周期、鏈長和線程數(shù)目的關(guān)系，從而節(jié)省景觀分類的時間代價，進而解決一些NP難題。

關(guān)鍵詞：森林分類；模擬退火算法；馬爾科夫鏈;異步通信;同步通信；Map Reduce框架；Hadoop

森林景觀是指在確定區(qū)域內(nèi)由不同類別生態(tài)系統(tǒng)構(gòu)成并具備重復(fù)性布局的不同地質(zhì)的地理塊，其分類是根據(jù)地理位置、自然氣候、地質(zhì)使用類別、植物和土地特征等要素進行[1～2]。復(fù)雜的林木空間分布會影響森林景觀的經(jīng)營分類，因此在固有的經(jīng)營模型中增加空間限制讓模型變得更為龐大且很難得到最優(yōu)解，唯有運用啟發(fā)式算法才能快速找到恰當(dāng)?shù)哪繕?biāo)解，所以探究基于啟發(fā)式算法的森林經(jīng)營管理成為林學(xué)急切解決的首要問題。

在森林經(jīng)營規(guī)劃中，研究人員利用一些分類指標(biāo)(如景觀多樣性指數(shù)和均勻度指數(shù)等)生成目標(biāo)函數(shù)，進而計算景觀分類代價。本文對模擬退火算法的并行化及其并行通信策略進行深入研究，并在SA算法中運用并行策略提高目標(biāo)函數(shù)中最優(yōu)解的搜索效率，進而減小景觀分類的經(jīng)營代價[3～4]。算法在Map Reduce框架下并行時，可采取一系列并行策略(線程通信策略和解決方案數(shù)目等)：線程可以采用異步通信和同步通信策略；算法并行化的解決方案分為每個線程有固定數(shù)目的解決方案(2K,4K，8K等)或所有線程有總共固定常數(shù)的解決方案。研究人員在上述并行策略的算法中探究森林景觀分類的經(jīng)營代價。

1問題提出

E=(H/Hmax)*100 %④,式中,E是均勻度指數(shù)，H是景觀多樣性指數(shù)，均勻度是指景觀中不同類型的分配均勻程度。本研究的目標(biāo)函數(shù)是在算法中利用這些指標(biāo)計算森林分類經(jīng)營代價。

烏賽高速公路生態(tài)保護控制區(qū)站區(qū)綠化建設(shè)實踐……………………………… 陳六明，朱坤，孫兆祜，錢麗（4-163）

2SA算法并行化的理化基礎(chǔ)

2.1　串行模擬退火算法

SA是一種普遍概率算法，在確定時間內(nèi)，在一個大的搜尋范圍內(nèi)查找最優(yōu)解[11～12]。傳統(tǒng)SA算法計算過程簡單，一目了然，魯棒性強，解決比較繁瑣的非線性優(yōu)化問題，但是具有速度慢、運行時間長等一系列缺點。考慮綜上缺點，可以設(shè)計適當(dāng)?shù)臓顟B(tài)生成函數(shù)，并且依據(jù)查找線程的需求顯示出狀態(tài)的一切空間分散性或區(qū)域性，以免產(chǎn)生狀態(tài)的迂回查找；并且復(fù)雜的數(shù)據(jù)集的問題使得運用Map Reduce框架并行化SA算法勢在必行[13～14]。

2.2　Map Reduce框架

在Hadoop中，用于執(zhí)行Map Reduce任務(wù)有兩個角色，一個是JobTracker，另一個是TaskTracker[15～16]。JobTracker是用于處理和安排工作的，TaskTracker是運行工作的。一個Hadoop集群中只有一臺JobTracker，各個Map Reduce任務(wù)都被初始化為一個Job。各個Job又可以分為兩個階段，Map階段和Reduce階段，用Map和Reduce函數(shù)來表示這兩個階段。

Hadoop的另外一個核心是HDFS，而整個Hadoop單元結(jié)構(gòu)通常是由HDFS來達成分布式存儲，而且HDFS會經(jīng)由Map Reduce來達成分布并行分布作業(yè)處理的程序支撐[17]。HDFS運用主從(Master/Slave)結(jié)構(gòu)模式，一個HDFS集群由一個Namenode和若干個Datanode構(gòu)成。Namenode是分布式文件系統(tǒng)的經(jīng)營者，Datanode負責(zé)管理文件系統(tǒng)客戶端的文件需求，并且在Namenode的統(tǒng)一安排下進行工作。

大數(shù)據(jù)集肢解成若干個小數(shù)據(jù)集合，各個數(shù)據(jù)集合有集群中的一個節(jié)點[18]，進而運行并行管理并形成中間結(jié)果，隨之此節(jié)點與其他很多節(jié)點歸并，生成終極結(jié)果(圖1)。

圖1　Map Reduce作業(yè)執(zhí)行的流程圖

2.3　模擬退火算法并行化分析

SA算法具備優(yōu)良的內(nèi)在并行性。當(dāng)前，存在一些已經(jīng)完成SA算法的并行解決辦法[19]：并行移動；移動加速；推測性計算和多馬爾科夫鏈。其中，multiple Markov chain是最常用的解決并行處理的辦法。此辦法是將傳統(tǒng)的串行SA中的一條Markov chain分裂為multiple Markov chain(多線程)，這些線程在確定的時間內(nèi)單獨生長，又能夠進行合理的互換信息，進而取得了能夠擴展的并行性能。另外，經(jīng)過保存Markov chain的最佳值，并遵照確定的時間間隔對不一樣的Markov chain獲得的最佳值進行互換，進而提速了優(yōu)化的過程，Markov chain策略分為異步和同步兩種通訊策略。

當(dāng)采用異步通信策略時，在以下兩種情況下發(fā)生通信，第一種情況是確定一個固定的周期；另一種各自搜索結(jié)束后，對比最終狀態(tài)。各個線程對應(yīng)一個Markov chain，并進行單獨的運行。在各個線程運行結(jié)束后，比較各個線程的局部優(yōu)化解，最終獲得終極解。當(dāng)選用同步通信策略時，各個線程以初始解X0單獨的執(zhí)行各自的Markov chain，溫度確定后，各個線程本質(zhì)上為Metropolis過程。當(dāng)通過一段確定的間隔周期W后，達到一個固定的中間溫度時，Markov chain比較當(dāng)前這些局部優(yōu)化解，將比較后的最佳局部優(yōu)化解作為下一個溫度下的初始解，一直反復(fù)這個過程，直到滿足結(jié)束條件。

通過研究并行同步算法得知，生成的Markov chain是不勻稱的。因為從此解轉(zhuǎn)變到另外解的概率不單受當(dāng)前解相應(yīng)的成本值和此刻溫度影響，而且與從算法過程中導(dǎo)入的上一輪次的局部最優(yōu)解有關(guān)?；诖怂枷?，在Map Reduce框架下，運用Master/Slave結(jié)構(gòu)優(yōu)化并行算法，在不相同溫度值間，采用并行同步通信策略，主線程掌管接受子線程的局部優(yōu)化解(圖2)。

圖2　優(yōu)化并行算法下線程的配合方式

運用p-SA算法，提高了SA算法的解決速度，不僅確保了算法有較大規(guī)模的并行粒度；而且在固定的溫度值下，上一輪次子線程搜查的結(jié)果轉(zhuǎn)達給下個子線程，完成了搜查信息的歸并。表1為并行SA的流程。在下面的算法流程中，parfor表示對一個for循環(huán)進行并行化計算。

表1　SA流程

表2　線程合作的流程

表3　并行SA算法的配合搜索

對于p-SA算法，線程要通過n步消息互換，關(guān)于每一步消息互換，有(w-1)-1個信息量為O(n)的信息被發(fā)配和收入，所以整個運行時間代價為n2〔n+(w-1)-1〕。所以，p-SA算法的總時間代價不超過O〔n3+(w-1)*n2〕。

3實驗分析

為驗證不同策略下并行算法的效率，本文基于Map Reduce在分布式集群平臺上對多組數(shù)據(jù)進行測試考證，測試使用的數(shù)據(jù)來自solomon提供的標(biāo)準測試集[20]，測試數(shù)據(jù)庫包括數(shù)據(jù)集 R(隨機分布)、C(堆分布)、RC(半堆分布)、拓撲地理位置具有以下的特點：數(shù)據(jù)集 R中節(jié)點是隨機生成，數(shù)據(jù)集C為聚類分布，數(shù)據(jù)集 RC為混合隨機聚類分布。本文只針對R測試集進行測試分析。

在這個測試數(shù)據(jù)集的基礎(chǔ)上，根據(jù)不同線程數(shù)目、鏈長、線程溝通周期，進行一系列的實驗。對于R測試集合,變化線程數(shù)目、鏈長、線程溝通周期,算法被執(zhí)行上千次，執(zhí)行結(jié)果的大體趨勢見圖3～8。

圖3　針對R101和R102優(yōu)化后的算法測試值

圖4　針對R103和R106優(yōu)化后的算法測試值

圖5　針對R101和R102優(yōu)化后的算法測試值

圖6　針對R107和R108優(yōu)化后的算法測試值

圖7　針對R107和R108優(yōu)化后的算法測試值

圖8　針對R109和R110優(yōu)化后的算法測試值

算法采用同步通信策略并行時，具有發(fā)現(xiàn)相關(guān)優(yōu)質(zhì)解決方案的良好平均行為和算法穩(wěn)定性基本不受線程數(shù)目增加的影響等一系列優(yōu)點。與此同時，線程間的通信提高了最優(yōu)解的搜索效率。然而，算法并行時，線程通信會增加一些通信負載的成本。因此，對于線程通信找出一種折中的優(yōu)化方案迫在眉睫。

4結(jié)語

本項目主要研究了并行模擬退火算法及其優(yōu)化策略，并在算法中利用景觀異質(zhì)性指標(biāo)代價函數(shù)節(jié)省景觀分類代價。主要結(jié)論如下，(1)算法利用同步通信策略并行時，隨著線程數(shù)目的增加，模擬退火算法收斂速度越快。(2)景觀異質(zhì)性指標(biāo)代價不僅與線程數(shù)目有關(guān)，還與線程溝通周期、鏈長有密切的關(guān)系。(3)當(dāng)固定每個線程的解決方案時，代價與線程的數(shù)目成反比；當(dāng)總共解決方案為常數(shù)時，代價并不總是與線程的數(shù)目成反比。運用模擬退火算法對森林景觀分類做深入研究，進而提高森林景觀分類的運作效率，節(jié)約成本，具有較高的理論與實踐研究價值。與此同時，對加強景觀分類建設(shè)的規(guī)劃以及管理化等也具有重要的意義。

參考文獻：

[1]趙春燕.顧及耦合作用的森林景觀多尺度分類[J].林業(yè)科學(xué),2013,49(11):185-188.

[2]梁發(fā)超.景觀分類的研究進展與發(fā)展趨勢[J].應(yīng)用生態(tài)學(xué)報,2011,22(6):1633-1637.

[3]陸元昌.分類評價中的應(yīng)用研究[J].林業(yè)科學(xué)研究,2005,18(1):31-35.

[4]陳勇.森林景觀經(jīng)營研究現(xiàn)狀與展望[J].東北林業(yè)大學(xué)學(xué)報,2010,38(4):111-113.

[5]傅伯杰.國際景觀生態(tài)學(xué)研究新進展[J].生態(tài)學(xué)報,2008,28(2):709-803.

[6]師慶東.基于氣候、地貌、生態(tài)系統(tǒng)的景觀分類體系[J].生態(tài)學(xué)報,2014,34(12):3359-3366.

[7]余新曉,李秀彬,夏兵.森林景觀格局與土地利用/覆被變化及其生態(tài)水文響應(yīng)[M].北京:科學(xué)出版社,2010:83-89.

[8]張蕓香,郭晉平.森林斑塊密度及邊緣密度動態(tài)研究——以關(guān)帝山林區(qū)為例[J].生態(tài)學(xué)雜志,2001,20(1):18-21.

[9]白降麗.森林景觀生態(tài)研究現(xiàn)狀與展望[J].生態(tài)學(xué)雜志,2005,24(8):943-947.

[10]黃龍生.我國森林景觀生態(tài)規(guī)劃研究進展[J].河北林業(yè)科技,2013,12(6):36-38.

[11]劉懷亮，劉淼.一種混合遺傳模擬退火算法及其應(yīng)用[J].廣州大學(xué)學(xué)報,2005,2(4):141-145.

[12]顧元憲.一種改進的連續(xù)變量全局優(yōu)化模擬退火算法[J].系統(tǒng)工程理論與實踐,2005,2(4):103-106.

[13]朱顥東.一種改進的模擬退火算法[J].計算機技術(shù)與發(fā)展,2009,19(6):32-35.

[14]蔣龍聰，劉江平.模擬退火算法及其改進[J].工程地球物理學(xué)報,2007,4(2):135-140.

[15]黃偉建.Map Reduce高可用性的研究與優(yōu)化[J].計算機工程與設(shè)計,2014,35(11):4044-4046.

[16]陳海波.云計算平臺可信性增強技術(shù)的研究 [D].上海:上海復(fù)旦大學(xué),2009.

[17]何榮波.Map Reduce模型在Hadoop中的性能優(yōu)化及改進[D].北京：北京化工大學(xué)，2011.

[18]Dean J，Ghemawat S． Map Reduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.

[19]Chandy J A,Kim S,Ramkumar B,etal.An evaluation of parallel simulated annealing strategies with application to standard cell placement[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1997，16(4):398-410.

[20]Solomon,M.M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1989,35:254-265.

Parallel Simulated Annealing Algorithm of Forest Classification

under Map Reduce Framework

YU Hui-ling1,CUI Shan-shan1，F(xiàn)AN De-lin2

(1.School of Information and Computer Engineering,Northeast Forestry University,Harbin Heilongjiang 150040,P.R.China;

2.School of Economics and Management,Northeast Forestry University,Harbin Heilongjiang 150040,P.R.China)

Abstract:Considering the shortcomings of the traditional simulated annealing algorithm,such as slow speed of the convergence and the time-consumption of its execution,this study presents a parallel simulated annealing method with an optimized strategy,which can be applied to the classification of forest landscape.Multiple Markov chain is commonly used for the parallel processing method,and there are two algorithms,which is a synchronous one and an asynchronous one.The benchmarking tests elaborated by Solomon were put into use.The results show that the communication of processors improves the efficiency of optimal solution’s search.Meanwhile,the solutions of the asynchronous algorithm are better than that of the synchronous one,even with the additional cost of a little more communication load.In the series of the experiments, it was found that the values of relevant parameters(the number of processors，a period of communication and a number of annealing steps) could give statistically the best solutions to the forest landscape classification,and save the time of landscape classification and solve some NP problems.

Key words:forest classification;simulated annealing algorithm;Markov chain;synchronous communication;asynchronous communication;Map Reduce framework;Hadoop

通訊作者簡介：范德林(1959-)，男，教授，博士，主要從事技術(shù)創(chuàng)新方法的研究與推廣工作。E-mail:dlfan33@aliyun.com

作者簡介：第一于慧伶(1980-)，女，副教授，博士，主要從事計算機輔助創(chuàng)新理論與方法研究。E-mail:yhl2016@163.com

基金項目：中央高校基本科研業(yè)務(wù)費項目(DL12EB01-02)，國家科技基礎(chǔ)性工作專項項目(2014IM020100)，黑龍江省教育廳科學(xué)技術(shù)研究項目(12523018)。

*收稿日期：2015-06-19

中圖分類號：TP 301.6;S 757

文獻標(biāo)識碼：A

文章編號：1672-8246(2016)01-0025-06