一種適用于森林管理變量的并行模擬退火算法

于慧伶，崔姍姍，陳廣勝，范德林

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

一種適用于森林管理變量的并行模擬退火算法

于慧伶1，崔姍姍1，陳廣勝1，范德林2

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

針對森林經(jīng)營管理的復雜性問題，通常以模擬實地的虛擬森林環(huán)境作為實驗區(qū)，運用模擬退火算法工具運營管理森林。由于傳統(tǒng)算法存在執(zhí)行時間長、收斂速度慢等一系列缺點，本文展示了一種在線的并行模擬退火算法及其優(yōu)化策略。在獨立搜索與合作搜索策略下優(yōu)化并行算法，獨立搜索時，彼此線程間不進行通信，各個線程獨立的運行各自的馬爾科夫鏈，在各線程運行結束后，主線程再統(tǒng)一接收各自線程的局部優(yōu)化解，經(jīng)過比較進而得出全局最優(yōu)解；合作搜索時，先通過若干步的退火步驟，線程根據(jù)情況產(chǎn)生2種退火鏈通信階段：同步通信褳階段和異步通信鏈階段，實時更新結果。經(jīng)過對比分析得出，串行模擬退火算法比并行算法的收斂速度快；并在Solomon提供的標準測試集上對并行算法的性能進行測試，分析進程數(shù)目對代價大體呈反比的趨勢，在理論和實驗上，表明并行策略可實現(xiàn)高效低成本的森林經(jīng)營管理。

森林經(jīng)營；并行算法；適應度景觀；模擬退火；馬爾科夫鏈

森林經(jīng)營[1-4]是指森林決策與管理活動的全部過程。合理的森林經(jīng)營管理，可以以最小的環(huán)境成本產(chǎn)生最大的社會、經(jīng)濟和生態(tài)效益，而不合理的森林管理，則可能造成嚴重的森林后果。然而，在每個階段，森林價值指標的側重點不同，以及森林的動態(tài)變化，這些都增加了森林管理的復雜性。綜合考慮以上多種因素，森林管理是一個繁雜的非線性規(guī)劃，歸于組合優(yōu)化問題中的NP難題。運用SA算法人為干涉，使得森林沿著人類所期望到達的狀態(tài)進化。從目前狀態(tài)到最佳狀態(tài)有很多條路徑，通過此算法找出花費代價最小的路徑。

本文采用獨立搜索和合作搜索策略將模擬退火算法并行化[5]。獨立搜索過程中，各個線程彼此之間互不通信；合作搜索過程中，各個線程彼此有通信，其中包括同步通信與異步通信。在森林經(jīng)營管理過程中，可以確定總共的解決方案為1個常數(shù)，也可以設定每個線程的解決方案為1個常數(shù)。本研究在森林管理研究過程中，采用同步通信，并且設定每個線程的解決方案為1個常數(shù)。每個線程的解決方案可以為2 k、4 k、8 k、16 k、32 k。隨著解決方案數(shù)和線程數(shù)的增加，代價隨之減少。然而考慮多線程通信的費用，代價并不總與線程的數(shù)目成反相關。

1 問題描述

進化[6-7]可以被認為是一種三維景觀的旅程。森林景觀中每個位置中可能基因組合的高度表示生存的適應度。森林景觀中有很多山峰和山谷，這樣山峰與山峰相鄰，山谷與山谷相鄰，即所謂的適應度景觀。進化就是在適應度景觀中查找高點的過程。

通過控制N和K2個參數(shù)來確定適應度景觀，進而觀察其復雜性對森林系統(tǒng)進化的影響。同樣，在經(jīng)營森林管理過程中，有很多森林的基因組合，以及這些組合中的相互影響關系，森林進化的優(yōu)劣用適應度景觀數(shù)值表示。因此，森林進化的適應度景觀實際上是全部基因狀態(tài)大體組合產(chǎn)生的三維立體圖。通過基因組合值的提高進而促進繁雜森林的進化(由現(xiàn)在的狀態(tài)轉換到最佳的狀態(tài))，詳細展現(xiàn)為適應度景觀上的攀躍過程[8]。假如，有一個具有4個基因組合的森林體系，N=4，目前狀態(tài)S0(0000)的適應度值為0.301，最佳狀態(tài)S′(1111)的適應度值為0.725，從圖1可以看出，從S0到S′有很多路徑，找出代價最小的1條路徑。

由于基因組合出現(xiàn)變化，不單會造成由它確定的森林適應度值產(chǎn)生變化，而且會造成與它關聯(lián)的其他基因組合確定的適應度值產(chǎn)生變化。這兩部分的變化共同決定了森林整體適應度值。具體而言，設1個森林系統(tǒng)的要素與要素間的相互作用表示為dij(j=1，2，…，K)，由目前狀態(tài)到最佳狀態(tài)所需的花費函數(shù)f，則森林系統(tǒng)的目標函數(shù)為：

(1)

2 串行模擬退火算法

模擬退火算法[9-12]可以分解為目標函數(shù)、解空間和初始解3部分。模擬退火算法運算流程簡便，普遍，魯棒性強，能夠使用于解決繁瑣的非線性優(yōu)化問題，然而存在實現(xiàn)時間較長、慢等缺點。綜合以上缺點，可以運用高效的退火策略，避免狀態(tài)的迂回搜索，以及采用并行搜索結構等方法來改進SA算法。

3 并行模擬退火算法

3.1 獨立搜素

并行模擬退火算法采用獨立搜索IS(Independent searches)時，有p0，p1，…，pp-1的線程獨立執(zhí)行，各個進程執(zhí)行SA算法。在各個進程計算完畢后使進程互換各自最優(yōu)解，從中再選取最優(yōu)解。

假如模擬退火步奏為I，獨立搜索時，每個線程執(zhí)行的模擬退火步奏為I/p。最終線程的解決方案{Sz，0，Sz，1，…，Sz，p-1}被計算。最佳解決方案確定為S′=Sz，0?Sz，1?…?Sz，p-1，式中：?為選取的最佳解決方案?？紤]收斂速度，得出[13]：

(2)

假設每個線程的概率收斂速度(P(Sz，j?Smin)～(K/Z)α)，得出：

(3)

假設鏈長I=106，K=100和α=0.01。模擬退火算法的概率(P(Sz，j?Smin)～(K/Z)α)為0.912，如果線程數(shù)目為2、4、8、16、32，獨立搜素下的公式(3)的收斂速度分別為0.843、0.731、0.565、0.357、0.159(表1、圖2)。因此，并行獨立的搜索比傳統(tǒng)的串行模擬退火算法具有更快的收斂比。

3.2 合作搜索

表1 不同線程數(shù)量下的算法收斂速度

在合作搜索CS(Co-operating searches)中，采用同步通信策略。各個進程得到原始解S0后，各自執(zhí)行各自的Markov Chain。當溫度一定時，各個進程本質為一個Metropolis過程。當經(jīng)歷某個恒定的間隔周期，到達某個特定的中間溫度時，每個Markov Chain比較當前各自的局部最優(yōu)解Sj及其對應的f(Sj)，j=0，1，2，…，p-1。對比P個進程的代價f(Sj)值。如果i進程的代價值最小，則在下一個溫度值下，當前的局部最優(yōu)解將成為每個進程的原始解。若是當前有多于2個的局部最優(yōu)解[14-18]，隨機選1個即可，此選取過程不影響最終的結果。主線程0主要負責接受每個分線程的結果，比較這些結果，并得出局部最優(yōu)解。具體流程見圖3。

圖3 優(yōu)化并行算法下線程的合作方式圖4 并行模擬退火流程

運用并行模擬退火算法，提升了算法的運行速度，確保了算法有很大并行粒度；且使得在確定的溫度值下，上一個分進程搜索的局部結果傳遞給下一個分進程，節(jié)省時間，進而實現(xiàn)搜尋消息的交融(圖4)。根據(jù)并行算法流程，可得森林管理問題的偽代碼表示(表2～表4)。

對于并行算法，進程要通過n步消息互換，關于每一步消息互換，(w-1)-1個消息量為O(n)的消息需要被發(fā)配與接收，所以整個運行時間代價為n2(n+(w-1)-1)。因此并行模擬退火算法的總時間成本不超過O(n3)。

表2 合作搜索下的P-SA算法

表3 模擬退火流程

表4 線程合作的流程

4 實驗分析

研究人員將在不同并行優(yōu)化策略下評估模擬退火算法各自的效率。此算法中用來測量效率的數(shù)據(jù)集合是基于100 個客戶規(guī)模的 Solomon測試集?？紤]到客戶的拓撲分布，此測試集由聚集在3個集合的56個問題組成。這3個集合分別是隨機分布的R()，堆分布的C()，半堆分布的RC()。它們的地理位置分布具有以下特點：R()數(shù)據(jù)集為隨機生成，C()數(shù)據(jù)集為聚類分布，數(shù)據(jù)集RC()為混合隨機聚類分布。在不同并行策略中，進程間溝通的重要性顯而易見，通過與以往的方法比較，部分解決方案的通信提高了最優(yōu)解的搜索效率。

對于每個測試集合，合作搜索和獨立搜索算法分別被執(zhí)行上千次，執(zhí)行結果如圖5～圖7所示。對于測試統(tǒng)計學得出：

在實驗中，分別對R類和RC類下數(shù)據(jù)集進行測試，得出在獨立搜索和合作搜索算法下代價與進程數(shù)目的關系曲線。

5 結論

通過實驗可以看出，在獨立搜索中，隨著線程數(shù)目的增加，模擬退火算法收斂速度越快。在獨立搜索和合作搜索算法下，考慮到溝通周期和鏈長的影響，Z并不與線程的數(shù)目成反比。如何得出線程數(shù)目、鏈長和線程溝通間隔三者間最佳的組合比，將成為研究者下一步探索的核心，進而找出高效的解決方案。從片面追求經(jīng)濟效益向社會、經(jīng)濟和生態(tài)多種效益并舉轉變是當今的森林經(jīng)營理念。每個群體對于森林管理效益的側重點不同，與此同時，森林隨著時間的動態(tài)變化，無疑增加了森林管理的復雜性。利用并行的模擬退火算法，使森林朝著人所期望的方向進化，高效率低成本的管理經(jīng)營森林。對加強林業(yè)建設的規(guī)劃化、產(chǎn)量化以及管理化等具有重要的意義。

[1]權兵.基于虛擬森林環(huán)境的林分生長和經(jīng)營模擬研究[D].福州：福州大學，2005.

[2]劉海.森林經(jīng)營可視化模擬研究[J].世界林業(yè)研究，2010，23(1)：21-25.

[3]梁發(fā)超.景觀分類的研究進展與發(fā)展趨勢[J].應用生態(tài)學報，2011，22(6)：1632-1638.

[4]潘存德，師瑞峰.森林可持續(xù)經(jīng)營：從木材到生物多樣性[J].北京林業(yè)大學學報，2006，28(2)：133-138.

[5]Onbas o glu，E.Parallel simulated annealing algorithms in global optimization[J].Journal of Global Optimization，2001，21(6)：27-50.

[6]Merkuryeva，Galina.Benchmark fitness landscape analysis[J].International Journal of Simulation：Systems，Science and Technology，2010，42(1)：38-86.

[7]Saakian，David B.Biological evolution in a multidimensional fitness landscape[J].Physical Review E-Statistical，Nonlinear，and Soft Matter Physics，2012，86(86)：1275-1292.

[8]Kauffman S A.The Origins of Order：Self-organization and Selection in Evolution[M].New York：Oxford University Press，1993.

[9]Reeves，C.R.，Direct statistical estimation of GA landscape properties[C]∥ Foundations of Genetic Algorithms 6，F(xiàn)OGA 2000，Martin，W.N.，Spears，W.M.(Eds.)，Morgan Kaufmann Publishers，2000：91-107.

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

[11]項寶衛(wèi).模擬退火算法在優(yōu)化中的研究進展[J].臺州學院學報，2005，27(6)：6-9.

[12]汪靈枝.一種有效的全局優(yōu)化算法-模擬退火算法[J].柳州師專學報，2005，20(2)：120-122.

[13]蔣龍聰.模擬退火算法及其改進[J].工程地球物理學報，2007，4(2)：135-138.

[14]Azencott，R.，Parallel simulated annealing：An overview of basic techniques[C]∥Azencott，R.Simulated annealing.Parallelization techniques，J.Wiley，NY，1992：37-46.

[15]Debudaj-Grabysz，Agnieszka.Theoretical and practical issues of parallel simulated annealing[C]∥Proceedings of the 7th international conference on Parallel processing and applied mathematics.Springer-Verlag，2007：189-198.

[16]Czech，Zbigniew J.Implementing a parallel simulated annealing algorithm[C]∥International Conference on Parallel Processing & Applied Mathematics：Part I.Springer-Verlag，2009：146-155.

[17]Czech.Speeding up sequential simulated annealing by parallelization[C]∥International Symposium on Parallel Computing in Electrical Engineering.IEEE Computer Society，2006：349-356.

[18]Nalepa J，Jakub .Co-operation schemes for the parallel memetic algorithm[M].Parallel Processing and Applied Mathematics.Springer Berlin Heidelberg，2013：191-201.

[19]Solomon，M.M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research，1987，35(2)：254-265.

Research and Application of the Parallel Simulated Annealing Algorithm inForest Management Variables

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

(1.Collegeofinformationcomputerengineering，NortheastForestryUniversity，Harbin150040，Heilongjiang，China；2.Collegeofeconomicsandmanagement，NortheastForestryUniversity，Harbin150040，Heilongjiang，China)

Taken the complexity of forest management issues into consideration，researchers regard the virtual forest environment as an experimental area，and manage the forests using a tool of simulated annealing algorithm.Due the traditional simulated annealing algorithm converges slowly，and has long execution time；this paper presents a parallel simulated annealing method and its optimization strategy.The solution consists of two phases of optimization：the Independent searches and the Co-operating searches.In the parallel algorithm of independent searches (IS)，every process performs its computations like in the sequential algorithm；on completion，the processes pass their best solutions to the master process.In the parallel algorithm of co-operating searches (CS)，there are synchronous communication and asynchronous communication strategy.After analysis，the parallel independent searches converge much faster than the sequential algorithm.The researchers examine the performance of parallel algorithms on bench-marking tests elaborated by Solomon，so the cost is roughly proportional to the number of threads，which shows that the parallel strategy can be efficient and low cost management of forest landscape.

forest management；parallel algorithm；fitness landscapes；simulated annealing algorithm；Markov chain

2015-03-21；

2015-05-11

中央高校基本科研業(yè)務費項目(DL12EB01-02)；國家科技基礎性工作專項項目(2014IM020100)；國家人社部留學歸國人員擇優(yōu)資助項目

于慧伶(1980—)，女，黑龍江哈爾濱人，東北林業(yè)大學信息與計算機工程學院副教授，博士，從事計算機輔助創(chuàng)新理論與方法研究。E-mail：yhl2016@163.com。

范德林(1959—)，男，東北林業(yè)大學經(jīng)濟與管理學院教授，從事技術創(chuàng)新方法的研究與推廣工作。E-mail：dlfan33@aliyun.com。

10.13428/j.cnki.fjlk.2016.01.024

S750

A

1002-7351(2016)01-0110-06