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

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

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

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

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

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

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

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

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

1 問(wèn)題描述

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

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

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

(1)

2 串行模擬退火算法

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

3 并行模擬退火算法

3.1 獨(dú)立搜素

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

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

(2)

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

(3)

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

3.2 合作搜索

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

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

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

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

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

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

表3 模擬退火流程

表4 線程合作的流程

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

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

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

在實(shí)驗(yàn)中，分別對(duì)R類和RC類下數(shù)據(jù)集進(jìn)行測(cè)試，得出在獨(dú)立搜索和合作搜索算法下代價(jià)與進(jìn)程數(shù)目的關(guān)系曲線。

5 結(jié)論

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

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

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

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

[4]潘存德，師瑞峰.森林可持續(xù)經(jīng)營(yíng)：從木材到生物多樣性[J].北京林業(yè)大學(xué)學(xué)報(bào)，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ìn)的模擬退火算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19(6)：32-35.

[11]項(xiàng)寶衛(wèi).模擬退火算法在優(yōu)化中的研究進(jìn)展[J].臺(tái)州學(xué)院學(xué)報(bào)，2005，27(6)：6-9.

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

[13]蔣龍聰.模擬退火算法及其改進(jìn)[J].工程地球物理學(xué)報(bào)，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è)務(wù)費(fèi)項(xiàng)目(DL12EB01-02)；國(guó)家科技基礎(chǔ)性工作專項(xiàng)項(xiàng)目(2014IM020100)；國(guó)家人社部留學(xué)歸國(guó)人員擇優(yōu)資助項(xiàng)目

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

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

10.13428/j.cnki.fjlk.2016.01.024

S750

A

1002-7351(2016)01-0110-06