IntroduçãoVocê verá nesta página um tutorial introdutório sobre a utilização de Algoritmos Genéticos. Serão analisados os principais aspectos e características da Computação Evolucionária e dos Algoritmos Genéticos (AGs) que os fazem extremamente interessantes como ferramenta de busca e otimização para a solução dos mais diferentes tipos de problemas.
IntroduçãoProjeto
Evolucionário de Arquiteturas NeuraisAbordagens
de RepresentaçãoAvaliação
de DesempenhoOperadores
GenéticosHot
Links
Os sistemas baseados em Redes Neurais Artificiais como as MLP, dependem fortemente
da topologia destas redes (tamanho, estrutura, conexões), assim como
de seus parâmetros (taxa de aprendizado, termo momentum). Como resultado,
a determinação da arquitetura da rede afeta muito o seu desempenho,
isto é, velocidade de aprendizado, exatidão do aprendizado, tolerância
a ruídos e capacidade de generalização.
É grande a dificuldade de se projetar Redes Neurais eficientes; existem algumas técnicas, nas quais são envolvidos alguns conhecimentos empíricos, que podem ajudar em alguns caso.
Uma abordagem muito utilizada na prática é a construção de redes com arquiteturas padronizadas, ou uma já utilizada em outros sistemas; o teste dessa rede para a função desejada e alteração da estrutura e parâmetros da rede até que se tenha uma arquitetura razoavelmente adequada para a aplicação desejada. Esse tipo de abordagem tem um custo muito elevado e não apresenta resultados muito confiáveis; além disso, não é possível garantir a otimização da solução, pois o critério de desempenho é baseado em uma combinação complexa de fatores. Este é um típico problema de otimização "multi-criterial". Assim, várias técnicas para automação de projeto de arquiteturas neurais para classes particulares de problemas vêm sendo pesquisadas. Uma destas técnicas é a utilização de abordagens evolucionárias como heurística de busca de arquiteturas aproximadamente ótima.
Algoritmos Genéticos proporcionam a abordagem mais natural para a solução deste problema, especialmente porque o cérebro humano também é, de alguma forma, resultado da evolução biológica.
Segundo o pesquisador Gerald Edelman, prêmio Nobel de 1972, a mente humana é resultado da seleção natural. Ele sugere que o aparecimento de sulcos cerebrais cada vez mais acentuados levou a um aumento significativo na área total do cérebro, o que, em outras palavras, significa um maior número de neurônios num mesmo espaço físico. Além disso, sugere que as conexões entre os neurônios não foram predeterminadas, mas foi algo que evoluiu para competir com as circunstâncias impostas pelo ambiente.
A arquitetura do cérebro foi, durante milhões de anos de evolução, astuciosamente modelada através da genética e da seleção natural. Assim, neste projeto, deseja-se utilizar uma abordagem artificialmente equivalente, para resolver este problema para "seres" também artificiais, que neste caso seriam Redes Neurais Artificiais.
Existem, ainda, outras possibilidades de utilização da abordagem evolucionária em Redes Neurais Artificiais, tais como a sua utilização como algoritmo de treinamento e na determinação de conjuntos de dados de treinamento, validação e teste.
Neste primeiro trabalho, será analisada apenas sua utilização para definição de arquiteturas e parâmetros de redes "feed-forward".
Para a aplicação de Algoritmos Genéticos, visando a resolução
de problemas específicos, tais como no projeto de arquiteturas neurais,
é necessário fornecer algumas informações a respeito
do problema, tais como:
Representação:
estes algoritmos utilizam representações "genéticas"
das possíveis soluções, normalmente na forma de vetores.
Assim, deve-se fornecer uma representação adequada da arquitetura
destas redes e uma função que transforme esta representação
genotípica, utilizada por estes algoritmos, em soluções
fenotípicas: arquiteturas de redes.
Desempenho:
é preciso que seja fornecida uma função que associe um
valor relacionado ao desempenho (performance), para cada uma das redes da população.
Este valor deve refletir a aptidão destas redes na solução
do problema considerado.
Reprodução:
deve-se especificar os operadores de cruzamento e mutação que
permitam a criação de novas gerações de arquiteturas
de redes, a partir de seus pais. A especificação destes operadores
depende fortemente da representação utilizada, em alguns casos
podem ser necessárias funções para assegurar que estas
novas gerações de redes sejam soluções válidas.
Estes aspectos serão analisados em maiores detalhes nas próximas seções. Agora, serão vistos os principais processos desta abordagem, ilustrados na figura abaixo. Neste caso, cada indivíduo pode ser visto como um estado do espaço de redes "feed-forward".
Iniciando o processo com uma população de representações genotípicas de redes válidas, geradas aleatoriamente, um gerador reconstrói essas redes (fenótipos) a partir de sua representação (genótipos), de acordo com a função de transformação utilizada.
Em seguida, um simulador treina todas as redes com um mesmo conjunto de dados de treinamento, e seus desempenhos sob dados de teste são avaliados. Com isso, são obtidos alguns dados que podem servir como critérios de desempenho, tais como: erro quadrático médio sob os dados de treinamento, validação e teste; tamanho da rede (número de unidades e conexões); número de ciclos de treinamento. Com esses dados, é possível avaliar o atual estado da população e determinar uma nota de aptidão para cada rede, de acordo com o seu desempenho em relação a todas as outras redes.
Através de um método como o da roleta são selecionadas as redes, de acordo com uma probabilidade relativa associada às suas notas de adaptação. Isto é feito até preencher o espaço de população, onde serão colocadas para reprodução regida pelos operadores genéticos de cruzamento e mutação; através destes operadores, é construída uma nova geração de arquiteturas neurais.
Para evitar que as melhores redes desapareçam rapidamente da população, pode ser utilizada uma política elitista, que faz com que estas redes estejam presentes na próxima geração. Esse ciclo é repetido e, com a passagem de novas gerações, a população vai gradativamente evoluindo rumo a genótipos que correspondam a fenótipos de mais altos desempenhos.
Isto é feito um determinado número de vezes, até que o algoritmo encontre soluções adequadas ao problema, ou, em casos extremos, até convergir para uma solução. Durante este processo, as melhores redes, assim como alguns dados estatísticos, podem ser coletados e armazenados, para uma análise posterior sobre o seu andamento.
A questão de como uma arquitetura neural é representada genotípicamente
é crítica no projeto de um sistema deste tipo. A representação
ou codificação utilizada determina não apenas as classes
de arquiteturas neurais que poderiam evoluir, mas também o funcionamento
do processo de decodificação e dos operadores de reprodução.
A representação da estrutura de uma rede neural não é tão direta. Alguns fatores devem ser considerados: se a representação permite que soluções ótimas ou proximamente ótimas sejam representadas; como estruturas inválidas poderiam ser excluídas; como deveriam atuar os operadores de reprodução, de forma que a nova geração possua somente arquiteturas neurais válidas; como a representação suportaria o crescimento de arquiteturas neurais.
O ideal seria que o espaço genético de arquiteturas neurais não contivesse genótipos de redes inviáveis e que pudesse expandir este espaço a todos os genótipos de arquiteturas potencialmente úteis.
Existem dois paradigmas de representação de arquiteturas neurais: a representação direta, ou de baixo-nível e a representação indireta ou de alto-nível. Existe uma clara distinção entre estes dois paradigmas.
Uma representação direta especifica exatamente cada parâmetro da rede, e requer pouco esforço de decodificação, pois a transformação de genótipos em fenótipos é trivial. Um exemplo é a codificação em uma matriz de conexões, que especifica de maneira direta e precisa a topologia de uma rede neural. Contudo, este tipo de codificação pode deixar o espaço de busca muito grande, com isto o algoritmo poderá necessitar de um maior número de iterações, sendo útil apenas para topologias neurais relativamente pequenas.
Um método de representação direta muito utilizado para a representação genotípica de topologias neurais é mapear as estruturas na forma de matrizes de conexões binárias, onde cada elemento da matriz determina se a conexão entre duas unidades existe ou não. Este método é ilustrado na figura abaixo. O problema principal dessa abordagem é que podem ser geradas estruturas incorretas, isto é, conexões com realimentação (feedback), além da necessidade de códigos muito grandes para grandes redes.
Por outro lado, as representações indiretas exigem um esforço considerável para a decodificação na construção de fenótipos. No entanto, este tipo de representação utiliza descrições abstratas para a caracterização das redes, geralmente através de codificações gramaticais. Além disso, as redes podem ser pré-estruturadas utilizando restrições para excluir algumas arquiteturas indesejáveis, o que faz com que o espaço de busca seja muito menor.
Desse modo, as buscas podem ser focalizadas na procura das melhores redes. Alguns métodos sofisticados trabalham com representações indiretas, através de descrições de redes em termos de vários parâmetros, como número de camadas, tamanho das camadas e conexões entre camadas, possibilitando a colocação de restrições na arquitetura das redes e reduzindo o número de estruturas incorretas. Com isso, o número de estruturas a serem treinadas e avaliadas, assim como o número de ciclos evolucionários necessários para se chegar à boas redes, são drasticamente reduzidos.
Um destes métodos, proposto por Mandisher, utiliza uma representação que descreve os componentes principais das redes, os quais podem ser divididos em duas áreas: área de parâmetros e área de camadas. A área de parâmetros especifica a taxa de aprendizado e o termo momentum para todas as conexões da rede. Cada camada tem sua própria área de camada, especificando o número de unidades na camada e as conexões às outras camadas. As conexões são separadas em projetivas (conexões com camadas posteriores) e receptivas (conexões com camadas anteriores), e são especificadas através dos parâmetros raio e densidade. O parâmetro raio especifica o raio de conexão para cada unidade, e é dado pela porcentagem relativa ao tamanho da camada de destino. Já o parâmetro densidade especifica a densidade de conexões de uma unidade receptiva, e é dado pela porcentagem de unidades que estão conectadas a esta unidade, como ilustra a figura abaixo.
Não é possível avaliar o desempenho das redes de modo direto.
Só depois de terem sido treinadas, as redes podem ser avaliadas. Os resultados
obtidos serão utilizados para estimar a qualidade das arquiteturas neurais.
As redes deverão ser treinadas por um número determinado de ciclos,
utilizando um mesmo conjunto de dados de treinamento e validação.
Após o treinamento, as redes poderão ser avaliadas utilizando
um conjunto de teste para determinar o desempenho destas redes com dados não
previamente utilizados.
Para a criação de uma função que associe um valor de desempenho para cada uma das redes, podem ser utilizadas algumas heurísticas que devem levar em conta alguns aspectos como: erro quadrático médio durante o treinamento e teste; integral do erro sobre o número de ciclos; tempo de treinamento; capacidade de generalização; tamanho das redes; entre outras. Tais heurísticas devem ponderar estes aspectos, dependendo do comportamento desejado para a aplicação. Por exemplo, para determinadas aplicações, a característica mais desejável poderá ser uma maior capacidade de generalização, e para outras poderá ser uma menor taxa de erro, ou ainda uma menor arquitetura.
Como a avaliação das arquiteturas neurais envolve treinamentos e testes, o custo computacional é muito elevado. No entanto, devido às características inerentemente paralelas dos algoritmos envolvidos, sua utilização em ambientes distribuídos ou em implementações paralelas pode reduzir estes custos.
Os operadores genéticos são utilizados para transformar a população
de arquiteturas neurais através das gerações, diversificando
esta população e mantendo as características de adaptação
desejáveis adquiridas pelas gerações anteriores. Eles são
especificados de acordo com a representação utilizada. Podem utilizar
funções que limitem suas transformações, heurísticas
de transformação de acordo com a funcionalidade desejada, além
de funções que assegurem a validade das arquiteturas neurais geradas.
Quando uma rede é escolhida para mutação, um de seus parâmetros é alterado, seguindo o princípio de que este operador deve causar apenas pequenas mudanças qualitativas. Estes parâmetros podem ser os seguintes: taxa de aprendizado, termo momentum, ou tamanho de uma camada escolhida aleatoriamente. Este operador também pode ser utilizado para a alteração das conexões, inserindo uma nova conexão válida, ou removendo uma conexão existente.
Em representações indiretas, o operador mutação pode ser utilizado para alterar o raio ou densidade de uma área de conexão escolhida aleatoriamente. Cada um desses parâmetros deve ter limites máximos e mínimos, e uma taxa de mudanças máxima para prevenir que essas mudanças sejam muito radicais.
O operador genético de cruzamento, é responsável pela recombinação de características das redes durante a reprodução, permitindo que as próximas gerações herdem essas características. O cruzamento, operador genético predominante, pode ser utilizado de várias maneiras, as mais conhecidas são:um-ponto, multi-pontos e uniforme.
A seguir serão analisadas as mais utilizadas: cruzamento de um-ponto e de multiplos-pontos.
O operador cruzamento
de um-ponto faz uma troca de camadas entre duas redes, onde essas redes
são selecionadas com probabilidade dada pela taxa de crossover Pc1.
Através de uma ordenação linear das camadas, um número
escolhido aleatoriamente especifica o ponto de recombinação
no qual as camadas serão trocadas.
O operador cruzamento
de multiplos-pontos faz uma troca de camadas entre duas redes, com n pontos
de recombinação p1, p2, ... , pn escolhidos também
aleatoriamente, indicando quais camadas serão trocadas. Novamente
essas redes são escolhidas com probabilidade dada pela taxa de crossover
de multiplos-pontos Pcm.
Com a troca de camadas, apenas novos indivíduos válidos são gerados e assim somente redes corretas participam da evolução. A maneira de se determinar as conexões entre essas camadas deve ser ditada pela heurística escolhida e pela representação utilizada. Dependendo da representação, este operador pode também ser utilizado para recombinar outros parâmetros da rede.
TópicosRedes
Neurais ArtificiaisAlgoritmos
Genéticos
Links
para páginas sobre EDNA.
Back
to my personal page!