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

于慧伶,崔姍姍,范德林

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

?

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

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

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

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

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

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

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

1問題提出

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

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

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

2.1　串行模擬退火算法

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

2.2　Map Reduce框架

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

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

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

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

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

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

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

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

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

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

表1　SA流程

表2　線程合作的流程

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

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

3實(shí)驗(yàn)分析

為驗(yàn)證不同策略下并行算法的效率，本文基于Map Reduce在分布式集群平臺(tái)上對(duì)多組數(shù)據(jù)進(jìn)行測試考證，測試使用的數(shù)據(jù)來自solomon提供的標(biāo)準(zhǔn)測試集[20]，測試數(shù)據(jù)庫包括數(shù)據(jù)集 R(隨機(jī)分布)、C(堆分布)、RC(半堆分布)、拓?fù)涞乩砦恢镁哂幸韵碌奶攸c(diǎn)：數(shù)據(jù)集 R中節(jié)點(diǎn)是隨機(jī)生成，數(shù)據(jù)集C為聚類分布，數(shù)據(jù)集 RC為混合隨機(jī)聚類分布。本文只針對(duì)R測試集進(jìn)行測試分析。

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

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

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

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

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

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

[8]張蕓香,郭晉平.森林斑塊密度及邊緣密度動(dòng)態(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ìn)展[J].河北林業(yè)科技,2013,12(6):36-38.

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

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

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

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

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

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

[17]何榮波.Map Reduce模型在Hadoop中的性能優(yōu)化及改進(jìn)[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-)，女，副教授，博士，主要從事計(jì)算機(jī)輔助創(chuàng)新理論與方法研究。E-mail:yhl2016@163.com

基金項(xiàng)目：中央高?；究蒲袠I(yè)務(wù)費(fèi)項(xiàng)目(DL12EB01-02)，國家科技基礎(chǔ)性工作專項(xiàng)項(xiàng)目(2014IM020100)，黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目(12523018)。

*收稿日期：2015-06-19

中圖分類號(hào)：TP 301.6;S 757

文獻(xiàn)標(biāo)識(shí)碼：A

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