65ª Reunião Anual da SBPC

A. Ciências Exatas e da Terra - 2. Ciência da Computação - 6. Inteligência Artificial e Redes Neurais

IMPLEMENTAÇÃO DE UM SEQUENCIADOR NUMÉRICO UTILIZANDO ALGORITMO GENÉTICO

Victor Silva de Freitas - Departamento de Engenharia Elétrica - CTC - UFSC Juan Ferreira Vidal - Faculdade de Engenharia Elétrica - ITEC - UFPA Danielle Lima Guedes - Faculdade de Engenharia Elétrica - ITEC - UFPA Duaymy Bruno Rodrigues Góes - Faculdade de Engenharia Elétrica - ITEC - UFPA Victor Marttan Pichara de Oliveira Ribeiro - Faculdade de Engenharia Elétrica - ITEC - UFPA Orlando Fonseca Silva - Prof. Dr./Orientador - Faculdade de Engenharia Elétrica - ITEC - UFPA

INTRODUÇÃO:

Os Algoritmos Genéticos (AG) são algoritmos matemáticos que permitem a realização de técnicas de busca e de otimização, utilizando os mecanismos de evolução natural e recombinação genética. A técnica fornece um mecanismo de busca adaptativa que se baseia no princípio Darwiniano de reprodução e sobrevivência dos seres ou indivíduos mais aptos. Deste modo, esta ferramenta pode ser empregada em vários tipos de situações, como por exemplo, na mineração de dados. Neste último exemplo, que visa à exploração de grandes quantidades de dados, são utilizados diversos métodos numéricos e lógicos que, uma vez implementados em um espaço amostral, buscam por padrões ou sequências para detectar relacionamentos sistemáticos entre variáveis. Baseando-se nestas formulações, um sequenciador numérico pode ser implementado de diversas formas e em diversos ambientes de programação e é capaz de auxiliar na mineração de dados, sejam os dados totalmente numéricos ou tenham relação numérica para chegar a um ponto ótimo. Assim, este trabalho visa a formulação de um AG, em ambiente Matlab, para sequenciar dados numéricos aleatórios, na ordem decrescente.

OBJETIVO DO TRABALHO:

Os objetivos deste trabalho são: a construção de um Algoritmo Genético em ambiente Matlab com uma função de avaliação de indivíduos para sequenciar números de forma decrescente; e realizar testes com sequências de n números naturais e racionais positivos aleatórios.

MÉTODOS:

No ambiente Matlab foi construído um Algoritmo Genético através de linhas de programação, partindo da criação de uma população aleatória e finita, sendo cada indivíduo representado por um cromossomo possuindo 44 genes binários e sequenciados randomicamente. Cada indivíduo foi transformado para a representação decimal, onde se consideram a largura do cromossomo e parâmetros da matriz na qual se deseja sequenciar, que são os valores superior e inferior. Cada valor decimal dos indivíduos é avaliado a partir de uma função de custo, representada pelo o inverso quadrático do módulo do desvio, onde o último é a diferença entre o valor máximo da matriz para sequenciar e o valor decimal de cada indivíduo. A partir de uma roleta viciada são escolhidos os pais, com maior probabilidade de escolha aqueles com maior avaliação numérica. Os filhos são reproduzidos baseando-se na combinação aleatória dos genes dos pais (com 5% de chance de mutação), e formarão uma nova população de número igual à geração anterior, e posteriormente são avaliados. Isto se repete uma quantidade finita de vezes, para obter um valor da matriz para sequenciar. Assim, haverá uma nova matriz com um novo valor máximo para o qual o AG deverá convergir e a rotina de programação irá sequenciar estes valores de máximo.

RESULTADOS E DISCUSSÃO:

A implementação do Algoritmo Genético no ambiente Matlab resultou nas seguintes características: a utilização de uma grande faixa de largura para os indivíduos permitiu que os genes dos mesmos, contendo as informações importantes, fossem transmitidos para as gerações posteriores; a maneira da reprodução dos filhos, sendo realizada na escolha de gene a gene, resultou em seres com conteúdo mais variado dos pais; a quantidade da população, com 100 indivíduos, mostrou-se bastante diversificada, não ocorrendo convergências precoces e errôneas, assim como o número de gerações estipuladas, com total de 50 gerações, que tenderam para os valores de ótimo sendo os mais exatos possíveis, ou seja, sem a presença de erros; a função de avaliação, ou de custo, apresentou-se capaz de encontrar os pontos de máximos das matrizes para sequenciar; foi presenciada a mutação no decorrer da simulação, porém, com percentagem estipulada e com o tamanho da população, não resultou em erros ou interferiu nos valores de ótimo; todas as matrizes para sequenciar, tanto as compostas por números naturais, quanto por números racionais foram sequenciadas com sucesso.

CONCLUSÕES:

O algoritmo genético implementado mostrou-se bastante eficiente, tanto para entrada de dados numéricos inteiros quanto racionais, e observou-se que a rotina de programação é útil e capaz de executar a mineração de dados aleatórios. Tendo em vista a importância dos trabalhos de pesquisa relacionados ao estudo de aplicações de algoritmos genéticos, projetos futuros buscarão aprimorar as mesmas, tais como a inserção de maiores informações ao algoritmo projetado, de modo que execute uma busca mais completa dessas informações requeridas por um usuário, além de abordar novas temáticas dentro desse campo científico.

Palavras-chave: Mineração de Dados, Matlab, Programação Orientada a Objeto.