Diferenças entre edições de "Algoritmo genético"

Edição atual desde as 14h13min de 4 de outubro de 2008

Um algoritmo genético (AG) é uma técnica de procura utilizada na ciência da computação para achar soluções aproximadas em problemas de optimização e busca. Algoritmos genéticos são uma classe particular de algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade, mutação, selecção natural e recombinação (ou crossing over).

Algoritmos genéticos são implementados como uma simulação de computador em que uma população de representações abstratas de solução é selecionada em busca de soluções melhores. A evolução geralmente se inicia a partir de um conjunto de soluções criado aleatoriamente e é realizada através de gerações. A cada geração, a adaptação de cada solução na população é avaliada, alguns indivíduos são seleccionados para a próxima geração, e recombinados ou mutados para formar uma nova população. A nova população então é utilizada como entrada para a próxima iteração do algoritmo.

Algoritmos genéticos diferem dos algoritmos tradicionais de optimização em basicamente quatro aspectos:

• baseiam-se em uma codificação do conjunto das soluções possíveis, e não nos parâmetros da optimização em si;
• os resultados são apresentados como uma população de soluções e não como uma solução única;
• não necessitam de nenhum conhecimento derivado do problema, apenas de uma forma de avaliação do resultado;
• usam transições probabilísticas e não regras determinísticas.<ref name="goldberg">Goldberg, David E.. Genetic Algorithms in Search, Optimization, and Machine Learning. EUA: Addison-Wesley, 1989. </ref>

Algoritmo

Os Algoritmos genéticos são em geral algoritmos simples e fáceis de serem implementados. Segue abaixo um trecho de pseudo-código descrevendo um algoritmo genético:

função AlgoritmoGenético(população, função-objetivo) saídas: indivíduo
  entradas: população -> uma lista de indivíduos
            função-objetivo -> uma função que recebe um indivíduo e retorna um número real.
  repetir
     lista de pais := seleção(população, função-objetivo)
     população := reprodução(lista de pais)
  enquanto nenhuma condiçao de parada for atingida
  retorna o melhor indivíduo da população de acordo com a função-objetivo

A função objetivo é o objecto de nossa optimização. Pode ser um problema de optimização, um conjunto de teste para identificar os indivíduos mais aptos, ou mesmo uma "caixa preta" onde sabemos apenas o formato das entradas e nos retorna um valor que queremos optimizar. A grande vantagem dos algoritmos genéticos esta no facto de não precisarmos saber como funciona esta função objectivo, apenas tê-la disponível para ser aplicada aos indivíduos e comparar os resultados.

O indivíduo é meramente um portador do seu código genético. O código genético é uma representação do espaço de busca do problema a ser resolvido, em geral na forma de sequências de bits. Por exemplo, para optimizações em problemas cujos valores de entrada são inteiros positivos de valor menor que 255 podemos usar 8 bits, com a representação binária normal, ou ainda uma forma de código gray. Problemas com múltiplas entradas podem combinar as entradas em uma única sequência de bits, ou trabalhar com mais de um "cromossoma", cada um representando uma das entradas. O código genético deve ser uma representação capaz de representar todo o conjunto dos valores no espaço de busca, e precisa ter tamanho finito.<ref name="goldbergp80"> Para uma discussão sobre as formas de representação do espaço de busca, veja: Goldberg, David E.. Genetic Algorithms in Search, Optimization, and Machine Learning. EUA: Addison-Wesley, 1989. página 80</ref>.

A selecção também é outra parte chave do algoritmo. Em geral, usa-se o algoritmo de selecção por "roleta", onde os indivíduos são ordenados de acordo com a função-objectivo e lhes são atribuídas probabilidades decrescentes de serem escolhidos. A escolha é feita então aleatoriamente de acordo com essas probabilidades. Dessa forma conseguimos escolher como pais os mais bem adaptados, sem deixar de lado a diversidade dos menos adaptados. Outras formas de selecção podem ser aplicadas dependendo do problema a ser tratado<ref name="goldbergp121"> Veja em Goldberg, David E.. Genetic Algorithms in Search, Optimization, and Machine Learning. EUA: Addison-Wesley, 1989. página 121 uma comparação sobre diversas formas de seleção.</ref>.

A reprodução, tradicionalmente, é divididas em três etapas: acasalamento, recombinação e mutação. O acasalamento é a escolha de dois indivíduos para se reproduzirem (geralmente gerando dois descendentes para manter o tamanho populacional). A recombinação, ou crossing-over é um processo que imita o processo biológico homónimo na reprodução sexuada: os descendentes recebem em seu código genético parte do código genético do pai e parte do código da mãe. Esta recombinação garante que os melhores indivíduos sejam capazes de trocar entre si as informações que os levam a ser mais aptos a sobreviver, e assim gerar descendentes ainda mais aptos. Por último vem as mutações, que são feitas com probabilidade a mais baixa possível, e tem como objectivo permitir maior variabilidade genética na população, impedindo que a busca fique estagnada num mínimo local.<ref name="goldbergp147"> Veja em Goldberg, David E.. Genetic Algorithms in Search, Optimization, and Machine Learning. EUA: Addison-Wesley, 1989. página 147 para ver outras orperações que podem ser aplicadas nos indivíduos para a reprodução.</ref>.

Programação Genética

Por ser um algoritmo extremamente simples e eficiente, existem diversas variações em cima do algorítmo genético básico para se obter resultados melhores ou mesmo tratar novas classes de problemas. Uma dessas variações é a Programação genética. Na Programação genética os indivíduos representam pequenos programas de computador que serão avaliados de acordo com o resultado de sua execução. Estes programas podem ser expressões simples, como fórmulas aritméticas ou programas complexos, com operações de loop e condicionais, típicas de uma linguagem de programação comum.<ref name="koza">KOZA, J.R.. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992. </ref>

Bibliografia

• KOZA, J.R.. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.
• GOLDBERG, David E.. Genetic Algorithms in Search, Optimization, and Machine Learning. EUA: Addison-Wesley, 1989.
• NORVIG, Peter, RUSSEL, Stuart. Artificial Intelligence: A Modern Aproach. Upper Saddle River, NJ, EUA: Prentice Hall, 1995.

Ver também

• Lista de algoritmos

Referências

<references />

Esta página usa conteúdo da Wikipedia. O artigo original estava em Algoritmo_genético. Tal como o Think Finance neste artigo, o texto da Wikipedia está disponível segundo a GNU Free Documentation License.