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

Research and Application of the Parallel Simulated Annealing Algorithm in Forest Management Variables

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

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.