Este artigo aborda o uso do MapReduce na solução de um problema complexo, que é melhor resolvido com a técnica de algoritmos genéticos (AG). Apesar da natureza iterativa dos AGs, com algumas adaptações é possível construir aplicações que necessitem de grande poder de processamento e que podem ser executadas de forma paralela e distribuída no modelo MapReduce. Entre os softwares que podem ser beneficiados, há algoritmos de inteligência computacional, como AGs e redes neurais, e qualquer problema de otimização que necessite encontrar boas respostas em situações que normalmente são difíceis de serem resolvidas com aplicações tradicionais em uma única máquina. Por exemplo, sistemas para identificar padrões em biometria, formulação de regras em jogos de estratégia, na busca de melhores rotas (caminhos) a serem percorridas em um conjunto de cidades, como é o caso do exemplo tratado neste artigo, entre outros.
Problemas que envolvem o tratamento de grandes conjuntos de dados têm como solução ideal o uso de um modelo de processamento paralelo e distribuído que se adapta a qualquer volume e grau de complexidade. Esse é o caso do MapReduce, uma técnica que abstrai os detalhes de paralelização e distribuição do processamento de dados, que pode ser utilizada em aplicações que necessitem dessas características, como ocorre com algumas abordagens não triviais, a exemplo do tratamento do “big data” e do processamento de algoritmos de alta complexidade e escalabilidade.
Tais algoritmos podem ser empregados em diversas situações que envolvam resolver problemas de busca e otimização, normalmente presentes em sistemas de tomada de decisão e descoberta de conhecimento. Por exemplo, escolher qual a melhor empresa para investir o capital (quantia) na bolsa de valores; solucionar problemas de agendamento e planejamento de recursos; auxiliar na organização e alocação de turmas a professores, presente na definição de grades horárias de trabalho; e qualquer situação que necessite uma boa solução (entre tantas), considerando as regras específicas para o domínio do problema a fim de alcançar o melhor resultado possível. Como podemos notar, são problemas complexos, muitas vezes de difícil solução e que envolvem significativas reduções de custos, melhorias dos tempos de processos e/ou melhor alocação dos recursos em atividade.
Como o MapReduce pode ajudar na solução desses problemas? Em essência, a resposta está na capacidade do poder de processamento paralelo e distribuído da técnica, fatores que permitem alta escalabilidade à solução.
O MapReduce é baseado no paradigma de programação funcional, adotando duas funções que dão nome ao modelo: a função map e a função reduce. Esse modelo estabelece uma abstração que permite construir aplicações com operações simples, escondendo os detalhes da paralelização. Em resumo, tais funções transformam um grande volume de dados de entrada em um conjunto resumido e agregado na saída, sendo cada função executada em uma etapa distinta. Na primeira etapa, Map, uma função de mapeamento distribui os dados em diversos nós de processamento e armazenamento. Na segunda etapa, Reduce, uma função agrega e sumariza os resultados obtidos no mapeamento, para gerar um resultado final.
A técnica MapReduce pode ser aplicada em vários campos, como o agrupamento de dados, aprendizado de máquina e visão computacional. Outro exemplo de campo que pode adotar essa técnica é o da Inteligência Computacional, em especial o dos Algoritmos Genéticos, que devem tratar uma grande base de dados (a chamada população de indivíduos) para localizar valores para uma tomada de decisão. Tais algoritmos exigem um alto custo de processamento para ser executado em uma única máquina, o que torna a técnica MapReduce ideal para ser adotada.
Com base nisso, este artigo demonstra o uso combinado da abordagem AG com MapReduce para resolver um tipo especial de problema complexo, chamado de “caixeiro viajante” (ou PCV). Este problema busca identificar os melhores caminhos para se percorrer um conjunto de cidades, visitando pelo menos uma vez cada cidade em um determinado percurso. O PCV envolve um número de combinações de caminhos de crescimento exponencial, em função do número de cidades, fato que o torna complexo para ser resolvido com algoritmos tradicionais. Para validar a técnica proposta (AGs adaptados ao modelo MapReduce), um cenário de teste foi aplicado para um conjunto de vinte cidades, o que demonstrou um bom desempenho na geração de boas respostas.
Pré-requisitos
Este tutorial foi projetado para ser executado em um computador com sistema operacional Linux, seja nativo ou rodando em uma máquina virtual (VMware ou VirtualBox, por exemplo), uma vez que o framework Hadoop (que implementa o MapReduce) utiliza tal ambiente. Em ambos os casos (nativo ou virtualizado), recomenda-se que a memória principal tenha no mínimo 1 Gigabyte e espaço em disco suficiente para comportar a instalação do pacote Hadoop. Por se tratar de uma aplicação que simula a maioria dos dados em memória, o espaço em disco exigido é no mínimo de 2 Gigabytes.
Além do espaço da aplicação, ao final foram utilizados aproximadamente dez gigabytes de espaço em disco para a distribuição Linux (Ubuntu, versão 12), para a instalação do Apache Hadoop (versão 1.2) e para a IDE Eclipse (versão Kepler 4.2).
Algoritmos Genéticos
A otimização é o processo de encontrar a melhor solução (ou solução ótima) de um conjunto de soluções para um problema. Normalmente, tais problemas envolvem um procedimento para escolha otimizada de recursos, que pode ser de natureza temporal/cronológica, financeira/econômica, de espaço físico, de priorização de tarefas, etc. Sendo assim, um processo de otimização procura, geralmente, maximizar lucros, minimizar perdas, realizar projetos econômicos e seguros, maximizar a capacidade de transmissão de uma rede satisfazendo suas limitações, escolher o melhor investimento, definir quando comprar e quando vender ações na bolsa de valores, traçar o roteiro de viagem e muitos outros exemplos. Em síntese, quando se fala em otimização, está se pensando em maximizar ou minimizar uma função, chamada de função objetivo, sujeita a certas restrições.
As técnicas de otimização devem ser utilizadas quando não existe uma solução simples e diretamente calculável para o problema. Isso geralmente ocorre quando a estrutura do problema é complexa ou existem muitas formas possíveis de resolver. Nesses casos, é possível que não exista uma equação direta ou um procedimento matemático ou algorítmico para resolver o problema, de forma que uma técnica de otimização seja a mais indicada para encontrar (ou se aproximar) da melhor resposta possível para o problema.
Para aplicar uma técnica de otimização, dois conceitos são relevantes: o espaço de busca, “local” onde todas as possíveis soluções do problema se encontram; e a função objetivo, utilizada para avaliar as soluções produzidas, associando a cada uma delas um valor que denota uma nota ou peso a ser considerado na avaliação.
O Algoritmo Genético é uma técnica de otimização inspirada no conceito da evolução natural das espécies. Essa técnica parte da ideia da sobrevivência do indivíduo mais apto em uma população. Traduzindo para o contexto computacional, um indivíduo pode ser a representação de uma informação em um conjunto de dados para um domínio particular, e o mais apto é o indivíduo que está próximo da melhor informação que se tenta localizar no espaço de busca (ou base de dados da solução). Dessa forma, um AG é um procedimento de otimização para encontrar a melhor (ou melhores) resposta(s), sem a necessidade de explorar todas as soluções possíveis nesse espaço de busca.
Para criar uma população de possíveis respostas para um problema, o AG usa um processo evolutivo. Em seguida, combina as melhores soluções para criar uma nova geração de soluções que deve ser melhor do que a geração anterior. Portanto, é um processo iterativo realizado em várias etapas (ou gerações) constituído das seguintes atividades:
1. Inicialização: É a criação da população inicial para o primeiro ciclo do algoritmo. A criação envolve produzir um conjunto de dados pertinentes com o contexto real do problema, podendo ser gerada aleatoriamente por meio de uma rotina automática;
2. Avaliação: Avalia-se a aptidão das soluções analisando a resposta de cada uma ao problema proposto;
3. Seleção: Os indivíduos são selecionados para combinação das características (para a reprodução). A seleção é baseada na aptidão dos indivíduos;
4. Cruzamento: Características das soluções escolhidas são recombinadas, gerando novos indivíduos;
5. Mutação: Características dos indivíduos resultantes do processo de reprodução são alteradas;
6. Atualização: Os indivíduos criados na iteração da etapa corrente são inseridos na população que será tratada na próxima iteração;
7. Finalização: Verifica se as condições de encerramento da evolução foram atingidas.
Em síntese, o processo inicia com a definição para o conceito de “indivíduo”, que deve ser codificado em uma representação que possa estruturar os dados para a solução do problema. A população inicial de indivíduos é então preparada, geralmente de forma aleatória, seguindo critérios estabelecidos a partir de uma função objetivo, que define a aptidão de cada indivíduo ao contexto do problema. Essa aptidão, u ...
