Performance of four meta-heuristics to solve a forestry production planning problem

Emanuelly Canabrava Magalhães

*, Carlos Alberto Araújo Júnior

, Francisco Conesa Roca

, Mylla Vyctória

Coutinho Sousa4

Abstract

The use of artificial intelligence as a tool to aid in the planning of forest production has gained more and more space.

Highlighting the metaheuristics, due to the ability to generate optimal solutions for a given optimization problem in a short time,

without great computational effort. The present study aims to evaluate the performance of the metaheuris- tics Genetic

Algorithm, Simulated Annealing, Variable Neighborhood Search and Clonal Selection Algorithm applied in a model of

regulation of forest production. It was considered a planning horizon of 16 years, in which the model aims to maximize the

Net Present Value (NPV), having as restrictions age of cut between 5 and 7 years and minimum and maximum logging demand

of 140,000 and 160,000 m3, respectively. Different combinations of configurations were considered for each of the

metaheuristics, 30-second processing time and 30 replicates for each configuration, all processing being performed in MeP -

Metaheuristics for forest Planning software. The Simulated Annealing me- taheuristic obtained the best results when

compared to the others, reaching the minimum and maximum demand demanded in all tested configurations, in contrast, the

Genetic Algorithm was the one with the worst performance. Thus, the capacity to use metaheuristics as a tool for forest

planning is observed.

Keywords:

Artificial intelligence. Forestry. Forest management. Operational research.

Performance de quatro metaheurísticas para solução de um problema de planejamento da

produção florestal

Resumo

O uso da inteligência artificial como ferramenta de auxílio ao planejamento da produção florestal tem ganhado cada vez mais

espaço. Destacando-se as metaheurísticas, em função da capacidade de gerar soluções ótimas para determi- nado problema de

otimização em um curto espaço de tempo, sem grande esforço computacional. Pensando nisso, o

presente estudo objetiva

avaliar o desempenho das metaheurísticas Algoritmo Genético, Simulated Annealing, Variable

Neighbourhood Search e Clonal

Selection Algorithm aplicadas em um modelo de regulação da produção florestal. Foi considerado um horizonte de

planejamento de 16 anos, no qual o modelo apresenta como objetivo a maximização do Valor Presente Líquido (VPL), tendo

como restrições idade de corte entre 5 e 7 anos e demanda mínima e máxima madeireira de 140.000 e 160.000 m3,

respectivamente. Considerou-se diferentes combinações de configurações para

cada uma das metaheurísticas, tempo de

processamento de 30 segundos e 30 repetições para cada configuração, sendo

todo o processamento realizado no software MeP -

Metaheuristics for Forest Planning. A metaheurística Simulated Annealing obteve os melhores resultados quando comparada

as demais, atingindo a demanda mínima e máxima exi- gida em todas as configurações testadas, em contrapartida, o Algoritmo

Genético foi o de pior desempenho. Assim, observa-se a capacidade de uso da metaheurística como ferramenta de

planejamento florestal.

Palavras-chave:

Inteligência Artificial. Silvicultura. Manejo Florestal. Pesquisa Operacional.

1Universidade Federal de Minas Gerais. Instituto de Ciências Agrárias. Montes Claros, MG. Brasil.

https://orcid.org/0000-0002-1240-2766

2Universidade Federal de Minas Gerais. Instituto de Ciências Agrárias. Montes Claros, MG. Brasil.

https://orcid.org/0000-0003-0909-8633

3Universidad de Huelva. Huelva. España.

https://orcid.org/0000-0002-8722-4263

4Universidade Federal de Minas Gerais. Instituto de Ciências Agrárias. Montes Claros, MG. Brasil.

https://orcid.org/0000-0001-6139-1250

*Autor para correspondência: emanuellymagalhaes1@gmail.com

Recebido para publicação em 28 de outubro de 2019. Aceito para publicação em 02 de fevereiro de 2020.

e-ISSN: 2447-6218 /

ISSN: 2447-6218. Atribuição CC BY.

CADERNO DE CIÊNCIAS AGRÁRIAS

Agrarian Sciences Journal

Magalhães, E. C. et al.

Introduction

One of the main challenges of the forest sector is to

attend to the growing demand for wood from legal

sources,

which should be done to optimize the production

process and

regulate the remaining stock over the years (Araújo Júnior,

2012). A regulated forest is subject to management

regulations that allow the uniformity of volumetric

production. This avoids the lack of wood and provides

sustainability to the enterprise (Carvalho et al., 2015).

Revenues referring to the commercialization of wood were:

R$ 20.00 m-3 (less than 3 years old); R$ 30,00 m-3 (4 years

old); R$ 40.00 m-3 (5 years old); and, R$ 80.00 m-3 (ages

equal or superior to 6 years).

The mathematical model for integer linear pro-

gramming aims to maximize the Net Present Value (NPV),

including as restrictions the age of cut between 5 and 7 years

and the minimum and maximum annual demand for wood of

140,000 m3 and 160,000 m3, respectively.

These issues are related to the long-term planning of

forest production (Werneburg, 2015), whose planning

horizon

is more than sixteen years due to the period of

growth and

development of the raw material, which crea- tes greater

complexity for the process of creating strategic

plans. This task

is commonly performed with the aid of operational research

tools, such as linear programming (PL) and integer linear

programming (PLI). However, depending on the desired

detail for the solution of the problem, PL and PLI have

limitations that result in the

impossibility to use or use with

high computational effort

(Araújo Júnior et al., 2017).

Max GNPV =

(01)

Subject to

(02)

(03)

(04)

(05)

where: GNPV is the global net present value for all the forest, in reais;

Cij is

NPV for stand i when assigned the prescription j, in reais; Xij is the decision

variable and represents the proportion area of stand i that will

be managed

with prescription j; M is the total number of stands; N is the total number of

different prescriptions for each stand; Vij(k) is the total volume of wood for

the stand i, when assigned the prescription j, in the period k of planning

horizon; Dmink and Dmaxk are minimum and maximum wood demand for

the period k of the planning horizon.

This is due to the fact that there is a need to find a

solution composed by a considerable set of binary-type

decision variables that relate to each other both in time

and

space. This makes the definition of forest production

plans fall

into the category of combinatorial problems.

In this way, different search techniques from

artificial intelligence have been constantly applied to

determine a suitable solution for such problem. In this

aspect, the metaheuristics stand out, which have as ad-

vantage to obtain very good answers in a relatively short time.

Examples are the work of Gomide and Silva, 2009; Binoti et

al., 2017; Araújo Júnior et al., 2017, 2018; Ferreira et al.,

2018.

Constraint (2) guarantee that all stand area re- ceive

one prescription. Constraints (3) and (4) limit the annual

harvested volume between a minimum and a maximum

values of demand. Finally, constraint (5) impose that there

is only one management prescription for each stand.

Thus, the problem of forest planning described is

the

definition of the sequence of harvest and planting of each of

the plots over the period of 16 years. With this,

each field can

be managed under 81 different prescriptions

and in combination

with the other 119 remaining fields in order to meet the

annual demand for wood. Thus, 120e81 solutions to the

problem are possible, and it is necessary to find the best of

them or the best possible ones.

Among the aspects considered when indicating a

metaheuristic to solve a problem of forest planning, the

time

spent to generate a very good solution is of extreme

importance. The aim of this study was to evaluate the

performance of the Metaheuristic Genetic Algorithm (GA),

Clonal Selection Algorithm (CSA), Simulated Annealing

(SA) and Variable Neighborhood Research (VNS) to obtain

potential solutions considering a short time interval.

Material and methods

For each metaheuristic, different combinations of

its parameters were tested, in order to find the one that best

solves the problem within the thirty second processing

interval.

The problem of forest production planning was

considered for a total area of 4,210 hectares comprising 120

plots, with ages ranging from 1 to 6 years and irre- gular

distribution of area by age class, under a planning horizon of

16 years.

For the Genetic Algorithm (GA), the following

parameters were considered: with and without elitism; two

types of crossing (1 cut-off point and uniform); two types of

parent selection for cross (roulette and tourna- ment); and

two types of mutation (random gene choice and gene to

gene). The initial population size was equal

Silvicultural costs were R$ 4,059.05 ha

-1

(year 1);

1,627.81 ha-1 (year 2); R$ 757.95 ha-1 (year 3); and R$ 88.20

ha-1 for the remaining years from the fourth.

Cad. Ciênc. Agrá., v. 12, p. 01–05, 2020. e-ISSN: 2447-6218 / ISSN: 1984-6738

Performance of four meta-heuristics to solve a forestry production planning problem

to 50 individuals, the mutation rate equal to 1% and the

crossing rate equal to 80%. For CSA, three different values

were considered for hypermutation (H), cloning (C),

selection (S) and substitution (Sub) rates, being equal to

0.20, 0.50 and 0.80. Three values for initial population

(InP) size were evaluated, being 20, 50 and

80 individuals. In

order to test the CSA parameters, it was

decided to follow the

methodology proposed by Araújo Júnior et al. (2018).

combination was 72.2% for SA, 10.8% for VNS and 4.4%

for

CSA.

The viability of the solutions is related to the fact

that it is necessary to produce an annual quantity of wood

that does not exceed the established minimum and maximum

limits. This was observed for the best solutions (Table 1). It

is important to note that harves- ting a larger total amount of

wood (over 16 years) did not reflect higher NPV. This is

due to the fact that the model seeks to optimize the financial

return rather than the maximization of production. Thus, the

importance of sequencing of the harvest is emphasized so

that there is a better yield in terms of NPV with lower

volume of harvested wood.

For the Simulated Annealing (SA) was evaluated:

three initial temperatures (IT), being 108, 106 and 104; three

temperature reduction rates (), being 0.01, 0.05 and 0.10;

and three numbers of neighbors evaluated in each iteration

(V), with quantities equal to 1, 10 and 30.

In the Variable Neighborhood Search (VNS), two

structures were analyzed: structure A with percentages of

changes of 1%, 2%, 3% and 4% and structure B with

percentages of 10%, 20%, 30% and 40%; each structu- re

was executed considering five different amounts of

neighbors evaluated (1, 10, 30, 50 and 100).

These results demonstrate the superiority of SA

metaheuristics in relation to the search for viable solu-

tions. Such performance had already been highlighted in

other studies, such as those of Ezquerro et al. (2016), in

which the authors mention that SA is one of the most

cited in

the forest literature, and Rodrigues et al. (2004a), where the

authors state that SA is one of the metaheuris-

tics that are less

affected by changes in their parameters.

Data processing considering the different configu-

rations was carried out in the application Metaheuristics for

Forest Planning (MeP), developed in the Laboratory of

Operational Research and Forest Modeling (LPM) of the

Federal University of Minas Gerais.

The metaheuristics AG is widely applied to solve

forestry planning problems (Rodrigues et al., 2004b; Go- mide

et al., 2009; Silva et al., 2009; Binoti et al., 2014 and

Matos,

2017). However, its use has been diminished as

new

algorithms appear that are more efficient during the

process of solutions. The algorithm was sensitive to the

parameter definition, as observed by Gomide et al. (2009).

With the results by the algorithms in each repeti- tion,

the amount of viable solutions obtained was counted.

After that,

the fitness values related to the NPV and the solutions that

obeyed the demand for the required wood demand were

evaluated.

Another aspect is related to the number of ope-

rations that the algorithm needs to perform during the

same

generation, especially when adopting a larger num-

ber of

individuals for the initial population. Thus, too much time

is spent without evolution of populations to generate better

individuals, as discussed by Rodrigues et al. (2004b). The

fact that the algorithm found no fea- sible solution in all

cases reveals that it is necessary to evaluate new ways of

improving the GA search process as suggested in Gaspar-

Cunha et al. (2013).

The entire linear programming model was exe-

cuted in the Lingo software considering a stop processing

time

equal to fifteen minutes.

Results and discussion

The best solutions presented by each algo- rithm

and their respective configurations were: R$ 31,954,028.00

for the VNS, with 100 neighbors and structure 1; R$

31,872,534.00 for CSA, with initial po- pulation size equal

to 20, substitution rate 0.2, selection rate 0.2, cloning rate

equal to 0.8, and hypermutation rate equal to 0.2; R$

30,782,473.00 for SA, with initial

temperature of 10e8,

temperature decay rate of 0,01 and

evaluation of 30

neighbors. The GA did not present any viable solution in all

evaluations. The solution obtained

by the branch and bound

algorithm presented value equal

to R$ 31,274,496.00.

The CSA and VNS metaheuristics presented bet- ter

solutions in terms of fitness value than the solutions found

by the SA. These algorithms were initially applied to forest

problems in the works of Araújo Júnior et al. (2017, 2018)

presenting efficacy above that found for the traditional

algorithms (SA and AG).

The values of the hypermutation and substitution

rates

were the same ones found by Araújo et al. (2018).

However,

the other parameters did not present the same values. This

shows the need to define a set of parameters

for each situation

analyzed, which suggests the use of adaptive mechanisms,

so that these values are changed during the execution of the

algorithm.

The CSA presented feasible solutions in only three

parameter combinations. VNS presented feasible solutions

in four of the 10 combinations evaluated and the SA

presented feasible solutions in 26 of the 27 com- binations

tested. The mean of viable replicates for each

Cad. Ciênc. Agrá., v. 12, p. 01–05, 2020. e-ISSN: 2447-6218 / ISSN: 1984-6738

Magalhães, E. C. et al.

Table 1 – Volume produced annually by the best solutions found

Volume of wood (m³)

Period

AG*

CSA

VNS

PLI

142,698

140,065

146,319

140,834

149,847

144,031

145,744

140,562

141,206

140,775

144,692

144,966

140,441

143,707

140,053

146,823

146,998

142,086

147,853

159,368

149,718

146,717

152,802

140,041

144,331

142,422

149,017

156,897

141,289

141,128

141,115

141,788

142,698

142,581

141,840

151,911

144,807

142,817

140,022

142,686

142,760

140,324

140,029

140,644

142,833

140,250

140,356

140,636

140,484

141,675

156,355

152,074

155,084

158,132

140,001

141,386

140,070

144,200

142,836

144,871

142,846

141,286

140,040

140,168

Total

2,292,763

2,343,570

2,277,194

2,321,508

The configuration determination of the metah-

euristics used is a process of great importance and com-

plexity, mainly because it is dependent on the problem to be

solved, so there is no standardization of the confi- guration

for each tool making scientific research in this area

necessary.

riable Neighborhood Search presented the highest values

fitness, although they occur in few repetitions. It is possible

to conclude that there is great potential in such algorithms to

solve the problem in question.

It can be concluded that for all metaheuristics, it

important to define an initial structure of parameters

that

guarantee good solutions in a relatively short period

of time.

Conclusion

The Metaheuristic Genetic Algorithm was unable

generate viable solutions in a short period of time and was not

indicated for the problem in question.

Acknowledgment

The authors express their thanks to The Minas

Gerais State Research Foundation (FAPEMIG) and Bra-

zilian National Council for Scientific and Technological

Development (CNPq) for their financial support and to the

Federal University of Minas Gerais for their scientific

support.

The simulated annealing metaheuristic was less

affected by the initial configuration of its parameters and

this is

an important feature when choosing an algorithm to optimize

a forest production planning problem.

The metaheuristics Clonal Selection Algorithm and Va-

References

Araújo Júnior, C. A.; Leite, H. G.; Soares, C. P. B.; Binoti, D. H. B.;

Souza, A. P.; Santana, A. F; Torre, C. M. M. E. 2017. A multi-agent

system for forest transport activity planning. Cerne, 23: 329–337. Doi:

http://dx.doi.org/10.1590/01047760201723032335.

Araújo Júnior, C. A.; Mendes, J. B.; Cabacinha, C. D.; Assis, A. L. de;

Matos, L. M. A.; Leite, H. G. 2018. Meta-heuristic clonal selection

algorithm for optimization of forest planning. Revista Árvore, 41: 1–10.

Doi:

http://dx.doi.org/10.1590/1806-90882017000600007.

Cad. Ciênc. Agrá., v. 12, p. 01–05, 2020. e-ISSN: 2447-6218 / ISSN: 1984-6738

Performance of four meta-heuristics to solve a forestry production planning problem

Araújo Júnior, C. A. 2012. Simulação multiagentes aplicada ao

planejamento da produção florestal sustentável. Viçosa: Universidade

Federal de Viçosa. Dissertação.

Matos, L. M. A. 2017. Utilização da metaheurística algoritmo genético em

um modelo de regulação da produção florestal. Montes Claros:

Universidade Federal de Minas Gerais. Dissertação.

Binoti, D. H. B.; Binoti, M. L. M. S.; Leite, H. G.; Gleriani, J. M.; Ribeiro,

C. A. A. 2014. Inclusão e influência de características espaciais em

modelos de regulação florestal. Cerne, 20: 157–164. Doi: http://dx.doi.

org/10.1590/S0104-77602014000100019.

Rodrigues, F. L.; Leite, H. G.; Santos, H. N.; Souza, A. L.; Ribeiro, C.

A. A.S. 2004a. Metaheurística simulated annealing para solução de

problemas de planejamento florestal com restrições de integridade. Revista

Árvore, 28: 247–256. Doi: http://dx.doi.org/10.1590/S0100-

67622004000200011.

Carvalho, K. H. A.; Silva, M. L.; Binoti, D. H. B.; Binoti, M. L. M. S.

2015. Influência da taxa de juros e do preço da madeira em modelos de

regulação florestal. Pesquisa Florestal Brasileira, 35: 143–151. Doi:

https://doi.org/10.4336/2015.pfb.35.82.554.

Rodrigues, F. L.; Leite, H. G.; Santos, H. N.; Souza, A. L.; Silva, G. F.

2004b. Metaheurística algoritmo genético para solução de problemas de

planejamento florestal com restrições de integridade. Revista Árvore, 28: 233–

245. Doi: http://dx.doi.org/10.1590/S0100-67622004000200010.

Ezquerro, M.; Pardos, M.; Diaz-Balteiro, L. 2016. Operational research

techniques used for addressing biodivertity objetives into forest

management: an overview. Forests, 7: 229–247. Doi: https://doi.

org/10.3390/f7100229.

Silva, G. F.; Piassi, L.C.; Mora, R.; Martins, L.; Teixeira, A. F.; Júnior, A.

A. B. 2009. Metaheurística algoritmo genético na solução de modelos de

planejamento florestal. Revista Brasileira de Ciências Agrárias, 4: 160–

166. Doi: http://dx.doi.org/10.5039/agraria.v4i2a7.

Ferreira, P. H. B.; Matos, L. M. A.; Assis, A. L.; Cabacinha, C. D.;

Araújo

Júnior, C. A. 2018. Influência dos parâmetros da metaheurística

simulated

annealing em um problema de planejamento da produção florestal.

Caderno de Ciências Agrárias, 10: 59–67.

Werneburg, M. A. P. 2015. Planejamento em grandes empresas florestais no

Brasil. Diamantina: Universidade Federal do Vale do Jequitinhonha

Mucuri. Dissertação.

Gomide, L. R.; Arce, J. E.; Silva, A. C. L. 2009. Uso do algoritmo genético

planejamento florestal considerando seus operadores de seleção. Cerne,

15: 460–467.

Cad. Ciênc. Agrá., v. 12, p. 01–05, 2020. e-ISSN: 2447-6218 / ISSN: 1984-6738