一种适用于森林管理变量的并行模拟退火算法

于慧伶，崔姗姗，陈广胜，范德林

(1.东北林业大学信息与计算机工程学院，黑龙江 哈尔滨 150040；2.东北林业大学经济与管理学院，黑龙江 哈尔滨 150040)

一种适用于森林管理变量的并行模拟退火算法

于慧伶1，崔姗姗1，陈广胜1，范德林2

(1.东北林业大学信息与计算机工程学院，黑龙江 哈尔滨 150040；2.东北林业大学经济与管理学院，黑龙江 哈尔滨 150040)

针对森林经营管理的复杂性问题，通常以模拟实地的虚拟森林环境作为实验区，运用模拟退火算法工具运营管理森林。由于传统算法存在执行时间长、收敛速度慢等一系列缺点，本文展示了一种在线的并行模拟退火算法及其优化策略。在独立搜索与合作搜索策略下优化并行算法，独立搜索时，彼此线程间不进行通信，各个线程独立的运行各自的马尔科夫链，在各线程运行结束后，主线程再统一接收各自线程的局部优化解，经过比较进而得出全局最优解；合作搜索时，先通过若干步的退火步骤，线程根据情况产生2种退火链通信阶段：同步通信裢阶段和异步通信链阶段，实时更新结果。经过对比分析得出，串行模拟退火算法比并行算法的收敛速度快；并在Solomon提供的标准测试集上对并行算法的性能进行测试，分析进程数目对代价大体呈反比的趋势，在理论和实验上，表明并行策略可实现高效低成本的森林经营管理。

森林经营；并行算法；适应度景观；模拟退火；马尔科夫链

森林经营[1-4]是指森林决策与管理活动的全部过程。合理的森林经营管理，可以以最小的环境成本产生最大的社会、经济和生态效益，而不合理的森林管理，则可能造成严重的森林后果。然而，在每个阶段，森林价值指标的侧重点不同，以及森林的动态变化，这些都增加了森林管理的复杂性。综合考虑以上多种因素，森林管理是一个繁杂的非线性规划，归于组合优化问题中的NP难题。运用SA算法人为干涉，使得森林沿着人类所期望到达的状态进化。从目前状态到最佳状态有很多条路径，通过此算法找出花费代价最小的路径。

本文采用独立搜索和合作搜索策略将模拟退火算法并行化[5]。独立搜索过程中，各个线程彼此之间互不通信；合作搜索过程中，各个线程彼此有通信，其中包括同步通信与异步通信。在森林经营管理过程中，可以确定总共的解决方案为1个常数，也可以设定每个线程的解决方案为1个常数。本研究在森林管理研究过程中，采用同步通信，并且设定每个线程的解决方案为1个常数。每个线程的解决方案可以为2 k、4 k、8 k、16 k、32 k。随着解决方案数和线程数的增加，代价随之减少。然而考虑多线程通信的费用，代价并不总与线程的数目成反相关。

1 问题描述

进化[6-7]可以被认为是一种三维景观的旅程。森林景观中每个位置中可能基因组合的高度表示生存的适应度。森林景观中有很多山峰和山谷，这样山峰与山峰相邻，山谷与山谷相邻，即所谓的适应度景观。进化就是在适应度景观中查找高点的过程。

通过控制N和K2个参数来确定适应度景观，进而观察其复杂性对森林系统进化的影响。同样，在经营森林管理过程中，有很多森林的基因组合，以及这些组合中的相互影响关系，森林进化的优劣用适应度景观数值表示。因此，森林进化的适应度景观实际上是全部基因状态大体组合产生的三维立体图。通过基因组合值的提高进而促进繁杂森林的进化(由现在的状态转换到最佳的状态)，详细展现为适应度景观上的攀跃过程[8]。假如，有一个具有4个基因组合的森林体系，N=4，目前状态S0(0000)的适应度值为0.301，最佳状态S′(1111)的适应度值为0.725，从图1可以看出，从S0到S′有很多路径，找出代价最小的1条路径。

由于基因组合出现变化，不单会造成由它确定的森林适应度值产生变化，而且会造成与它关联的其他基因组合确定的适应度值产生变化。这两部分的变化共同决定了森林整体适应度值。具体而言，设1个森林系统的要素与要素间的相互作用表示为dij(j=1，2，…，K)，由目前状态到最佳状态所需的花费函数f，则森林系统的目标函数为：

(1)

2 串行模拟退火算法

模拟退火算法[9-12]可以分解为目标函数、解空间和初始解3部分。模拟退火算法运算流程简便，普遍，鲁棒性强，能够使用于解决繁琐的非线性优化问题，然而存在实现时间较长、慢等缺点。综合以上缺点，可以运用高效的退火策略，避免状态的迂回搜索，以及采用并行搜索结构等方法来改进SA算法。

3 并行模拟退火算法

3.1 独立搜素

并行模拟退火算法采用独立搜索IS(Independent searches)时，有p0，p1，…，pp-1的线程独立执行，各个进程执行SA算法。在各个进程计算完毕后使进程互换各自最优解，从中再选取最优解。

假如模拟退火步奏为I，独立搜索时，每个线程执行的模拟退火步奏为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，如果线程数目为2、4、8、16、32，独立搜素下的公式(3)的收敛速度分别为0.843、0.731、0.565、0.357、0.159(表1、图2)。因此，并行独立的搜索比传统的串行模拟退火算法具有更快的收敛比。

3.2 合作搜索

表1 不同线程数量下的算法收敛速度

在合作搜索CS(Co-operating searches)中，采用同步通信策略。各个进程得到原始解S0后，各自执行各自的Markov Chain。当温度一定时，各个进程本质为一个Metropolis过程。当经历某个恒定的间隔周期，到达某个特定的中间温度时，每个Markov Chain比较当前各自的局部最优解Sj及其对应的f(Sj)，j=0，1，2，…，p-1。对比P个进程的代价f(Sj)值。如果i进程的代价值最小，则在下一个温度值下，当前的局部最优解将成为每个进程的原始解。若是当前有多于2个的局部最优解[14-18]，随机选1个即可，此选取过程不影响最终的结果。主线程0主要负责接受每个分线程的结果，比较这些结果，并得出局部最优解。具体流程见图3。

图3 优化并行算法下线程的合作方式图4 并行模拟退火流程

运用并行模拟退火算法，提升了算法的运行速度，确保了算法有很大并行粒度；且使得在确定的温度值下，上一个分进程搜索的局部结果传递给下一个分进程，节省时间，进而实现搜寻消息的交融(图4)。根据并行算法流程，可得森林管理问题的伪代码表示(表2～表4)。

对于并行算法，进程要通过n步消息互换，关于每一步消息互换，(w-1)-1个消息量为O(n)的消息需要被发配与接收，所以整个运行时间代价为n2(n+(w-1)-1)。因此并行模拟退火算法的总时间成本不超过O(n3)。

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

表3 模拟退火流程

表4 线程合作的流程

4 实验分析

研究人员将在不同并行优化策略下评估模拟退火算法各自的效率。此算法中用来测量效率的数据集合是基于100 个客户规模的 Solomon测试集。考虑到客户的拓扑分布，此测试集由聚集在3个集合的56个问题组成。这3个集合分别是随机分布的R()，堆分布的C()，半堆分布的RC()。它们的地理位置分布具有以下特点：R()数据集为随机生成，C()数据集为聚类分布，数据集RC()为混合随机聚类分布。在不同并行策略中，进程间沟通的重要性显而易见，通过与以往的方法比较，部分解决方案的通信提高了最优解的搜索效率。

对于每个测试集合，合作搜索和独立搜索算法分别被执行上千次，执行结果如图5～图7所示。对于测试统计学得出：

在实验中，分别对R类和RC类下数据集进行测试，得出在独立搜索和合作搜索算法下代价与进程数目的关系曲线。

5 结论

通过实验可以看出，在独立搜索中，随着线程数目的增加，模拟退火算法收敛速度越快。在独立搜索和合作搜索算法下，考虑到沟通周期和链长的影响，Z并不与线程的数目成反比。如何得出线程数目、链长和线程沟通间隔三者间最佳的组合比，将成为研究者下一步探索的核心，进而找出高效的解决方案。从片面追求经济效益向社会、经济和生态多种效益并举转变是当今的森林经营理念。每个群体对于森林管理效益的侧重点不同，与此同时，森林随着时间的动态变化，无疑增加了森林管理的复杂性。利用并行的模拟退火算法，使森林朝着人所期望的方向进化，高效率低成本的管理经营森林。对加强林业建设的规划化、产量化以及管理化等具有重要的意义。

[1]权兵.基于虚拟森林环境的林分生长和经营模拟研究[D].福州：福州大学，2005.

[2]刘海.森林经营可视化模拟研究[J].世界林业研究，2010，23(1)：21-25.

[3]梁发超.景观分类的研究进展与发展趋势[J].应用生态学报，2011，22(6)：1632-1638.

[4]潘存德，师瑞峰.森林可持续经营：从木材到生物多样性[J].北京林业大学学报，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，FOGA 2000，Martin，W.N.，Spears，W.M.(Eds.)，Morgan Kaufmann Publishers，2000：91-107.

[10]朱颢东.一种改进的模拟退火算法[J].计算机技术与发展，2009，19(6)：32-35.

[11]项宝卫.模拟退火算法在优化中的研究进展[J].台州学院学报，2005，27(6)：6-9.

[12]汪灵枝.一种有效的全局优化算法-模拟退火算法[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，FAN 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

中央高校基本科研业务费项目(DL12EB01-02)；国家科技基础性工作专项项目(2014IM020100)；国家人社部留学归国人员择优资助项目

于慧伶(1980—)，女，黑龙江哈尔滨人，东北林业大学信息与计算机工程学院副教授，博士，从事计算机辅助创新理论与方法研究。E-mail：yhl2016@163.com。

范德林(1959—)，男，东北林业大学经济与管理学院教授，从事技术创新方法的研究与推广工作。E-mail：dlfan33@aliyun.com。

10.13428/j.cnki.fjlk.2016.01.024

S750

A

1002-7351(2016)01-0110-06