XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
UMA ABORDAGEM VIA PROGRAMAÇÃO DINÂMICA NÃO-LINEAR PARA O
PROBLEMA DO CONTROLE BIOLÓGICO DE PRAGAS NUMA LAVOURA
André Rodrigues da Cruz
Graduando em Matemática Computacional
Universidade Federal de Minas Gerais
Av. Antônio Carlos 6627, Belo Horizonte, MG 31270-010
[email protected]
Rodrigo Tomás Nogueira Cardoso
Doutorando em Engenharia Elétrica
Universidade Federal de Minas Gerais
Av. Antônio Carlos 6627, Belo Horizonte, MG 31270-010
[email protected]
Ricardo Hiroshi Caldeira Takahashi
Departamento de Matemática
Universidade Federal de Minas Gerais
Av. Antônio Carlos 6627, Belo Horizonte, MG 31270-010
[email protected]
RESUMO
O controle biológico de pragas em uma lavoura é feito liberando-se uma quantidade
correta de inimigos naturais das pragas numa determinada plantação em tempos adequados. O
presente trabalho tem como proposta apresentar soluções matemáticas para esse problema,
baseadas em técnicas de otimização dinâmica não-linear. O objetivo é minimizar o custo e
viabilizar o processo através da inserção de predadores na lavoura em estágios definidos por
intervalos de tempo não-contínuos. Para isso, propõe-se uma ação de controle discreto ótima num
horizonte de tempo finito, calculada através de algoritmos genéticos que operam sobre um
problema formulado como uma otimização dinâmica não-linear. Os resultados obtidos levam em
conta a necessidade de controlar o nível das pragas na lavoura agindo em intervalos de tempo
factíveis com um mínimo custo.
PALAVRAS-CHAVE. Aplicações Agropecuárias e Meio Ambiente, Programação
Matemática, Programação Dinâmica, Algoritmos Genéticos.
ABSTRACT
The biological control of plague in agriculture is performed by leaving a suitable quantity
of natural enemies of the plague in the farm at adequate instants. This work has the purpose of
presenting mathematical solutions for this problem, based on non-linear dynamical optimization
techniques. The aim is to minimize the financial cost, allowing the procedure through the
insertion of predators in the farming at discrete time stages. For performing this, it is proposed a
discrete-time optimal control action in a finite time horizon, calculated via genetic algorithms,
using a non-linear dynamic optimization formulation. The results take into account the need for
controlling the level of plague in framing, acting in feasible time intervals with a minimal cost.
KEYWORDS. Farming applications and Environment, Mathematical programming,
dynamic programming, genetic algorithms.
XXXVIII SBPO
[ 48 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
1. Introdução
O controle biológico de pragas em uma lavoura é uma ação que a humanidade executa
desde os tempos remotos e, atualmente, possui grande importância devido a um melhor
aproveitamento e conservação dos recursos naturais pela substituição do uso de agrotóxicos. Isso
resulta em produtos agrícolas de melhor qualidade nutricional, que possui uma aceitação melhor
no mercado.
Existem três tipos de controles biológicos a se considerar [Rafikov e Feltrin (2002)][
DeBach (1964)][Dent (1995)]:
1. Controle Biológico Clássico: envolve investigação a respeito da origem da praga, a fim
de descobrir quais são os inimigos naturais. Os indivíduos da espécie inimiga
(normalmente exótica) são importados para a lavoura a fim de que naturalmente se
reproduzam e ataquem a praga. Esse tipo de controle é datado como o mais antigo.
2. Aumento: é um método mais atual, que consiste na liberação de grandes quantidades de
predadores (inimigos naturais), os quais são produzidos em massa em laboratórios. A
liberação é feita, geralmente, apenas no período e local em que for necessária. Esse
método exige uma contínua manutenção e não fornece uma solução permanente.
3. Controle de Conservação: enfatiza a manipulação de aspectos de ecossistema para
conservar e aumentar populações de predadores naturais de modo que os problemas com
a praga fiquem reduzidos.
O tipo de controle a ser considerado neste trabalho se enquadra no controle clássico e de
aumento. Nestes tipos de controle, normalmente são liberadas grandes quantidades de predadores
naturais a fim de dizimar totalmente ou reduzir a população de pragas a um número
insignificante. Uma visão ecológica considera um inseto como praga se e somente se a
quantidade deste inseto na lavoura causa danos econômicos.
O trabalho de [Rafikov e Feltrin (2002)] consistiu em determinar um controle ótimo
contínuo de pragas, de modo que a densidade dessas pragas fique abaixo de um nível considerado
tolerável, ou seja, de modo que não haja danos econômicos e que a população de inimigos
naturais se estabilize em um valor suficiente para controlar as pragas. Os resultados apesar de
serem ótimos, são inviáveis sob o ponto de vista prático, devido à necessidade de inserções de
predadores num tempo contínuo, necessitando de uma aproximação contínua para sua
implementação, à custa da otimalidade da solução.
O presente trabalho tem como objetivo otimizar o controle de pragas através de inserções
de predadores na lavoura por estágios definido por intervalos de tempo não-contínuo, de forma a
minimizar o custo e viabilizar a implementação do mesmo, com otimalidade exata, e
considerando funções-objetivo com formato mais flexível.
2. Modelo Matemático
A interação entre os predadores e as presas pode ser modelada através de um sistema
dinâmico não-linear de equações diferenciais dado por [Rafikov e Feltrin (2002)]:
dx/dt = x.(a – γ.x – α.y)
dy/dt = y.( – b + β.x)
(1)
Em que a, γ, α, b e β são constantes positivas com valores conhecidos. Esse sistema
caracteriza a relação entre presa e predador sem uma ação de controle.
As variáveis x e y representam as densidades das presas e predadores, respectivamente;
os produtos a.x e –b.y modelam a taxa de crescimento das presas e a taxa de mortalidade dos
predadores; os termos –α.x.y e β.x.y representam as interações entre as duas populações em
ambas as equações, em que cada encontro tende a ser favorável ao predador, pois possibilita o
XXXVIII SBPO
[ 49 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
crescimento dessa espécie e desfavorável à presa por reduzir a sua população; o produto (-γ.x).x
determina a competição intra-específica.
Os valores para as constantes utilizadas nesse trabalho foram baseados em dados da
EMBRAPA apresentados em [Rafikov e Feltrin (2002)].
A
0,16
α
0,02
b
0,19
γ
0,001
β
0,0029
Tabela 1: Tabela de constantes
Assim, para esse caso, a equação (1) ficará:
dx/dt = x.(0,16 – 0,001.x – 0,02.y)
dy/dt = y.( –0,19 + 0,0029.x)
(2)
De acordo com estas informações, a densidade de 20 lagartas de soja grande por metro
quadrado (com mais de 1,5 cm) ou a densidade de 40 lagartas pequenas (de 0,5 a 1,5 cm) por
metro quadrado não causam danos econômicos a lavoura. Assim, queremos que ao final do
processo de otimização, a densidade das presas seja x*=20 ou x*=40 para lagartas de soja
grandes e pequenas, respectivamente.
Para valores diferentes de zero de presas e predadores como condição inicial, esse
sistema dinâmico possui um único ponto fixo, que por sinal é estável. Assim, a partir de uma
condição inicial não-nula, com o passar do tempo, as variáveis se estabilizam nesse ponto de
equilíbrio e qualquer pequeno distúrbio na vizinhança não alterará a trajetória. No presente caso,
o ponto de estabilidade será:
Densidade de Presas (Equilíbrio)
Densidade de Predadores (Equilíbrio)
x (Equilíbrio) = 65,5172
y (Equilíbrio) = 4,7241
Tabela 2: Ponto fixo estável
A figura 1 apresenta o comportamento do sistema presa-predador para a condição inicial
de presas igual a 50, predadores igual a 10, num tempo decorrido igual a 200.
Para o número de predadores inicial igual a zero e presas diferente de zero o sistema
estabiliza em:
Densidade de Presas (Equilíbrio)
Densidade de Predadores (Equilíbrio)
x (Equilíbrio) = 160
y (Equilíbrio) = 0
Tabela 3: Ponto fixo estável para número de predadores nulo
Os dados acima demonstram que há uma competição interna entre as próprias presas
nessa situação. Para o número de presas igual a zero e predadores diferente de zero ocorre a
extinção dos predadores conforme mencionado anteriormente.
Nos testes realizados nesse trabalho considera-se como condição inicial a densidade de
presas igual a 100 e o tempo final (ou o instante da colheita) como 200. O nível tolerável de
pragas, que não causa danos econômicos a lavoura, é definido como x*=20.
Supõe-se que não há interferência de agentes externos que possam causar modificações
XXXVIII SBPO
[ 50 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
no comportamento do sistema dinâmico.
Figura 1: Comportamento do sistema presa-predador
3. Controle Dinâmico Por Estágios Sem Restrição de Tempo
O objetivo dessa parte do trabalho é otimizar o controle de pragas, para que seja possível
manter a densidade de lagartas que atacam a lavoura abaixo do nível considerado tolerável, para
que não haja prejuízos econômicos. A solução deve ter o menor custo possível para execução.
É necessário saber qual é o número médio de predadores a serem lançados inicialmente
na lavoura de forma a atingir o nível tolerável de presas e mantê-lo sempre abaixo dessa meta a
um menor custo possível.
Assim, temos que minimizar:
Min C = dY0 + dY1.TF/dT
Sujeito a:
{ x(TF) <= x* = 20
(3)
Em que C é o custo total, dY0 é a densidade média de predadores a serem lançados
inicialmente, dY1 é a densidade de predadores a serem lançados a cada tempo dT, após o número
de presas começar a ultrapassar x*, que é o valor tolerável da densidade de presas na lavoura. TF
é o tempo total em que se deseja minimizar o custo do controle.
A idéia é acrescentar um número inicial de predadores de forma a atingir o valor objetivo
de pragas e, quando esse valor começar a passar do valor de controle deve-se acrescentar mais
predadores de forma a estabelecer um ciclo a cada intervalo de tempo.
Para solucionar o problema utilizou-se a idéia de otimização dinâmica, em que se deve
XXXVIII SBPO
[ 51 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
verificar, a cada estágio, quais são os valores ótimos que nos permitirão otimizar o custo final.
Construiu-se, para isso, um algoritmo genético (AG) que executa as seguintes ações:
• Primeiro define-se qual o limite inferior do espaço de busca para a população de
predadores que garantirá que a densidade de presas atinja o objetivo depois de certo
tempo. Para isso, utilizou-se a técnica da bisseção.
• O limite superior do espaço de busca do número de predadores por unidade de área foi
definido como a metade do valor da densidade inicial de presas.
• Com isso, executam-se as gerações do AG, em que para cada solução-tentativa (número
de predadores) extraem-se os valores dY1 e dT conforme a equação (3) e a figura 2. Daí
avalia-se tais soluções-tentativas.
• Com o passar das gerações do AG, obtém-se a solução que produzirá o menor custo para
se executar o controle.
Figura 2: Extraindo informações do indivíduo
O algoritmo genético, com adequabilidade quadrático [Silva et al. (2006)] e seleção
através do resto estocástico, foi executado para 100 gerações, com uma população de 50
indivíduos, taxa de combinação de 0,7 e de mutação 0,1. O número de presas por área foi 100 e o
tempo total de 200. Assim o custo para cada solução-tentativa da população, conforme a fórmula
(3) será:
Min C = dY0 + dY1.200/dT
Sujeito a:
{x(TF)<= x* = 20
(4)
XXXVIII SBPO
[ 52 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
O limite inferior para a densidade de predadores foi de 16,7088 e o limite inferior foi de
50.
Após a primeira geração do genético a melhor solução-tentativa obteve um
comportamento apresentado na figura 3.
Figura 3: Comportamento do melhor indivíduo na primeira geração
Após a última geração obteve-se o número médio de predadores por área a ser lançado
inicialmente e posteriormente a cada intervalo de tempo para um menor custo. Os resultados
finais foram:
• Número médio de predadores inicial a ser lançado (dY0): 16,7101.
• Número médio de predadores a serem lançados posteriormente a cada intervalo de tempo
(dY1): 0,1844.
• Intervalo de tempo (dT): 0,2000.
• Custo total minimizado: C = 16,710076 + 0,184441.200/0,200040 = 201,1138
• O tempo em que se atingiu a meta inicialmente foi de 10,8822 e a partir do tempo de
11,0822 foi iniciado o controle por ciclos.
Os gráficos que representam o resultado final se encontram logo abaixo, nas figuras 4, 5
e 6, em que se observa o pequeno intervalo de tempo para o ciclo. Ou melhor, o ciclo proposto
nesse método é tão pequeno que quase não é observado nas figuras 4, 5 e 6.
XXXVIII SBPO
[ 53 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Figura 4: Ciclo de menor custo encontrado
Figura 5: Detalhe do ciclo de menor custo encontrado
XXXVIII SBPO
[ 54 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Figura 6: Presa e predador por tempo com menor custo
Conclui-se que o menor custo obtido para se executar o controle ainda possui um
intervalo de tempo ainda pequeno, mas já é um pouco mais viável, com relação à aplicabilidade.
A próxima sessão soluciona o problema inserindo uma restrição de tempo mínimo em que o
produtor deseja executar o controle de pragas, dessa forma minimizando o custo a um intervalo
de no mínimo dT.
4. Controle Dinâmico Por Estágios Com Restrição de Tempo
Para facilitar o controle da praga, com a inserção de uma ação de controle mais espaçada,
o algoritmo genético da sessão anterior foi adaptado para selecionar o melhor controle com a
restrição da densidade de pragas ficar abaixo do nível tolerado x* e o tempo de controle ficar
acima de um determinado valor dT. Logo a equação (3) ficará:
Min C = dY0 + dY1.TF/dT
Sujeito a:
{ x(TF)<= x* = 20
{dT >= dTMin
(5)
O algoritmo genético com adequabilidade quadrática [Silva et al. (2006)] e seleção
através do resto estocástico, foi executado para 100 gerações, com uma população de 50
soluções-tentativas, taxa de combinação de 0,7 e de mutação 0,1. A restrição de tempo mínimo
foi de dTMin>=8. O número inicial de presas por área foi 100 e o horizonte de tempo de 200.
O limite inferior para a população de predadores foi de 18.6080 e o limite inferior foi de
50.
XXXVIII SBPO
[ 55 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Após a última geração obtiveram-se os seguintes resultados:
• Número médio de predadores inicial a ser lançado (dY0): 18.6425.
• Número médio de predadores a serem lançados posteriormente a cada intervalo de tempo
(dY1): 7.8399.
• Intervalo de tempo (dT): 8.0416.
• Custo total minimizado: C = 18.642466 + 7.839852 * 200/8.041608 = 213.6247
• O tempo em que se atingiu a meta inicialmente foi de 7.2414 e a partir do tempo de
15.2831 foi iniciado o controle por ciclos.
O gráfico que representa o resultado final se encontra logo abaixo, na figura 7, em que se
observa o intervalo de tempo bem definido para o ciclo:
Figura 7: Ciclo de menor custo encontrado
Conclui-se que o menor custo obtido para se executar o controle é um pouco maior do
que o encontrado anteriormente, mas com certeza é mais viável devido ao maior intervalo de
tempo para executar o controle das pragas na lavoura. Se o tempo considerado for medido em
dias, esta ação de controle deveria se feita de 8 em 8 dias, em vez de “continuamente” no tempo.
5. Controle Dinâmico Por Estágios Com Tempo Fixo
A idéia principal da terceira proposta de minimizar o custo do controle de pragas é
executar a liberação de predadores a cada intervalo de tempo fixo pré-definido. Ou seja,
dividindo-se o tempo total em n estágios, a cada estágio i deve-se liberar certa quantidade de
predadores na lavoura (n e i são inteiros, sendo que 1<=i<=n) de forma a se executar o controle,
deixando a densidade de pragas abaixo do nível tolerável.
Esta proposta para a solução do problema se enquadra dentro dos métodos de
programação dinâmica apresentados em [Cardoso (2005)]. Essa metodologia propõe verificar, a
XXXVIII SBPO
[ 56 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
cada estágio, quais são os valores ótimos para cada ação de controle sem listar todos os estados
possíveis.
Como desejamos minimizar o número de predadores lançados na lavoura e desejamos
minimizar também a quantidade de presas, vamos otimizar a seguinte função objetivo:
n
Min C =
∑ x(i) + y(i)
i =1
Sujeito a:
{ x(TF) <= x* = 20
(6)
Deseja-se que o custo seja o menor possível e que o prejuízo seja o mínimo também. O
método de otimização usado nessa sessão possui um resultado imediato, de forma que o nível de
pragas se normaliza já no primeiro estágio e que o prejuízo com as pragas na lavoura se torna
muito pequeno. Porém, apesar do eficiente resultado, o custo é um pouco mais alto que os dos
métodos apresentados anteriormente.
O algoritmo genético para solucionar o problema consiste em validar e avaliar as
soluções-tentativas (vetor de n coordenadas em que o valor da i–ésima posição representa a
densidade de predadores a serem liberados no estágio i) de forma a executar o controle a um
menor custo.
O algoritmo genético aqui proposto executa as seguintes ações:
• Geram-se as soluções-tentativas.
• Nas gerações, validam-se as soluções-tentativas ao avaliá-las, de forma que são
aniquiladas as que não satisfazem a restrição, gerando outras factíveis no lugar.
• As soluções-tentativas mais adequadas são selecionadas.
• No final, a melhor solução indicará o controle mais barato que garante a eficiência no
controle.
O algoritmo genético, com adequabilidade quadrática [Silva et al. (2006)] e seleção
através do resto estocástico, foi executado para 100 gerações, com uma população de 50
soluções-tentativas, taxa de combinação de 0,7 e de mutação 0,1. O número de presas por área foi
100 e o tempo total de 200. O intervalo de tempo para cada estágio foi de dT=20 (N=10 estágios).
Após a última geração obtiveram-se os seguintes resultados:
• Vetor de predadores a serem lançados nos estágios:
Estágio
Predadores
1
37.5905
2
38.9511
3
29.4099
4
34.0585
5
20.7752
6
36.5059
7
17.6515
8
39.4529
9
30.4671
10
5.9702
Tabela 4: Vetor de predadores ótimo
•
•
Intervalo de tempo (dT): 20.
Custo total minimizado: C = 290.8328
O gráfico que representa o resultado final se encontra logo abaixo, na figura 8, em que se
observa o intervalo de tempo bem definido para o ciclo:
XXXVIII SBPO
[ 57 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Figura 8: Presa e predador por tempo com menor custo
O método empregado nesta sessão é mais fácil de ser aplicado nas lavouras, sendo que os
resultados são muito úteis para melhorar a produtividade e reduzir os custos com as perdas
devido a pragas. Pode-se concluir, conforme os resultados obtidos e pela análise dos gráficos, que
o prejuízo foi o mínimo dentre os métodos, já que no primeiro estágio o nível de pragas já fica
abaixo do nível tolerável. Porém o custo desse controle foi o mais alto.
6. Conclusões
O presente trabalho propõe novas abordagens para o problema do Controle Biológico de
Pragas numa Lavoura. A primeira abordagem (seções 3 e 4) propõe a otimização em dois
estágios: levar o nível de pragas até um nível tolerável e depois manter um controle em ciclos.
Esta é uma opção mais barata, porém há prejuízos durante o tempo em que a densidade das pestes
ainda não atingiu o nível tolerável. Na seção 3, o ciclo tem um tamanho ótimo, mas de duração
muito pequena, difícil de ser implementada na prática. Na seção 4, o ciclo tem um tamanho prédefinido. A segunda abordagem (seção 5) propõe um resultado imediato. Esta opção é um pouco
mais custosa, porém o prejuízo com as pragas é mínimo.
A proposta para trabalhos futuros é considerar uma abordagem multiobjetivo, onde se
deseja minimizar tanto a quantidade de pragas na lavoura quanto a quantidade de predadores
lançados na lavoura, de modo a encontrar um conjunto de soluções de compromisso, o chamado
conjunto Pareto-ótimo [Takahashi et al. (2003)].
Referências Bibliográficas
1. Cardoso, R. T. N., Algoritmos para programação dinâmica baseados em famílias
invariantes. Dissertação de mestrado, Departamento de Matemática, Universidade
XXXVIII SBPO
[ 58 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Federal de Minas Gerais, 2005.
2. Dent, D., Ed., Integrated Pest Management, pp. 356, Chapman and Hall, London, NY
UK.
3. P. DeBach, The scope of biological control, in: “Biological Control of Insects Pests and
Weeds” (P. DeBach Ed.), pp.3-20, Chapman & Hall, London, U.K., 1964.
4. Takahashi, R. H. C., Vasconselos, J. A., Ramirez, J. A., and Krahenbuhl, L., “A
Multiobjetive Methodology for Evaluating Genetic Operators”. IEEE Transactions on
Magnetics, 39(3):1321-1324, 2003.
5. Rafikov, M., Feltrin, C.C., Aplicação da Função de Lyapunov num Problema de Controle
Ótimo de Pragas, em “Tendências em Matemática Computacional e Aplicada”, 3, No. 2
(2002), 83-92. Uma Publicação da Sociedade Brasileira de Matemática Aplicada e
Computacional.
6. Silva, V.L.S., Cruz, A.R., Carrano, E.G, Takahashi, R.H.C., Guimarães, F., “On
Nonlinear Fitness Functions for Ranking-Based Selection”, IEEE World Congress
on Computational Intelligence, 2006.
XXXVIII SBPO
[ 59 ]
Download

UMA ABORDAGEM VIA PROGRAMAÇÃO DINÂMICA NÃO