Planejamento florestal com restrições de adjacência utilizando programação paralela

Abstract

Resumo: O presente trabalho teve como objetivo avaliar versões paralelas e sequenciais dos algoritmos enxame de partículas (particle swarm optimization - PSO) e busca tabu (BT), aplicados a modelos de planejamento florestal com diferentes tipos de restrições de adjacência entre talhões. Os dados foram obtidos de povoamentos de Pinus spp e Eucalyptus spp com área total de 2.429,99 ha e 236 talhões, pertencentes à empresa REMASA Reflorestadora S.A. Foram gerados cenários considerando os tipos de restrição de adjacência denominados unit restriction model (URM) e area restricition model (ARM). Os métodos de resolução dos cenários foram os algoritmos PSO, BT e o método exato branch and bound. Foi também proposta uma modificação ao algoritmo PSO com intensificação de busca em vizinhança. Para os três métodos, PSO, BT e modificação da PSO, foram avaliadas diferentes configurações de seus parâmetros. Como forma de melhorar o tempo de processamento das meta-heurísticas, foram implementadas versões paralelas dos algoritmos PSO e BT conforme o modelo fork-and-join empregando a biblioteca OpenMP. Os resultados demonstram que o modelo ARM gera maior quantidade de restrições que o modelo URM. As melhores configurações para o algoritmo PSO foram com velocidade máxima de 10% e populações maiores que 100 partículas. Para a modificação proposta ao algoritmo PSO a melhor configuração foi com população de 10 partículas e intensificação de busca em vizinhança de uma solução vizinha por partícula por iteração. O algoritmo BT apresenta as melhores soluções quando a busca é realizada na vizinhança total e o tempo tabu é igual a 10 iterações. Quando comparado o desempenho dos três algoritmos, a BT apresenta as soluções de melhor qualidade, seguido da modificação da PSO com busca em vizinhança e, por fim, o algoritmo original PSO. As versões paralelas dos algoritmos PSO e BT apresentaram economia de tempo de processamento em relação às versões sequenciais, indicando que a programação paralela é uma estratégia promissora para resolução de problemas de planejamento florestal de grande porte. Palavras-chave: restrições espaciais, meta-heurísticas, agendamento da colheita florestal.

Abstract: This study aimed to evaluate parallel and sequential versions of particle swarm optimization (PSO) and tabu search (BT) algorithms, applied to forest planning models with different types of adjacent constraints between stands. Data were obtained from stands of Pinus spp and Eucalyptus spp with total area of 2,429.99 ha and 236 stands belonging to the REMASA Reflorestadora S.A. enterprise. Scenarios were generated considering the adjacency constraint denominated unit restriction model (URM) and area restricition model (ARM). The methods of solving scenarios were the PSO, BT algorithms and the exact method branch and bound. It has also proposed a modification to the PSO algorithm by intensifying the search in the neighborhood. For the three methods, PSO, BT and modification of PSO have been evaluated different settings of its parameters. In order to improve the processing time of the meta-heuristics, parallel versions of PSO and BT algorithms have been implemented as the fork-and-join model using the OpenMP library. The results demonstrate that although less restrictive, the ARM model generates more constraints that the URM. The best settings for the PSO algorithm have been maximum speed of 10% and populations greater than 100 particles. To the proposed modification to the PSO algorithm was the best configuration with a population of 10 particles and intensification search in a neighboring solution per particle per iteration neighborhood. The BT algorithm presents the best solutions when the search is performed in the full neighborhood and tabu time is equal to 10 iterations. When comparing the performance of three algorithms, BT has the better solutions, followed by modification of the PSO using neighborhood search, and finally, the original PSO algorithm. The parallel versions of PSO and BT algorithms showed processing time savings compared to the sequential versions, indicating that parallel programming is a promising strategy for solving problems of large forest planning. Key-words: spatial constraints, meta-heuristics, harvesting scheduling.