ANÁLISE DO USO DE FERRAMENTAS BIO-INSPIRADAS DE OTIMIZAÇÃO NO ÂMBITO DO PROBLEMA DE PREVISÃO DE

VAZÕES COM ESTRUTURAS LINEARES GERAIS

HUGO VALADARES SIQUEIRA Faculdade de Engenharia Elétrica e de Computação (FEEC)

Universidade Estadual de Campinas (UNICAMP) Avenida Albert Einstein, 400, Campinas – SP – Brasil, CEP 13083-970

hugo@densis.fee.unicamp.br

ROMIS RIBEIRO DE FAISSOL ATTUX Faculdade de Engenharia Elétrica e de Computação (FEEC)

Universidade Estadual de Campinas (UNICAMP) Avenida Albert Einstein, 400, Campinas – SP – Brasil, CEP 13083-970

attux@dca.fee.unicamp.br

CHRISTIANO LYRA FILHO

Faculdade de Engenharia Elétrica e de Computação (FEEC) Universidade Estadual de Campinas (UNICAMP)

Avenida Albert Einstein, 400, Campinas – SP – Brasil, CEP 13083-970 chrlyra@densis.fee.unicamp.br

RESUMO

O planejamento da utilização dos recursos hidrológicos necessários à obtenção de energia elétrica é dependente da previsão de vazões. Estruturas lineares são bastante utilizadas nesse contexto, sobretudo filtros com resposta ao impulso finita. Não obstante, o projeto de um preditor linear geral exige que sejam contempladas também estruturas com resposta ao impulso infinita, as quais, no entanto, requerem um processo de otimização significativamente mais complexo. Neste trabalho, realizou-se uma análise comparativa de três ferramentas bio-inspiradas capazes de conduzir tal processo: um algoritmo genético, um sistema imunológico artificial e uma proposta híbrida. Os resultados obtidos permitem que sejam identificados elementos analíticos vinculados a desempenho e custo computacional que indicam a relevância de fatores como manutenção de diversidade e pressão seletiva e que também ilustram o potencial de aproximação trazido pela estrutura recorrente.

PALAVARAS CHAVE. Previsão linear de vazões, computação natural, filtros IIR.

ABSTRACT The planning of the use of water resources necessary to obtain eletric power depends on the forecast of seazonal streamflow. Linear techniques are largely employed in this context, particularly finite impulse response filters. The project of a general linear predictor, notwithstanding, requires that infinite impulse response structures be taken into account, which, however, gives rise to a significantly more complex optimization process. In this work, was performed a comparative analysis of three bio-inspired tools that are capable of conducting such process: a genetic algorithm, an artificial immune system and a hybrid proposal. The obtained results allow the identification of analytical elements related to performance and computational cost that indicate the relevance of factors like population diversity and selective pressure and illustrate the approximation potential associated with the recurrent structure. KEYWORDS. Linear prediction of streamflow series, natural computing, IIR filters.

2721

1. Introdução

O parque gerador brasileiro é predominantemente hidráulico. Dessa forma, gerir os recursos hídricos de uma maneira sistemática é essencial, e boas metodologias devem ser empregadas na previsão de séries de vazões de usinas hidrelétricas. Embora haja vários dispositivos de processamento aplicáveis a tal problema, parece justificado considerar bastante usual a abordagem que se baseia no uso de estruturas lineares. Essa abordagem é caracterizada por um grau de tratabilidade matemática que, tanto do ponto de vista analítico quanto em termos de projeto, é maior que aquele associado a mapeadores não-lineares.

A tarefa de estabelecer uma metodologia geral de projeto de dispositivos de previsão lineares exige que se contemplem estruturas com laços de realimentação, as quais impõem algumas dificuldades em termos de projeto (Shynk, 1989): 1) a impossibilidade de obter soluções fechadas de modo direto por meio das equações de Wiener-Hopf ou de Yule-Walker (Haykin, 1997); 2) a existência de dificuldades para obtenção das derivadas de uma função custo baseada em uma medida de erro quadrático médio; 3) o caráter potencialmente multimodal da função de erro quadrático médio; 4) a possibilidade de que, num processo iterativo de escolha de parâmetros, alcance-se uma configuração instável, o que inviabilizaria a convergência do método.

É importante notar que essas dificuldades podem ser contornadas caso se disponha de técnicas de otimização que sejam dotadas de um significativo potencial de busca global, que não requeiram manipulações da função custo de erro quadrático médio e que tenham um caráter populacional (que leva a uma maior robustez ao aparecimento de más soluções). Dentre as técnicas que atendem a esses requisitos, selecionou-se, neste trabalho, a classe das ferramentas bio-inspiradas de otimização (Castro, 2006). Dois membros representativos dessa classe serão analisados no âmbito do problema de projeto de um preditor linear genérico: algoritmos genéticos (Holland, 1992) e sistemas imunológicos artificiais (Castro e Timmis, 2002). A análise contemplará diversos aspectos de implementação dos algoritmos e buscará sempre estabelecer bases para uma efetiva comparação à luz das características do problema abordado, tendo sempre em mente o risco de generalizações incoerentes com o espírito dos teoremas no free lunch (Wolpert e Macready, 1997). Ademais, também será estabelecida uma metodologia híbrida para buscar o aproveitamento de características desejáveis das duas abordagens tratadas. Em todos os ensaios, as metodologias serão aplicadas a problemas de previsão de uma série de vazões da usina de FURNAS, um problema de grande relevância prática para a comunidade brasileira.

Este artigo está organizado da seguinte maneira: na Seção 2, será tratado o problema de previsão aplicado a série de vazões, a Seção 3, por sua vez, descreve a ferramentas de busca dos parâmetros do filtro: os algoritmos genético, imunológico e genético híbrido. A Seção 4 contém os resultados computacionais obtidos e sua análise e a Seção 5 apresenta as conclusões. 2. Descrição do Problema 2.1 - O Problema de Previsão com Modelos Lineares

O estudo de séries temporais se vincula intimamente à idéia de prever valores futuros de

um processo estacionário. A previsão se dá por meio do processamento de valores passados da série de modo a produzir uma estimativa de seu valor P passos à frente. Para que essa idéia tome forma, é preciso escolher um modelo de previsão adequado e também ajustar satisfatoriamente seus parâmetros livres. Uma escolha bastante imediata em termos de tratabilidade é lançar mão de um modelo linear (Oppenheim et al., 1996) e promover o ajuste de seus parâmetros por meio de um critério de mínimo erro quadrático médio de previsão.

Tendo em vista a discussão pregressa, o erro de previsão é definido como:

)(ˆ)()( PnxPnxne +−+= , (1)

2722

sendo x(n+P) o valor da série no instante n+P e )(ˆ Pnx + o valor fornecido pelo modelo tendo por base o valor x(n) e, eventualmente, valores anteriores da série. No contexto de um modelo linear geral (Haykin, 1997), temos:

∑∞

=

−=0

)()(ˆk

k knxwnx (2)

A equação (2) leva à função de transferência genérica do preditor:

RR

MM

zbzbzbzazazaazW −−−

−−−

−−−−++++

=...1...)( 2

21

1

22

110 (3)

Os coeficientes ai , relativos a ponderações de atrasos da entrada do preditor, definem os zeros da função de transferência. Os coeficientes bi, relativos à ponderação de versões atrasadas da saída do preditor, definem os pólos da mesma função. Observa-se um caso particular importante quando se considera que o filtro tem resposta ao impulso finita (isto é, não conta com realimentação). Nesse caso, b1 = b2 =...= bR = 0, e a informação relevante acerca da função de transferência do filtro passa a estar apenas nos zeros. 2.2 A Escolha dos Coeficientes

Para que o preditor linear opere de maneira apropriada, é necessário escolher adequadamente os valores dos coeficientes mostrados na equação (3). Uma maneira de fazê-lo é estabelecer uma medida de erro quadrático médio de predição e procurar os coeficientes que minimizem tal medida, ou seja, o problema pode ser formulado como sendo o de encontrar o conjunto de parâmetros ai, i = 1,...,M e bi, i=1,...,R tal que a seguinte função custo seja minimizada:

)]([ 2 neEJw = (4)

sendo E[.] o operador de esperança matemática. Tal abordagem é a essência do critério de Wiener de filtragem ótima (Haykin, 1997).

Se o filtro tiver resposta ao impulso finita, é possível mostrar que a solução que minimiza a função custo descrita em (4) é dada por:

rR 1−=w (5)

sendo R a matriz de autocorrelação das entradas do filtro, dada por

−−

−−

=

)0(...)2()1(.........

)2(...)0()1()1(...)1()0(

rMrMr

MrrrMrrr

R ,

e r o vetor de correlação cruzada entre o sinal desejado (no caso, x(n+P)) e as entradas, dado por

+

+=

)(...

)1()(

MPr

PrPr

r .

Essa solução, denominada solução de Wiener, é também a solução das equações de Yule-Walker (tipicamente para P = 1), o que mostra o vínculo conceitual entre um preditor linear com resposta

2723

ao impulso finita e um modelo auto-regressivo (AR) da série temporal em questão (Haykin, 1997). Caso o filtro não tenha resposta ao impulso finita, ou seja, caso os coeficientes associados às realimentações não sejam nulos, o projeto do filtro ótimo se torna mais complicado: é possível que haja mínimos locais, por exemplo, e mesmo a obtenção de derivadas passa a ser uma dificuldade (Shynk, 1989). Em geral, também passa a existir o risco de que se atinjam configurações de coeficientes que levem o filtro a ser instável. Interessantemente, ferramentas de computação evolutiva permitem que se lide com todos esses aspectos de modo promissor devido a algumas características suas: elas possuem potencial de busca global, não requerem manipulações da função custo e, devido a seu caráter populacional, não são inviabilizadas pela eventual presença de soluções correspondentes a filtros instáveis (Attux et al., 2003). É importante frisar que não apenas ferramentas evolutivas podem ser aplicadas no problema: trata-se de uma delimitação de escopo investigativo.

Neste trabalho, foram escolhidos dois paradigmas de otimização evolutiva para que se estabelecessem elementos de uma análise comparativa no âmbito do problema exposto: algoritmos genéticos (AGs) (Holland, 1992) e sistemas imunológicos artificiais (SIAs) (Castro e Timmis, 2002). Também foi considerada uma versão híbrida de ambos de modo a buscar uma combinação de características desejáveis.

3. Ferramentas Evolutivas de Otimização: Algoritmos Genéticos, Sistemas Imunológicos Artificiais e uma Proposta Híbrida 3.1 Algoritmos Genéticos

Algoritmos genéticos (AGs) são técnicas de otimização baseadas em conceitos derivados da moderna teoria da evolução das espécies (Holland, 1992)(Von Zuben, 2000). A essência dessas técnicas é considerar cada solução do problema tratado como sendo um indivíduo cujo genótipo se vincula a uma codificação dos parâmetros livres e cujo grau de adaptação ao ambiente é expresso por meio de uma função de fitness que se relaciona intimamente à função a ser otimizada. A interação entre a função de fitness e um conjunto de operadores leva a uma modificação genotípica que corresponde à exploração do espaço de busca subjacente ao problema tratado.

Em termos simples, o algoritmo genético empregado utiliza a estrutura geral descrita por Michalewicz (1996) aliada a um procedimento de busca local. A busca atua da seguinte forma: após um determinado número de gerações, o melhor indivíduo tem um valor pseudo-aleatório gaussiano delta somado ao primeiro de seus genes, ou, no caso deste trabalho, ao valor do primeiro parâmetro do filtro. Após isso, o fitness dele é medido e, caso tal perturbação tenha originado um melhor resultado, novamente esse valor será somado e o indivíduo reavaliado até que melhorias não aconteçam. Caso, na primeira tentativa, o fitness decresça, o valor pseudo-aleatório é subtraído do gene, e o processo é essencialmente repetido. Por fim, o mecanismo como um todo atua seqüencialmente em todos os genes.

Para dar uma idéia mais clara do algoritmo adotado, apresentamos a seguir a sua estrutura geral:

Inicialização - Escolha os parâmetros do algoritmo e inicialize aleatoriamente os (Npop) indivíduos da população. Processo Iterativo

- Enquanto um número máximo de iterações ou gerações (gen) não for atingido, faça:

1- Mantenha uma população de potenciais soluções (cromossomos);

2724

2- Aplique alterações na população, por meio de crossover e mutação, para formar novas soluções potenciais; 3- Avalie cada solução e produza uma medida de sua adaptação, ou fitness; 4- Selecione Npop indivíduos da população total; 5- A cada k iterações, aplique o mecanismo de busca local no melhor indivíduo.

Para que o algoritmo se torne uma ferramenta aplicável, é necessário definir alguns aspectos (Von Zuben, 2000):

• uma representação genotípica para as soluções candidatas (processo de codificação); • uma função de avaliação ou fitness que quantifica o grau de influência do ambiente sobre

os indivíduos e sua adaptação a ele (ou seja, sua capacidade de resolver o problema); • operadores genéticos responsáveis pela modificação e seleção dos indivíduos; • valores adequados para os diversos parâmetros relevantes (tamanho da população,

probabilidades de aplicação dos operadores genéticos etc.).

Neste trabalho, a partir de uma análise inicial do problema de predição linear e de ensaios preliminares, foram realizadas as seguintes opções no que se refere ao AG: codificação real (valores entre -1 e +1), crossover de um ponto (Michalewicz, 1996), mutação gaussiana dinâmica (Queiroz, 2005) com taxa de ocorrência dada por

−−=

fffRDMR '1(%) max

, (6)

sendo Rmax o valor máximo permitido de taxa de mutação e f e 'f os valores médio e máximo de fitness, respectivamente, e seleção por meio do algoritmo roulette wheel (ou roleta) (Castro, 2006). Testes foram feitos com crossover aritmético e um método de seleção por torneio no qual dois indivíduos da população são sorteados e o de melhor fitness é selecionado, até que todos os indivíduos tenham participado da competição. Todavia os resultados obtidos foram favoráveis (em termos de erro quadrático médio) às opções aqui relatadas. A medida de custo (ou fitness) é dada por:

)ˆ1(1

wfit J

J+

= (7)

onde wJ é uma estimativa da função custo de Wiener baseada numa média amostral:

∑=

+−+=N

1t

2w ))Pn(x)Pn(x(

N1)J(EQM (8)

O mapeamento descrito em (7) é imposto com o fim de transformar o problema de minimização do erro quadrático médio de predição num problema de maximização, mais adequado ao emprego da abordagem evolutiva. 3.2 Sistemas Imunológicos Artificiais

Os sistemas imunológicos artificiais (SIAs) são algoritmos computacionais inspirados em teorias acerca do modus operandi dos mecanismos de defesa contra antígenos dos organismos superiores (Castro, 2006). Tais algoritmos são hoje aplicados na solução de diversos problemas de Engenharia (Castro e Timmis, 2002) e constituem uma importante área da Computação Evolutiva.

O algoritmo imunológico utilizado neste trabalho faz uso de algumas associações para estabelecer uma relação entre uma tarefa de otimização genérica e o processo biológico de reconhecimento de um antígeno. A associação fundamental é que uma possível solução do

2725

problema analisado, um vetor de parâmetros reais, equivale a um anticorpo cuja afinidade com o antígeno genérico é dada pela função custo ou função de fitness. Na técnica aplicada, a adaptação dos anticorpos se dá basicamente por meio de uma implementação do chamado princípio da seleção clonal (Castro e Von Zuben, 2002).

Segundo este princípio, quando há o reconhecimento de um antígeno, a célula de defesa tende a produzir clones de si mesma, os quais estão sujeitos a um processo de mutação proporcional à afinidade anticorpo-antígeno (Castro e Timmis, 2002). Esse princípio indica que tem lugar no sistema imunológico um processo evolutivo em escala microscópica, o qual se baseia principalmente na combinação entre mudanças espúrias e numa pressão seletiva. Esse processo é complementado por outros mecanismos, dentre os quais tem destaque a edição de receptores (Castro e Timmis, 2002), que se vincula à introdução de material novo na população de células de defesa. O esquema a seguir mostra o funcionamento da técnica utilizada neste trabalho:

Inicialização - Escolha os parâmetros do algoritmo e inicialize aleatoriamente os indivíduos da população. Processo Iterativo - Enquanto um número máximo de iterações ou gerações (gen) não for atingido, faça:

1- Calcule o custo (fitness) de todos os indivíduos da população. 2- A cada Nit iterações, inclua Nind soluções geradas aleatoriamente no lugar dos Nind indivíduos com menor fitness. 3- Produza Nc cópias de cada indivíduo. 4- Aplique um processo de mutação a cada uma dessas cópias (clones), mantendo, no entanto, o indivíduo original inalterado. A mutação é proporcional ao custo e segue as duas equações a seguir:

c´ = c + αN(0,1) α = (1/β)exp(-f),

sendo β um parâmetro regulador da amplitude de mutação e f o valor de fitness do clone c. 5- Determine o valor do custo dos novos indivíduos e, de cada grupo formado pelos clones e pelo indivíduo original, mantenha apenas a melhor solução.

O algoritmo descrito combina mecanismos de busca local (binômio clonagem / mutação)

e de introdução de diversidade que, conseqüentemente, aumentam o potencial de busca global da ferramenta (inserção periódica de novos indivíduos). Essa idéia corresponde, em sua essência, a uma modificação da proposta de (Castro e Von Zuben, 2002) no sentido de empregar codificação real. A medida de fitness e a função custo são exatamente as mostradas nas equações (7) e (8). Novamente, o mapeamento descrito em (7) faz com que o problema seja de maximização. 3.3 Algoritmo Genético Híbrido

A hibridização proposta neste trabalho é baseada na idéia de clonagem e mutação presente no algoritmo imunológico descrito no item 3.2. Nessa abordagem, cromossomos idênticos são gerados na população selecionada e pequenas modificações com valores gaussianos são acrescentadas às estruturas dos clones. Após isso, uma nova seleção é feita e os indivíduos de melhor fitness passam a ser os componentes da população de cromossomos. Esse mecanismo atua como um método de busca local eficiente e adicionalmente abre a perspectiva de que um elemento estocástico a mais de busca global seja incorporado ao AG. O mecanismo também incorpora o esquema de busca fundamental do SIA ao AG, de modo a realizar uma combinação de propriedades desejáveis de ambas as ferramentas.

No pseudocódigo do item 3.1, o mecanismo corresponde ao acréscimo de outra linha de comando ao laço principal (para detalhes do processo, vide a seção anterior):

2726

6- clone os indivíduos da população, some valores gaussianos aos clones, reavalie e selecione os melhores que cada clonagem proporcionou. Caso a clonagem não tenha ocasionado melhoras, continue com o indivíduo original.

4. Estudo de Casos 4.1 Pré-Processamento dos Dados de Entrada

Séries de vazões possuem uma componente marcadamente sazonal, a qual demanda um tratamento anterior ao processo de predição em si. Neste trabalho, será realizado um pré-processamento baseado na metodologia proposta por Ballini (2000) para que essa componente seja excluída do processo de predição. As observações da série temporal x(n) como um todo são transformadas em observações padronizadas z(n):

)()()()(

nnnxnz

σµ−

= (9)

onde µ(n) é a média adequada a cada mês e σ(n) o desvio padrão respectivo. A nova série z(n) tem média aproximadamente nula e desvio padrão unitário. Os valores µ(n) e σ(n) são calculados através de estimativas baseadas em médias amostrais:

∑=

=N

tnx

Nn

1)(1)(µ (10)

∑=

−=N

t

nnxN

n1

2))()((1)( µσ (11)

Dessa forma, as técnicas de previsão são aplicadas a dois conjuntos da série z(n), que será chamada de série padronizada (Ballini, 2000): um de treinamento e um de teste. Como cada conjunto individualmente não tem necessariamente média nula, é preciso incluir uma etapa adicional de remoção de offset de cada trecho. Ao final do processo, a componente sazonal é reintroduzida para análise de erro médio quadrático. 4.2. Resultados

No trabalho, utilizou-se a série de vazões médias mensais da usina hidrelétrica de FURNAS, localizada no Rio Grande. A base de dados pode ser obtida na página web da ELETROBRÁS (www.eletrobras.gov.br), que mostra as vazões médias entre os anos 1931 e 2005. A fase de treinamento para previsão escolhida foi de 1947 a 1951, e a de testes, de 1952 a 1956, em consonância com estudos prévios acerca da série (Ballini, 2000). As configurações do algoritmo genético, do sistema imunológico e do algoritmo genético híbrido estão nas Tabelas 1, 2 e 3, respectivamente. É importante ressaltar que todos os parâmetros foram escolhidos de modo a estabelecer bases satisfatórias de comparação, tendo em vista a estrutura de cada método e uma série de testes preliminares. Também é importante frisar que, para que fosse possível ter uma referência de desempenho, foi utilizado também o modelo auto-regressivo (AR) padrão, ou seja, o clássico preditor linear sem pólos.

Inicialmente, a série foi padronizada de acordo com o descrito no item 4.1. Os dados de treinamento foram utilizados na construção da função custo estimada de Wiener, e o processo adaptativo de escolha de pesos para o filtro linear de resposta ao impulso infinita – com dois coeficientes na parte forward e dois pólos – foi, para cenários de previsão com P = 1, 3, 6 e 12 passos à frente (note que o aumento do número de passos à frente leva a uma redução do número de amostras efetivamente empregáveis), realizado com os três algoritmos descritos.

2727

Paralelamente, calcularam-se os coeficientes do modelo de resposta ao impulso finita com o mesmo número de zeros através das equações de Yule-Walker.

Número inicial de indivíduos (Nind) 20 Número de filhos gerados por crossover 20 Regulador de amplitude de mutação (β) 50 Taxa percentual de mutação 20 Taxa percentual de mutação (hibridização) 10 Periodicidade de uso da busca local (k) 50 Delta da busca local 0.01

Tabela 1 – Configurações do algoritmo genético com busca local

Número inicial de indivíduos (Nind) 10 Número de clones (Nc) 5 Regulador de amplitude de mutação (β) 50 Número de indivíduos reinseridos 3 Periodicidade de reinserções (Nit) 20

Tabela 2 – Configurações do algoritmo imunológico

Número inicial de indivíduos (Nind) 20 Número de filhos gerados por crossover 20 Taxa percentual de mutação 20 Regulador de amplitude de mutação (β) 50 Número de clones (hibridização) 5 Taxa percentual de mutação (hibridização) 10 Periodicidade de uso da busca local (k) 50 Delta da busca local 0.01

Tabela 3 – Configurações do algoritmo genético híbrido

Os resultados das previsões estão sumarizados nas tabelas 4 e 5, que trazem a média dos valores de erro quadrático médio de treinamento e de teste para 10 simulações. A tabela 6 apresenta o número de vezes que cada método precisou chamar a função de fitness durante todo o processo de previsão (treinamento e teste). A inclusão do número de chamadas do custo tem o fim de prover meios para que se forme uma idéia do custo computacional de cada método.

TREINAMENTO

Passos AR x(104) IMUNO x(104) GENETICO x(104) HIBRIDO x(104) 1 10.614 10.271 10.703 10.706 3 6.4237 5.6027 6.1633 6.4099 6 5.8917 4.6975 5.4248 4.6880 12 6.0070 5.3342 5.7483 5.3485

Tabela 4 – Valores de erro médio quadrático dos modelos estudados na fase de treinamento

TESTE Passos AR x(104) IMUNO x(104) GENETICO x(104) HIBRIDO x(104)

1 5.2580 5.2120 5.2090 5.2099 3 3.8153 3.4607 3.7546 3.8768 6 3.3023 2.3511 2.8442 2.3496 12 3.7063 2.7026 3.2788 2.8793

Tabela 5 – Valores de erro médio quadrático dos modelos estudados na fase de testes

Passos IMUNO GENETICO HIBRIDO 1 11001 5205 25191 3 11001 5235 25192 6 11001 5191 25242 12 11001 5219 25203

média 11001 5212 25207 Tabela 6 – número de vezes que a função de fitness foi chamada

2728

Uma primeira conclusão extraída das tabelas é que o modelo AR tem um desempenho equivalente ou inferior ao do preditor linear genérico, o que é esperado tendo em vista a sua impossibilidade de contar com a informação adicional trazida pela realimentação. O desempenho do modelo AR também mostra que o preditor genérico é particularmente relevante para um número elevado de passos à frente, o que pode ser interpretado como uma conseqüência da capacidade de “memória” trazida pela presença de feedback. Dentre os métodos evolutivos empregados, de certa forma, o algoritmo imunológico foi o que apresentou o melhor desempenho geral nos testes conduzidos. O método híbrido foi capaz de melhorar o desempenho geral do AG, mas não obteve, em alguns casos, um desempenho comparável ao do SIA: isso pode ser interpretado como sendo uma conseqüência de a busca local ser limitada por uma menor diversidade trazida pela atuação do algoritmo genético. No caso do SIA, o mecanismo de clonagem atua no material aleatório da população inicial, e, num modus operandi que faz lembrar o dos métodos de niching, evita-se uma competição que envolva todos os indivíduos. Ademais, a inserção periódica de novos indivíduos é responsável por trazer à cena material novo, o que aumenta o potencial de exploração do espaço de busca.

As medidas de desempenho devem ser avaliadas tendo em vista também o número de chamadas da função de fitness: nesse quesito, o AG se mostrou o método mais parcimonioso, enquanto o método híbrido foi o mais dispendioso. O SIA teve uma exigência intermediária, a qual o credencia como um candidato interessante em termos do compromisso “custo-desempenho”. Para concluir essa etapa da análise, observa-se, na figura 1, os gráficos dos valores de erro quadrático médio de teste obtidos na fase de testes para os quatro modelos (com P=1, 3, 6 e 12), que expõem de forma direta as bases da análise de desempenho realizada. Note que há uma redução no erro quadrático médio obtido para P>1, o que não significa que o problema de predição seja mais simples no domínio da série padronizada: além da influência das componentes sazonais, ainda deve ser levado em conta o fato de que a previsão vários passos à frente leva, no esquema adotado neste trabalho, à análise de um número ligeiramente diferente de amostras em cada caso.

Figura 1 – valores de erro médio quadrático obtidos pelos modelos

Nas Figuras 2 a 5, apresentamos as formas de onda obtidas com o algoritmo com a

melhor resposta para o problema, em cada caso, na fase de testes:

- 1 passo à frente: Algoritmo Genético; - 3 passos à frente: Algoritmo Imunológico; - 6 passos à frente: Algoritmo Genético Híbrido; - 12 passos à frente: Algoritmo Imunológico.

Essas figuras, por mostrarem simultaneamente o comportamento da série real e da série predita, permitem que se tenha uma idéia do potencial associado ao uso do preditor linear genérico para cada valor de P. Por sua vez, as figuras 6 a 9 mostram o comportamento do fitness máximo e do médio da população no decurso do treinamento para cada caso. Essas figuras são uma rica fonte

2729

de conclusões acerca da dinâmica de cada método. Primeiramente, verifica-se, a partir da curva de fitness máximo, que a velocidade de convergência é razoavelmente alta em todos os casos (particularmente nos algoritmos genético e híbrido, que realizam competições envolvendo a população como um todo), ou seja, que a vizinhança de um ótimo local é atingida em, no máximo, 100 iterações. Uma outra constatação interessante: na figura 7, observa-se um aumento no valor do fitness máximo ocorrido próximo à ducentésima iteração, o qual nos permite supor que houve um escape de um mínimo local, ilustrando o potencial de busca global do SIA.

Quando se analisam as distâncias entre as curvas de fitness médio e de fitness máximo em cada caso, verifica-se que o algoritmo genético tende a perder diversidade rapidamente, mesmo com a elevada taxa de mutação adotada, o que o torna mais vulnerável à convergência para soluções subótimas, enquanto o SIA apresenta um grau de diversidade razoável ao longo de todo o processo de busca (note as oscilações que acompanham a inserção periódica de novos indivíduos). O algoritmo híbrido, por sua vez, apresenta um comportamento intermediário nesse quesito, como era esperado. Esses resultados nos levam a concluir que o algoritmo imunológico foi o que se mostrou mais apropriado ao problema em questão dentre as três implementações evolutivas aqui discutidas. Seu bom desempenho pode ser atribuído ao eficiente mecanismo de busca local inspirado no princípio da seleção clonal e ao potencial de manutenção de diversidade trazido pela inexistência de competições envolvendo a população como um todo (o que, como já foi dito, evoca as idéias-chave associadas à noção de niching) e pela constante inserção de novos indivíduos. O método híbrido foi capaz de trazer melhorias em relação ao AG adotado, mas, devido ao processo de perda de diversidade que caracterizou o desempenho do genético, não foi capaz em alguns casos de atingir o desempenho do SIA.

Figura 2 – forma de onda da previsão 1 passo a frente Figura 6 – curva de fitness da previsão 1 passo a frente

Figura 3 – forma de onda da previsão 3 passos a frente Figura 7 – curvas de fitness da previsão 3 passos a frente

2730

Figura 4 – forma de onda da previsão 6 passos a frente Figura 8 – curvas de fitness da previsão 6 passos a frente

Figura 5 – forma de onda da previsão 12 passos a frente Figura 9 – curvas de fitness da previsão 12 passos a frente

5. Conclusões Foram propostas três metodologias para previsão de séries de vazões baseadas num modelo linear geral (de resposta ao impulso infinita) e em algoritmos de otimização bio-inspirados: um algoritmo genético, um sistema imunológico artificial e um algoritmo genético híbrido (que incorpora características do imunológico). Essa metodologia foi aplicada para previsão de uma série de vazões do posto de FURNAS entre os anos de 1947 e 1956. O desempenho dos modelos foi comparado ao de uma abordagem auto-regressiva, largamente utilizada nesse tipo de aplicação.

No que diz respeito ao desempenho do preditor geral em si mesmo, foi possível perceber que a realimentação trouxe um ganho de desempenho particularmente pronunciado para um número razoável de passos à frente, o que nos parece justificado tendo em mente a maior memória do modelo e a perspectiva de que ela seja útil na exploração de algum comportamento de longo prazo ou mesmo sazonal.

No que se refere às técnicas de busca empregadas, que correspondem, de certa forma, ao foco principal deste trabalho, foi possível, tendo em vista o binômio desempenho-custo, verificar que o SIA foi a ferramenta de busca que mais se destacou. A mesma nos parece uma opção bastante viável no âmbito do problema de predição com estruturas recorrentes, por apresentar um equilíbrio interessante entre busca local e busca global que leva a bons níveis de exploração do espaço de busca e de refinamento de soluções obtidas. O algoritmo genético implementado foi bastante comprometido pelo problema de perda de diversidade mesmo com elevadas taxas de mutação, e o algoritmo híbrido, embora tenha alcançado um melhor desempenho, não foi capaz de atingir o grau de performance da técnica imunológica em alguns casos, mesmo com uma maior demanda por avaliações da função de fitness.

Por fim, é importante ressaltar que essas conclusões devem ser analisadas com cautela, tendo sempre em vista as especificidades do problema abordado, das técnicas escolhidas e das

2731

implementações e escolhas de parâmetros. O objetivo foi principalmente chegar a resultados e análises potencialmente úteis àqueles que desejam abordar a tarefa de predição descrita. Também há ainda muitas perspectivas trazidas, por exemplo, pela idéia de analisar o desempenho de técnicas de niching e pela aplicação de estruturas não-lineares e recorrentes.

Agradecimentos Este trabalho contou com o suporte da CAPES e do CNPq. Os autores gostariam também de agradecer ao matemático Eduardo Tadeu Bacalhau e à engenheira Cristina Wada as sugestões e informações.

Referências Bibliográficas Attux, R. R. F., de Castro, L. N., Von Zuben e F. J, Romano, J. M. T. (2003). A Paradigm for Blind IIR Equalization Using the Constant Modulus Criterion and an Artificial Immune Network, IEEE International Workshop on Neural Networks for Signal Processing, Toulouse, França. Ballini, R. (2000). Análise e Previsão de Vazões Utilizando Séries Temporais, Redes Neurais e Redes Neurais Nebulosas, Tese de Doutorado, FEEC-Unicamp, Brasil. de Castro, L. N. (2006). Fundamentals of Natural Computing: Basic Concepts, Algorithms and Application. Chapman & Hall. de Castro, L. N e Von Zuben, F. J. (2002). Learning and Optimization Using the Clonal Selection Principle, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 3, pp. 239-251. de Castro, L. N. e Timmis, J. (2002). Aritificial Imune Systems: a New Computacional Intelligence Approach. Springer. Haykin, S. (1997). Adaptive Filter Theory.Prentice Hall. Holland, J. H. (1992). Adaptation in Natural and Artificial Systems, MIT Press. Michalewicz, Z. (1996), Genetic Algorithms + Data Structures = Evolution Programs, Springer. Oppenheim, A. V., Willsky, A. S. e Nawab, S. H. (1996). Signals and System, Prentice Hall. Shynk, J. J. (1989). Adaptive IIR Filtering, IEEE ASSP Magazine, Vol. 6, No. 2, pp. 4-21. Queiroz, L. M. O. (2005). Algoritmos Genéticos Híbridos para Redução de Perdas Técnicas em Redes Primárias de Distribuição Considerando Variações de Demandas. Dissertação de Mestrado, FEEC-Unicamp, Brasil. Von Zuben, F. J. (2000). Computação Evolutiva: Uma Abordagem Pragmática, Anais da I Jornada de Estudos em Computação de Piracicaba e Região (1a JECOMP), vol. 1, pp. 25. Wolpert, D. H. e Macready, W. G. (1997). No Free Lunch Theorems for Optimization, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 67-82.

2732