sexta-feira, janeiro 16, 2009

,

Algoritimos Genéticos [AG] III


bom continuando o artigo sobre algoritimo genético II, vamos entrar mais afundo nessa maravilha que é a genética humana? :D continuando... então vamos fazer uma descrição basica sobre o mesmo.
Algoritmos Genéticos são inspirados na teoria da evolução de Darwin. Solução de um problema através de algoritmos genéticos utiliza um processo evolucionário (a solução é desenvolvida).

O algoritmo começa um um conjunto de soluções (representadas por cromossomas) chamados população. Soluções de uma população são utilizadas para formar uma nova população. Isto é motivado pela esperança que a nova população será melhor do que a primeira. Soluções que são selecionadas para formar novas gerações de soluções são selecionadas de acordo com sua adequação - quanto melhores, mais chances de reprodução terão.

Esse processo é repetido até que alguma condição é satisfeita (por exemplo o número de populações ou o aperfeiçoamento da melhor solução).
Exemplo
Como você já sabe se viu o capítulo sobre espaço de soluções, a solução de problemas pode freqüentemente ser expressa como a procura pelo extremo de uma função. Nós resolveremos aqui exatamente esse problema - dada uma função o algoritmo genético tenta achar o mínimo dessa função.
Experimente rodar o algoritmo genético no applet a seguir apertando o botão "Start". O gráfico representa o espaço de soluções e as linhas verticais representam soluções (pontos no espaço de soluções). A linha vermelha é a melhor solução e as verdes são as outras.
O botão "Start" inicia o algoritmo, o botão "Step" executa um passo (isto é, produz uma nova geração), o botão "Stop" pára o algoritmo e o botão "Reset" reinicia a população.

"Segue aqui exemplo do site do Dr marek"


Esboço Básico do Algoritmo Genético

  1. [Início] Gere uma população aleatória de n cromossomas (soluções adequadas para o problema)
  2. [Adequação] Avalie a adequação f(x) de cada cromossoma x da população
  3. [Nova população] Crie uma nova população repetindo os passos seguintes até que a nova população esteja completa
    1. [Seleção] Selecione de acordo com sua adequação (melhor adequação, mais chances de ser selecionado) dois cromossomas para serem os pais
    2. [Cruzamento] Com a probabilidade de cruzamento cruze os pais para formar a nova geração. Se não realizar cruzamento, a nova geração será uma cópia exata dos pais.
    3. [Mutação] Com a probabilidade de mutação, altere os cromossomas da nova geração nos locus (posição nos cromossomas).
    4. [Aceitação] Coloque a nova descendência na nova população
  4. [Substitua] Utilize a nova população gerada para a próxima rodada do algoritmo
  5. [Teste] Se a condição final foi atingida, pare, e retorne a melhor solução da população atual
  6. [Repita] Vá para o passo 2

Alguns comentários

Como você viu, a estrutura deste Algoritmo Genético Básico é bastante geral. Há muitos parâmetros e ajustes que podem ser implementados de forma diferente em variados problemas.

A primeira questão a ocorrer é como criar cromossomas e que tipo de codificação escolher. Nós veremos então Cruzamento e Mutação, os dois operadores básicos dos Algoritmos Genéticos. A codificação do cruzamento e da mutação serão introduzidos no próximo capítulo.

A próxima questão é: como selecionar os pais para o cruzamento? Isso pode ser feito de muitas formas, mas a idéia principal é selecionar os melhores pais (os melhores sobreviventes), na suposição que os melhores pais produzirão as melhores descendências.

Você pode achar que gerando as populações apenas de dois pais, pode fazer com que se perca os melhores cromossomas da última população. Isto é verdade, e portanto, o elitismo é usado com freqüência. Isto significa que pelo menos uma cópia sem alterações da melhor solução da geração é passada para a nova população, de forma que a melhor solução possa sobreviver às sucessivas gerações.

Você deve estar querendo saber por que os Algoritmos Genéticos funcionam. Isso pode ser explicado parcialmente pelo Teorema do Esquema de Holland, entretanto, esse Teorema tem sido criticado ultimamente. Se você deseja saber mais, veja outras fontes.


V. Operadores dos Algoritmos Genéticos

Visão Geral

Ocruzamento e a mutação são as partes mais importantes do algoritmo genético. O desempenho é influenciado principalmente por esses dois operadores. Antes de detalharmos mais cruzamento e mutação, vejamos mais alguma informação sobre cromossomas.

A Codificação de um Cromossoma

Um cromossoma deve de alguma maneira conter a informação da solução que ele representa. A forma mais comum de codificar é uma série (string) binária. Um cromossoma pode então se parecer como isto:

Cromossoma 1 1101100100110110
Cromossoma 2 1101111000011110

Cada cromossoma é representado por uma série binária. Cada bit da série representa alguma característica da solução. Outra possibilidade é que a série toda possa representar um número - isso foi feito basicamente no applet AG. É claro, há muitas outras formas de codificar. A codificação dependerá principalmente do problema a ser solucionado. Por exemplo, um pode codificar diretamente números inteiros ou reais, algumas vezes é útil codificar algumas permutações, e assim por diante.

Cruzamento

Depois de decidirmos que codificação usaremos, podemos proceder a operação de cruzamento. O cruzamento opera em determinados genes dos cromossomas dos pais e cria novas descendências. A maneira mais simples de fazer isso é escolher aleatóriamente alguns pontos de cruzamento e copiar tudo o que vem antes desse ponto de um dos pais e então copiar tudo o que vem depois desse ponto do outro pai.

O Cruzamento pode ser ilustrado da seguinte maneira: ( | é o ponto de cruzamento):

Cromossoma 1 11011 | 00100110110
Cromossoma 2 11011 | 11000011110
Descendência 1 11011 | 11000011110
Descendência 2 11011 | 00100110110

Há outras maneiras de fazer cruzamento. Por exemplo, nós podemos escolher mais pontos de cruzamento. O cruzamento pode ser um pouco complicado e depender principalmente da codificação dos cromossomas. Cruzamentos especificos feitos para problemas específicos podem melhorar o desempenho dos algoritmos genéticos.


Mutação

Depois que um cruzamento é realizado, acontece a mutação. A mutação tem a intenção de prevenir que todas as soluções do problema dessa população caiam em um ponto ótimo local. A operação de mutação muda aleatóriamente a descendência criada pelo cruzamento. No caso de uma codificação binária, podemos mudar aleatóriamente alguns bits escolhidos de 1 para 0, ou de 0 para 1. A mutação pode então ser ilustrada como a seguir:

Descendência Original 1 1101111000011110
Descendência Original 2 1101100100110110
Descendência Mutada 1 1100111000011110
Descendência Mutada 2 1101101100110110

A técnica da mutação (da mesma forma que a do cruzamento) depende muito da codificação dos cromossomas. Por exemplo, quando codificamos permutações, mutações podem ser realizadas como uma troca de dois genes. (:

bom terminamos por aqui espero que tenham gostado que como estamos abordando o assunto por aqui!bons estudos ate a proxima []'s










0 comentários:

Postar um comentário