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 ]