于慧伶,崔姗姗,范德林

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



框架下森林分类的并行模拟退火算法*

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

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

摘要：针对传统模拟退火算法存在收敛速度慢、执行时间长的缺点，本研究提出了一种并行在线的模拟退火算法及其优化策略，并将其运用到森林景观分类中。研究人员运用多马尔科夫链异步通信和同步通信两种策略实现模拟退火算法的并行处理。在Solomon提供的标准测试集上对并行算法性能进行测试和分析，得出并行算法时线程间的通信可以提高目标解的搜索效率。与此同时，同步通信策略目标解的搜索效率优于异步通信策略，但是会增加一些通信负载的成本。通过大量实验得出森林分类经营代价与线程沟通周期、链长和线程数目的关系，从而节省景观分类的时间代价，进而解决一些NP难题。

关键词：森林分类；模拟退火算法；马尔科夫链;异步通信;同步通信；Map Reduce框架；Hadoop

森林景观是指在确定区域内由不同类别生态系统构成并具备重复性布局的不同地质的地理块，其分类是根据地理位置、自然气候、地质使用类别、植物和土地特征等要素进行[1～2]。复杂的林木空间分布会影响森林景观的经营分类，因此在固有的经营模型中增加空间限制让模型变得更为庞大且很难得到最优解，唯有运用启发式算法才能快速找到恰当的目标解，所以探究基于启发式算法的森林经营管理成为林学急切解决的首要问题。

在森林经营规划中，研究人员利用一些分类指标(如景观多样性指数和均匀度指数等)生成目标函数，进而计算景观分类代价。本文对模拟退火算法的并行化及其并行通信策略进行深入研究，并在SA算法中运用并行策略提高目标函数中最优解的搜索效率，进而减小景观分类的经营代价[3～4]。算法在Map Reduce框架下并行时，可采取一系列并行策略(线程通信策略和解决方案数目等)：线程可以采用异步通信和同步通信策略；算法并行化的解决方案分为每个线程有固定数目的解决方案(2K,4K，8K等)或所有线程有总共固定常数的解决方案。研究人员在上述并行策略的算法中探究森林景观分类的经营代价。

1问题提出

E=(H/Hmax)*100 %④,式中,E是均匀度指数，H是景观多样性指数，均匀度是指景观中不同类型的分配均匀程度。本研究的目标函数是在算法中利用这些指标计算森林分类经营代价。

乌赛高速公路生态保护控制区站区绿化建设实践……………………………… 陈六明，朱坤，孙兆祜，钱丽（4-163）

2SA算法并行化的理化基础

2.1　串行模拟退火算法

SA是一种普遍概率算法，在确定时间内，在一个大的搜寻范围内查找最优解[11～12]。传统SA算法计算过程简单，一目了然，鲁棒性强，解决比较繁琐的非线性优化问题，但是具有速度慢、运行时间长等一系列缺点。考虑综上缺点，可以设计适当的状态生成函数，并且依据查找线程的需求显示出状态的一切空间分散性或区域性，以免产生状态的迂回查找；并且复杂的数据集的问题使得运用Map Reduce框架并行化SA算法势在必行[13～14]。

2.2　Map Reduce框架

在Hadoop中，用于执行Map Reduce任务有两个角色，一个是JobTracker，另一个是TaskTracker[15～16]。JobTracker是用于处理和安排工作的，TaskTracker是运行工作的。一个Hadoop集群中只有一台JobTracker，各个Map Reduce任务都被初始化为一个Job。各个Job又可以分为两个阶段，Map阶段和Reduce阶段，用Map和Reduce函数来表示这两个阶段。

Hadoop的另外一个核心是HDFS，而整个Hadoop单元结构通常是由HDFS来达成分布式存储，而且HDFS会经由Map Reduce来达成分布并行分布作业处理的程序支撑[17]。HDFS运用主从(Master/Slave)结构模式，一个HDFS集群由一个Namenode和若干个Datanode构成。Namenode是分布式文件系统的经营者，Datanode负责管理文件系统客户端的文件需求，并且在Namenode的统一安排下进行工作。

大数据集肢解成若干个小数据集合，各个数据集合有集群中的一个节点[18]，进而运行并行管理并形成中间结果，随之此节点与其他很多节点归并，生成终极结果(图1)。

图1　Map Reduce作业执行的流程图

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

SA算法具备优良的内在并行性。当前，存在一些已经完成SA算法的并行解决办法[19]：并行移动；移动加速；推测性计算和多马尔科夫链。其中，multiple Markov chain是最常用的解决并行处理的办法。此办法是将传统的串行SA中的一条Markov chain分裂为multiple Markov chain(多线程)，这些线程在确定的时间内单独生长，又能够进行合理的互换信息，进而取得了能够扩展的并行性能。另外，经过保存Markov chain的最佳值，并遵照确定的时间间隔对不一样的Markov chain获得的最佳值进行互换，进而提速了优化的过程，Markov chain策略分为异步和同步两种通讯策略。

当采用异步通信策略时，在以下两种情况下发生通信，第一种情况是确定一个固定的周期；另一种各自搜索结束后，对比最终状态。各个线程对应一个Markov chain，并进行单独的运行。在各个线程运行结束后，比较各个线程的局部优化解，最终获得终极解。当选用同步通信策略时，各个线程以初始解X0单独的执行各自的Markov chain，温度确定后，各个线程本质上为Metropolis过程。当通过一段确定的间隔周期W后，达到一个固定的中间温度时，Markov chain比较当前这些局部优化解，将比较后的最佳局部优化解作为下一个温度下的初始解，一直反复这个过程，直到满足结束条件。

通过研究并行同步算法得知，生成的Markov chain是不匀称的。因为从此解转变到另外解的概率不单受当前解相应的成本值和此刻温度影响，而且与从算法过程中导入的上一轮次的局部最优解有关。基于此思想，在Map Reduce框架下，运用Master/Slave结构优化并行算法，在不相同温度值间，采用并行同步通信策略，主线程掌管接受子线程的局部优化解(图2)。

图2　优化并行算法下线程的配合方式

运用p-SA算法，提高了SA算法的解决速度，不仅确保了算法有较大规模的并行粒度；而且在固定的温度值下，上一轮次子线程搜查的结果转达给下个子线程，完成了搜查信息的归并。表1为并行SA的流程。在下面的算法流程中，parfor表示对一个for循环进行并行化计算。

表1　SA流程

表2　线程合作的流程

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

对于p-SA算法，线程要通过n步消息互换，关于每一步消息互换，有(w-1)-1个信息量为O(n)的信息被发配和收入，所以整个运行时间代价为n2〔n+(w-1)-1〕。所以，p-SA算法的总时间代价不超过O〔n3+(w-1)*n2〕。

3实验分析

为验证不同策略下并行算法的效率，本文基于Map Reduce在分布式集群平台上对多组数据进行测试考证，测试使用的数据来自solomon提供的标准测试集[20]，测试数据库包括数据集 R(随机分布)、C(堆分布)、RC(半堆分布)、拓扑地理位置具有以下的特点：数据集 R中节点是随机生成，数据集C为聚类分布，数据集 RC为混合随机聚类分布。本文只针对R测试集进行测试分析。

在这个测试数据集的基础上，根据不同线程数目、链长、线程沟通周期，进行一系列的实验。对于R测试集合,变化线程数目、链长、线程沟通周期,算法被执行上千次，执行结果的大体趋势见图3～8。

图3　针对R101和R102优化后的算法测试值

图4　针对R103和R106优化后的算法测试值

图5　针对R101和R102优化后的算法测试值

图6　针对R107和R108优化后的算法测试值

图7　针对R107和R108优化后的算法测试值

图8　针对R109和R110优化后的算法测试值

算法采用同步通信策略并行时，具有发现相关优质解决方案的良好平均行为和算法稳定性基本不受线程数目增加的影响等一系列优点。与此同时，线程间的通信提高了最优解的搜索效率。然而，算法并行时，线程通信会增加一些通信负载的成本。因此，对于线程通信找出一种折中的优化方案迫在眉睫。

4结语

本项目主要研究了并行模拟退火算法及其优化策略，并在算法中利用景观异质性指标代价函数节省景观分类代价。主要结论如下，(1)算法利用同步通信策略并行时，随着线程数目的增加，模拟退火算法收敛速度越快。(2)景观异质性指标代价不仅与线程数目有关，还与线程沟通周期、链长有密切的关系。(3)当固定每个线程的解决方案时，代价与线程的数目成反比；当总共解决方案为常数时，代价并不总是与线程的数目成反比。运用模拟退火算法对森林景观分类做深入研究，进而提高森林景观分类的运作效率，节约成本，具有较高的理论与实践研究价值。与此同时，对加强景观分类建设的规划以及管理化等也具有重要的意义。

参考文献：

[1]赵春燕.顾及耦合作用的森林景观多尺度分类[J].林业科学,2013,49(11):185-188.

[2]梁发超.景观分类的研究进展与发展趋势[J].应用生态学报,2011,22(6):1633-1637.

[3]陆元昌.分类评价中的应用研究[J].林业科学研究,2005,18(1):31-35.

[4]陈勇.森林景观经营研究现状与展望[J].东北林业大学学报,2010,38(4):111-113.

[5]傅伯杰.国际景观生态学研究新进展[J].生态学报,2008,28(2):709-803.

[6]师庆东.基于气候、地貌、生态系统的景观分类体系[J].生态学报,2014,34(12):3359-3366.

[7]余新晓,李秀彬,夏兵.森林景观格局与土地利用/覆被变化及其生态水文响应[M].北京:科学出版社,2010:83-89.

[8]张芸香,郭晋平.森林斑块密度及边缘密度动态研究——以关帝山林区为例[J].生态学杂志,2001,20(1):18-21.

[9]白降丽.森林景观生态研究现状与展望[J].生态学杂志,2005,24(8):943-947.

[10]黄龙生.我国森林景观生态规划研究进展[J].河北林业科技,2013,12(6):36-38.

[11]刘怀亮，刘淼.一种混合遗传模拟退火算法及其应用[J].广州大学学报,2005,2(4):141-145.

[12]顾元宪.一种改进的连续变量全局优化模拟退火算法[J].系统工程理论与实践,2005,2(4):103-106.

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

[14]蒋龙聪，刘江平.模拟退火算法及其改进[J].工程地球物理学报,2007,4(2):135-140.

[15]黄伟建.Map Reduce高可用性的研究与优化[J].计算机工程与设计,2014,35(11):4044-4046.

[16]陈海波.云计算平台可信性增强技术的研究 [D].上海:上海复旦大学,2009.

[17]何荣波.Map Reduce模型在Hadoop中的性能优化及改进[D].北京：北京化工大学，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，FAN 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-)，男，教授，博士，主要从事技术创新方法的研究与推广工作。E-mail:dlfan33@aliyun.com

作者简介：第一于慧伶(1980-)，女，副教授，博士，主要从事计算机辅助创新理论与方法研究。E-mail:yhl2016@163.com

基金项目：中央高校基本科研业务费项目(DL12EB01-02)，国家科技基础性工作专项项目(2014IM020100)，黑龙江省教育厅科学技术研究项目(12523018)。

*收稿日期：2015-06-19

中图分类号：TP 301.6;S 757

文献标识码：A

文章编号：1672-8246(2016)01-0025-06