Graduada

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2131 palavras )
  • Download(s) : 0
  • Publicado : 26 de abril de 2013
Ler documento completo
Amostra do texto
Algoritmos Genéticos: Fundamentos e Aplicações
Introdução:
 
Os problemas de otimização são baseados em três pontos principais: a codificação do problema, a função objetivo que se deseja maximizar ou minimizar e o espaço de soluções associado. Pode-se imaginar um problema de otimização como uma caixa preta com n botões, onde cada botão é um parâmetro do problema, e uma saída que é o valor dafunção objetivo, indicando se um determinado conjunto de parâmetros é bom ou não para resolver este problema.
Os algoritmos genéticos são uma família de modelos computacionais inspirados na evolução, que incorporam uma solução potencial para um problema específico numa estrutura semelhante a de um cromossomo e aplicam operadores de seleção e "cross-over" a essas estruturas de forma a preservarinformações críticas relativas à solução do problema. Normalmentes os AG's são vistos como otimizadores de funções, embora a quantidade de problemas para o qual os AG's se aplicam seja bastante abrangente.
Uma das vantagens de um algoritmo genético é a simplificação que eles permitem na formulação e solução de  problemas de otimização. AG's simples normalmente trabalham com descrições de entradaformadas por cadeias de bits de tamanho fixo. Outros tipos de AG's podem trabalhar com cadeias de bits de tamanho variável., como por exemplo AG's usados para Programação Genética. AG's possuem um paralelismo implícito decorrente da avaliação independente de cada uma dessas cadeias de bits, ou seja, pode-se avaliar a viabilidade de um conjunto de parâmetros para a solução do problema deotimização em questão. O AG é indicado para a solução de problemas de otimização complexos, NP-Completos, como o "caixeiro viajante", que envolvem um grande número de variáveis e, consequentemente, espaços de soluções de dimensões elevadas. Além disso, em muitos casos onde outras estratégias de otimização falham na busca de uma solução, os AG's convergem. Os AG's são numericamente robustos, ou seja, não sãosensíveis a erros de arredondamento no que se refere aos seus resultados finais.
Existem três tipos de representação possíveis para os cromossomos: binária, inteira ou real. A essa representação se dá onome de alfabeto do AG. De acordo com a classe de problema que se deseje resolver pode-se usar qualquer um dos três tipos.
Uma implementação de um algoritmo genético começa com uma populaçãoaleatória de cromossomos. Essas estruturas são, então, avaliadas e associadas a uma probabilidade de reprodução de tal forma que as maiores probabilidades são associadas aos  cromossomos que representam uma melhor solução para o problema de otimização do que àqueles que representam uma solução pior. A aptidão da solução é tipicamente definida com relação à população corrente.

A função objetivo deum problema de otimização é construída a partir dos parâmetros envolvidos no problema. Ela fornece uma medida da proximidade da solução em relação a um conjunto de parâmteros. Os parâmetros podem ser conflitantes, ou seja, quando um aumenta o outro diminui. O objetivo é encontrar o ponto ótimo. A função objetivo permite o cálculo da aptidão bruta de cada indivíduo, que fornecerá o valor a ser usado para o cálculo de sua probabilidade de ser selecionado para reprodução.
 

Principais conceitos:
 
cromossomo (genótipo) - cadeia de bits que representa uma solução possível para o problema.
gene - representação de cada parâmetro de acordo com o alfabeto utilizado (binário, inteiro ou real).
fenótipo - cromossomo codificado
população - conjunto de pontos (indivíduos) no Espaçode Busca
geração - iteração completa do AG que gera uma nova população
aptidão bruta - saída gerada pela função objetivo para um indivíduo da população
aptidão normalizada - aptidão bruta normalizada, entrada para o algoritmo de seleção.
aptidão máxima - melhor indivíduo da população corrente
aptidão média - aptidão média da população corrente
 
Operações Básicas de um AG simples...
tracking img