AMBIENTE PARA MODELAGEM, PLANEJAMENTO E AVALIAÇÃO
Transcrição
AMBIENTE PARA MODELAGEM, PLANEJAMENTO E AVALIAÇÃO
UNIVERSIDADE FEDERAL DO ESTADO DO RIO DE JANEIRO CENTRO DE CIÊNCIAS EXATAS E TECNOLOGIA PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA AMBIENTE PARA MODELAGEM, PLANEJAMENTO E AVALIAÇÃO DE POLÍTICAS NO MERCADO DE AÇÕES Augusto Cesar Espíndola Baffa Orientador Prof. Angelo Ernani Maia Ciarlini RIO DE JANEIRO, RJ – BRASIL Abril DE 2010 AMBIENTE PARA MODELAGEM, PLANEJAMENTO E AVALIAÇÃO DE POLÍTICAS NO MERCADO DE AÇÕES Augusto Cesar Espíndola Baffa DISSERTAÇÃO APRESENTADA COMO REQUISITO PARCIAL PARA OBTENÇÃO DO TÍTULO DE MESTRE PELO PROGRAMA DE PÓSGRADUAÇÃO EM INFORMÁTICA DA UNIVERSIDADE FEDERAL DO ESTADO DO RIO DE JANEIRO (UNIRIO). APROVADA PELA COMISSÃO EXAMINADORA ABAIXO ASSINADA. Aprovada por: ________________________________________________ Prof. Angelo Ernani Maia Ciarlini, D. Sc. – UNIRIO ________________________________________________ Prof. José de Jesús Pérez Alcázar, D. Sc. – USP ________________________________________________ Prof. Márcio de Oliveira Barros, D. Sc. – UNIRIO ________________________________________________ Prof. Sean Wolfgand Matsui Siqueira, D. Sc. – UNIRIO ________________________________________________ Prof. Antonio Luz Furtado, Ph. D. - PUC-Rio RIO DE JANEIRO, RJ – BRASIL Abril DE 2010 II B143 Baffa, Augusto Cesar Espíndola. Ambiente para modelagem, planejamento e avaliação de políticas no mercado de ações / Augusto Cesar Espíndola Baffa, 2010. xi, 104f. Orientador: Angelo Ernani Maia Ciarlini. Dissertação (Mestrado em Informática) – Universidade Federal do Estado do Rio de Janeiro, Rio de Janeiro, 2010. 1. POMDPs. 2. Inteligência artificial. 3. Planejamento. 4. Investimentos – Análise. 5. Mercado de ações. I. Ciarlini, Angelo Ernani Maia. II. Universidade Federal do Estado do Rio de Janeiro (2003-). Centro de Ciências Exatas e Tecnologia. Curso de Mestrado em Informática. III. Título. CDD – 005.5 III Agradecimentos Aos meus familiares e a minha companheira que me apoiaram nos momentos mais críticos e compreenderam minhas ausências. A todos os amigos e colegas que acompanharam o desenvolvimento deste trabalho, e contribuiram com apoio e sugestões. A Capes pelo fornecimento da bolsa de estudos que me apoiou durante o curso de mestrado. Ao meu orientador Angelo Ciarlini, por toda a dedicação e contribuições durante o processo de pesquisas. IV BAFFA, Augusto Cesar Espíndola. Ambiente para Modelagem, Planejamento e Avaliação de Políticas no Mercado de Ações. UNIRIO, 2010. 104 páginas. Dissertação de Mestrado. Departamento de Informática Aplicada, UNIRIO. RESUMO Analistas e investidores usam ferramentas de análise técnica para criar gráficos e indicadores de preços para ajudá-los em tomadas de decisão. Algumas ferramentas permitem ao usuário especificar os parâmetros e criar macros ou regras de negócio, mas cada pessoa pode ter uma interpretação diferente desses indicadores. Padrões gráficos não são determinísticos e até mesmo os analistas podem ter diferentes interpretações, dependendo por exemplo, da sua experiência, antecedentes, personalidade e estado emocional. Ferramentas que permitam aos usuários formalizar esses conceitos e o estudo de políticas de investimento podem fornecer uma base mais sólida para a tomada de decisão. Neste trabalho, apresentamos uma ferramenta para modelar contextos formalmente, para então, gerar e simular políticas de investimento para o mercado de ações. Os contextos de investimento são modelados como um Processo de Decisão de Markov Parcialmente Observável (POMDP). Em um determinado período de tempo, o estado do processo é composto de informações que são diretamente observáveis (tais como a variação dos preços na última semana e a posição do investidor) e a variação de preços no futuro, o que evidentemente não pode ser diretamente observado. Para obter uma observação não determinística e parcial dos preços futuros, podemos recorrer a combinações formalmente especificadas de sensores de análise técnica. As séries históricas são usadas para fornecer tanto as probabilidades de transição de um estado para outro quanto as probabilidades de se estar em um determinado estado quando um evento é relatado pelos sensores. Essas probabilidades são utilizadas por um algoritmo de planejamento automatizado para criar políticas que tentam maximizar o lucro do investimento. As políticas geradas podem então ser simuladas e avaliadas. A ferramenta também oferece flexibilidade para o usuário experimentar e comparar diferentes modelos. V Palavras-chave: Mercado de Ações, POMDP, Inteligência Artificial, Planejamento. ABSTRACT Analysts and investors use Technical Analysis tools to create charts and price indicators that help them in decision-making. Some tools allow the user to specify parameters and to create macros or business rules, but each person can have a different interpretation of these indicators. Chart patterns are not deterministic and even analysts may have different interpretations, depending on their experience, background and emotional state. In this way, tools that allow users to formalize these concepts and study investment policies based on them can provide a more solid basis for decision-making. In this work, we present a tool to formally model contexts, so that investment policies in the stock market can be generated and simulated. Investment contexts are modeled as Partially Observable Markov Decision Processes (POMDP). The state of the process at a certain time is composed of both information that is directly observable (such as the price variation in the last week and the investor's position) and the future price variation, which of course cannot be directly observed. To obtain a nondeterministic partial observation of future prices, we resort to formally specified combinations of Technical Analysis sensors. Historical series are used to provide both the probability of changing from one state to another and the probability of being in a certain state when the sensors report an event. These probabilities are used by an automated planning algorithm to create policies that try to maximize the profit. The execution of generated policies can then be simulated and evaluated. The tool also provides flexibility for trying and comparing different models. Keywords: Stock Market, POMDP, Artificial Intelligence, Planning. VI Índice Capítulo 1 – Introdução.................................................................................................... 12 1.1. Motivação ............................................................................................................. 12 1.2. Proposta ................................................................................................................ 13 1.3. Estrutura................................................................................................................ 15 Capítulo 2 - Predição no Mercado de Ações..................................................................... 16 2.1. Mercado de Capitais .............................................................................................. 16 2.2. Análise Técnica..................................................................................................... 19 2.2.1. Indicadores de Tendência ............................................................................... 20 2.2.2. Indicadores de Reversão ................................................................................. 24 2.2.3. Outros métodos de Análise Técnica ................................................................ 28 2.3. Alternativas de Predição com Aprendizado de Máquina ........................................ 36 2.3.1. Redes Neurais Artificiais ................................................................................ 36 2.3.2. Algoritmos Genéticos ..................................................................................... 38 2.3.3. Aprendizado por reforço ................................................................................. 40 2.4.Conclusão .............................................................................................................. 42 Capítulo 3 - Planejamento Baseado em MDPs e POMDPs ............................................... 43 3.1. Domínios Totalmente Observáveis ........................................................................ 43 3.1.1. Função de Utilidade........................................................................................ 44 3.1.2. Algoritmos ..................................................................................................... 45 3.2. Domínios Parcialmente Observáveis...................................................................... 48 3.2.1. Estado de Crenças........................................................................................... 49 3.2.2. Função de Utilidade........................................................................................ 50 3.2.3. Problema de Otimização ................................................................................. 50 3.2.4. Algoritmos ..................................................................................................... 51 3.3.Conclusão .............................................................................................................. 59 Capítulo 4 - Metamodelo de Suporte à Decisão ................................................................ 61 4.1. O Metamodelo....................................................................................................... 61 4.2. Arquitetura Geral do Protótipo .............................................................................. 65 4.2.1. Contexto......................................................................................................... 65 4.2.2. Probabilidades ................................................................................................ 66 4.2.3. Observações ................................................................................................... 67 4.2.4. Planejamento e Simulação .............................................................................. 67 4.3.Conclusão .............................................................................................................. 68 Capítulo 5 – Implementação............................................................................................. 70 5.1. Estrutura Básica .................................................................................................... 70 5.1.1. Descrição dos Pacotes..................................................................................... 70 5.1.2. Diagrama de classes........................................................................................ 71 5.2. Sensores ................................................................................................................ 74 5.3. Planejadores .......................................................................................................... 76 5.4. Processamento em Grid......................................................................................... 77 5.5. Interfaces de Usuário............................................................................................. 79 5.5.1. Interface Local – Nó Mestre ........................................................................... 79 5.5.2. Interface Remota Via Email............................................................................ 81 VII 5.5.3. Twitter............................................................................................................ 83 5.6. Planejador Implementado ...................................................................................... 83 5.7.Conclusão .............................................................................................................. 85 Capítulo 6 - Aplicação da Ferramenta a um Modelo Básico ............................................. 86 6.1. Composição de Estados......................................................................................... 87 6.2. Ações e Transições................................................................................................ 88 6.3. Recompensas......................................................................................................... 89 6.4. Observações e Sensores......................................................................................... 89 6.5. Experimentos ........................................................................................................ 91 6.5.1. 1ª Etapa: Período entre Janeiro/2008 e Junho/2009 ......................................... 92 6.5.2. 2ª Etapa: Período entre Janeiro/2009 e Dezembro/2009 .................................. 92 6.5.3. Resultados ...................................................................................................... 93 6.6.Conclusão .............................................................................................................. 95 Capítulo 7 - Conclusões ................................................................................................... 96 7.1. Considerações Finais ............................................................................................. 96 7.2. Contribuições ........................................................................................................ 97 7.3. Trabalhos Futuros.................................................................................................. 99 Referências .................................................................................................................... 101 VIII Índice de figuras Figura 1 – Padrão Gráfico Bandeira ................................................................................. 29 Figura 2 – Padrão Gráfico Flâmula................................................................................... 29 Figura 3 – Padrão Gráfico Triângulo Ascendente ............................................................. 30 Figura 4 – Padrão Gráfico Triângulo Descendente ........................................................... 30 Figura 5 – Padrão Gráfico Triângulo Simétrico ................................................................ 30 Figura 6 – Padrão Gráfico Ombro-Cabeça-Ombro............................................................ 30 Figura 7 – Padrão Gráfico Ombro-Cabeça-Ombro invertido............................................. 30 Figura 8 – Padrão Gráfico Topo Duplo............................................................................. 31 Figura 9 – Padrão Gráfico Fundo Duplo........................................................................... 31 Figura 10 - Demonstração do Candlestick ........................................................................ 32 Figura 11 – Representação de um martelo ou enforcado ................................................... 33 Figura 12 – Exemplo de um martelo invertido.................................................................. 33 Figura 13 – Exemplo de uma nuvem negra....................................................................... 33 Figura 14 – Exemplo de um piercing ............................................................................... 34 Figura 15 – Exemplo de estrela doji ................................................................................. 34 Figura 16 – Exemplo de estrela da manhã ........................................................................ 34 Figura 17 – Exemplo de estrela da tarde........................................................................... 34 Figura 18 – Exemplo de estrela que atira para o céu ......................................................... 35 Figura 19 – Exemplo engolfo de baixa ............................................................................. 35 Figura 20 – Exemplo engolfo de alta................................................................................ 35 Figura 21 – Visão geral da Arquitetura do Protótipo......................................................... 65 Figura 22 – Estrutura de pacotes do protótipo................................................................... 71 Figura 23 – Diagrama de classes da geração de contexto.................................................. 72 Figura 24 – Diagrama de classes da utilização do simulador............................................. 73 Figura 25 – Classe abstrata “PluginAbstract” para definição de sensor............................. 75 Figura 26 – Classe abstrata para definição de interface com planejador ............................ 77 Figura 27 – Diagrama de classes do Grid ......................................................................... 78 Figura 28 – Interface Local do Grid ................................................................................. 80 Figura 29 – Diagrama de classes do Algoritmo PBVI ....................................................... 84 IX Índice de tabelas Tabela 1 – Exemplo de definição que produz 6 estados .................................................... 62 Tabela 2 – Exemplo de definição de observações ............................................................. 62 Tabela 3 – Exemplo de definição de observações ............................................................. 63 Tabela 4 – Exemplo de definição de recompensas ............................................................ 64 Tabela 5 – Descrição dos métodos da classe abstrata “PluginAbstract” ............................ 75 Tabela 6 – Descrição dos métodos da classe abstrata “Planner” ....................................... 77 Tabela 7 – Comandos da interface via Email.................................................................... 81 Tabela 8 – Arquivos de Saída do planejador..................................................................... 84 Tabela 9 – Modelo de Transições de estados .................................................................... 88 Tabela 10 – Recompensas para os estados baseados na tupla <Tendência dos 6 dias anteriores, Tendência dos 6 dias seguintes, posição do investidor>................................... 89 Tabela 11 – Modelo de geração de observações ............................................................... 90 Tabela 12 – Resultados para operações de compra ........................................................... 94 Tabela 13 – Resultados para operações de venda.............................................................. 94 Tabela 14 – Resultados do Planejador x Ibovespa ............................................................ 94 Tabela 15 – Resultados para a obediência imediata dos indicadores ................................. 94 Tabela 16 – Resultados do Novo Planejador x Ibovespa................................................... 94 Tabela 17 – Comparação entre os resultados dos planejadores para o período entre 02/01/08 à 31/05/09........................................................................................................................ 95 Tabela 18 – Comparação entre os resultados dos planejadores para o período entre 02/01/09 à 30/12/09........................................................................................................................ 95 X Índice de quadros Quadro 1 – Descrição das variáveis da fórmula da Média Móvel Exponencial ................. 21 Quadro 2 – Descrição das variáveis da fórmula do CCI.................................................... 23 Quadro 3 – Algoritmo Policy Iteration............................................................................. 46 Quadro 4 – Algoritmo Value Iteration.............................................................................. 47 Quadro 5 – Algoritmo PBVI............................................................................................. 55 Quadro 6 – Rotina Backup do Algoritmo PBVI ................................................................ 56 Quadro 7 – Rotina Expand usando Random Action .......................................................... 57 Quadro 8 – Rotina Expand usando Stochastic Simulation with Random Action ................ 57 Quadro 9 – Rotina Expand usando Stochastic Simulation with Greedy Action .................. 58 Quadro 10 – Rotina Expand usando Stochastic Simulation with Exploratory Action......... 59 Quadro 11 – Comando “GridList”.................................................................................... 81 Quadro 12 – Comando “PendingJobs” ............................................................................. 82 Quadro 13 – Comando “RunningJobs”............................................................................. 82 Quadro 14 – Comando “AddTask” ................................................................................... 83 XI Capítulo 1 – Introdução 1.1. Motivação A análise de investimentos é uma atividade bastante comum na economia. Diariamente, administradores de empresa precisam recorrer às suas técnicas para poder avaliar onde e quando investir o dinheiro da companhia, seja em busca de produtividade ou apenas de correção monetária. A análise de investimentos pode ser vista como um problema nãodeterminístico e parcialmente observável, pois não se pode ter certeza sobre os resultados das suas decisões. No mercado de ações, por ser um mercado de risco, a previsibilidade do resultado de um investimento é ainda mais incerta. Mesmo analistas experientes em bolsa de valores não são capazes de prever todos os fatores que podem afetar os preços das ações. No entanto, as ferramentas da Análise Técnica [9], baseadas na hipótese de Dow [8], afirmam que as séries temporais de preços das ações podem ser consideradas as únicas fontes de informação relevantes para estimar o melhor momento para comprar ou vender ações. A Análise Técnica fornece muitas ferramentas para estudo de série de preços, tais como padrões gráficos, indicadores e outros conceitos, mas existem várias maneiras de interpretar os dados. Uma ferramenta para modelagem e análise que combine os conceitos de Análise Técnica pode ajudar nas tomadas de decisão, considerando os riscos e benefícios potenciais de uma determinada decisão. As decisões anteriores podem influenciar os resultados e decisões futuras. Desta forma, a estimativa de períodos de alta ou de baixa não é suficiente para tomar a decisão correta em certo momento. A compra realizada após uma tendência de alta, por exemplo, deve considerar as possibilidades do mercado continuar em 12 alta para que se possa realizar lucro. Então, é necessário adotar políticas que levem em consideração os riscos e benefícios da combinação de decisões a longo prazo. Este trabalho é motivado pela idéia de construir um mecanismo para criar políticas de investimento, assumindo a hipótese de Dow, mas levando em conta que nunca se tem observação total da tendência dos preços. 1.2. Proposta Neste trabalho, objetiva-se estudar a possibilidade da utilização de técnicas de planejamento para a análise e o auxílio na tomada de decisão de compra e venda no mercado de ações. Para alcançar estes objetivos, propõe-se um ambiente de estudo para modelagem de contexto, planejamento e simulação, utilizando Processos de Decisão de Markov Parcialmente Observáveis (POMDPs) [3]. Processos de Decisão de Markov (MDPs) são processos onde o resultado da execução de uma ação pode levar a estados diferentes (segundo uma distribuição de probabilidade) e as probabilidades dependem apenas do estado anterior. Normalmente, são associados custos às ações e recompensas aos estados, e tenta-se maximizar o benefício (recompensas menos custos) ao longo do tempo. Em POMDPs, adicionalmente, não se tem noção total do estado corrente e é necessário tomar decisões com base na crença sobre a probabilidade de se estar em cada estado. No ambiente proposto [39], fornece-se apoio para a modelagem de um contexto de investimento no mercado acionário, levando-se em conta a idéia de que as tendências de preços fazem parte do estado corrente, embora não se consiga observá-las diretamente. A ferramenta que dá suporte ao ambiente permite ao usuário modelar formalmente o que compõe um estado em um determinado momento. Além disso, permite especificar os sensores baseados em Análise Técnica que indicam a ocorrência de padrões em séries temporais correspondentes à observação parcial de tendências. Com base em um modelo definido para os estados e as observações, políticas de investimento podem ser geradas, simuladas e avaliadas automaticamente. A fim de modelar o processo como um POMDP, deve-se assumir a hipótese de Markov, que estabelece que o próximo estado depende apenas do estado atual. Desta forma, inserem-se no estado todas as informações que poderiam ser relevantes para a tomada de decisão. Um estado contém dados que podem ser diretamente observáveis, tais como a 13 posição do investidor e as informações sobre preços a partir de dados do passado (até o ponto em que são considerados úteis). Além disso, assume-se que há sempre uma tendência definida para os preços futuros. A fim de incorporar essa idéia, os estados também contêm informações sobre os preços que serão formados em um futuro próximo. Esta parte do estado não pode ser observada diretamente, mas pode-se tentar "parcialmente observá-la" através dos sensores de Análise Técnica. Com base nas especificações formais que descrevem os estados e os sensores, as séries temporais são investigadas para determinar as probabilidades de mudança de um estado para outro e as probabilidades de se observar um padrão de Análise Técnica em um determinado estado. As probabilidades também podem ser especificadas manualmente por analistas experientes e comparadas às ocorrências da série temporal. Ao modelar-se o problema como um POMDP, supõe-se que os conceitos de Análise Técnica fornecem apenas uma observação parcial da realidade. Observa-se o histórico para estabelecer as probabilidades de correspondência entre padrões de Análise Técnica e as tendências verificadas em seguida. Ao utilizar essas probabilidades, é possível criar políticas que tentam combinar ações a fim de aumentar os lucros, levando-se em conta a imprecisão dos métodos de Análise Técnica. De posse do modelo probabilístico para o POMDP, a ferramenta utiliza técnicas de planejamento automatizado [16] para gerar as políticas. Estas políticas definem quais ações devem ser executadas de acordo com as observações obtidas do ambiente através dos sensores. Os mesmos sensores que foram utilizados anteriormente para obter as probabilidades fornecem observações que permitem a seleção da ação que deve ser executada. As políticas são avaliadas em cenários de mercado diferentes (como, por exemplo, situações de alta, baixa ou estabilidade). O simulador avalia as políticas usando as informações de mercado em tempo real ou as guardadas no banco de dados. A ferramenta permite que o usuário teste diversos conceitos de Análise Técnica e verifique sua eficácia em diferentes cenários. A influência dos dados anteriores sobre os preços futuros pode variar, assim como a melhor interpretação dos conceitos da Análise Técnica. Desta forma, a ferramenta tenta oferecer flexibilidade tanto para a modelagem da composição de um estado quanto para a criação e a utilização de sensores. Seu propósito é fornecer meios para o estudo de modelos 14 de investimento utilizando várias alternativas. Diversos POMDPs podem ser especificados e resolvidos em paralelo, gerando diversas políticas que podem ser avaliadas antes de serem utilizadas para apoiar a tomada de decisões. Como o processo de resolução de POMDPs é custoso, a ferramenta incorpora mecanismos de computação em grid para dar conta de várias tarefas de planejamento em paralelo. 1.3. Estrutura No capítulo 2, são introduzidos os conceitos básicos sobre predição de preços no Mercado de Ações e finanças. Este capítulo é destinado a documentação e compreensão das teorias utilizadas por analistas de investimentos e que são utilizadas durante este trabalho. Também são comentadas outras técnicas computacionais de previsão de preços e comparadas a abordagem proposta. No capítulo 3, apresenta-se a fundamentação teórica sobre planejamento automático baseado em Processos de Decisão de Markov para domínios totalmente e parcialmente observáveis. O capítulo 4 descreve um metamodelo para descrição de contextos de investimentos e geração de modelos POMDPs. Também inclui a proposta de arquitetura para desenvolvimento de um ambiente para o planejamento e simulação das políticas de investimento. O capítulo 5 descreve como o metamodelo e a ferramenta foram implementados. Os esquemas para inclusão de novos sensores e planejadores são apresentados através de exemplos. No capítulo 6, é descrito um modelo básico POMDP para o contexto de investimentos. Este modelo foi utilizado durante os experimentos e produziu os resultados que são comentados neste capítulo. O capítulo 7 contém as conclusões da pesquisa com a descrição de suas principais contribuições e dos potenciais trabalhos futuros. 15 Capítulo 2 - Predição no Mercado de Ações A análise de investimentos é um tema bastante pesquisado por diversas áreas, sempre com o mesmo objetivo: avaliar formas de maximizar os resultados dos investimentos através da percepção do melhor momento para aplicação e resgate. Um bom analista de investimentos procura prever boas oportunidades de compra e os melhores momentos para venda. Define-se como “investimento” a aplicação de qualquer recurso (seja financeiro, títulos, equipamentos, imóveis, etc.) com o objetivo de receber algum retorno de valor superior ao aplicado. O resultado da aplicação deve compensar as perdas decorrentes do uso dos recursos durante o período de aplicação (que podem ser corretagens, taxas, juros ou inflação) [40]. As condições, os prazos e os preços de cada investimento são fornecidos pelo mercado correspondente. O mercado é o local onde agentes negociam a troca de bens por uma unidade monetária ou por outros bens. O preço e as condições de troca são baseados na lei de oferta e demanda. A análise de investimentos pode ser aplicada a diversos mercados. É possível utilizar suas técnicas para avaliar oportunidades de investimento nos mercados de capitais, cambial, imobiliário, entre outros. Este trabalho relaciona-se especificamente ao mercado de capitais. A seguir, são apresentados o contexto do Mercado de Capitais, os indicadores de Análise Técnica e as alternativas de predição automática disponíveis que usam mecanismos de aprendizado de máquina. 2.1. Mercado de Capitais No mercado, os preços das ações são definidos pela lei da oferta e demanda. A oferta ou a demanda de uma determinada ação está relacionada ao comportamento histórico dos seus 16 preços e às perspectivas futuras sobre a empresa. Quando existe grande quantidade de um bem no mercado, ou seja, demanda inferior à oferta, seu preço tende a cair. O inverso ocorre quando o mesmo bem é raro ou encontra-se escasso (demanda superior à oferta): seu preço tende a subir. [15] O Mercado de Capitais é constituído pelas bolsas de valores, sociedades corretoras e outras instituições financeiras autorizadas por uma agência reguladora (por exemplo: a CVM - Comissão de Valores Mobiliários - no Brasil, a FSA - Financial Services Authority - na Inglaterra e a SEC - Securities and Exchange Commission - nos EUA). Seu objetivo é viabilizar o processo de capitalização que proporciona liquidez aos títulos emitidos por empresas (títulos esses, ações ou debêntures). As ações representam frações do capital social das empresas e são, em geral, negociadas em bolsas de valores. As corretoras e os bancos participam como intermediários, responsáveis por representar pessoas físicas e instituições que pretendem adquirir ou negociar ações, opções ou debêntures. As negociações de ações podem ocorrer em um pregão “físico”, realizado no salão da bolsa de valores, ou através de um pregão eletrônico, que permite ao investidor lançar suas operações através de sistemas eletrônicos ligados em rede, usualmente através da Internet. Alguns mercados operam exclusivamente através do pregão eletrônico, porém a maioria das bolsas de valores também dispõe de um pregão físico, onde são realizadas as negociações. Dentre as atribuições da instituição, as bolsas têm o dever de repassar aos investidores (através de boletins ou de meios eletrônicos) informações sobre seus negócios diários, informações sobre as empresas abertas participantes e qualquer outro dado que contribua para a transparência das operações. O mercado à vista é onde se realiza a compra ou a venda de uma determinada quantidade de ações, a um preço estabelecido em pregão. Após a realização de um negócio, cabe ao comprador despender o valor estabelecido na operação e, ao vendedor, a entrega do título negociado no prazo estabelecido. [41] Além da negociação imediata de ações no mercado à vista a preços correntes, existem outros tipos de contratos de ações que podem ser realizados no mercado de futuros e no mercado de opções. Os contratos no mercado de futuros envolvem a troca de ações a 17 um preço acordado em uma data especificada. Uma opção é um contrato entre um comprador e um vendedor, negociado por uma taxa (chamada prêmio), que dá ao comprador o direito, mas não a obrigação, de comprar ou vender um determinado ativo1 em um dia determinado (data de vencimento) a um preço acordado (chamado de alvo ou strike). As opções podem ser determinadas como de compra ou de venda. Nas opções de compra, é vendido o direito de comprar ativos e, nas opções de venda, o direito de vendêlos. Além disso, os investidores podem tomar emprestado ativos e vendê-los com a intenção de comprá-los outra vez mais tarde, antes de devolvê-los ao credor. Tanto no mercado de opções quanto no mercado à vista, os investidores podem ser posicionados como “comprados”, quando eles apostam que o preço de uma determinada ação irá aumentar, ou em “vendidos”, quando eles apostam que os preços vão cair. No mercado de opções, posições “compradas” são assumidas quando se compra uma opção de compra ou se vende uma opção de venda. Posições “vendidas” são assumidas quando se vende uma opção de compra ou se compra uma opção de venda. No mercado à vista, as posições “compradas” podem ser assumidas pela simples compra de ativos, na expectativa de vendê-los a preços mais elevados. Posições “vendidas” podem ser assumidas por empréstimo de ativos, seguido de sua venda, com a intenção de comprá-los mais tarde, a preços mais baixos, devolvendo o ativo ao dono original. Vários outros tipos de operações, com riscos diferentes, podem ser executados através da combinação de operações realizadas no mercado à vista, mercado de futuros e mercado de opções. As duas principais disciplinas sobre a análise de investimento são: a Análise Fundamentalista e a Análise Técnica. A Análise Fundamentalista [9] procura analisar as demonstrações financeiras e a saúde financeira de uma empresa. O analista utiliza o fluxo de caixa, os balanços e os resultados operacionais da empresa para determinar as oportunidades de investimento. Seu objetivo é estimar o valor “justo” e o valor de mercado potencial de um ativo financeiro. Este processo é chamado de Valuation. A diferença entre o valor “justo” e o valor de mercado (listado na bolsa de valores) determina a decisão de comprar ou vender a ação. A Análise Técnica [9] é uma disciplina que procura prever a direção futura dos preços através da análise dos dados históricos do mercado, principalmente preço e volume. 1 a ação em questão, quando se tratando do mercado de ações 18 Ela utiliza métodos estatísticos para determinar o melhor momento para comprar ou vender um ativo. Durante a análise, o analista tenta identificar padrões gráficos não aleatórios, como a reversão "ombro-cabeça-ombro". O analista também utiliza indicadores matemáticos e estudos estatísticos adicionais para auxiliá-lo em sua decisão. Esta disciplina baseia-se na Teoria de Dow [8], que diz que os preços dos ativos refletem a reação do mercado em todas as informações pertinentes. O preço desconta tudo, tem tendências e padrões que se repetem. Analistas que utilizam a Análise Técnica podem ignorar qualquer outra informação sobre a empresa porque, de acordo com a Teoria de Dow, a série de preços fornece as informações necessárias para a análise e também reflete decisões que foram baseadas em Análise Fundamentalista. Tanto a Análise Fundamentalista quanto a Análise Técnica podem ser utilizadas isoladamente ou em conjunto para ajudar os investidores a decidir se devem assumir uma posição comprada ou vendida em um determinado momento. A Análise Fundamentalista depende, contudo, de muita informação sobre a empresa na qual se deseja investir e que, muitas vezes, não está disponível. Desta forma, a Análise Técnica pode ser muito útil, pois as séries de preços estão sempre disponíveis. O problema com a Análise Técnica é que existem muitas maneiras de se analisar uma série temporal e os analistas podem ter diferentes interpretações dependendo da sua experiência, de seus antecedentes e de seu estado emocional. Alguns conceitos "grafistas" e suas interpretações dos indicadores não são formais. A fim de aplicar e avaliar automaticamente o uso de conceitos da Análise Técnica é necessário formalizá-los matematicamente, de modo que eles possam gerar observações para apoiar as decisões. 2.2. Análise Técnica A Análise Técnica procura identificar e explorar diversos padrões não aleatórios nos preços e tendências de séries de ativos do mercado financeiro. Para isto, métodos de Análise Técnica baseados em indicadores utilizam funções matemáticas que indicam momentos favoráveis para compra ou venda a partir das informações de preço, volume e quantidades negociadas do ativo. Um indicador pode gerar lucro enquanto outro pode gerar prejuízo, devido às teorias e às fórmulas que os compõem. Não há garantia alguma de que a simples obediência a um indicador gera bons resultados. Em geral, os investidores precisam definir 19 estratégias de atuação assumindo que os indicadores são úteis, mas estão longe de serem perfeitos. Por este motivo, é necessário comparar indicadores e verificar a sua adequação aos períodos e aos ativos que estão sendo analisados. 2.2.1. Indicadores de Tendência Indicadores de tendência são aqueles que demonstram os melhores momentos de compra ou de venda quando um determinado papel segue em uma tendência bem definida de alta ou baixa. 2.2.1.1. Média Móvel Simples A média móvel simples (Simple Moving Average - SMA) é um indicador que gera uma série composta de valores que representam a média simples dos n valores anteriores [15]. Sua fórmula é: t ∑ SMAt = xi i = t − n +1 n Onde n é o tamanho da janela de previsão, t é o ponto da série original e x o valor dos pontos anteriores a ser somado. Outra forma de calcular a média móvel simples é utilizando a média móvel já calculada para o ponto anterior e o valor do ponto seguinte, como demonstrado a seguir. SMAt = SMAt −1 + xt − n xt − n n Este é um método muito simples e de fácil entendimento, porém considera que todos valores da janela de previsão têm a mesma influência no ponto atual. É bastante utilizado para eliminar ruídos em séries com grandes períodos de flutuação. As indicações que uma média móvel pode mostrar são “ponto de compra” e “ponto de venda”. Existem três estratégias para interpretação dos pontos. A primeira utiliza uma média móvel rápida (normalmente com janela de previsão composta de 7, 10 ou 13 dias) e uma média móvel lenta (20 ou 30 dias) desenhadas sobre a série do ativo. O ponto de compra ocorre quando a série mais rápida cruza para cima a lenta, e o ponto de venda quando ocorre o cruzamento da série mais lenta sobre a rápida. 20 A segunda estratégia utiliza apenas uma média móvel lenta. De forma semelhante, o ponto de compra ocorre quando a linha que representa o preço do ativo cruza para cima a média móvel lenta, e o ponto de venda, quando o ocorre o inverso. A terceira estratégia é a combinação das duas primeiras. Os pontos de compra ou de venda ocorrem quando indicados por uma das estratégias anteriores e confirmados pela outra. 2.2.1.2. Média Móvel Exponencial A média móvel exponencial (Exponential Moving Average – EMA) é também conhecida como suavização exponencial [15] e é calculada a partir das fórmulas α = 2 /(n + 1) e EMAt = Pt −1 + α (Rt −1 − Pt −1 ) , conforme o quadro 1. n é o tamanho da janela de previsão α é o fator de suavização. (0 < α < 1) EMAt é o novo valor da média móvel exponencial Pt-1 é o último valor da média móvel exponencial R t-1 é o valor da série que está sendo analisada Quadro 1 – Descrição das variáveis da fórmula da Média Móvel Exponencial O fator de suavização α representa a influência dos dados da série. Quanto maior for seu valor, mais significativos serão os dados recentes e quanto menor, mais significativos serão os dados antigos [15]. Utilizam-se as mesmas estratégias de interpretação descritas para a média móvel simples. 2.2.1.3. Oscilador de média móvel O Oscilador de Média Móvel é um indicador que procura medir as mudanças de preços em um período específico da série. É calculado utilizando uma média móvel simples e duas médias móveis exponenciais de diferentes períodos. Geralmente, utilizam-se janelas de 3 e de 13 dias para calcular a diferença entre as médias móveis exponenciais e de 3 dias para a média móvel simples [15]. OMM = SMA(3 _ dias )(EMA(3 _ dias ) − EMA(3 _ dias ) ) 21 Como resultado, o oscilador de média móvel produz valores que tendem a variar entre -100 e +100. Sua única estratégia define a ocorrência de um ponto de compra quando seu valor cruza a linha zero para cima, e o ponto de venda quando cruza a linha zero para baixo. 2.2.1.4. MACD O MACD (Moving Average Convergence / Divergence) é um dos indicadores mais conhecidos e utilizados. É definido pela diferença entre duas médias móveis exponenciais dos preços de fechamento: uma rápida, com 12 dias, e outra lenta, com 26 dias. Os períodos padrão para as séries foram recomendados pelo seu criador Gerald Appel [1]. MACD = EMA(12 dias) do preço de fechamento – EMA(26 dias) do preço de fechamento Outro componente deste indicador é a linha de sinal (ou gatilho). Ela é formada pela suavização da série MACD por uma média móvel exponencial de 9 dias. Sinal = EMA(9 dias) do MACD O terceiro componente de um MACD é formado pela diferença entre o MACD e a linha de sinal e é geralmente demonstrado como um histograma em barras. Histograma = MACD - Sinal Os períodos das médias de 12, 26 e 9 dias podem variar de acordo com as necessidades do analista e das séries a serem analisadas. A interpretação dos indicadores pode ser feita utilizando-se uma de suas três estratégias: • Linha de MACD cruza a linha de sinal – Indica compra quando MACD cruza para cima a linha de sinal e venda quando cruza para baixo. O histograma também indica quando um cruzamento acontece: torna-se positivo quando a linha MACD cruzou a linha de sinal e negativo quando o inverso ocorre. A queda no histograma pode sugerir que um cruzamento está para acontecer. 22 • Linha de MACD cruza zero – Quando a linha MACD torna-se positiva, pode indicar uma possível alta dos preços e quando se torna negativa, uma possível queda. • Diferença entre preço e MACD – A diferença positiva entre o MACD e o preço pode indicar uma subvalorização do papel e uma possível alta dos preços. A diferença negativa pode indicar o oposto e uma possível queda. Estas indicações devem ser confirmadas com o histograma. 2.2.1.5. CCI O CCI (Commodity Channel Index) é classificado como um oscilador e possui grande popularidade entre os analistas. Normalmente, é utilizado para identificar períodos cíclicos em séries de commodities, mas também pode ser utilizado no mercado à vista e de câmbio. O CCI é calculado através da diferença entre o preço e sua média móvel simples, divididos pelo desvio padrão do preço. O autor sugere a utilização do fator 1/0.015 para manter os valores entre 100 e -100 e facilitar sua leitura [11]. A fórmula é descrita a seguir: CCI = é a média entre os preços de fechamento, máximo e mínimo. pt SMA(20 dias) σ ( pt ) 1 pt − SMA(20 _ dias )( pt ) 0.015 σ ( pt ) é a média móvel simples de 20 dias. é o desvio padrão do preço de pt. Quadro 2 – Descrição das variáveis da fórmula do CCI A principal função do CCI é a detecção de divergências nos preços das ações, que podem indicar se o papel está supervalorizado ou subvalorizado. Como é um oscilador, descreve valores entre -100 e +100, indicando que o mercado está provavelmente precificando corretamente o ativo. Leituras acima de +100 podem indicar uma supervalorização e abaixo de -100, uma subvalorização. A média móvel do CCI pode utilizar outras janelas de acordo com o interesse do analista. 2.2.1.6. Parabolic SAR Parabolic SAR (Stop and Reverse) ou “Sistema seguidor de tendência” caracteriza-se por determinar pontos de venda que devem ser utilizados como proteção. É calculado utilizando um fator de aceleração, que define pesos para os pontos de venda na medida em que uma tendência se desenvolve [22]. Quando os valores calculados estão abaixo do preço 23 do ativo, indicam uma possível alta futura e quando acima, indicam uma possível baixa. O SAR é calculado através da fórmula: SARn+1 = SARn + α (EP − SARn ) Onde SARn representa o último valor calculado (valor atual) e SARn+1 o valor seguinte. EP (extreme point) é o valor mais alto da série do ativo durante uma atual tendência de alta ou o mais baixo durante uma atual tendência de baixa. O EP é atualizado sempre que um novo valor máximo (ou mínimo) é observado. A cada nova tendência, o EP é restaurado e recebe o valor atual da série do ativo. O fator de aceleração é representado por α . Normalmente, utiliza-se 0.02 como fator de aceleração inicial e acrescenta-se a este 0.02 (ou um valor definido pelo analista) a cada novo valor de EP. Em outras palavras, sempre que um novo valor de EP é observado, incrementa-se o fator de aceleração. Para evitar distorções, o fator não deve ultrapassar o valor máximo de 0.20. O SAR é calculado recursivamente para cada período. Porém, se o valor de SAR calculado para n+1 (dia seguinte) encontra-se entre os valores da máxima e mínima do ativo em n (hoje), então: • Quando em Tendência de Alta – O valor de SAR deverá ser igual ao limite superior (ou seja, o valor máximo da tendência que foi calculado em EP – Extreme point). • Quando em Tendência de Baixa – O valor de SAR deverá ser igual ao limite inferior (ou seja, o valor mínimo da tendência que foi calculado em EP – Extreme point). A mudança ocorre porque quando o valor de n+1 (SAR de amanhã) encontra-se entre os valores da máxima e mínima do ativo em n (hoje), uma nova tendência é assinalada e o SAR deve trocar os valores. O primeiro valor de SAR para a nova tendência é o último EP registrado na tendência anterior. O α é então restaurado, retornando ao valor inicial de 0.02. 2.2.2. Indicadores de Reversão Os indicadores de reversão procuram definir o momento em que as cotações de um papel estão esgotando uma tendência, que pode ser de baixa ou de alta, e entrando em tendência inversa. 24 2.2.2.1. Momentum e ROC Momentum e ROC(Rate of Change) são indicadores similares que indicam a diferença entre o preço de fechamento de hoje e o de fechamento de n dias atrás [9]. O Momentum é a diferença simples entre os fechamentos, conforme descrito a seguir. Momentum = fechamentohoje − fechamenton _ dias _ atrás O ROC representa o percentual de acréscimo (ou decréscimo) do preço atual em relação ao preço de n dias atrás. Rate _ of _ Change = fechamentohoje − fechamenton _ dias _ atrás fechamenton _ dias _ atrás Ao interpretar estes indicadores, define-se a tendência atual como positiva quando seus resultados são positivos e vice-versa. Dizemos que uma reversão ocorreu quando a tendência anterior é diferente da tendência atual. Sendo assim, a reversão de uma tendência negativa para uma tendência positiva indica um ponto de compra, e a reversão de uma tendência positiva para uma negativa indica um ponto de venda. Quanto mais expressivos forem os valores resultantes, mais forte será a tendência. Podemos calcular o Momentum de uma média móvel de n dias e assim definir sua tendência, como demonstrado a seguir. Momentum = SMA(n _ dias ) hoje − SMA(n _ dias ) ontem n Na fórmula anterior, n é o número de dias da janela de previsão utilizado no cálculo das médias móveis. 2.2.2.2. Índice de Força Relativa O RSI (Relative Strength Index) é um oscilador que procura descrever a força de um preço em comparação aos movimentos de alta e de baixa dos preços de fechamento. É um indicador bastante popular devido à sua fácil interpretação. [22] A cada dia, calcula-se um valor de mudança de Alta ou de Baixa. Nos dias de alta (quando o fechamento é superior ao fechamento do dia anterior) definem-se os seguintes valores: Alta = fechamentohoje − fechamentoontem Baixa = 0 25 E, em dias de baixa, definem-se os valores: Alta = 0 Baixa = fechamentoontem − fechamentohoje Se o fechamento de hoje for igual ao de ontem, ambos Alta (mudança de alta) e Baixa (mudança de baixa) deverão ser iguais a zero. A força relativa é então calculada a partir da divisão entre as médias móveis exponenciais de Alta e de Baixa para n dias, como demonstrado a seguir. RS = EMA(n _ dias) _ de _ Alta EMA(n _ dias) _ de _ Baixa Este indicador parte da premissa de que EMA[n] de Baixa nunca é igual a zero e não pode ser calculado caso ocorra esta exceção. Em seguida, converte-se o valor de RS para uma escala de 0 a 100. RSI = 100 − 100 × 1 1 + RS Normalmente, utiliza-se um período de 14 dias para a média móvel exponencial conforme sugerido pelo autor do indicador [22]. Quando o valor da RSI ultrapassa 70 pontos, pode significar que o ativo está sobre avaliado e que a venda do ativo deverá ser considerada. Quando retrocede a um valor inferior a 30 pontos, pode indicar que o ativo está sub avaliado e sugere-se um ponto de compra. Este indicador considera que uma possível reversão aproxima-se quando existe uma alta proporção do movimento diário em uma única direção, alcançando os valores limite. Valores como 80 e 20 também podem ser usados como limitadores, de acordo com as condições de mercado. Existe uma variante do RSI, chamada RSI de Cutler [11], que é calculada através de médias móveis simples em vez das médias móveis exponenciais. O RSI de Cutler é utilizado como complemento, auxiliando na confirmação dos sinais. RS _ de _ Cutler = SMA(n _ dias) _ de _ Alta SMA(n _ dias ) _ de _ Baixa 26 Para calcular a média móvel simples, utiliza-se uma janela de previsão de 27 dias conforme sugerido pelo autor do indicador, de acordo com [22]. 2.2.2.3. Oscilador Estocástico O Oscilador Estocástico é um indicador de momento criado por George Lane na década de 1950 para comparar o preço de fechamento de uma commodity aos preços máximos e mínimos em um período [12]. É calculado através da fórmula: STS = 100 fechamento − mínimo máximo − mínimo O conceito por trás deste indicador é que, durante um período específico, os preços tendem a fechar próximo às máximas anteriores quando em tendências de alta e próximo às mínimas quando em tendências de baixa. Sinais de reversão são definidos quando o Oscilador Estocástico cruza sua própria média móvel. Geralmente são calculados 2 osciladores estocásticos para que indiquem futuras variações de preço – um rápido (%K) e um lento (%D). A comparação entre estas variações indica a velocidade da mudança dos preços. Os osciladores %K e %D utilizam uma escala de 0 a 100 e geralmente são visualizados como um gráfico de linhas. Valores próximos dos extremos 100 e 0 em ambos indicadores definem forças e fraquezas (respectivamente) porque os preços estão próximos das maiores máximas ou menores mínimas do período de n dias [12]. O Oscilador Estocástico rápido (ou Stoch %K) indica o percentual da diferença entre o último preço de fechamento e o menor preço mínimo no período dos últimos n dias, sobre a diferença entre a maior máxima e a menor mínima neste período, como a seguir: %K = fechamentohoje − menor _ mínimaultimos _ n _ dias maior _ máximaultimos _ n _ dias − menor _ mínimaultimos _ n _ dias × 100 O período de 14 dias é definido como o padrão do %K, mas pode variar de acordo com a necessidade do analista. Quando o último fechamento é o preço mais baixo dos últimos n dias, então %K é igual a zero. Quando o fechamento é o maior preço do período, então %K é igual a 100. O Oscilador Estocástico lento (ou Stoch %D) é calculado através da média móvel simples do Stoch %K com s dias. Geralmente utilizam-se 3 dias. % D = SMA(3 _ dias) _ de _ % K 27 Existem duas estratégias conhecidas para os indicadores %K e %D para compra e venda de papéis. A primeira envolve o cruzamento do sinal dos indicadores: o sinal de compra acontece quando %K cruza para cima o sinal de %D; o sinal de venda acontece quando ocorre o oposto. Quando diversos cruzamentos simultâneos acontecem (devido à volatilidade da série), é possível utilizar uma pequena média móvel simples sobre o valor de %D, suavizando flutuações rápidas de preço. Outra estratégia utiliza os limites de 80 e 20 como indicadores de supervalorização e subvalorização dos valores de %K ou %D. Vende-se quando o valor ultrapassa o limite superior e compra-se quando ultrapassa o inferior. 2.2.3. Outros métodos de Análise Técnica A Análise Técnica possui outros métodos populares e cuja interpretação é mais subjetiva que a dos indicadores. Em geral, esses métodos são baseados na interpretação de padrões gráficos que podem ser identificados visualmente na série de preços. Alguns desses métodos são descritos a seguir. 2.2.3.1. Suporte e Resistência Suporte e resistência é um conceito básico para a escola de Análise Técnica. De acordo com a Teoria de Dow, os padrões se repetem, então, admite-se que o mercado tem memória e que lembra dos preços das mínimas e das máximas passadas [9]. Sendo assim, as resistências são preços considerados “caros” para determinada ação e os suportes são preços considerados “baratos” demais pelo mercado. As resistências são percebidas quando o preço de uma ação encontra-se em uma tendência de alta e tem dificuldade de ultrapassar certo patamar. O mesmo ocorre na situação inversa, quando em uma tendência de baixa, o preço não consegue ultrapassar um limite inferior. Normalmente, esses limites são definidos por máximas ou por mínimas históricas, facilmente percebidas nos gráficos das séries de preços [9]. Quando ocorre um suporte, e este se encontra no mesmo patamar de um suporte ou de uma mínima anterior, o analista traça uma linha no gráfico que é usada para prever sua ocorrência no futuro. Da mesma forma, o analista traça uma linha quando ocorre uma resistência que pode ser confirmada por uma resistência ou uma máxima anterior. 28 2.2.3.2. Padrões Gráficos Existem diversos padrões gráficos apresentados pela escola de Análise Técnica. A seguir, são apresentados os padrões mais utilizados pelos analistas de investimentos. Bandeiras e Flâmulas Bandeiras e flâmulas são padrões semelhantes, formados durante tendências de curta duração e que surgem durante movimentos bruscos de alta ou baixa. Normalmente ocorrem após um movimento mais forte, seguido da correção do preço e da retomada do movimento na direção original [41]. A figura 1 demostra uma bandeira e a figura 2 uma flâmula. A diferença principal entre uma bandeira e uma flâmula é o formato do padrão corretivo da formação. O movimento de correção de uma bandeira forma um desenho semelhante a um retângulo, enquanto o movimento de correção de uma flâmula é semelhante a uma flâmula (ou uma bandeira pontiaguda) e lembra um triângulo. Figura 1 – Padrão Gráfico Bandeira Figura 2 – Padrão Gráfico Flâmula Triângulos Os triângulos são classificados como padrões de continuação de tendência e se formam quando a flutuação dos preços começa a atingir amplitudes cada vez menores [41]. Classifica-se como triângulo ascendente quando o desenho formado no gráfico possui o lado superior horizontal e o inferior como uma linha ascendente. O rompimento da linha superior normalmente indica a continuação da tendência de alta. O triângulo descendente é exatamente o inverso do triângulo ascendente. Ele possui o lado inferior horizontal e o superior como uma linha ascendente. O rompimento da linha inferior normalmente indica a continuação da tendência de alta. A diferença entre a flâmula 29 e o triângulo descendente é que a flâmula é formada durante uma tendência de alta e o triângulo descendente é formado durante uma tendência de baixa. Existe uma terceira forma de triângulo que um gráfico pode assumir e é chamada de triângulo simétrico. O triângulo simétrico é formado por um lado inferior ascendente e um lado superior descendente e é uma formação típica de indecisão. Caso ocorra o rompimento da linha superior, o triângulo indica uma tendência de alta, e caso ocorra o rompimento da linha inferior, indica uma tendência de baixa. As figuras 3, 4 e 5 demostram estes padrões. Figura 3 – Padrão Gráfico Triângulo Ascendente Figura 4 – Padrão Gráfico Triângulo Descendente Figura 5 – Padrão Gráfico Triângulo Simétrico Ombro-Cabeça-Ombro O Ombro-Cabeça-Ombro é um padrão gráfico que define uma reversão. Parte da premissa de que uma tendência perde força e abranda até que se processa a inversão. O OmbroCabeça-Ombro parte de uma tendência de alta que perde força e inicia uma tendência de baixa [41]. Durante uma tendência de baixa, pode ocorrer o Ombro-Cabeça-Ombro invertido. O Ombro-Cabeça-Ombro invertido parte de uma tendência de baixa que perde força e inicia uma tendência de alta. As figuras 6 e 7 demostram o Ombro-Cabeça-Ombro. Figura 6 – Padrão Gráfico Ombro-Cabeça-Ombro Figura 7 – Padrão Gráfico Ombro-Cabeça-Ombro invertido 30 Topos e Fundos Duplos e Triplos O topo duplo (ou M) sinaliza o final de uma tendência de alta [41]. É formado quando o preço sobe até atingir um determinado patamar e perde força, iniciando um processo de retração. Após a retração, uma nova tendência de alta inicia-se e continua até alcançar o patamar atingido anteriormente. Então, uma nova retração ocorre e inicia uma tendência de baixa. A figura 8 demostra um topo duplo. O fundo duplo (ou W) é exatamente o oposto do topo duplo. Ele sinaliza o final de uma tendência de baixa e é formado quando o preço desce até atingir um determinado patamar e começa a subir. Após um movimento de alta, ocorre uma retração até que o preço volte ao patamar anterior. Em seguida, inicia-se um novo movimento de alta que, caso ultrapasse o movimento de alta anterior, inicia uma tendência de alta. A figura 9 demostra um fundo duplo. Figura 8 – Padrão Gráfico Topo Duplo Figura 9 – Padrão Gráfico Fundo Duplo Topos e Fundos Triplos - Os topos e fundos triplos seguem os mesmos conceitos dos topos e fundos duplos e a sua única diferença é a ocorrência de um topo ou fundo a mais [41]. 2.2.3.3. Candlesticks O candelabro japonês, ou candlestick, é uma representação gráfica da Análise Técnica, baseada nas antigas bolsas de arroz de Osaka em meados do século XVIII. A análise é feita através da interpretação de padrões formados pelos candles (pontos do gráfico) em um determinado período [17]. Os padrões de candlestick podem indicar reversões, tendências e sinalizar suportes e resistências. Também são normalmente utilizados para avaliar se um ativo está sobre 31 avaliado ou sub avaliado. Alguns analistas utilizam somente a análise baseada em candlesticks, porém sugere-se a confirmação dos sinais utilizando-se outros indicadores de Análise Técnica. Os candles são constituídos por dois componentes: o retângulo é chamado de corpo, e a linha vertical é chamada de sombra. O corpo delimita o intervalo entre o preço de abertura e o preço de fechamento, e a sombra delimita o intervalo entre o preço mínimo e o preço máximo do dia. Conforme demostrado na figura 10, quando o preço de fechamento é superior ao preço de abertura, o corpo é representado por um retângulo branco e quando o fechamento é inferior a abertura, o corpo é representado por um retângulo preto. Figura 10 - Demonstração do Candlestick Existem alguns padrões gráficos que podem ser formados pelos candlesticks. A seguir, são apresentados os padrões mais conhecidos pelos analistas de investimento. Martelos e Enforcados Os martelos e os enforcados são representados por um candle cujo corpo encontra-se na parte superior da sombra. A informação sobre a cor do corpo (alta ou baixa) não é considerada. A sombra inferior deve ser longa e ter, no mínimo, o dobro do tamanho do corpo [17]. A figura 11 representa um martelo e um enforcado. Chamamos de martelo (takuri em japonês), quando o candle encontra-se após uma tendência de baixa, como se o mercado estivesse martelando uma base. O martelo indica uma possível reversão de baixa para alta. O enforcado ocorre quando o candle aparece em uma tendência de alta e indica uma possível tendência de baixa. 32 Figura 11 – Representação de um martelo ou enforcado Martelo Invertido O martelo invertido é semelhante ao martelo porém o corpo encontra-se na parte inferior da sombra do candle. Ocorre durante uma tendência de baixa e pode indicar uma possível reversão [17], conforme exemplo na figura 12. Figura 12 – Exemplo de um martelo invertido Nuvens Negras É um padrão de dois candles que indica uma possível reversão após um candle de alta. Conforme a figura 13, o primeiro candle produz um corpo de alta forte. O segundo candle tem sua abertura acima do fechamento do dia anterior e uma máxima ainda mais acima, porém seu fechamento ocorre próximo à mínima do candle e penetra o seu corpo [17]. Figura 13 – Exemplo de uma nuvem negra 33 Piercing É um padrão de dois candles que indica uma possível reversão após um candle de baixa. O primeiro candle produz um corpo de baixa forte. O segundo candle tem sua abertura abaixo do fechamento do dia anterior e uma máxima ainda acima da abertura, porém seu fechamento ocorre próximo a máxima do candle anterior e penetra seu o corpo [17]. O piercing é demostrado na figura 14. Figura 14 – Exemplo de um piercing Estrelas As estrelas são definidas por candles com corpos pequenos e cujo valor de abertura é normalmente superior ao valor de fechamento do candle anterior. As estrelas podem ocorrer em tendências de alta ou tendências de baixa. Nas tendências de alta elas são chamadas de estrelas da tarde e nas tendências de baixa de estrelas da manhã. A estrela é chamada de doji quando não possui corpo. O doji ocorre mais vezes que as outras estrelas e representa um aviso de que a tendência anterior pode estar acabando [17]. As figuras 15, 16, 17 e 18 são exemplos de estrelas. Figura 15 – Exemplo de estrela doji Figura 16 – Exemplo de estrela da manhã Figura 17 – Exemplo de estrela da tarde 34 Existe um outro tipo de estrela que seria o equivalente a um “enforcado invertido” e é chamada de estrela que atira para o céu. A estrela que atira para o céu ocorre durante uma tendência de alta e indica uma possível reversão. Figura 18 – Exemplo de estrela que atira para o céu Padrão de Engolfo O Padrão de Engolfo é um sinal de reversão composto de candles de cores opostas. Ocorre quando o corpo do primeiro candle é menor que o corpo do segundo candle. É chamado de engolfo de baixa quando, durante uma tendência de alta, o primeiro candle representa uma alta e o segundo representa uma baixa. O engolfo de baixa indica uma possível tendência de baixa. Quando o primeiro candle representa uma baixa e o seguinte uma alta, durante uma tendência de alta, o padrão formado é chamado de “engolfo de alta” e simboliza uma possível tendência de alta [17]. O padrão de engolfo é apresentado nas figuras 19 e 20. Figura 19 – Exemplo engolfo de baixa Figura 20 – Exemplo engolfo de alta 35 2.3. Alternativas de Predição com Aprendizado de Máquina Nesta seção, são apresentadas algumas alternativas de Predição com Aprendizado de Máquina propostas para auxiliar nas tomadas de decisão em mercado de ações. 2.3.1. Redes Neurais Artificiais Redes Neurais são modelos matemáticos inspirados em neurônios biológicos, propostos por McCulloch e Pitts em 1943. Procuram simular, de forma aproximada, o funcionamento do cérebro humano [42]. As redes neurais permitem a construção de uma arquitetura que realiza o aprendizado através de exemplos. As conexões existentes entre os neurônios (sinapses) armazenam valores que são ajustados no momento do aprendizado. Estes valores são conhecidos como pesos sinápticos e são responsáveis por expressar o conhecimento adquirido durante este processo. Cada neurônio possui um limiar de excitação (bias), que determina se ele irá ou não disparar. Quando o limiar de excitação é superado, o neurônio propaga o sinal através de uma função de ativação que descreve como o sinal deverá ser propagado para os neurônios seguintes. As redes são projetadas de acordo com o problema no qual serão utilizadas. Uma arquitetura bastante utilizada é composta de três camadas de neurônios: uma camada de entrada, uma camada oculta e uma camada de saída. A camada de entrada é responsável por receber os dados a serem avaliados, a camada de saída fornece o resultado da rede e a camada oculta auxilia, refinando o processamento. [42] Durante o processo de avaliação, os dados são aplicados sobre os neurônios da camada de entrada. Dentro de cada neurônio, os valores de entrada são multiplicados pelo valor do peso de sua sinapse e, em seguida, somados. Se a soma ultrapassar um valor limite estabelecido (bias), propaga-se seu sinal pela saída (axônio) deste neurônio. Este processo é repetido em todos os demais neurônios da rede, até a camada de saída. O processo de aprendizagem é responsável por extrair o conhecimento de uma amostra de dados e ajustar as sinapses dos neurônios. As mudanças nos pesos ocorrem de acordo com a ativação dos neurônios. As conexões mais usadas são reforçadas enquanto que as demais são enfraquecidas. Classifica-se o aprendizado basicamente em três tipos: 36 • Aprendizado Supervisionado: utiliza um conjunto de amostras de entrada e suas respectivas saídas para realizar ajustes nos pesos sinápticos até que o erro entre os padrões de saída gerados pela rede alcance um valor de erro mínimo desejado[44]; • Aprendizado Não-supervisionado: utiliza os dados de entrada de forma a determinar suas propriedades estatísticas. Uma vez que a rede tenha se ajustado às regularidades estatísticas dos dados de entrada, ela desenvolve a habilidade de formar representações internas para codificar as características da entrada e, desde modo, criar novas classificações [44]; • Aprendizado Híbrido: combina-se o aprendizado supervisionado e o não- supervisionado. Assim, uma camada pode trabalhar com um tipo de aprendizado enquanto outra camada trabalha com o outro tipo[44]. Durante o treinamento supervisionado, utiliza-se usualmente o algoritmo Backpropagation [42] para atualizar os pesos sinápticos. Este algoritmo é uma generalização do método Delta para redes neurais de múltiplas camadas, onde os valores dos pesos são modificados na direção negativa do gradiente da função de erro. Ao apresentar um determinado valor de entrada a uma rede não treinada, produz-se uma saída aleatória. Comparando-se a saída ao valor esperado, obtém-se um valor de erro que é a diferença entre o valor obtido e o desejado. Em seguida, realiza-se o ajuste dos pesos sinápticos através da regra Delta, calculando-se o valor de erro e propagando-o para a camada anterior e assim, ajustando os pesos entre as conexões dos neurônios. Ao final, todos os neurônios têm seus pesos ajustados de modo a minimizar o erro da rede. O processo é repetido continuamente até que o erro alcance um determinado valor aceitável. As redes neurais artificiais têm sido amplamente utilizadas no mercado financeiro nos últimos anos. Dentre suas aplicações destacam-se a análise de preços, a classificação de papéis e a administração de portfólios. Algumas destas aplicações são descritas a seguir. Previsão de Séries Temporais A previsão de séries temporais é uma técnica que tem por objetivo sugerir os próximos pontos de uma determinada série, utilizando os pontos anteriores como entrada. Para isto, utiliza-se uma rede neural com uma quantidade de neurônios na camada de 37 entrada igual ao tamanho da janela de previsão. Durante o processo de aprendizado, apresentam-se n pontos à camada de entrada e o ponto seguinte como resultado esperado. Em seguida, a rede é capaz de definir os próximos pontos da série. [5] [13] [24] Predição de Tendências A predição de tendências funciona de forma semelhante a previsão de séries temporais. O aprendizado utiliza a série de preços e uma série com as respectivas tendências. A rede recebe os pontos que compõem a janela de previsão e deverá ser capaz de identificar a tendência subseqüente. [6] [25] [26] Sugestão de Compra e de Venda Uma rede neural pode aprender sugestões de compra e de venda, com base em dados gerados por analistas. [27] sugere o treinamento de redes neurais utilizando o histórico de ordens de compra e de venda de um investidor ao longo de um período. As amostras de treinamento utilizam os pontos que compõem a janela de previsão e a ordem que foi dada naquele momento. Após o treinamento, a rede é capaz de sugerir novos pontos de compra ou de venda, baseando-se nos critérios adotados pelo analista. Detecção de Padrões Podemos utilizar redes neurais para detectar padrões grafistas em uma série de ações. Para isto, a rede deve ser treinada a partir de um conjunto composto de amostras de pontos e das respectivas definições de padrões. [28] 2.3.2. Algoritmos Genéticos Os algoritmos genéticos foram propostos por John Holland em meados da década de 60 para resolver, de forma aproximada, problemas de otimização e de busca. São algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva, tais como hereditariedade, mutação, seleção natural e crossing over. [44] Em algoritmos genéticos, o universo de soluções do problema é representado por populações descritas pelos cromossomos. Novas gerações são obtidas a partir de cruzamentos de gerações anteriores e ocorre então um processo de seleção de indivíduos 38 que simula o processo de seleção natural. O critério de parada pode se basear em um número máximo de gerações (iterações) ou quando não houve melhora nas soluções (melhor solução obtida até aquele momento) [44]. Os algoritmos genéticos funcionam da seguinte forma: primeiro gera-se uma população inicial com indivíduos que são possíveis soluções. As soluções da população inicial são criadas aleatoriamente ou podem ter sido geradas a partir de uma base de dados. Em seguida, as soluções da população interagem, misturam-se e produzem “filhos” que compõem uma nova população. Em cima da nova população, é feita uma seleção para a manutenção dos indivíduos que melhor se adaptam ao “ambiente”, ou seja, que estão mais próximos da qualidade de solução desejada. O cruzamento, ou crossover, é a geração de um novo indivíduo que herda características dos indivíduos pais através do código genético. No caso, o código de um indivíduo é representado por (conjuntos de) seqüências de bits. Existem várias formas de se realizar o cruzamento. Por exemplo, pode-se realizá-lo em um único ponto predefinido ou selecionado aleatoriamente. Também é possível realizar-se o cruzamento com dois ou mais pontos. A mutação tem a intenção de prevenir que todas as soluções do problema dessa população caiam em um ponto ótimo local. A operação de mutação muda aleatoriamente alguns componentes da solução, gerando um indivíduo diferente. Algumas aplicações de algoritmos genéticos foram propostas para o mercado de ações. A seguir, descrevem-se algumas. Seleção de portfólio A seleção de portfólio é um problema de otimização que visa a escolher ações da bolsa que melhor correspondam ao perfil do investidor. Os critérios de seleção podem minimizar o risco de investimento, maximizar o lucro ou ambos. Para isto, define-se uma população composta por indivíduos que representem as possíveis combinações de ações. As gerações refinam estas soluções até que se alcance uma população com as melhores combinações para o portfólio. Uma variação desta aplicação é utilizada em sistemas de controle de risco de portfólio. [14] [29] [30] 39 Tomada de Decisão usando Indicadores A tomada de decisão procura definir qual a melhor ação a ser tomada, dado um cenário específico. A população é composta por indivíduos que simbolizam a ação que deve ser tomada e pelos resultados de indicadores de Análise Técnica. Podem ser usados na composição do indivíduo os últimos n resultados de um indicador ou a combinação das indicações de n indicadores. As populações são avaliadas utilizando uma série de dados com os preços das ações e selecionando os indivíduos com melhores resultados baseados em suas ações. [31] [32] Geração de Regras em cromossomos A geração de regras funciona de forma semelhante à tomada de decisão, porém, sua principal diferença é que os cromossomos da população final contêm instruções que representam uma condição específica de qual é a melhor ação a ser tomada. A cada geração, os indivíduos são avaliados junto a uma série de dados com os preços das ações, corrigidos através de mutação ou simplesmente retirados da população. O conhecimento gerado pela população final pode ser usado por um agente. [33] [34] [35] 2.3.3. Aprendizado por reforço O aprendizado por reforço (reinforcement learning) é uma técnica baseada na psicologia animal e define o aprendizado através de recompensas positivas ou negativas recebidas quando ocorre uma ação. De forma análoga ao aprendizado não-supervisionado de redes neurais artificiais, procura extrair o conhecimento de um ambiente desconhecido através de experiências positivas ou negativas, após a execução das ações possíveis [44]. O agente pode realizar o aprendizado utilizando uma das abordagens descritas a seguir. • Agente baseado na função utilidade – aprende uma função utilidade sobre estados e a utiliza para selecionar ações que maximizem a utilidade esperada do resultado. O agente baseado na função utilidade adota uma das três estratégias básicas: o Estimativa de Utilidade Direta – utiliza a recompensa observada de um estado em diante como evidência direta para a aprendizagem da sua utilidade. Parte do pressuposto que a utilidade de um estado é a recompensa total deste estado em diante. 40 o Programação Dinâmica Adaptativa – aprende o modelo de transições e a função de recompensa do ambiente a partir de observações, durante a execução de um Processo de Decisão de Markov (MDP). o Diferença Temporal – atualiza estimativas de utilidade para corresponder às de estados sucessores baseando-se na diferença entre as utilidades dos estados transitados. É uma aproximação da Programação Dinâmica Adaptativa que não depende de um modelo para iniciar o processo de aprendizagem. • Aprendizagem de uma função de ação-valor – aprende uma função ação-valor (também chamada de função Q) que fornece a utilidade esperada de se adotar uma ação dado um estado específico. • Agente Reativo – aprende uma política qualquer que faz o mapeamento direto de estados em ações. Uma das principais vantagens do uso de reinforcement learning é a possibilidade de eliminar a codificação manual de estratégias de controle de um agente, fazendo com que ele esteja sempre aprendendo e corrigindo seu conhecimento através de suas ações. A seguir, descrevem-se algumas aplicações de reinforcement learning para o mercado de ações: Seleção de portfólio A seleção de portfólio através de reinforcement learning utiliza programação dinâmica adaptativa para realizar o aprendizado. As possíveis soluções são modeladas como estados do agente, que aprende as melhores seleções a partir de uma série de preços. Após o período de aprendizado inicial, o agente pode ser utilizado para selecionar as ações no ambiente real e continuará aprendendo e se adaptando à medida que vai executando novas ações. [37] Geração de Regras para tomada de decisão Esta aplicação utiliza um agente reativo que aprende uma política inicial e, em seguida, utiliza programação dinâmica adaptativa para correção do modelo. Os estados são compostos de condições de mercado e de carteira. As condições de mercado fornecem dados de eventos passados e futuros, tais como tendências e eventos. A carteira é composta 41 pelas ações que foram compradas. O agente deve decidir por executar uma ação de compra ou venda de determinados papéis e assim compor a carteira de investimentos. Os trabalhos relacionados a esta aplicação sugerem que sejam utilizados até três papéis da bolsa de valores para que o problema não fique muito complexo. Durante a execução, o agente determinará as regras de compra e de venda na forma de políticas que são continuadamente revisadas. [36] [38] 2.4.Conclusão Este capítulo apresentou de forma aprofundada o mercado de ações e as teorias de análise de investimento necessárias para a implementação dos indicadores de Análise Técnica. Os indicadores são utilizados pelo planejador automático na forma de sensores que fornecem informações quanto ao mercado de ações e a evolução dos preços. A Análise Técnica ainda fornece outras ferramentas além de indicadores tais como: padrões gráficos, interpretação de candlesticks e “suporte e resistência”. Apesar destas outras ferramentas não terem sido usadas neste trabalho, fez-se importante documentá-las visto que poderão ser utilizadas em trabalhos futuros. O capítulo também apresentou alternativas computacionais para a predição de preços no mercado de ações. Cada alternativa foi descrita, comparada com a abordagem atual e exemplificada através de trabalhos relacionados. 42 Capítulo 3 - Planejamento Baseado em MDPs e POMDPs Planejamento baseado em processos de Markov (MDPs) é um método utilizado para resolver problemas não determinísticos, através do cálculo de probabilidades. O problema de planejamento é definido como um problema de otimização, sendo possível utilizar diferentes algoritmos para alcançar o melhor resultado. Os MDPs podem ser classificados como totalmente observáveis, quando as informações necessárias para saber qual o estado corrente estão disponíveis ao controlador (agente), e parcialmente observáveis, quando as informações não estão disponíveis. Em ambientes parcialmente observáveis, o estado atual e o resultado das possíveis ações não são conhecidos. Para tomar decisões, o controlador precisa raciocinar com base nas observações sobre o estado do mundo, que consegue obter através de sensores. Como não se tem a informação completa, o raciocínio deve levar em consideração as probabilidades de se estar em cada estado. De acordo com Markov, as probabilidades de transições dependem exclusivamente do estado atual, e não são influenciadas pelos estados anteriores. 3.1. Domínios Totalmente Observáveis A sigla MDP2 é usada normalmente para designar problemas onde o domínio é totalmente observável. Um MDP é um sistema estocástico de transição de estados com uma distribuição de probabilidade em cada transição, formalmente representado pela tupla ∑ = (S , A, P, C, R) [16], onde: 2 • S é um conjunto finito de estados. • A é um conjunto finito de ações. Markov Decision Processes 43 • Pa ( s' | s ) , onde a ∈ A , s e s' ∈ S , e P é uma distribuição de probabilidade. Pa ( s' | s ) indica probabilidade de, ao se executar uma ação a no estado s, alcançar o estado s’. Para cada s ∈ S , se existir a ∈ A e s' ∈ S tal que Pa (s' | s ) ≠ 0 , então ∑ Pa (s' | s) = 1 . s '∈S • C : S × A → ℜé uma função que atribui um custo para cada estado e ação. • R : S → ℜ é uma função que atribui uma recompensa a cada estado. O conjunto A(s) das ações que podem ser executadas a partir do estado s é definido conforme a fórmula: A(s) = {a ∈ A | ∃ s’ ∈ S, Pa (s´|s) ≠ 0} O resultado do planejamento é um plano que especifica a ação que deve ser executada em cada estado. O plano é representado através de uma política π que mapeia todos os estados em ações: π : S → A. A política é gerada pelo planejador e executada por um controlador (ou agente) que observa qual estado é alcançado pela ação (de acordo com o não-determinismo de cada ação). A execução de uma política corresponde a uma seqüência infinita de estados, a qual é chamada de história. Cada história corresponde a uma seqüência de estados, que são as cadeias de Markov. Uma política π determina a probabilidade de uma história h ocorrer. Esta probabilidade pode ser calculada através da equação P(h | π) = Πi ≥ 0 Pπ (si+1| si). 3.1.1. Função de Utilidade A função de utilidade descreve o objetivo do planejamento baseado em MDPs. É calculada a partir dos custos e recompensas definidos pelo modelo. Os custos e recompensas representam uma condição mais geral do que um conjunto de estados finais desejados, porque provêem uma maneira quantitativa de representar preferências por toda a execução do caminho do plano. Define-se a utilidade em um estado s com a ação a como V(s,a) = R(s) – C(s,a), e a utilidade da política em um estado como V(s|π) = R(s) – C(s, π(s)). A função de utilidade da história h induzida pela política π é descrita a seguir: V(h|π) = Σi≥0 (R(si) – C(si,π(si))) 44 O fator de desconto é utilizado para garantir que uma história tenha um horizonte finito. Define-se um fator de desconto γ, com 0 < γ < 1, que faz com que o custo e a recompensa acumulada nos passos mais tardios tenha menos influência em relação aos acumulados nos primeiros passos. Acrescentando o fator de desconto, descreve-se a função de utilidade da história h da seguinte forma: V(h|π) = Σi≥0 γi (R(si) – C(si,π(si))) Dada uma política, podemos calcular sua função utilidade levando em conta a probabilidade das histórias geradas por ela. Seja Σ um sistema estocástico e H um conjunto de todas as histórias possíveis de Σ, então, a utilidade esperada de π é: E(π) = Σh∈H P(h|π) V(h|π) A política π* é chamada de política ótima para o sistema estocástico Σ, se E(π*) ≥ E(π) para qualquer política π gerada por Σ, ou seja, se π* tem a utilidade máxima esperada. Para que a política ótima seja calculada, é necessário calcular a utilidade esperada E(s) para cada estado s. Definimos Q(s, a) como a relação recompensa/custo esperada no estado s quando se executa a ação a: Q(s, a) = R(s) - C(s, a) + γ Σs’ ∈ S Pa(s’|s) E(s’) De acordo com o Teorema de Bellman [2], a ação mais eficiente para o estado s será a ação prevista na política ótima E(π*) e ela é calculada utilizando a Equação de Bellman E ( s ) = arg max Q( s, a ) . De acordo com isso, é preciso otimizar o benefício para cada a∈ A estado, considerando seus estados subseqüentes. Para todo s ∈ S, chamamos Eπ*(s) de recompensa/custo mais eficiente no estado s. Então, a partir da equação de Bellman temos: Eπ ∗ ( s ) = arg max{R(s ) − C ( s, a) + γ a∈A ∑ Pa ( s'| s) Eπ ∗ (s ' )} s '∈S 3.1.2. Algoritmos A seguir, apresentam-se os dois algoritmos para planejamento automático de MDPs. A principal diferença entre eles é a abordagem: enquanto o Policy Iteration foca exclusivamente na alteração da política como um todo, o Value Iteration verifica se existe um ganho alterando a ação apenas do estado em questão [16]. 45 Policy Iteration O algoritmo Policy Iteration calcula uma política mais eficiente π, dados um sistema estocástico Σ e um fator de desconto γ. Ele começa com uma política gerada aleatoriamente e tenta refiná-la a cada iteração. O algoritmo é descrito no quadro 3. Iteração de política (Σ, C, γ) 1 πØ 2 selecione qualquer π’ ≠ Ø 3 Enquanto π’ ≠ π faça 4 π π’ 5 para cada s ∈ S, 6 Eπ(s) a solução do sistema de equações: 7 Eπ(s) = R(s) - C(s, π(s)) + γ Σs’ ∈ S Pπ(s)(s’|s) E(s’) 8 Para cada s ∈ S faça 9 Se ∃a ∈ A e Eπ(s) < (R(s) - C(s,a)) + γ Σs’ ∈ S Pπ(s)(s’|s) E(s’) 10 então π’(s) a 11 senão π’(s) π(s) 12 retorne(π) fim Quadro 3 – Algoritmo Policy Iteration No algoritmo, π’ representa a política corrente e π a política anterior. Nas linhas 1 e 2 do algoritmo, inicializa-se a política π com um valor vazio e π’ com uma política aleatória. Em seguida, realiza-se um laço enquanto π for diferente de π’. Durante as linhas 5, 6 e 7, calcula-se o sistema de equações de Bellman para todos os estados, baseando-se na política π. Caso exista alguma ação a que melhore o resultado de um determinado estado s, então esta ação substitui a ação que consta na política π’. Quando não existem mais modificações, encerra-se o algoritmo retornando a política π encontrada. Value Iteration O Value Iteration inicia-se selecionando aleatoriamente um custo estimado E0(s) para cada s ∈ S. Em seguida, procura refinar o valor de cada estado a cada iteração através da escolha de uma ação que maximize a recompensa/custo esperada. O critério de parada utilizado é: arg max | E n (s ) − E n−1 ( s ) |< ε s∈S 46 Esse critério garante que a política retornada é uma política ε mais eficiente, isto é, tem um custo esperado que não difere do otimizado por mais do que um pequeno número arbitrário ε. O algoritmo é descrito no quadro 4. Iteração de valores (Σ, C, γ) 1 Para cada s ∈ S, selecione qualquer valor inicial para E0(s) 2 K1 3 Enquanto K < número máximo de iterações faça 4 para cada s ∈ S faça 5 para cada a ∈ A faça 6 Q(s, a) R(s) - C(s, a) + γ Σs’ ∈ S Pa(s’|s) Ek-1(s’) 7 EK(s) maxa∈A Q(s,a) 8 π(s) maxa∈A Q(s,a) 9 KK+1 10 retorne(π) fim Quadro 4 – Algoritmo Value Iteration O algoritmo Value Iteration inicia determinando um valor utilidade inicial para todos os estados na linha 1 e em seguida realiza o laço entre as linhas 3 e 9 até que o número máximo de iterações seja alcançado. Durante cada iteração, verifica-se na linha 7 a ação a que maximiza a utilidade do estado em questão, sem alterar as ações dos estados subseqüentes. Em seguida, a ação a, que maximiza o estado s, passa a fazer parte da política π . Ao final das n iterações, o algoritmo retorna a política π refinada. Tanto Value Iteration quanto Policy Iteration são polinomiais em relação ao tamanho do espaço de estados, mas como o espaço de estados tende a ser enorme, eles dificilmente podem ser aplicados em domínios realistas. Muitas abordagens existem para reduzir esse problema de explosão do espaço de estados. O algoritmo Real Time Value Iteration, descrito brevemente a seguir, é um dos que tem sido aplicado com sucesso para tal [16]. Real Time Value Iteration A idéia do algoritmo é fazer uma busca para frente, partindo do conjunto de estados iniciais e chegar até o conjunto de estados correspondente aos objetivos que devem ser alcançados, mudando o valor de Q(s,a) somente nos estados que forem visitados [16]. O algoritmo Real Time Value Iteration não dá garantia de retornar a solução mais eficiente ou mesmo de que 47 termine. É possível que o algoritmo termine e retorne uma política eventualmente se o valor inicial do custo esperado E0(s) não for superestimado, ou seja, se E0(s) ≤ Eπ*(s), e se existir um caminho com probabilidade positiva de todo o estado para um estado objetivo. Se, no espaço de busca existir um caminho com probabilidade de cada estado para outro estado, então o algoritmo retorna uma política ótima. O problema dessa abordagem é que o modelo deve ser constituído de estados que correspondam aos objetivos. 3.2. Domínios Parcialmente Observáveis Um Processo de Decisão de Markov Parcialmente Observável (POMDP3) é uma estrutura que nos permite descrever um processo no qual um agente executa ações sem ser capaz de observar diretamente o estado subjacente. O agente tem então que decidir suas ações com base em algumas observações locais e em distribuições de probabilidade sobre os estados do mundo que está sendo modelado. O conjunto de probabilidades que determina estar em um estado específico em um determinado momento é chamado de crença. O domínio deve ser modelado como um sistema estocástico com transições de estado não-determinísticas, causadas por ações. As transições de estados realizadas por meio de ações também estão associadas a probabilidades específicas [16]. Formalmente, um POMDP é representado pela tupla ∑ = ( S , A, T , O, P, C , R) onde: • S é um conjunto finito de estados. • A é um conjunto finito de ações. • Ta ( s ' | s ) é uma distribuição de probabilidade. Para cada a ∈ A , s ∈ S e s '∈ S , Ta ( s ' | s ) é a probabilidade de atingir o estado s' depois de executar uma ação a em s. Para qualquer estado s e ação a, se existe s’ tal que Ta (s ' | s ) ≠ 0 , então ∑ T ( s' | s) = 1 . a s '∈S • O é um conjunto finito de observações. • Pa (o | s) é uma distribuição de probabilidade. Para cada a ∈ A , s ∈ S e o ∈ O , Pa (o | s) é a probabilidade de observar o no estado s após a execução de a. Para 3 Partially Observable Markov Decision Processes 48 qualquer estado s e ação a, se existe observação o tal que Pa (o | s) ≠ 0 , então ∑ P (o | s ) = 1 . a o∈O • C : S × A → ℜ é uma função que atribui um custo para cada estado e ação. • R : S → ℜ é uma função que atribui uma recompensa a cada estado. Os conjuntos de observações O e as distribuições de probabilidade em P introduzem o modelo de observação parcial. As informações sobre o estado em que se encontra o controlador são obtidas através de observações. O controlador pode não perceber diferenças entre os estados a partir das observações válidas. Dessa forma, diferentes estados do sistema Σ podem resultar na mesma observação. 3.2.1. Estado de Crenças Como o estado atual é desconhecido, é necessário calcular a distribuição de probabilidade de se estar em cada estado. Esta distribuição de probabilidade é chamada de estado de crença. Seja B o conjunto de todas as crenças possíveis, se b ∈ B é um estado de crença, a probabilidade de estar no estado s é denotada por b(s) , onde 0 ≤ b(s) ≤ 1, para todo s ∈ S e Σs’ ∈ S b(s) = 1. A função ba ( s ) calcula a probabilidade de alcançar estado s a partir de s’, executando uma ação a a partir do estado atual de crença b, ou seja, fornece o estado de crença subseqüente à execução de a no estado b. ba ( s) = ∑ Ta ( s | s' )b( s' ) s '∈S A função ba (o) calcula a probabilidade de observar o ∈ O, depois de ter executado uma ação a ∈ A, a partir do estado atual de crença b. ba (o) = ∑ Pa (o | s)ba ( s) s∈S Assim, dado um estado de crença b, a execução de uma ação a e a subseqüente observação de o resultam em um novo estado de crença definido por bao ,cujo valor pode ser facilmente tirado pela regra de Bayes [44]. A probabilidade de se observar o e estar no estado s, dado apenas que se executou a ação a pode ser calculada de duas formas: 49 • Multiplicando-se bao (s) (a probabilidade de estar em s, dado que se observa o após a execução de a) por ba(o) (a probabilidade de observar o após a execução de a), ou; • Multiplicando-se Pa(o|s)(a probabilidade de observar o dado que se está em s após a execução de a) por ba(s) (a probabilidade de se estar em s após a execução de a). Disso resulta que: bao ( s) = Pa (o | s)ba ( s) ba (o) As soluções de um POMDP são dadas através de uma política π : B → A que mapeia estados crença a ações. A política ótima é uma política que maximiza a possibilidade de alcançar benefícios futuros, determinada pela diferença entre as recompensas e os custos. Como mencionado anteriormente, o fator de desconto γ garante que uma história tenha um horizonte finito e é normalmente usado para gerar políticas que dão mais importância às recompensas e custos no curto prazo. 3.2.2. Função de Utilidade O custo de transição a partir de um estado de crença b, quando uma ação a é executada, é calculado pela função: C (b, a) = ∑ b( s)C (s, a ) s∈S A recompensa para um estado de crença b, quando uma ação a é executada, é calculada pela função: ρ (b, a ) = ∑ b( s)R( s) s∈S Sendo assim, podemos dizer que a função de utilidade de um estado de crença b com a ação a é: V (b, a ) = ∑ b(s)( R( s) − C ( s, a )) s∈S 3.2.3. Problema de Otimização O problema de planejamento em POMDPs pode ser encarado como um problema de otimização. Seu objetivo é a geração de uma política que determina, para cada estado de crença b, a ação a que maximiza o benefício esperado E(b). A equação para os estados de crença corresponde à equação de Bellman: E (b) = max{V (b, a ) + γ ∑ ba (o) E (bao )} a∈ A o∈O 50 Uma forma possível de se resolver os problemas POMDP é dada por algoritmos que convertem POMDPs em Processos de Decisão de Markov totalmente observáveis (MDPs), com base na crença de estados em vez dos estados de domínio. O MDP resultante é então resolvido por meio de algoritmos como o Policy Iteration [19] ou o Value Iteration [2]. No entanto, como o conjunto de estados de crença geralmente é infinito e contínuo, os POMDPs são computacionalmente muito difíceis de resolver. Normalmente, recorre-se a programação dinâmica [19] para lidar com o espaço de estados de crença. Mesmo assim, algoritmos que retornam políticas ótimas trabalham apenas com problemas muito pequenos. Para problemas reais são adotados algoritmos que buscam soluções aproximadas. A seguir explica-se o uso de programação dinâmica na solução do problema e um algoritmo que fornece solução aproximada, também usando programação dinâmica. 3.2.4. Algoritmos Para que seja possível resolver problemas POMDP diretamente e de forma exata, é necessário utilizar uma abordagem como a apresentada por Sondik [45] que utiliza múltiplas iterações de programação dinâmica. Define-se E como a função utilidade que mapeia estados de crença em valores de ℜ , representando o benefício que pode ser esperado a partir de cada estado de crença. Esse valor pode ser obtido para uma série de tempos sucessivos através da equação: E (b) = max{∑ b( s)( R( s) − C ( s, a )) + γ ∑ ba (o) E (bao )} a∈ A s∈S o∈O A estratégia básica para se resolver esse problema de horizonte infinito com fator de desconto é resolver o problema equivalente com horizonte finito até que a contribuição das parcelas futuras convirja para zero. Pode-se calcular o benefício de um estado de crença no caso de um horizonte finito de t transições, utilizando-se os valores dos benefícios para horizontes de t-1 transições, segundo as fórmulas a seguir. Et (b) = max{∑ b( s)( R( s) − C ( s, a )) + γ ∑ ba (o) Et −1 (bao )} , para t > 0 a∈A s∈S o∈O E0 (b) = max{∑ b(s)( R( s) − C ( s, a ))} a∈ A s∈S 51 Nessa forma, a equação representa um problema de programação dinâmica em cima de um espaço de estados de crença contínuo. A solução do problema, conforme demonstrado em [45], decorre do fato da função ser uma função linear em trechos e convexa4, podendo ser então expressa por: Et (b) = max{∑ α ( s)b( s)} α∈Γt s∈S O valor em cada horizonte finito t é obtido através de um conjunto de funções Γt = {α 0 ,α1 ,...,α m } . Cada α é uma função que associa um valor de benefício a cada um dos possíveis estados. Pode ser também encarada como um vetor em um espaço vetorial de |S| dimensões, onde cada coordenada contém um valor de benefício para um estado. Nesse caso, representando o estado de crença também como um vetor, poderia usar alternativamente a notação vetorial: Et (b) = max {α • b} α ∈Γt Cada vetor α está associado a uma ação a e corresponde a uma região convexa do espaço de estados de crença. Essa região é delimitada por hiperplanos e o benefício gerado com a ação a pode ser calculado através do produto escalar de α pelo estado de crença. Assim, pode-se adaptar a função utilidade original para calcular a melhor ação a para um estado de crença b, em um horizonte t, utilizando o vetor α, conforme a seguir. E t (b) = max{ ∑ b( s )( R ( s ) − C (s , a )) + γ ∑ ba (o) max { ∑ α ( s )bao ( s )}} a∈ A s∈S o∈O α ∈Γt −1 s∈S A mesma equação pode ser descrita conforme abaixo, caso a função ba(o) seja substituída por sua fórmula: E t (b) = max{ ∑ b( s)( R( s) − C (s, a )) + γ ∑ arg max ∑ ∑ Ta (s' | s) Pa (o | s' )α ( s' )b( s)}} a∈A s∈S o∈O α ∈Γt −1 s∈S s '∈S Esta fórmula será dividida em duas partes e utilizada durante o cálculo do conjunto de funções Γt . Para todo estado de crença b, Γt deve conter um vetor, associado a uma ação a, que permite calcular o benefício esperado a partir de b. Nota-se que vários vetores α podem estar associados a uma mesma ação, mas cada α está associado a uma única ação. Γt é calculado a partir do Γt −1 , conforme explicado a seguir. 4 A função linear em trechos e convexa (conhecida em inglês como convex piecewise-linear function) é uma função convexa formada por pontos que definem intervalos preenchidos por trechos lineares. 52 Para cada ação a é preciso definir o conjunto de vetores que permitem o cálculo do benefício esperado quando a ação a é executada em qualquer estado de crença. Chamemos esse conjunto de Γta . Para calcular Γta , é necessário gerar os conjuntos Γta ,* para cada ação e Γta, o para cada par de ações e observação. Γta ,* contém um único vetor αa,∗, que representa o benefício gerado pela execução da ação a no estado corrente, e é definido como: Γta ,* = {αa,∗} α a,* ( s ) = R ( s ) − C ( s, a) O conjunto Γta, o contém vetores que contabilizam os benefícios a partir dos estados subseqüentes: Γta ,o = {{γ ∑ Ta (s'| s) Pa (o | s' )α i (s' ) | ∀s ∈ S} | ∀α i ∈ Γt −1} s '∈S Em seguida é necessário criar o conjunto Γta a partir da soma de Γta ,* pela somacruzada5 de cada Γta, o para todas as observações o∈ O: Γta = Γta,* + Γta,o1 ⊕ Γta,o 2 ⊕ ... , para t>0 Γ0a = Γ0a,* Ao final, realiza-se a união dos conjuntos Γta para todas as ações a∈ A: Γt = {Γta | ∀a ∈ A} Esta abordagem otimiza o valor da função utilidade para todos os estados de crença. Porém, devido a grande complexidade do problema, modelos com poucos estados e observações tornam-se inviáveis. Por este motivo, algoritmos que geram soluções aproximadas são mais utilizados. As principais vantagens do uso de algoritmos aproximados são: o consumo inferior de memória e a resolução em menor tempo, pois as atualizações são aplicadas em um conjunto pequeno e específico de estados de crença ao invés de atualizar todos [18]. 5 O símbolo ⊕ denota o operador de soma-cruzada: A soma-cruzada é definida por dois conjuntos A = {a1, a2, ..., am} e B = {b1, b2, ..., bn} e produz um terceiro conjunto C = {a1 + b1, a1 + b2, ..., a1 + bn, a2 + b1, a2 + b2, ..., ..., am + bn}. 53 Point-Based Value Iteration Existem diversos algoritmos para resolução de POMDPs de forma aproximada. Neste trabalho, optou-se pelo uso do algoritmo PBVI6 [18] por gerar soluções aproximadas de boa qualidade e em um número de iterações aceitável. Dado um conjunto de solução Γt −1 , a solução aproximada procura definir um operador de backup exato para cada estado de crença, ou seja, um único vetor α a ser mantido. O operador de backup do algoritmo PBVI retorna um vetor α que passa a ser válido por toda a região ao redor da solução do estado de crença b. Sendo assim, assume-se que outros estados de crença parecidos com o estado de crença b (ou seja, que estão na mesma região) possuem características semelhantes tais como: a ação escolhida que direciona para mesma equação Et −1 , e o estado de crença futuro b’. A resolução de um PBVI começa obtendo-se o conjunto Γt a partir do conjunto Γt −1 , como na solução completa. A cada nova iteração, expande-se o conjunto de estados de crença corrente Bc, que contém apenas estados de crença aproximados. Primeiramente, calculam-se os conjuntos α a,* e Γta,o , onde a ∈ A e o ∈ O. O conjunto Γta, o contém vetores que contabilizam os benefícios a partir dos estados subseqüentes: α a,* ( s ) = R ( s ) − C ( s, a) Γta ,o = {{γ ∑ Ta (s'| s) Pa (o | s' )α i (s' ) | ∀s ∈ S} | ∀α i ∈ Γt −1} s '∈S Em seguida, cria-se o conjunto Γta sobre um conjunto finito de crenças: Γta = {α a ,* + ∑ arg max{ ∑ α (s )bi (s )} | ∀bi ∈ Bc}, t > 0 o∈O α∈Γ ta ,o s∈S Γ0a = {α a,* } Ao final, forma-se o conjunto de soluções Γt com um elemento para cada estado de crença b∈ Bc. Cada conjunto Γta é composto por elementos que representam uma solução 6 Point-Based Value Iteration 54 da ação a∈ A para cada estado de crença b. Então, o conjunto de soluções Γt é formado pelo elemento do conjunto Γta relativo à ação a que resulta na melhor solução para o estado de crença b: Γt = {arg max{ ∑ α ba ( s )b( s )} | ∀b ∈ Bc} αba∈Γta s∈S Conforme mencionado anteriormente, o valor função da utilidade de qualquer estado de crença pode ser calculado através da equação: Et (b) = arg max{ ∑ α ( s)b( s)} α ∈Γt s∈S No quadro 5, demonstra-se o algoritmo PBVI propriamente dito. O algoritmo recebe como parâmetros o estado de crença inicial BInit, o conjunto inicial de soluções Γ0, o número desejado de expansões N e o horizonte de planejamento T. O parâmetro Γ0 é usando quando se deseja continuar o planejamento partindo-se de um conjunto soluções anterior e normalmente é iniciado utilizando-se um valor bem baixo, para que seja superado logo. O algoritmo acaba quando o número de expansões N é completado. Também é possível utilizar um critério de parada no algoritmo, quantidade limite de estados de crença, tempo ou quando um erro mínimo aceitável é alcançado. PBVI(BInit, Γ0 , N, T) 1 B = BInit Γ = Γ0 2 3 Faça N expansões 4 Faça T iterações 5 Γ = BACKUP(B, Γ ) 6 Bnew = EXPAND(B, Γ ) 7 B = B ∪ Bnew 8 retorne( Γ ) fim Quadro 5 – Algoritmo PBVI O algoritmo principal do PBVI é bem simples. Durante N iterações que serão responsáveis pelas expansões do conjunto de estados de crença, ele realiza o cálculo das utilidades e geração da política ótima para um horizonte T. A rotina de backup é normalmente encontrada em diversos algoritmos para resolução de POMDPs que calculam uma solução aproximada e serve para auxiliar a 55 função utilidade, tornando seu valor mais exato a cada iteração T [18]. Ela é responsável pelo calculo da função utilidade, para um conjunto de crenças B e um conjunto de soluções Γ atual. O algoritmo da rotina de backup é descrito no quadro 6: BACKUP(B, Γt −1 ) 1 Para cada ação a ∈ A 2 Para cada observação o ∈ O Para cada vetor solução α t ∈ Γt −1 3 α ta,o (s ) ← γ 4 s '∈S Γta ,o 5 6 7 8 9 ∑ Ta (s '| s) Pa (o | s' )α t (s ' ), ∀s ∈ S = Γta,o U {α ta,o } Γt = ∅ Para cada estado de crença b ∈ B αb = max[∑ b( s)( R(s ) − C ( s, a)) + ∑ maxa ,o{∑ α (s )b( s)}] a∈ A s∈S o∈O α ∈Γt s∈S Se αb ∉ Γt 10 Γt = Γt U{αb} 11 retorne( Γt ) fim Quadro 6 – Rotina Backup do Algoritmo PBVI Durante as linhas 1 a 5 da rotina BACKUP, calcula-se todos os valores de α para cada uma das ações a∈ A e observações o∈ O. Em seguida, seleciona-se a melhor ação a para o estado de crença b, maximizando a função utilidade. Ao final, retorna o conjunto Γt contendo apenas os vetores α das ações que maximizam os estados de crença. A rotina EXPAND seleciona os novos estados de crença a serem adicionados no conjunto finito de estados de crença, para um conjunto de crenças B e um conjunto de soluções Γ atual. A estratégia mais utilizada para a seleção dos estados de crença é a seleção aleatória, porém é possível adotar outras que serão detalhadas logo a seguir. Seleção de Crenças Aleatória7 A seleção aleatória é uma estratégia de seleção simples onde, como o nome já diz, seleciona aleatoriamente estados de crença. O algoritmo no quadro 7 demonstra como é 7 RA - Random Action 56 possível duplicar a quantidade de estados de crença de B, gerando estados de crença aleatoriamente. EXPANDRA(B, Γ ) 1 Bnew = B Γ = Γ0 2 3 Para cada estado de crença b ∈ B 4 S:= numero de estados 5 Para i = 0 até S 6 btmp[i] = rnduniforme(0,1) 7 Ordenar em btmp ordem ascendente 8 Para i = 1 até S – 1 9 bnew[i] = btmp[i + 1] - btmp[i] 10 Bnew = Bnew ∪ {bnew} 11 retorne(Bnew) fim Quadro 7 – Rotina Expand usando Random Action Simulação Estocástica com Ação Aleatória8 Esta estratégia seleciona novos estados de crença através da atualização dos estados de crenças que fazem parte do conjunto atual de estados de crença B. Para cada estado de crença b, seleciona aleatoriamente uma ação a, uma observação o e calcula o estado de crença seguinte. EXPANDSSRA(B, Γ ) 1 Bnew = B 2 Para cada estado de crença b ∈ B 3 s = rndmultinomial(b) 4 a = rnduniforme(A) s’ = rndmultinomial ( Ta (⋅, s) ) 5 o = rndmultinomial ( Pa (⋅, s' ) ) 6 bnew = bao 7 8 Bnew = Bnew ∪ {bnew} 9 retorne(Bnew) fim Quadro 8 – Rotina Expand usando Stochastic Simulation with Random Action 8 SSRA - Stochastic Simulation with Random Action 57 O algoritmo demostrado no quadro 8 tenta simular a incerteza da transição através da seleção aleatória do estado s, e do estado seguinte s’. A linha 2 garante que os estados de crença de B serão duplicados, a partir da repetição das linhas 3 a 9. Nas linhas 3 e 4, são selecionados um estado inicial s e uma ação a, e baseando-se neles, as linhas 5 e 6 selecionam um estado final s’ e uma observação o válidos. Em seguida, um novo estado de crença é gerado na linha 7 a partir da transição de b utilizando a observação o e a ação a selecionadas anteriormente. Simulação Estocástica com Ação Gulosa9 Semelhante ao SSRA, porém, a principal mudança neste algoritmo é que a ação a que maximiza a função utilidade baseada no estado de crença b é selecionada na linha 7 e utilizada na geração do estado de crença seguinte. O Algoritmo é demostrado no quadro 9. EXPANDSSGA(B, Γ ) 1 Bnew = B 2 Para cada estado de crença b ∈ B 3 s = rndmultinomial(b) 4 Se rnduniforme[0,1] < ε 5 a = rnduniforme(A) 6 Caso contrário a = arg max ∑α (s)b(s ),α → a ∈ A 7 α ∈Γ s∈S s’ = rndmultinomial ( Ta (⋅, s) ) 8 o = rndmultinomial ( Pa (⋅, s' ) ) 9 bnew = bao 10 11 Bnew = Bnew ∪ {bnew} 12 retorne(Bnew) fim Quadro 9 – Rotina Expand usando Stochastic Simulation with Greedy Action Simulação Estocástica com Ação Exploratória10 O algoritmo apresentado no quadro 10 realiza um forward search para cada ação (ao invés de selecioná-la aleatoriamente ou de forma gulosa) e gera um conjunto de crenças para cada ação. 9 SSGA - Stochastic Simulation with Greedy Action SSEA - Stochastic Simulation with Exploratory Action 10 58 EXPANDSSEA(B, Γ ) 1 Bnew = B 2 bnew = ∅ 3 Para cada estado de crença b ∈ B 4 Para cada ação a ∈ A 5 s = rndmultinomial(b) s’ = rndmultinomial ( Ta (⋅, s) ) 6 o = rndmultinomial ( Pa (⋅, s' ) ) 7 bnew = { bao } 8 9 Bnew = Bnew ∪ bnew 10 retorne(Bnew) fim Quadro 10 – Rotina Expand usando Stochastic Simulation with Exploratory Action De acordo com [39], o algoritmo PBVI demonstra-se bastante eficiente em resolver problemas POMDP, gerando boas soluções aproximadas. Os métodos de expansão sugeridos por ele são: a simulação estocástica com ação gulosa e a simulação estocástica com ação exploratória. Métodos de expansão aleatórios são utilizados para acelerar o tempo de planejamento, mas podem gerar algumas distorções devido à aproximação de estados de crença que estariam na fronteira entre dois ou mais outros estados. Estas distorções fazem com que estados sejam alcançados de forma errônea, não respeitando a tabela de transições. 3.3.Conclusão Neste capítulo, abordaram-se os dois domínios para o planejamento baseado em processos de Markov. O planejamento baseado em MDP é utilizado em domínios totalmente observáveis; já o baseado em POMDP é utilizado para domínios parcialmente observáveis. Desta forma, o POMDP é compreendido mais facilmente através da apresentação do MDP. Embora seja possível descrever a solução completa de um POMDP, sua utilização é praticamente inviável devido a sua complexidade computacional. Logo, é preciso recorrer a algoritmos aproximados para alcançar uma solução razoável. 59 Para que fosse possível calcular soluções aproximadas, selecionou-se o algoritmo PBVI que foi descrito integralmente, além de várias abordagens para a expansão do conjunto de estado de crença. Os métodos de expansão mais simples - que utilizam seleções aleatórias - são utilizados devido a sua eficiência computacional para alcançar as soluções, porém obtém resultados inferiores ou às vezes muito aproximados. Melhores resultados são obtidos através de métodos de expansão que implementam algoritmos gulosos. No entanto, sua complexidade é maior e às vezes torna inviável sua utilização. 60 Capítulo 4 - Metamodelo de Suporte à Decisão Este capítulo propõe um metamodelo que é utilizado para gerar o modelo POMDP e uma arquitetura para processá-lo, gerando políticas de investimento e avaliando-as. O metamodelo fornece instruções sobre como o modelo deve ser gerado, a partir da definição de seus elementos pelo usuário. O modelo contém informações sobre a composição dos estados, as observações e as probabilidades de transição entre os estados e serve de entrada para o planejador. 4.1. O Metamodelo O metamodelo define regras sobre como os estados, as transições, as observações e as probabilidades do POMDP são organizados e calculados a partir das definições do usuário. Cada item é explicado a seguir. • Estados - Os estados são compostos por uma parte determinística e outra não- determinística. A parte determinística representa o estado atual da carteira do investidor e pode ser definida pelo usuário, listando as situações possíveis. Basicamente, a parte determinística é usada para informar se o investidor está comprado, vendido ou fora do mercado, mas pode indicar também intensidades como “muito comprado”, “um pouco vendido”, ou outras características do posicionamento do investidor em relação ao mercado. A parte não-determinística pode ser formada por um ou mais componentes correspondentes à variação ou à média do preço, volume ou quantidade em um período. Normalmente, haverá componentes correspondentes a períodos diferentes em relação a cada data, como, por exemplo, a variação na semana anterior e a variação na semana seguinte dos preços de um ativo. A definição sobre como os dados são interpretados 61 também é fornecida pelo usuário. Os valores são classificados dentro de um conjunto discreto de faixas informado pelo usuário. Através desse mecanismo, o usuário pode, por exemplo, definir faixas para representar tendências de alta, de baixa ou neutra. Pode também definir faixas associadas às tendências, como “alta acentuada”, “pequena baixa”, etc. A seguir, apresenta-se um exemplo de definição de estados na tabela 1. Componente Determinístico Comprado Fora do Mercado ... Componente Não-Determinístico Tendência de Alta Tendência de Baixa Estável Tabela 1 – Exemplo de definição que produz 6 estados • • Comprado: investidor possui ação • Fora do Mercado: investidor não possui ação • Tendência de Alta: mercado em alta para a variação ≥ +1% • Tendência de Baixa: mercado em baixa para a variação ≤ -1% • Estável: mercado estável para o intervalo entre os dois. Observações - As observações devem ser definidas pelo usuário e serão fornecidas pelo sensor ou sensores que deverão compor o modelo. Os sensores devem ser selecionados de acordo com aqueles disponíveis no sistema, os quais implementam métodos de Análise Técnica e produzem indicações como “ponto de compra” ou “ponto de venda”. Os sensores podem ser compostos para fornecer resultados que incorporem mais de um método. O usuário pode então definir como traduzir as observações produzidas por sensores básicos em observações resultantes da composição. As definições de observações e interpretações do indicador são exemplificadas na tabela 2. Observação Ponto de Compra Ponto de Venda Indefinido Indicador Força Relativa Força Relativa Força Relativa Parâmetros valor_atual ≥ 0.2 e valor_anterior ≤ 0.2 valor_anterior ≥ 0.8 e valor_atual ≤ 0.8 - Tabela 2 – Exemplo de definição de observações • Ações, Transições e Custos - As ações podem ser definidas pelo usuário e são relacionadas à parte determinística do estado. Basicamente, utilizam-se as ações: comprar, vender e manter. Cada ação deverá definir as transições que modificam a parte 62 determinística do estado e seu custo. As transições dos estados do modelo são geradas a partir dessas definições, combinando as partes determinística e não-determinística dos estados. As transições entre os estados gerados a partir do exemplo da tabela 1 são demostradas na tabela 3. Neste exemplo, o custo de transição representa o custo de corretagem que é pago durante a compra e a venda das ações. Ação Compra Compra Compra Compra Compra Compra Compra Compra Compra Venda Venda Venda Venda Venda Venda Venda Venda Venda Nada Nada Nada Nada Nada Nada Estado Inicial Fora e Alta Fora e Alta Fora e Alta Fora e Baixa Fora e Baixa Fora e Baixa Fora e Estável Fora e Estável Fora e Estável Comprado e Alta Comprado e Alta Comprado e Alta Comprado e Baixa Comprado e Baixa Comprado e Baixa Comprado e Estável Comprado e Estável Comprado e Estável Fora e Alta Fora e Baixa Fora e Estável Comprado e Alta Comprado e Baixa Comprado e Estável Estado Final Comprado e Alta Comprado e Baixa Comprado e Estável Comprado e Alta Comprado e Baixa Comprado e Estável Comprado e Alta Comprado e Baixa Comprado e Estável Fora e Alta Fora e Baixa Fora e Estável Fora e Alta Fora e Baixa Fora e Estável Fora e Alta Fora e Baixa Fora e Estável Fora e Alta Fora e Baixa Fora e Estável Comprado e Alta Comprado e Baixa Comprado e Estável Custo 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 0 0 0 0 0 0 Tabela 3 – Exemplo de definição de observações • Probabilidades - As probabilidades de transições e de observações são geradas a partir da análise de séries históricas. Durante a geração do modelo, são geradas estatísticas sobre todas as transições e observações utilizando uma série de aprendizado. As probabilidades de transição referem-se às transições entre as partes não-determinísticas dos estados entre dois instantes consecutivos. As probabilidades de observação referemse à correspondência entre a parte não-determinística do estado associado a um instante e a observação gerada para aquele instante. Todos os valores observados na série de aprendizado são levados em conta para estabelecer as distribuições de probabilidade. 63 As probabilidades são calculadas da seguinte forma: • • Quantidade (estado alcançado e observação) / Quantidade de preços da série • Quantidade (transição entre estados x e estado y) / Quantidade de preços da série Recompensas - As recompensas estão relacionadas diretamente aos estados do modelo. Por exemplo, a definição de estados compostos de 3 valores possíveis para a parte determinística e 3 valores possíveis para a parte não-deterministica gera um modelo de 9 estados. O usuário deve definir qual é a recompensa ao alcançar cada um desses estados. As recompensas podem ser positivas ou negativas de acordo com a necessidade do modelo e devem ser especificadas de tal forma que os estados que geram lucro devem possuir recompensas positivas e os que causam perdas devem possuir recompensas negativas. A tabela 4 representa as recompensas para os estados do exemplo da tabela 1. As recompensas positivas incentivam a permanência os estados que geram um bom resultado ao investimento e as recompensas negativas definem os estados que devem ser evitados. Estado Final Fora e Alta Fora e Baixa Fora e Estável Comprado e Alta Comprado e Baixa Comprado e Estável Recompensa -10 10 0 20 -20 5 Tabela 4 – Exemplo de definição de recompensas Um bom modelo pode depender especificamente do ativo ou do período de tempo no qual é aplicado. Sendo assim, procura-se proporcionar um meio onde se possa criar e avaliar os modelos. Dada a complexidade do planejamento POMDP, o modelo deve possuir poucos estados, caso contrário, a geração automática de políticas de investimento pode não ser viável. Inicialmente, o metamodelo proposto adotou apenas o mercado à vista, analisando uma única ação ou índice. 64 4.2. Arquitetura Geral do Protótipo Para dar suporte à definição pelo usuário dos dados que levam à geração do POMDP, foi proposta uma arquitetura geral do ambiente para modelagem de contextos de investimentos e simulações. Esta arquitetura é dividida em módulos. Controlador de Contexto Planejador Usuário Gerador de Probabilidades Séries Temporáis Gerador de Observações Sensor 1 Mercado de Ações Séries de Teste Sensor x Mercado Contexto: -Estados -Ações -Transições -Modelo de Observações -Probabilidades -Politicas Agente Simulador Usuário Figura 21 – Visão geral da Arquitetura do Protótipo Esta arquitetura também é responsável pela geração do POMDP propriamente dita, pela busca de políticas eficientes através dos algoritmos de planejamento e pela simulação da execução de políticas, bem como a execução destas políticas em tempo real. Esta arquitetura é apresentada na figura 21 e descrita em seguida. 4.2.1. Contexto Os modelos POMDP são arquivados junto com as políticas geradas pelo planejador. Desta forma, fica fácil recuperar os dados durante as simulações, sem haver necessidade de utilizar o planejador novamente. Chamamos de contexto o conjunto de informações relacionadas a um único modelo. O contexto é formado tanto pelas definições do usuário que permitem gerar o POMDP, como pelo modelo gerado e pelas políticas. Para uma única ação da bolsa, podem existir diversos contextos, dependendo das configurações do metamodelo. 65 O módulo Controlador de Contexto é responsável por gerenciar os contextos e fornecer a interface que permite ao usuário criar as definições de um modelo POMDP. Com base nessas definições, são formados os estados, as observações e as recompensas do modelo. Em seguida, os módulos “Gerador de Probabilidades” e “Gerador de Observações” são ativados para que se possam calcular as tabelas de transições e de probabilidades de observações. De posse do modelo POMDP completo, é possível iniciar o planejamento. Durante este processo, o módulo Planejador é acionado e monitorado até o fim, quando é gerada a política para o POMDP definido. Então, a política é guardada no contexto e fica disponível para as simulações e/ou execuções em tempo real. 4.2.2. Probabilidades As probabilidades são calculadas pelo módulo Gerador de Probabilidades. Este módulo analisa uma série temporal armazenada no banco de dados para atribuir probabilidades de transições entre os estados e probabilidades de observações. É importante utilizar um longo intervalo de tempo durante a análise para que possam ser estimadas probabilidades representativas. O período utilizado na geração de probabilidades não deve se sobrepor aos intervalos de tempo da avaliação das políticas. Utilizam-se os estados gerados pelo Controlador de Contexto, com base nas definições feitas pelo usuário. As probabilidades de transição são obtidas através da contagem do número de vezes em que uma dada transição entre as partes nãodeterminísticas dos estados ocorreu. Ao final do processo, é gerada uma tabela de transições para cada ação. As tabelas especificam as probabilidades de transição entre os estados completos, incluindo as partes determinística e não-determinística. Para as mudanças entre estados onde a parte determinística é transformada de acordo com o especificado pelo usuário para a ação, a probabilidade de transição corresponde à probabilidade de transição calculada para as partes não-determinísticas. As transições entre os demais estados recebem probabilidade nula. Assume-se assim que o usuário isoladamente não tem capacidade de influenciar o mercado. Por outro lado, assume-se também que há sempre liquidez para que o usuário possa comprar ou vender os ativos pelo preço de mercado. As probabilidades de observação são obtidas através da contagem do número de vezes nos qual uma observação é verificada em um determinado estado. Durante este 66 processo, utiliza-se o módulo Gerador de Observações que analisa a série de dados e a transforma em observações. Ambas as tabelas de probabilidades podem ser ajustadas ou inseridas manualmente pelo usuário, baseado em sua experiência. 4.2.3. Observações As observações são geradas por meio de sensores que implementam os conceitos da Análise técnica e traduzem os dados do mercado em observações discretas, baseadas nas definições do metamodelo fornecidas pelo usuário. Podem ser geradas por um único indicador, por um padrão gráfico ou por uma combinação. O módulo Gerador de Observações é responsável por analisar as séries de dados e por produzir as observações, de acordo com as definições do usuário e os dados fornecidos pelo Módulo de Mercado. As observações são utilizadas durante a geração de probabilidades e a aplicação das políticas em simulações ou em tempo real, para suporte à decisão. 4.2.4. Planejamento e Simulação O módulo Planejador é responsável pelo processo de planejamento automatizado que gera políticas. As políticas são armazenadas no banco de dados através do Controlador de Contexto e utilizadas em simulações futuras ou em tempo real. Este módulo Planejador também gerencia o uso dos algoritmos de planejamento disponíveis para resolver POMDPs de acordo com a preferência do usuário. O Módulo de Mercado é responsável pela aquisição de dados a partir de uma corretora ou diretamente da bolsa. Disponibiliza ferramentas para que o usuário possa gerenciar as séries de dados disponíveis no banco de dados e criar novas séries a partir da importação de dados de mercado. O Módulo de Mercado possui uma interface gráfica para cadastrar os possíveis provedores de conteúdo e realizar a tradução dos dados11. Assim, é possível cadastrar mercados de ações do mundo todo, ou mesmo, diferentes provedores de dados para uma mesma bolsa. A tradução é necessária pois cada provedor pode possuir um formato de dados diferente. Por exemplo, a coluna de preços das ações pode ter nomes ou 11 Os provedores podem possui modelo de dados e/ou dicionário de dados diferentes do utilizado pelo ambiente. A definição das representações dos provedores e suas equivalências com o modelo de dados do ambiente são cadastradas pelo usuário durante a inserção de um novo provedor de dados. 67 precisões de valores diferentes, então, é necessário realizar um ajuste para que seja possível realizar a leitura dos dados. Durante as avaliações, o Módulo de Mercado pode simular as informações sobre o mercado de ações usando dados históricos fornecidos pelo Módulo Simulador. Este módulo é responsável por receber as ordens de compra e venda do Módulo Agente, registrar os estados da carteira de investimento e avaliar o resultado financeiro. O Módulo Simulador também pode funcionar como uma bolsa de valores em conjunto com o Módulo de Mercado, enviando dados de séries salvas no banco de dados de testes. Estas séries podem ter sido geradas através de informações de mercado reais e selecionadas devido a algum fator histórico relevante, sejam eventos importantes ou apenas cenários. Os dados da base de testes também podem ter sido gerados pelo próprio usuário para testar o comportamento de cenários fictícios. O Módulo Agente é responsável por executar as políticas. É ele que controla e gera os novos estados de crença, baseado nas observações fornecidas pelo Gerador de Observações, e verifica qual a ação que deve ser executada. Durante a simulação, a cada novo período (que pode ser de 15 minutos, hora, dia semana etc, de acordo com a série), uma ação é executada e uma observação é registrada. A cada nova observação, um novo estado de crença é atingido e uma nova ação é executada. Durante uma simulação, apenas o Módulo Simulador tem acesso às informações financeiras do mercado, sendo este responsável pela avaliação de resultados. O Módulo Agente só tem acesso ao estado de crença atual, às observações e às políticas que informam a ação que deve ser executada. Durante uma simulação em tempo real, as ações podem ser informadas ao usuário como uma sugestão e alteradas antes de serem enviadas ao Módulo Simulador. Ao final de cada simulação, relatórios sobre a qualidade das políticas são gerados automaticamente. 4.3.Conclusão Este capítulo apresentou as definições do metamodelo proposto para gerar o modelo POMDP no contexto de investimentos. O metamodelo é fundamental para que se possa descrever o contexto de investimentos e como cada item é formado e interpretado. Cada componente do metamodelo (estados, observações, etc), assim como a definição dos seus itens, é flexível e definível pelo usuário/investidor. Assim, é possível descrever não só o 68 que é um estado (composto de tendências de preço), mas também o que é uma tendência (tendência de alta quando preço > 1% e de baixa quando preço < 1%). O modelo POMDP é então gerado a partir destas definições e utilizado pelo planejador automático. O capítulo ainda apresenta a definição de uma arquitetura básica para a confecção de uma ferramenta para auxiliar modelagem de contextos e simulação das políticas. Esta ferramenta fornece um ambiente completo para que se possa definir cada componente do contexto de investimentos, gerar o modelo POMDP, realizar o planejamento e avaliar o resultado das políticas geradas. A arquitetura é constituída de módulos que são responsáveis por cada uma das funções da ferramenta e prevê a possibilidade de expansão para incluir novos sensores, novos algoritmos de planejamento e novos provedores de dados (mercados ou corretoras). A seguir, o capítulo 5 demostra como o protótipo foi implementado seguindo as especificações da arquitetura proposta. No capítulo 6, é apresentado um modelo básico de investimentos que foi definido através das instruções do metamodelo e seus resultados. 69 Capítulo 5 – Implementação A fim de estudar as políticas de investimento no mercado de ações de acordo com o metamodelo descrito no Capítulo 4, foi desenvolvida uma ferramenta na qual o usuário pode especificar modelos POMDP para representar um contexto de investimento, resolver o POMDP e confrontar a solução com a realidade. As probabilidades de transição e observação podem ser geradas a partir de dados históricos (normalmente a partir de um longo intervalo de tempo) e a política é obtida pelo planejador que gera as soluções ótimas aproximadas. Finalmente, tanto a eficácia do modelo quanto da política correspondente podem ser avaliadas por meio de simulações que adotem a política em outros intervalos de tempo. 5.1. Estrutura Básica A estrutura básica do protótipo implementado em Java, foi dividida de forma semelhante à arquitetura proposta no Capítulo 4. Foram implementadas, no entanto, as funcionalidades básicas da arquitetura proposta, sendo deixada a sua complementação para trabalhos futuros. Cada pacote contém as classes relacionadas a uma função específica. A estrutura de pacotes é demonstrada na figura 22. As setas indicam a dependência do pacote destino em relação ao pacote de origem, de acordo com a notação UML. 5.1.1. Descrição dos Pacotes • Market – Responsável pela interface com o mercado e pelas séries de dados das ações negociadas em bolsa. • Context – Processa as definições do metamodelo fornecidas pelo usuário e gera o modelo POMDP. 70 • ProbabilityGenerator – Calcula as probabilidades de transições de estados e probabilidades de observações. Gera as tabelas de probabilidades. • ObservationGenerator – Realiza a tradução das séries de cotações em observações. Possui interface com os sensores que serão utilizados. • Simulator – Responsável pela simulação e apuração de resultados. • Planner – Realiza o planejamento automático para geração de políticas. Recebe o modelo POMDP e faz interface com o planejador. Figura 22 – Estrutura de pacotes do protótipo 5.1.2. Diagrama de classes As classes que compõem cada um dos pacotes e seus relacionamentos são demonstradas nas figuras 23 e 24. As classes StateDefinitions, ActionDefinitions, ObservationDefinitions e RewardDefinitions recebem as definições de metamodelo do usuário e são utilizadas pelas outras classes para gerar o modelo. As classes State, Action, Observation e Reward são responsáveis por gerar e registrar o modelo POMDP. 71 Figura 23 – Diagrama de classes da geração de contexto 72 Figura 24 – Diagrama de classes da utilização do simulador A classe StateProbability calcula a probabilidade de transições baseando-se nas informações da classe State e nos dados recebidos através da interface com o mercado (conforme arquitetura explicada no Capítulo 4). De forma semelhante, a classe ObservationProbability calcula as probabilidades de observações através da série traduzida pela classe ObservationGenerator. A classe ObservationGenerator faz interface com os sensores de acordo com as definições do usuário. Os sensores são explicados em detalhes mais adiante. A classe Planner realiza a interface com o planejador para a geração das políticas e depende somente do arquivo de modelo POMDP. O arquivo de modelo é criado pela classe Job do Grid, demonstrada na figura 27. Mais detalhes sobre o Grid estão descritos mais adiante. Durante a simulação, a classe Simulator utiliza a política gerada e informações sobre o mercado que são fornecidas pela classe ObservationGenerator para executar as ações. A avaliação financeira utiliza os dados reais, fornecidos em paralelo pela interface de mercado. 73 5.2. Sensores Os sensores são responsáveis por analisar as séries e retornar as observações para o agente. Durante a geração de probabilidades e a simulação, os sensores que serão utilizados são chamados pela classe ObservationGenerator. A classe recebe a série de preços através da classe Market e a fornece ao sensor em questão. Em seguida, o sensor retorna as séries que representam seus valores para a classe ObservationGenerator. As séries de valores geradas pelo sensor poderiam ser utilizadas para desenhar o gráfico referente ao indicador que foi implementado por ele. A quantidade de séries que um sensor pode retornar varia de acordo com o indicador, por exemplo, um sensor que implementa Médias Móveis, pode retornar uma série lenta e outra rápida. O ObservationGenerator interpreta as séries geradas pelo sensor de acordo com as definições do usuário(conforme arquitetura explicada no Capítulo 4) e gera uma outra série com as observações discretas. Ao final, para cada elemento da série original de valores haverá uma observação correspondente na série de observações discretas. A arquitetura da ferramenta propõe que os sensores sejam expansíveis, para que novas e melhores formas de analisar as séries possam ser adicionadas. Na ausência de um sensor ideal para um modelo específico, o usuário pode desenvolver o seu próprio. Os sensores que foram adicionados ao protótipo e já podem ser utilizados são os seguintes indicadores de Análise Técnica: Médias Móveis, Oscilador de Médias Móveis [15], MACD (Moving Average Convergence / Divergence) [1], DUAL CCI (Commodity Channel Index) [11], Momentum, ROC (Rate of Change) [9], Parabolic SAR, RSI (Índice de Força Relativa) [22] e Oscilador Estocástico (SO) [12]. Modelos de Candlestick [17], Suporte e Resistências [9] também podem ser usados para produzir observações. Para criar um novo sensor, é necessário implementar uma classe que herde as características da classe abstrata PluginAbstract demostrada na figura 25 e descrita na tabela 5. Em seguida, empacotar as classes compiladas em um arquivo Jar. O protótipo é capaz de listar os sensores de um arquivo Jar para que o usuário selecione aquele que deseja usar no modelo. 74 Figura 25 – Classe abstrata “PluginAbstract” para definição de sensor Métodos Fixos Retorna o nome do sensor implementado. Retorna a descrição do sensor implementado. Retorna verdadeiro, caso o sensor possa ser configurável via interface. public boolean isCanceled() Retorna verdadeiro, se o usuário cancelou o sensor via interface de configuração. public void setSeries(Series series) Fornece a série a ser utilizada. Métodos que podem ser modificados protected void cancel() Executa a ação de cancelamento do sensor. protected void closeConfFrame() Fecha a interface de configuração do sensor. Métodos que devem ser implementados public abstract void showConfig() Implementa a tela de configuração. É utilizada para exibir a interface de configuração do sensor. public abstract ArrayList<String> Implementa a arraylist que retorna a legenda de cada getResultDescription() uma das séries de resultados. public abstract ArrayList<double []> Implementa a arraylist que retorna as séries de getResultValues() resultados do sensor. public abstract ArrayList<String> Implementa a arraylist que retorna a legenda das getBuySellDescription() séries com as interpretações do sensor. public abstract ArrayList<String []> Implementa a arraylist que retorna as séries com as getBuySellValues() interpretações do sensor. public String getName() public String getDescription() public boolean isConfigurable() Tabela 5 – Descrição dos métodos da classe abstrata “PluginAbstract” 75 5.3. Planejadores Novos algoritmos, possivelmente melhores, surgem a cada ano. Assim, o protótipo prevê a adaptação de novos planejadores. Durante os testes, a ferramenta incorporou alguns planejadores de código aberto (open-source) para resolver os POMDPs. Inicialmente, optou-se por utilizar os algoritmos implementados por Cassandra [4], que estão disponíveis em http://www.pomdp.org. Para os testes iniciais, foi adotado o algoritmo Finite Horizon, que é uma instância do algoritmo PBVI descrito no Capítulo 3, o qual resolve POMDPs de forma aproximada, mas muito mais rapidamente que algoritmos que fornecem a solução ótima. Como este planejador utilizava uma estratégia de estados de crença aleatórios(Algoritimo SSRA, explicado no capítulo 3 pagina 57), às vezes as políticas geradas determinavam transições inválidas entre estados, devido à aproximação. Para contornar este problema, as ações que não correspondiam ao estado atual eram ignoradas durante a simulação. Decidiu-se, então, por implementar um planejador próprio. Este novo planejador contribuiu com este trabalho por duas razões: utilizou um algoritmo de expansão mais sofisticado que gera apenas estados de crença que podem ser alcançados durante as transições, sem comprometesse a geração de políticas, e permitiu uma melhor compreensão da resolução de POMDPs através da implementação em Java do algoritmo PBVI. O novo planejador foi desenvolvido de acordo com as especificações da arquitetura proposta e permite trabalhar em modificações futuras dos próprios algoritmos. Seus resultados foram comparados com os obtidos através do planejador anterior para verificar seu funcionamento. Optou-se por utilizar utiliza o mesmo modelo de arquivo de entrada que o planejador de Cassandra, já que este formato tornou-se padrão e é utilizado por outros planejadores de código aberto. Também, por que o formato já estava implementado na ferramenta e foi utilizando nos testes usando o planejador anterior. A classe abstrata que define a interface com o planejador é demonstrada na figura 26 e descrita na tabela 6. A classe LogControl fornece a interface de saída das mensagens do planejador, utilizando o framework Log4J. A saída pode exibida na tela ou escrita em arquivo de acordo com a necessidade 76 Figura 26 – Classe abstrata para definição de interface com planejador Métodos que devem ser implementados public abstract void setEpoch(int) Utilizado para fornecer o número de iterações que serão realizadas durante o planejamento. public abstract void setTimeLimit(int) Utilizado para definir o tempo máximo de planejamento em segundos. public abstract void pomdp() Implementa o processo de planejamento automático. public abstract int getBInitIndex() Retorna o índice relativo a ação da política que deve ser executada pelo estado de crença inicial. public abstract void SearchInitialNode() Implementa a busca pelo índice da política gerada, responsável pelo estado de crença inicial. Tabela 6 – Descrição dos métodos da classe abstrata “Planner” 5.4. Processamento em Grid Durante os primeiros experimentos, verificou-se a necessidade de experimentar diversos modelos, com indicações diferentes da forma de composição dos estados, da atribuição de custos e recompensas e com períodos para a coleta das estatísticas diferentes. O processo de planejamento e geração de políticas para um modelo POMDP leva cerca de 12 horas (de acordo com o modelo a ser processado). Então, para facilitar o estudo de várias hipóteses de modelagem do mercado, tornou-se necessário criar um mecanismo que permitisse enfileirar os modelos que seriam processados pelo planejador. Como o planejamento é um processo muito custoso e demorado, acreditava-se que quanto mais computadores pudessem ser utilizados, mais modelos poderiam ser processados. Partindo deste princípio, pesquisou-se um Framework em Java para Grid Computing que pudesse ser utilizado para executar diferentes trabalhos de planejamento em paralelo. O GridGain 2.1.1 foi o Framework escolhido e utilizado na implementação da ferramenta. A arquitetura em Grid é capaz de processar diferentes modelos simultaneamente. O GridGain fornece somente a interface para comunicação em rede entre 77 as máquinas e o controle sobre as tarefas que serão executadas. Então, para funcionar com a ferramenta proposta, toda a arquitetura do Grid teve que ser modelada e implementada conforme figura 27. Optou-se por utilizar um nó mestre para controle e nós escravos para processamento. Também foi necessário definir uma classe para as tarefas que seriam executadas em Grid. Figura 27 – Diagrama de classes do Grid Inicialmente, é preciso instalar o GridGain em computadores que estejam na mesma rede. Os planejadores implementados em Java não precisam ser instalados, uma vez que o Grid se encarrega de replicá-los aos outros nós. Porém, planejadores que não estejam em Java devem ser instalados no diretório do GridGain em todas as máquinas que compõem o Grid. Cada computador pode executar mais de uma instância do GridGain mas recomenda-se que não ultrapasse a quantidade de Núcleos/CPUs, ou seja, n instâncias para n Núcleos/CPUs (esta recomendação é importante visto que o processo de planejamento consome 100% do núcleo de CPU onde é executado). Cada instância em execução cria um nó do Grid e, em seguida, avisa aos demais pela rede. Os nós são responsáveis pelos processos do Grid. 78 Ao ser executada, a ferramenta conecta-se ao Grid na forma de “nó mestre”. O “nó mestre” é responsável por receber as ordens do usuário (definições do metamodelo que serão utilizadas na geração do modelo POMDP), reuni-las em uma fila e distribuí-las aos nós de processamento que estão vagos. Os nós podem estar disponíveis ou executando o processamento das ordens. As ordens podem estar na fila aguardando execução, em execução ou concluídas. Caso ocorra algum erro de processamento, seja pela execução ou por um nó que tenha falhado e saído do Grid, as ordens podem ainda apresentar uma situação de falha. Nesse caso, a ordem aguarda novamente na fila a possibilidade de ser executada novamente. 5.5. Interfaces de Usuário Durante os experimentos, novas interfaces de usuário foram acrescentadas ao protótipo. A primeira interface criada é chamada de interface local e é disponibilizada pelo nó mestre. A interface local monitora o estado do Grid Pomdp e permite ao usuário inserir definições de metamodelo utilizando linhas de comando. Ao longo dos experimentos, foram incorporadas interfaces remotas para controle do Grid Pomdp e para divulgação de informações. 5.5.1. Interface Local – Nó Mestre A interface local fornece informações sobre os nós do Grid e a fila de processos de forma simplificada (conforme demostrado na figura 28). O usuário pode inserir novos processos através de um formulário onde define cada um dos itens do modelo. Os campos são: • State Def – Definição de Estado: onde o usuário define o componente nãodeterminístico dos estados. A definição segue o formato ttdd, onde tt é o tipo de dado e dd é o período em dias para a apuração. As definições podem ser compostas de mais de um critério, e para isto, utiliza-se o caractere “#” para separá-las. Por exemplo, o usuário gostaria de definir um componente não-determinístico como a variação dos preços dos 5 dias anteriores (pv5) e a possível variação dos 5 dias seguintes (pv-5). Então, descreve o estado como “pv5#pv-5”, utilizando # como separador. O período é descrito em relação ao dia de análise, sendo positivo para expressar o passado (pois o dia base estaria a 5 dias do dia de referência) e negativo para expressar o futuro (pois o 79 dia base estaria a -5 em relação ao dia de referência). Os parâmetros que podem ser utilizados são: o pv – variação de preço o pm – média de preço o vv – variação de volume o vm – média de volume o qv – variação de quantidade negociada o qm – média de quantidade negociada • Observ Def – Definição de observação: Define quais sensores serão utilizados para geração de observações. • Share – Ação da Bolsa: Seleciona qual ação que será utilizada na geração do modelo e simulação. • FromPol, ToPol – Datas inicial e final do período que será utilizado no cálculo das probabilidades do modelo. • FromSim, ToSim – Datas inicial e final do período que será utilizado na simulação. • Email (opcional) – Email para envio dos resultados da simulação. Figura 28 – Interface Local do Grid 80 5.5.2. Interface Remota Via Email Durante os testes, fez-se necessária a criação de uma interface remota, por onde o usuário poderia receber os resultados e enviar novas propostas de modelo para a fila de processamento. Assim, desenvolveu-se uma interface via email para atender esta demanda e que poderia ser ativada quando necessário. Os comandos deveriam ser enviados para o email [email protected] com o comando específico escrito no assunto e, se necessário, parâmetros no corpo da mensagem. A interface processa os e-mails recebidos e responde com o resultado, seja apenas confirmando o comando, seja recebendo informações do Grid. Os comandos estão listados na tabela 7 e descritos logo a seguir. Assunto/Comando Help GridList PendingJobs RunningJobs GridStatus AddTask Descrição Listagem de Comandos da Interface. Lista Nós do Grid Lista Fila de Tarefas Lista Tarefas em Execução Lista Status Completo do Grid Adiciona nova tarefa ao Grid Tabela 7 – Comandos da interface via Email Comando “Help” Responde ao usuário a lista de comandos possíveis. Comando “GridList” Retorna a lista de nós que compõem o Grid. Exemplo no quadro 11. Grid List: ########## <<IP Master >> : Master << IP Nó >> : <<Status>> << IP Nó >> : <<Status>> << IP Nó >> : <<Status>> Exemplo: Grid List: ########## 192.168.1.66 : Master 192.168.1.66 : Working 192.168.1.67 : Working 192.168.1.64 : Working Quadro 11 – Comando “GridList” 81 Comando “PendingJobs” Retorna a fila de Jobs que estão aguardando processamento. Exemplo no quadro 12. Pending Jobs: ############# #<<N Fila>> : <<Parâmetros Modelo>> : <<Data Inicio>> : <<Data Fim>> : Failed #<<N Fila>> : <<Parâmetros Modelo>> : <<Status>> #<<N Fila>> : <<Parâmetros Modelo>> : <<Status>> Exemplo: Pending Jobs: ############# #8 : pm5#pm-5 : ^BVSP : RSI3 : 2009-09-07 02:15:25 : 2009-09-07 02:17:22 : Failed #9 : pm5#pm-5 : ^BVSP : MACD2 : Waiting #10 : pm5#pm-5 : ^BVSP : OST2 : Waiting Quadro 12 – Comando “PendingJobs” Comando “RunningJobs” Retorna a lista de Jobs em execução. Exemplo no quadro 13. Pending Jobs: ############# #<<N Fila>> : <<Parâmetros Modelo>> : <<Status>> : <<IP Nó>> #<<N Fila>> : <<Parâmetros Modelo>> : <<Status>> : <<IP Nó>> Exemplo: Running Jobs: ############# #3 : pv5#pv-5 : ^BVSP : pv5#RSI2 : 06/09/2009 22:15:10 : Running on 192.168.1.64 #4 : pv5#pv-5 : ^BVSP : pv5#RSI3 : 06/09/2009 22:15:20 : Running on 192.168.1.64 Quadro 13 – Comando “RunningJobs” Comando “GridStatus” Retorna uma única resposta com o conteúdo dos comandos “GridList”, “PendingJobs” e “RunningJobs”. Comando “AddTask” Este comando adiciona n ordens à fila de Jobs do Grid. Cada uma das ordens deverá estar em uma linha diferente. No corpo da mensagem, o usuário descreve a definição dos componentes do modelo separados por vírgula conforme exemplo no quadro 14. Os 82 componentes são: definição de Estado, definição de Observações, ação ou índice da bolsa a ser analisado, data que inicia a geração de probabilidades, data que finaliza a geração de probabilidades, data que inicia a simulação, data que finaliza a simulação e número de iterações do planejador como parâmetro opcional. Parâmetros: defEstado, defObs, papelGeracao, DTIniAval, DTFimAval, DTIniSim, DTFimSim, [i] Exemplo do corpo da mensagem: pv5#pv-5, RSI1, ^BVSP, 2000-06-01, 2008-02-01, 2008-02-01, 2009-06-01 pm5#pm-5, RSI3, ^BVSP, 2001-01-01, 2008-12-31, 2009-01-01, 2009-12-31, 500 Quadro 14 – Comando “AddTask” 5.5.3. Twitter O Twitter foi adicionado como uma interface opcional de divulgação dos dados para outros envolvidos. Enquanto a interface via email pode ser utilizada para controle do Grid, o Twitter funcionou apenas para leitura, informando sobre o comportamento do Grid e os resultados dos Jobs. A idéia surgiu pois apenas o usuário que envia uma ordem via email recebe os seus resultados, e ordens adicionadas localmente via interface gráfica só informam os resultados no console. Assim, com a interface twitter ativada, era possível todos os envolvidos acompanharem os resultados em tempo real e, principalmente, remotamente, bastando acessar http://twitter.com/gridpomdp. 5.6. Planejador Implementado O planejador implementado durante este trabalho utiliza o algoritmo PBVI (Point Based Value Iteration), descrito no Capítulo 3, e, como mencionado anteriormente, usa como entrada o mesmo formato dos arquivos de modelo e políticas adotados nos planejadores implementado por Cassandra [4]. As classes do planejador implementado são demonstradas na figura 29. A classe Model é responsável por representar o modelo que será utilizado durante o planejamento. É carregada pela classe PlannerModel que realiza a verificação e leitura do arquivo de modelo POMDP. Se existir alguma inconsistência no modelo, a classe PlannerModel retornará uma mensagem que descreve o erro e determina a linha da ocorrência. A classe Planner implementa os métodos definidos pela classe abstrata e as 83 rotinas do algoritmo PBVI. Ao final do planejamento, a classe Planner gera três arquivos de saída descritos na tabela 8. Extensão .b .alpha .pol Descrição Arquivo que relaciona os índices aos estados de crença Arquivo que relaciona os alfas as ações Arquivo que define a política gerada Tabela 8 – Arquivos de Saída do planejador Figura 29 – Diagrama de classes do Algoritmo PBVI 84 A classe PlannerUtils implementa métodos de suporte para leitura e escrita de arquivos, conversão de estados de crença em índices e definição de qual índice corresponde ao estado de crença inicial. Optou-se em utilizar a rotina de expansão utilizando Simulação Estocástica com Ação Gulosa (ExpandSSGA), descrita no capítulo 3, por obter um conjunto de Estados de Crença mais consistente que as rotinas que utilizam estratégia aleatória. As outras rotinas de expansão foram implementadas e também estão disponíveis. 5.7.Conclusão Este capítulo documenta a implementação do protótipo utilizado durantes as experiências que serão apresentadas no capítulo 6. Neste trabalho, optou-se por implementar apenas o núcleo da arquitetura para que se pudesse primeiramente comprovar sua hipótese. A estrutura em módulos, apresentada no capítulo 4, foi representada através de diagramas de classe e explicada. Detalhes da arquitetura, como a forma de expandir os sensores e planejadores disponíveis também foram apresentados e explicados. Esta etapa também é responsável pelo desenvolvimento de um planejador próprio que contribuiu para o teste do mecanismo de expansão do ambiente, além de obter melhores resultados que o anterior. A arquitetura em Grid, utilizada para a criação da ferramenta, permitiu o processamento simultâneo de diferentes modelos POMDP. No futuro, novos planejadores que utilizem algoritmos de processamento paralelo ser incorporados, aproveitando melhor a arquitetura em Grid. Finalmente, as interfaces utilizadas pela ferramenta para entrada e saída de dados são comentadas. A primeira interface criada, limitada o uso da ferramenta ao usuário que tivesse acesso ao nó mestre. Durante o período de experiências fez-se necessário o desenvolvimento de interfaces remotas. Assim, foram confeccionadas outras duas interfaces: uma através de email para entrada de dados e outra via twitter para divulgação de resultados. 85 Capítulo 6 - Aplicação da Ferramenta a um Modelo Básico Para avaliar a utilidade e a flexibilidade do metamodelo proposto e da ferramenta implementada, foi proposto um modelo básico. Este modelo é bastante simples, mas já permitiu obter resultados interessantes, como serão mostrados a seguir. Modelos mais sofisticados podem, no entanto, ser aplicados para se estudar mais a fundo a importância das diversas variáveis para a tomada de decisão. Entre essas variáveis, destacam-se os volumes diários e as correlações entre as variações de preços em intervalos de longo e curto prazo. Todo o processo é baseado na idéia de que, a todo instante, há uma tendência para os preços de um determinado ativo. Desta forma, em cada instante, o estado corrente é composto por um conjunto de dados sobre a negociação recente do ativo, pela posição atual do investidor e pela tendência de variação dos preços naquele instante (que corresponde ao aumento dos preços no futuro próximo). Supõe-se que não se pode conhecer as tendências, mas estas são sempre confirmadas e podem ser parcialmente observadas por meio de sensores de Análise Técnica. Desta forma, os preços no futuro próximo são parte do estado subjacente em cada momento. Em tempo real, nunca se sabe os preços futuros, mas, quando se examina o histórico, os preços após certo período passado são conhecidos e podem ser comparados com os resultados dos indicadores de Análise Técnica. Em seguida, as probabilidades da relação entre os indicadores e os preços futuros podem então ser coletadas. 86 6.1. Composição de Estados No modelo básico proposto, os estados são compostos por apenas três variáveis: (a) tendência do mercado nos últimos 6 dias12 (alta, baixa ou neutra), (b) tendência do mercado nos 6 dias seguintes, e (c) posição do investidor (comprado, vendido ou fora). Esta definição segue o metamodelo apresentado no capítulo 4. As primeiras duas variáveis (a e b) são responsáveis pela parte não-derminística do estado, sendo que a primeira é observável por se tratar de um evento que já ocorreu e a segunda não observável por se tratar de um evento futuro. A terceira variável é a parte determinística do estado e é responsável por representar a posição em que o investidor se encontra. Como cada uma das variáveis pode assumir 3 valores diferentes, o modelo possui 27 estados. Cada tendência é definida por um intervalo de variação de preços e seus parâmetros são ajustáveis pelo usuário. Neste trabalho, determinou-se que as tendências serão representadas por períodos de 6 dias e foram assumidas as seguintes definições em conformidade com a variação de preços: • Alta: mercado em alta para a variação ≥ +2% • Baixa: mercado em baixa para a variação ≤ -2% • Neutra: mercado estável para o intervalo entre os dois. Os investidores podem possuir posições “comprado” ou “vendido” para as ações que estão sendo analisadas ou podem estar “fora” do mercado. Em uma posição “comprado”, o investidor terá comprado ações que correspondem financeiramente a um valor D. Em uma posição “vendido”, o investidor tomará emprestado e imediatamente vendido ações que correspondem financeiramente ao valor D. Em posições “comprado”, o lucro é proporcional à variação dos preços das ações e, em relação às posições “vendido”, é simetricamente proporcional à variação dos preços. Por razões de simplicidade, não se consideraram taxas de corretagem, nem a associação com a compra de opções de compra para limitar as perdas de posições “vendido”. Assume-se que os lucros e prejuízos são acumulados quando o investidor abre uma posição e assume uma outra, de modo que a 12 Tendência Semanal - 6 dias representam uma semana no mercado de ações, ou seja, 5 dias úteis que antecedem ou precedem o pregão em questão mais o resultado deste. 87 quantidade de dinheiro investido é sempre D. Os lucros não são reinvestidos e o investidor sempre tem dinheiro para investir o montante D, mesmo se ele tiver tido perdas anteriores. 6.2. Ações e Transições As ações possíveis são: “compra”, “venda”, “compraDupla”, “vendaDupla” e “nada”. As ações “compra” e “venda” correspondem, respectivamente, à compra e à venda de uma quantidade de dinheiro D em ações. As ações “compraDupla” e “vendaDupla” correspondem a um montante de 2D e são usados para alterar diretamente a posição do investidor “vendido” a “comprado”, e vice-versa. Estas ações são extremamente importantes por mantem o resultado de uma operação durante uma reversão de tendência e posiciona-la para tendência seguinte. A ação “nada” corresponde a manter a posição do investidor. Ação nada nada nada compra compra venda venda compraDupla vendaDupla Estado Inicial comprado vendido nada nada vendido nada comprado vendido comprado Estado Final comprado vendido nada comprado nada vendido nada comprado vendido Tabela 9 – Modelo de Transições de estados As transições entre os estados exercem influência apenas no componente determinístico dos estados e estão relacionadas na tabela 9. Existem algumas restrições de transição devido à posição do investidor. As ações para comprar e vender só podem ser executadas quando a posição do investidor não é respectivamente “comprado” ou “vendido”. Por outro lado, as ações compraDupla e vendaDupla só pode ser executadas se a posição do investidor é “vendido” ou “comprado”, respectivamente. O conjunto de estados que podem ser alcançados depois de uma ação também é limitado. Após uma ação vendaDupla, por exemplo, a posição do investidor é sempre “vendido”. Isto significa que a partir de um estado, outros 9 estados distintos podem ser atingidos, variando apenas as tendências para os dias anteriores e seguintes. Como apresentado no capítulo 4, as probabilidades de cada transição são estimadas com base no histórico de preços dos ativos. 88 6.3. Recompensas A atribuição de recompensas aos estados é essencial para especificar como cada estado é rentável. É altamente desejável estar em uma posição comprada quando o mercado está em alta. Em contraste, em um mercado em baixa, devemos tentar assumir uma posição vendida. Quando o mercado está estável, pode ser preferível ficar de fora, evitando-se custos de compensação e perda de oportunidades de investimento. Conforme mostrado na tabela 10, atribui-se uma alta recompensa positiva para os estados onde o investidor assume posições rentáveis e uma alta recompensa negativa para os estados em que o investidor está em uma posição que certamente provoca perdas. Quando as tendências não são tão claras, são atribuídas recompensas menores. São atribuídas recompensas próximas de zero quando o investidor está fora do mercado, sendo ligeiramente positivas se o mercado está estável e ligeiramente negativas quando existe uma clara tendência que o investidor poderia ter aproveitado. A atribuição inicial mostrada na tabela 10 foi utilizada na aplicação do modelo básico, mas não é fixa e pode ser alterada a fim de estudar os modelos que melhor correspondem a um determinado contexto. Por razões de simplicidade, também se decidiu não atribuir custos às transições, mas elas podem ser atribuídas normalmente, considerando-se as taxas que devem ser pagas às corretoras quando as ações são compradas e vendidas. alta, alta, comprado alta, estável, comprado alta, baixa, comprado estável, alta, comprado estável, estável, comprado estável, baixa, comprado baixa, alta, comprado baixa, estável, comprado baixa, baixa, comprado alta, alta, vendido alta, estável, vendido alta, baixa, vendido estável, alta, vendido estável, estável, vendido 10 5 0 5 0 -5 5 -2 -10 -10 -2 5 -5 0 estável, baixa, vendido baixa, alta, vendido baixa, estável, vendido baixa, baixa, vendido alta, alta, fora alta, estável, fora alta, baixa, fora estável, alta, fora estável, estável, fora estável, baixa, fora baixa, alta, fora baixa, estável, fora baixa, baixa, fora 5 0 5 10 -2 0 0 0 2 0 0 0 -2 Tabela 10 – Recompensas para os estados baseados na tupla <Tendência dos 6 dias anteriores, Tendência dos 6 dias seguintes, posição do investidor> 6.4. Observações e Sensores As observações são produzidas pelo acompanhamento da série histórica através de sensores. Os sensores podem produzir observações simples ou complexas envolvendo fatos 89 como: faixas de valores dos indicadores e de ponderações desses valores; quebras de resistência e rompimento de suportes; e combinações de candlesticks específicos. Cada período observado produzirá uma única observação. As observações são definidas com base na definição formal de cada sensor. Inicialmente, este modelo utilizou “ponto de compra”, “ponto de venda”, e “sem definição” como observações. Foram selecionados os seguintes indicadores: Força Relativa (RSI), MACD e Oscilador Estocástico. Os indicadores possuem mais de uma interpretação baseadas nos possíveis aspectos que se deseja analisar. E como o modelo básico define estados baseados na tendência semanal, decidiu-se que cada indicador utiliza apenas 2 interpretações que representam períodos curtos. Assim, cada interpretação gera um modelo diferente e, ao final, gerou-se 6 modelos diferentes para cada única ação da bolsa e período de análise. Os parâmetros de interpretação dos sensores são descritos na tabela a seguir: Indicador RSI1 RSI1 RSI1 RSI2 RSI2 RSI2 MACD1 MACD1 MACD1 MACD2 MACD2 MACD2 OST1 OST1 OST1 OST2 OST2 OST2 Parâmetros short_atual ≥ 0.2 e short_anterior ≤ 0.2 short_anterior ≥ 0.8 e short_atual ≤ 0.8 short_atual ≥ 0.3 e short_anterior ≤ 0.3 short_anterior ≥ 0.7 e short_atual ≤ 0.7 Macd_atual ≥ 0 e macd_anterior ≤ 0 Macd_anterior ≥ 0 e macd_atual ≤ 0 Histogram_atual ≥ 0 e histogram_anterior ≤ 0 Histogram_anterior ≥ 0 e histogram_atual ≤ 0 short_atual ≥ 0.2 e short_anterior ≤ 0.2 short_anterior ≥ 0.8 e short_atual ≤ 0.8 long_atual ≥ 0.2 e long_anterior ≤ 0.2 long_anterior ≥ 0.8 e long_atual ≤ 0.8 - Observação pcompra pvenda pnada pcompra pvenda pnada pcompra pvenda pnada pcompra pvenda pnada pcompra pvenda pnada pcompra pvenda pnada Tabela 11 – Modelo de geração de observações A observação pcompra representa o “ponto de compra“ e pode confirmar uma tendência de alta ou representar uma reversão de tendência de baixa para tendência de alta. Similarmente, pvenda representa o “ponto de venda“ e pode confirmar uma tendência de baixa ou representar uma reversão de tendência de alta para tendência de baixa. A observação pnada corresponde a “sem definição“ e significa que não existe uma nova indicação clara. 90 Os indicadores Força Relativa (RSI1 e RSI2) geram duas séries. A série curta (ou short) é gerada utilizando-se 14 dias na janela de previsão, e a série longa (ou long) utiliza 27 dias. Como o resultado final depende de uma reação rápida aos eventos, optou-se pelo uso apenas da série curta. A série longa é influenciada por tendências de longo prazo, indica eventos após mais confirmações e acaba atrasando uma reação. O parâmetro short_atual representa o valor da linha curta do RSI para o dia d, enquanto o short_anterior representa o valor da linha curta do RSI para o dia anterior. Os indicadores MACD (MACD1 e MACD2) geram três séries, sendo a primeira o valor do MACD, a segunda representando o sinal (ou gatilho) e a terceira o histograma. O MACD é calculado utilizando como parâmetros de 12 dias como período curto, 26 dias como período longo e 9 dias para suavização. Estes parâmetros são internos, utilizados pelos cálculos do indicador e não geram séries curtas ou longas. Para a interpretação do indicador, foram definidas as seguintes variáveis: macd_atual e histogram_atual, as quais representam respectivamente o valor de macd e do histograma do dia de análise e, macd_anterior e histogram_anterior, o valor de macd e histograma do dia anterior. Os indicadores “Oscilador Estocástico” (OST1 e OST2) geram duas séries: uma curta e outra longa. Utiliza como parâmetros 14 dias como período e 3 dias para a média móvel simples. As variáveis short_atual e long_atual representam respectivamente o valor da série curta e longa para o dia de análise e short_anterior e long_anterior os valores para o dia anterior. 6.5. Experimentos Os primeiros experimentos foram realizados utilizando o planejador POMDP implementado por Cassandra e, em seguida, confirmados pelo planejador implementado durante a pesquisa. Ambos os planejadores utilizaram versões do algoritmo POMDP PBVI. Os experimentos foram realizados em duas etapas: a primeira utiliza o período entre Janeiro/2008 e Junho/2009; a segunda verifica o desempenho durante o ano todo de 2009. Nos experimentos, optou-se por utilizar o índice da Bolsa de Valores de São Paulo, IBOV, como o ativo em estudo. Tal opção justifica-se por procurar analisar inicialmente a capacidade de avaliar tendências do mercado em geral, em vez de tendências de um papel 91 específico. Nota-se que o mercado possibilita também a realização de negócios onde os investidores compram ou vendem índices. Durante a avaliação do modelo, optou-se por experimentar 6 sensores, cada um baseado em um indicador de Análise Técnica, conforme mencionado anteriormente. Desta forma, pretendeu-se comparar os resultados de diferentes indicadores através da adoção das políticas geradas contra a obediência imediata à clássica interpretação de cada indicador. Foram realizadas simulações com base nos seguintes indicadores: duas versões do indicador Moving Average Convergence / Divergence (MACD1 e MACD2), duas versões do Índice de Força Relativa (RSI1 e RSI2) e duas versões do Oscilador Estocástico (OST1 e OST2). Diferentes versões de um mesmo indicador variam de acordo com diferentes estratégias de interpretação. 6.5.1. 1ª Etapa: Período entre Janeiro/2008 e Junho/2009 Para a primeira etapa, selecionou-se o período de 2 de janeiro de 2000 a 30 de dezembro de 2007 para ser utilizado durante a aprendizagem estatística adotada para estimar probabilidades. Durante este período, aconteceram muitos eventos importantes que tiveram impacto no mercado, como a bolha das empresas de Internet (ponto com), os ataques terroristas de 11 de setembro e a crise da eleição presidencial brasileira em 2002. Selecionou-se para a simulação o período de 2 de janeiro de 2008 a 30 de junho de 2009 devido à ocorrência de 3 diferentes tendências. No primeiro semestre de 2008, houve uma tendência de estabilidade. No segundo semestre de 2008, ocorreu a crise do subprime e houve uma forte tendência de baixa. No primeiro semestre de 2009 houve uma recuperação da crise (um período de alta). 6.5.2. 2ª Etapa: Período entre Janeiro/2009 e Dezembro/2009 A segunda etapa utilizou o período de 2 de janeiro de 2001 a 30 de dezembro de 2008 para o aprendizado. Este período inclui praticamente todos os eventos do período anterior e o ano de 2008 (ignorou-se o ano 2000 para manter uma janela de 7 anos). O período de simulação é compreendido entre 2 de janeiro e 30 de dezembro de 2009. Em 2009, houve uma grande recuperação na bolsa de valores de São Paulo, com algumas quedas provocadas por resistências. Este período foi interessante para avaliar o comportamento das políticas durante uma tendência de longo prazo, visto que o comportamento normal de um investidor 92 é sempre vender o ativo no momento em que o resultado esperado é alcançado (exercer o lucro) e, possivelmente, recomprá-lo em seguida. 6.5.3. Resultados Em média, as simulações geraram políticas com aproximadamente 1500 estados de crença, cada uma estabelecendo faixas de probabilidade para cada estado subjacente. A política mapeia cada estado de crença e observação em uma ação e indica o novo estado de crença que será atingido após a execução desta ação. Durante as simulações, as observações são fornecidas continuamente para cada dia de pregão e a execução de cada ação é determinada pela política em questão. Toda vez que uma operação de compra ou de venda é fechada, o resultado correspondente é acumulado. Se, no último dia de simulação, existe uma posição em aberto a simulação força seu encerramento. Operações em que o investidor assume uma posição “vendido” foram importantes para minimizar as perdas e ainda gerar lucros durante a crise. Operações em que o investidor assume posições “comprado” mostraram-se importantes, em especial no período de recuperação após a crise. Durante a primeira etapa, utilizou-se o planejador de Cassandra para obter as políticas e realizar as simulações. Os resultados obtidos para cada indicador, bem como a variação do Índice Bovespa (IBOV), são descritos na tabela 14. Todos os indicadores, com exceção de OST2 (-26.79%) e MACD2 (-10.97%), obtiveram um desempenho melhor do que o IBOV (-10.80%), porém alguns indicadores foram muito melhores do que outros. Em particular, as simulações com base em RSI2 (67.84%) e OST1 (90.67%) foram capazes de realizar lucros, mesmo durante a crise (entre julho e novembro de 2008). As tabelas 12 e 13 apresentam os resultados de operações de compra e venda, respectivamente e demonstram que o planejador foi capaz de obter um resultado semelhante durante as tendências de alta (tabela 12) e as tendências de baixa (tabela 13). É importante destacar que todos os indicadores obtiveram melhores resultados quando utilizado o modelo básico POMDP em relação à opção de simplesmente seguir as indicações dos sensores, conforme demonstrado na tabela 15. 93 Indicadores RSI1 RSI2 MACD1 MACD2 OST1 OST2 2008 Jan-Jun 1.19% 9.22% 15.64% 19.61% 4.42% -0.03% 2008 2009 Total Jul-Nov Dez-Jun -30.47% 52.22% 22.94% -19.96% 42.56% 31.82% 0.00% 2.80% 18.44% -63.79% 37.50% -6.69% -11.32% 49.52% 42.62% -64.39% 52.44% -11.98% Indicadores RSI1 RSI2 MACD1 MACD2 OST1 OST2 Tabela 12 – Resultados para operações de compra Indicadores RSI1 RSI2 MACD1 MACD2 OST1 OST2 IBOV 2008 Jan-Jun 2.06% 14.57% 20.80% 19.77% 10.06% 2.14% -1.35% 2008 Jul-Nov -10.50% 14.39% 0.00% -59.46% 28.78% -84.37% -36.88% 2008 2008 2009 Total Jan-Jun Jul-Nov Dez-Jun 0.87% 19.96% 3.50% 24.33% 5.35% 34.34% -3.68% 36.02% 5.16% 0.00% 1.58% 6.74% 0.16% 4.33% -8.78% -4.29% 5.64% 40.10% 2.31% 48.05% 2.17% -19.98% 3.00% -14.81% Tabela 13 – Resultados para operações de venda 2009 Total Dez-Jun 55.72% 47.27% 38.88% 67.84% 4.38% 25.18% 28.72% -10.97% 51.83% 90.67% 55.44% -26.79% 39.69% -10.80% Indicadores RSI1 RSI2 MACD1 MACD2 OST1 OST2 Tabela 14 – Resultados do Planejador x Ibovespa 2008 Jan-Jun 1.67% 14.01% 1.98% 14.71% -7.37% 4.67% 2008 2009 Total Jul-Nov Dez-Jun 0.00% -5.93% -4.26% -28.14% 25.38% 11.25% 0.00% -6.36% -4.38% -65.53% 11.80% -33.13% -69.06% 5.98% -70.45% -86.77% 0.00% -82.10% Tabela 15 – Resultados para a obediência imediata dos indicadores Após o desenvolvimento do novo planejador, realizou-se uma nova simulação para que se pudessem comparar os resultados. O novo planejador obteve resultados próximos aos resultados obtidos anteriormente pelo planejador do Cassandra como demonstrado na tabela 16. Em geral, todos os indicadores utilizados no planejamento também obtiveram melhores resultados que a “obediência imediata”. Indicadores RSI1 RSI2 MACD1 MACD2 OST1 OST2 IBOV 2008 Jan-Jun 1.16% -3.42% 20.88% 19.01% 9.02% 2.11% -1.35% 2008 Jul-Nov -11.24% 0.00% -1.03% -57.17% 9.76% -83.28% -36.88% 2009 Total Dez-Jun 55.72% 45.64% 77.07% 73.65% 5.42% 25.26% 27.64% -10.53% 37.30% 56.08% 54.73% -26.45% 39.69% -10.80% Tabela 16 – Resultados do Novo Planejador x Ibovespa A simulação da segunda etapa foi realizada utilizando os dois planejadores para que se pudesse não só comparar seus resultados, como também comparar sua eficiência aos resultados obtidos no período anterior. Em geral, bons resultados continuaram sendo obtidos pelos indicadores Força Relativa e Oscilador Estocástico, porém o MACD também 94 obteve bons resultados, aparentemente funcionando melhor em períodos com tendências bem definidas. Esperava-se que, devido às interrupções para exercer o lucro, os indicadores obtivessem resultado menor que o índice Bovespa, porém próximo. Com exceção do indicador OST1 e do RSI2 apenas para o planejador novo, todos os resultados foram bons e superiores à obediência imediata aos indicadores. Os resultados da primeira etapa estão resumidos na tabela 17 e os resultados da segunda etapa são demonstrados na tabela 18. Como o período refere-se a um único evento e possui uma longa tendência definida, os dados não foram divididos em períodos menores. Indicadores Cassandra RSI1 RSI2 MACD1 MACD2 OST1 OST2 IBOV 47.27% 67.84% 25.18% -10.97% 90.67% -26.79% Novo Obediência 45.65% 73.66% 25.27% -10.55% 56.10% -26.45% -10.80% -4.26% 11.25% -4.38% -33.13% -70.45% -82.10% Tabela 17 – Comparação entre os resultados dos planejadores para o período entre 02/01/08 à 31/05/09 Indicadores Cassandra RSI1 RSI2 MACD1 MACD2 OST1 OST2 IBOV 73.14% 26.08% 63.40% 44.48% 9.37% 55.79% Novo Obediência 88.55% -18.46% 66.92% 39.94% 6.72% 60.43% 70.43% 21.83% 10.78% 5.54% 19.36% 16.43% 36.71% Tabela 18 – Comparação entre os resultados dos planejadores para o período entre 02/01/09 à 30/12/09 Cada etapa de experimentos levou em média cerca de 5 dias para ser concluída, utilizando 4 computadores Pentium 4 com 2GBs de memória RAM. As tarefas de planejamento foram enfileiradas utilizando o ambiente em Grid mencionado anteriormente. 6.6.Conclusão Este capítulo apresentou um modelo básico para o contexto de investimentos, baseado no metamodelo proposto no capítulo 4. Este modelo foi usado durante os experimentos e obteve bons resultados, comprovando a hipótese de que é possível utilizar o planejamento baseado em POMDPs para gerar políticas de investimentos. Os experimentos foram conduzidos utilizando um protótipo implementado conforme descrito no capítulo 5 e seguindo a arquitetura básica proposta no capítulo 4. 95 Capítulo 7 - Conclusões 7.1. Considerações Finais Neste trabalho foi proposta uma abordagem para a geração e simulação da aplicação de políticas de investimento no mercado de ações. O principal objetivo era verificar a possibilidade de utilizar as teorias de investimento da Análise Técnica, em conjunto com o planejamento automático, para gerar políticas de investimento. As políticas geradas devem representar um comportamento coerente e próximo ao de um investidor experiente e, se possível, alcançar algum resultado financeiro (lucro). A Análise Técnica foi escolhida por lidar com informações sempre disponíveis (isto é, os dados sobre o histórico das negociações), os quais geram indicadores e gráficos interpretáveis de acordo com formulações matemáticas. Embora as interpretações não sejam absolutas nem totalmente precisas, elas ajudam a traduzir os indicadores e gráficos em variáveis discretas que podem servir de base para a tomada de decisão. Se modelos formais são definidos para representar a situação atual do mercado e as indicações sobre tendências futuras de preços, torna-se possível tentar automatizar decisões, mesmo assumindo que as interpretações não são perfeitas. Como o mercado de ações é probabilístico e parcialmente observável, optou-se por modelar o investimento em ações como um problema de planejamento baseado em Modelos de Markov Parcialmente Observáveis - POMDPs (Partially Observable Markov Decision Processes). O planejador POMDP é responsável por analisar um modelo POMDP e gerar as políticas a serem utilizadas durante o investimento, de acordo com observações parciais sobre a tendência futura que são fornecidas por métodos de Análise Técnica devidamente formalizados. 96 Foi proposto um metamodelo para modelar contextos de investimento de diversas formas, correspondendo a diversas possibilidades de utilização da Análise Técnica. O metamodelo foi implementado por meio de uma ferramenta que fornece um ambiente de estudos para a modelagem do mercado, a geração de políticas de investimento por planejadores e a avaliação dos resultados. É através deste ambiente que se torna possível a verificação de teorias e estratégias de investimento e também das premissas descritas no modelo do investidor. Este trabalho implementa o núcleo deste ambiente, que tornou possível a realização de vários experimentos. O núcleo é totalmente funcional, porém não fornece ainda uma interface gráfica completa ao usuário, ficando esta para trabalhos futuros. Durante as pesquisas, encontrou-se extrema dificuldade para a reunião de todas as informações e teorias necessárias para que fosse possível compreender o funcionamento de um POMDP e do algoritmo de planejamento. Os fundamentos reunidos aqui ainda não estão disponíveis em livros que possam ser consultados e foram reunidos através da leitura de diversos artigos, sendo que ainda não existem nomes de variáveis comuns e uma nomenclatura universal para os componentes de um POMDP. Realizou-se um esforço grande para compreender o funcionamento do algoritmo de planejamento PBVI que produzisse um texto de fácil compreensão. Os primeiros resultados da pesquisa produziram um artigo que foi aceito e apresentado no 25th ACM Symposium on Applied Computing - SAC2010 (Advances in Computer Simulation track), realizado em Sierre, Suíça, em março de 2010. 7.2. Contribuições A primeira premissa verificada foi se realmente era possível realizar o planejamento automático no domínio do mercado de ações, utilizando a Análise Técnica. Para isto, utilizou-se o Microsoft Excel para auxiliar nos cálculos de probabilidades e gerar os primeiros modelos POMDP. Estes modelos foram gerados manualmente e aplicados ao planejador automático implementado por Cassandra [4]. Os primeiros resultados foram promissores, mas cada condição de modelo demorava pelo menos três horas de trabalho manual no Excel. Fez-se necessário implementar um Controlador de Contexto básico para automatizar este processo e verificar 97 se as premissas de combinação de Análise Técnica com planejamento baseadas em POMDPs eram plausíveis. Após a confirmação, definiu-se um metamodelo para a geração e processamento de modelos POMDP que representasse contextos de investimento, permitindo especificar as informações de mercado e os métodos de Análise Técnica a serem levados em conta no processo. O metamodelo definiu também uma arquitetura básica, com os componentes e as normas para a construção de uma ferramenta que facilitasse a modelagem, o planejamento e a simulação para a avaliação dos resultados. Em seguida, partiu-se para a implementação do núcleo de uma ferramenta que confeccionasse a arquitetura. Adicionalmente, propôs-se um modelo básico a ser utilizado nos experimentos. Com o núcleo do protótipo desenvolvido, foi possível realizar diversos experimentos para comprovar as premissas do metamodelo e do modelo básico proposto. Verificou-se que o uso combinado de Análise Técnica com POMDPs produziu resultados muito melhores do que a obediência imediata aos indicadores de Análise Técnica. Os resultados confirmaram a hipótese de que POMDPs podem melhorar a rentabilidade, pois os indicadores não são perfeitos. A ferramenta se mostrou útil na comparação de conceitos da Análise Técnica, de modo que um investidor possa escolher o sensor que lhe pareça produzir melhores resultados para um determinado ativo. Nos testes com o índice da BOVESPA no período entre 2008 e 2009 foi possível notar que, além de resultados melhores que os obtidos pelo índice da BOVESPA e pela obediência imediata aos indicadores de Análise Técnica, as políticas geradas alcançaram bons resultados de lucro, mesmo em períodos de crise, devido à estratégia utilizada na modelagem. O período compreendido pelo ano de 2009 também produziu bons resultados e possivelmente próximos aos que poderiam ser obtidos por um investidor humano experiente. Ainda durante os primeiros testes do núcleo da ferramenta, fez-se necessário estudar uma forma de enfileirar os modelos que seriam processados. Então, adaptou-se o núcleo para Computação em Grid, o que fez com que o tempo para calcular todos os modelos em questão fosse dividido pelo número de máquinas usadas no Grid. 98 Após a realização de diversos experimentos, já com o Grid funcionando e utilizando o planejador de Cassandra [4], iniciou-se o estudo para a compreensão do algoritmo de planejamento e sua implementação em Java. Ao final do desenvolvimento, os resultados alcançados com o novo planejamento foram semelhantes aos resultados encontrados com o planejador anterior, confirmando seu funcionamento. O novo algoritmo contribui com este trabalho, pois permitiu a compreensão melhor do processo e criou uma base para melhoramentos futuros. Em resumo, as contribuições da pesquisa foram as seguintes: • Revisão da Literatura sobre planejamento automático utilizando MDPs e POMDPs; • Proposta de um metamodelo flexível que define regras para geração de modelos POMDP, baseados nas definições do usuário; • Proposta de uma arquitetura geral para o desenvolvimento de um ambiente para modelagem de contextos de investimentos e simulações; • Implementação da ferramenta que permite estudar várias hipóteses baseadas na definição dos elementos do modelo e em teorias de análise de investimentos; • Proposta e avaliação de um modelo básico que produziu bons resultados em situações diferentes e que permitiu demonstrar a viabilidade da combinação de Análise Técnica com planejamento baseado em POMDPs; • Extensão da ferramenta para processamento em Grid de modo a possibilitar a realização de vários estudos em paralelo; • Implementação de um planejador para resolução de POMDPs que serve de base para extensões futuras. 7.3. Trabalhos Futuros Na continuação da pesquisa, pretende-se aplicar a ferramenta a outras ações e índices e verificar se os outros modelos para a composição dos estados do POMDP podem produzir melhores resultados que o modelo básico. A combinação de tendências de curto e de longo prazo para a composição de um estado merece uma atenção especial. A ferramenta deverá incorporar outras funções previstas na arquitetura, destacandose uma interface gráfica mais amigável e o suporte a banco de dados para armazenamento 99 de dados de mercado, de modelos de contexto e de políticas. Além disso, outros indicadores de Análise Técnica e métodos para a interpretação de padrões gráficos deverão ser implementados. Por fim, deverá ser investigada a criação de sensores complexos que combinam sensores mais básicos, de modo a tentar aumentar a confiabilidade da previsão. Para facilitar essa composição, a ferramenta deverá ser estendida. Estudos que estendam o metamodelo proposto também deverão ser realizados. Pretende-se estudar como lidar com contextos de investimentos mais complexos, como aqueles em que o usuário tem recursos limitados, quer limitar os riscos ou quer combinar vários investimentos como ações e opções. Deseja-se também estudar como correlações entre preços de diferentes ativos e índices podem ajudar na previsão de preços de um determinado ativo. Algoritmos que utilizem processamento paralelo devem ser estudados para que a arquitetura em Computação em Grid seja melhor aproveitada. O planejador PBVI implementado poderá ser convertido e adaptado para trabalhar em Grid, de modo que o processamento de um único POMDP possa ser distribuído entre várias máquinas. Por fim, outros algoritmos de planejamento ainda poderão ser estudados e incorporados à ferramenta conforme sejam propostos. 100 Referências [1] Appel, G. The Moving Average Convergence-Divergence Trading Method( Advanced Version). Traders Pr, 1985 [2] Bellman, R. Dynamic Programming. Princeton University Press, 1957 [3] Cassandra, A. R., Kaelbling, L. P., and Littman, M. L. Acting optimally in partially observable stochastic domains. In Proceedings of the Twelfth National Conference on Artificial Intelligence, (AAAI) Seattle, WA, 1994 [4] Cassandra, A.R. Exact and Approximate Algorithms for Partially Observable Markov Decision Processes. Ph.D. Thesis. Brown University, Department of Computer Science, Providence, RI, 1998 [5] Davey, N., Hunt, S.P. and Frank, R.J. Time Series Prediction and Neural Networks, Kluwer Academic Publishers Journal of Intelligent and Robotic Systems archive, Volume 31: May /July,2001 [6] Egeli, B., Ozturan, M. and Badur, B. Stock Market Prediction Using Artificial Neural Networks, Hawaii International Conference on Business, Honolulu, Hawaii, USA, 2003 [7] Elder, T. Creating Algorithmic Traders with Hierarchical Reinforcement Learning, MSc. Dissertation, Informatics University of Edinburgh, 2008 [8] Hamilton, W. The Stock Market Barometer: A Study of its Forecast Value Based on Charles H. Dow’s Theory of the Price Movement.. New York, NY: John Wiley & Sons,Inc., 1998 (reprint of 1922 edition) [9] Kirkpatrick, C. and Dahlquist, J. Technical Analysis: the Complete Resource for Financial Market Technicians. First. FT Press, 2006 [10] Kurniawati, H., Hsu, D., and Lee, W.S. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Proc. Robotics: Science and Systems, 2008 [11] Lambert, D. Commodity channel index: Tool for trading cyclic trends, Technical Analysis of Stocks & Commodities, Volume 1: July/August, 1983 101 [12] Lane, G. C.. Lane’s stochastics: the ultimate oscillator. Journal of Technical Analysis, May, 1985 [13] Lezos, G., and Tull, M. Neural network & fuzzy logic techniques for time series forecasting. Conference on Computational Intelligence for Financial Engineering, New York, NY, 1999 [14] Lin, L., Cao, L., Wang, J. and Zhang, C. The Applications of Genetic Algorithms in Stock Market Data Mining Optimisation, Fifth International Conference on Data Mining, Text Mining and their Business Applications, Malaga, Spain, 2004 [15] Murphy, J.J. Technical Analysis of the Financial Markets: A Comprehensive Guide to Trading Methods and Applications. Prentice Hall Press, 1999 [16] Nau, D., Ghallab, M., and Traverso, P. Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc. , 2004 [17] Nison, S. Japanese Candlestick Charting Techniques, Second Edition. Prentice Hall Press., 2001 [18] Pineau, J., Gordon, G., and Thrun, S. Point-based value iteration: An anytime algorithm for POMDPs. In Proc. Int. Joint Conf. on Artificial Intelligence, Acapulco, Mexico, 2003 [19] Puterman, M.L. Markov Decision Processes : DiscreteStochastic Dynamic Programming. New York : John Wiley & Sons, 1994 [20] Smith, T. and Simmons, R. Heuristic search value iteration for POMDPs. In Proceedings of the 20th Conference on Uncertainty in Artificial intelligence (Banff, Canada, July 07 11, 2004). ACM International Conference Proceeding Series, vol. 70. AUAI Press, Arlington, Virginia, 520-527, 2004 [21] Smith, T., Thompsom,D.R., and Wettergreen,D.S. Generating exponentially smaller POMDP models using conditionally irrelevant variable abstraction. In Proc. Int. Conf. on Applied Planning and Scheduling (ICAPS), 2007 [22] Wilder, J.W. New Concepts in Technical Trading Systems. Greensboro, SC: Trend Research, 1978 [23] Zahedim, R. and Chong, E., Portfolio Management using Partially Observable Markov Decision Processes, Colorado State University Information Science and Technology Research Colloquium, 2005 [24] Saad, Emad W., Prokhorov, Danil V., Wunsch II, Donald C., Comparative Study of Stock Trend Prediction Using Time Delay, Recurrent and Probabilistic Neural Networks. IEEE Transactions on Neural Network, 1998 102 [25] Fu, Tak-chung, Cheung, Tsz-leng, Chung, Fu-lai, Ng, Chak-man, An Innovative Use of Historical Data for Neural Network Based Stock Prediction. JCIS-2006 Proceedings, 2006 [26] Chang, Pei-Chann, Liu, Chen-Hao, Fan, Chin-Yuan, Lin, Jun-Lin, Lai, Chih-Ming, An Ensemble of Neural Networks for Stock Trading Decision Making. Lecture Notes in Computer Science, 2009 [27] Tilakaratne, C. D., Morris, S. A., Mammadov, M. A., Hurst, C. P., Predicting Stock Market Index Trading Signals Using Neural Networks. Proceedings of the 14th Annual Global Finance Conference, Melbourne, Australia, 2007 [28] Kainijo, Ken-ichi, Tanigawa Tetsuji, Stock Price Pattern Recognition - A Recurrent Neural Network Approach. Proc of Int Conf Neural Networks, 1990 [29] Lin, Chang-Chun, Liu, Yi-Ting, Genetic algorithms for portfolio selection problems with minimum transaction lots. European Journal of Operational Research, 2007. [30] Qin, Sen, Log-optimal Portfolio Models with Risk Control of VaR and CVaR Using Genetic Algorithms. Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, Shanghai, China, 2009. [31] Chen, Mei-Chih, Lin, Chang-Li, Chen, An-Pin, Constructing a dynamic stock portfolio decision-making assistance model: using the Taiwan 50 Index constituents as an example. Special issue on intelligent systems for financial engineering and computational finance, 2007 [32] Fuente, David de la, Garrido, Alejandro, Laviada, Jaime, Gómez, Alberto, Genetic Algorithms to Optimise the Time to Make Stock Market Investment. Proceedings of the 8th annual conference on Genetic and evolutionary computation table of contents, Seattle, USA, 2006 [33] Potvina, Jean-Yves, Sorianoa, Patrick, Vallée, Maxim, Generating trading rules on the stock markets with genetic programming. Computers and Operations Research archive, 2004 [34] Allen, Franklin, Karjalainen, Risto, Using genetic algorithms to find technical trading rules. Journal of Financial Economics, 1999 [35] Garcia-Almanza, Alma Lilia, Tsang Edward P.K., Forecasting stock prices using Genetic Programming and Chance Discovery. Computing in Economics and Finance, 2006 [36] Li, Hailin, Dagli, Cihan H., Enke, David, Short-term Stock Market Timing Prediction under Reinforcement Learning Schemes. IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning, 2007 103 [37] Nevmyvaka, Yuriy, Feng, Yi, Kearns, Michael, Reinforcement Learning for Optimized Trade Execution. Proceedings of the 23rd international conference on Machine learning, Pittsburgh, Pennsylvania, 2006 [38] Mabu, Shingo, Hirasawa, Kotaro, Furuzuki, Takayuki, Trading Rules on Stock Markets Using Genetic Networking Programming with Reinforcement Learning and Importance Index. [39] Baffa, Augusto C. E., Ciarlini, Angelo E. M., Modeling POMDPs for Generating and Simulating Stock Investment Policies. Proceedings of the 25st ACM Symposium On Applied Computing, Sierre, Switzerland, 2010. [40] Perez, Dennis D., Anytime Point Based Approximations for Interactive POMDPs. M.Sc. Thesis. University of Georgia, Department of Computer Science, Athens, Georgia, 2007 [41] Haugen, Robert, Os Segredos da Bolsa. Editora Person Education do Brasil, São Paulo, Brasil, 2000 [42] Noronha, Marcio, Análise Técnica: Teorias, Ferramentas e Estratégias, Editora Editec, São Paulo, Brasil, 1995 [43] Haykin, Simon, Neural Networks: A Comprehensive Foundation. 2nd Edition, Prentice Hall, 1998 [44] Russell, Stuart, Norvig, Peter, Artificial Intelligence: A Modern Approach. 2nd Edition, Prentice Hall, 2002 [45] Smallwood, Richard D., Sondik, Edward J., The Optimal Control of a Partially Observable Markov Processes over a Finite Horizon. Operations Research, Vol. 21, No. 5, 1973 104