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

Parallel Simulated Annealing Algorithm of Forest Classification under Map Reduce Framework

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

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.