sexta-feira, janeiro 16, 2009

,

Algoritimos Genéticos [AG] V


lol de volta estaremos aqui continuando o artigo sobre algoritimos geneticos Iv.

Seleção

IntroduçãO

Como você já sabe de AG esboço, os cromossomas são selecionados de uma população para serem pais de um cruzamento. O problema é como selecionar esses cromossomas. De acordo com a teoria da evolução de Darwin, o melhor sobrevive para criar a descendência. Há muitos métodos para selecionar o melhor cromossoma. Exemplos são: seleção por roleta, seleção Boltzman, seleção por campeonato, seleção por classificação, seleção por estado estacionário, e outras.Algumas delas serão descritas a seguir.

Seleção por Roleta

Os pais são selecionados de acordo com sua adequação. Quanto melhores são os cromossomos, mais chances de serem selecionados. Imagine uma roleta onde são colocados todos os cromossomas da população. O lado de cada secção da roleta é proporcional ao valor da adequação de cada cromossoma: quanto maior for esse valor, mais larga a secção. Veja a imagem a seguir para um exemplo.











Uma bolinha é lançada na roleta e o cromossomo onde ela para é selecionado. Evidentemente os cromossomas com maiores valores de adequação serão selecionados mais vezes.

Este processo pode ser descrito pelo seguinte algoritmo:


  1. [Soma] Calcule a soma dos valores de adequação de todos os cromossomas da população - soma S.
  2. [Seleção] Gere um número aleatório no intervalo (0,S) - r.
  3. [Repetição] Percorra toda a população e some a adequação de 0 - soma s. Quando a soma s for maior que r, pare e retorne o cromossoma atual.

É claro, o passo 1 somente é realizado uma vez para cada população.

Seleção por Classificação

O método anterior de seleção tem problemas quando há grandes diferenças entre os valores de adequação. Por exemplo, se a melhor adequação dos cromossomas é 90% da soma de todas as adequações, então haverá cromossomas com chances muito baixas de serem selecionados.

A Seleção por Classificação primeiro classifica a população e então atribui a cada cromossoma um valor de adequação determinado pela sua classificação. O pior terá adequação igual a 1, o segundo pior 2 etc. de forma que o melhor terá adequação igual a N (número de cromossomas na população).

Você pode ver na figura seguinte como a situação muda depois de mudar a adequação pelos números determinados pela adequação.










Situação antes da Classificação (gráfico da adequação)












Situação depois da Classificação (gráfico dos números de ordem)

Agora todos os cromossomas tem uma chance de serem selecionados. Entretanto, este método pode resultar em menor convergência, porque os melhores cromossomas não se distinguem muito dos outros.

Seleção por Estado Estacionário

Este não é um método particular de seleção de pais. A idéia principal deste tipo de seleção é que a nova população deve ter uma grande parte de cromossomas que sobreviverão para a próxima geração.

A seleção tipo Estado Estacionário dos AG funciona do seguinte modo: Em cada nova geração uns poucos bons cromossomas (com alta adequação) são selecionados para a criação da descendência. A seguir alguns maus cromossomas (com baixa adequação) são removidos e novos descendentes são colocados em seus lugares. Todo o resto da população sobrevive para as próximas gerações.

Elitismo

A idéia básica do elitismo já foi introduzida. Quando criamos uma nova população por cruzamento e mutação, nós temos uma grande chance de perder os melhores cromossomas.

Elitismo é o nome do método que primeiro copia os melhores cromossomas (or os poucos melhores cromossomas) para a nova população. O resto da população é construída das formas descritas acima. Elitismo pode aumentar rapidamente o desempenho do AG, porque previne a perda da melhor solução já encontrada.


Codificação


A codificação dos cromossomas é a primeira questão a ser feita quando começamos a resolver um problema utilizando AG. A codidicação depende muito do problema. Neste capítulo, algumas codificações que já foram utilizadas com sucesso serão apresentadas.

Codificação Binária

Codificação Binária é a mais comum principalmente porque foi a que os primeiros pesquisadores de AG usaram e devido à sua relativa simplicidade.

Na Codificação Binária, cada cromossoma é uma série de bits - 0 or 1.

Cromossoma A 101100101100101011100101
Cromossoma B 111111100000110000011111

Exemplo de cromossomas com codificação binária

Codificação Binária permite muitos possíveis cromossomas, mesmo com pequenos número de alelos. Por outro lado, esta codificação não é natural para muitos problemas e algumas vezes é necessário fazer correções antes dos cruzamentos e/ou mutações.


Exemplo de Problema: Problema da Mochila
O problema: É dada uma lista de coisas com preços e tamanhos. É fornecido o valor da capacidade da mochila. Escolha as coisas de forma a maximizar o valor das coisas que cabem dentro da mochila, sem ultrapassar sua capacidade.
Codificação: Cada bit é usado para dizer se a coisa correspondente está ou não na mochila.

Codificação por Permutação

A Codificação por Permutação pode ser usada em problemas que envolvem ordenação como o "Problema do Caixeiro-Viajante" ou problemas de ordenação de tarefas.

Na Codificação por Permutação, cada cromossoma é uma série de números que representa uma posição em uma seqüência>.

Cromossoma A 1 5 3 2 6 4 7 9 8
Cromossoma B 8 5 6 7 2 3 1 4 9

Exemplo de cromossoma com codificação por permutação

A Codificação por Permutação é útil para solução de problemas de ordenação. Para alguns tipos de cruzamentos e mutações, são necessárias correções para que os cromossomas fiquem consistentes (isto é contenham seqüências reais) para alguns problemas.


Exemplo de Problema: Problema do Caixeiro Viajante (Travelling Salesman Problem - TSP)
O problema: São dadas cidades e as distâncias entre elas. O caixeiro viajante tem que visitar todas elas, sem viajar mais do que o necessário. A solução do problema consiste em encontrar a seqüência de cidades em que as viagens devem ser feitas de forma que a distância percorrida seja a mínima possível.
Codificação: Os cromossomas descrevem a ordem em que o caixeiro visitará as cidades.

Codificação de Valores

A codificação direta dos valores pode ser usada em problemas em que são usados valores mais complicados tais como números reais. Usar codificação binária para esse tipo de problema seria muito difícil.

Na Codificação de Valores, cada cromossoma é uma seqüência de alguns valores. Esses valores podem ser qualquer coisa relacionada com o problema, tais como: números reais, caracteres ou qualquer outro objeto.

Cromossoma A 1.2324 5.3243 0.4556 2.3293 2.4545
Cromossoma B ABDJEIFJDHDIERJFDLDFLFEGT
Cromossoma C (atrás), (atrás), (direita), (frente), (esquerda)

Exemplo de cromossoma com codificação de valores

Codificação de Valores é uma boa escolha para alguns problemas especiais. Entretanto, para essa codificação, é frequentemente necessário desenvolver um método de cruzamento e mutação específico para o problema.


Exemplo de Problema: Cálculo de Pesos para uma Rede Neural
O problema: É dada uma rede neural com arquitetura definida. Encontre os pesos entre os neurônios da rede de forma a obter a resposta desejada da rede.
Codificação: Valores reais dos cromossomas representam os pesos da rede neural.

Codificação em Árvore

Codificação em Árvore é usada principalmente para desenvolver programas ou expressões, isto é, para programação genética. Na Codificação em Árvore cada cromossoma é uma árvore de alguns objetos, tais como funções ou comandos de uma linguagem de programação.

Cromossoma A

Cromossoma B

( + x ( / 5 y ) )

( do_until step wall )

Exemplo de cromossoma com codificação em árvore

A Codificação em Árvore é útil para desenvolver programas ou qualquer outra estrutura que pode ser codificada em árvores. A programação na linguagem LISP é frequentemente utilizada para este propósito uma vez que os programas em LISP são diretamente representados na forma de árvores e podem ser facilmente processados como uma árvore, de forma que o cruzamento e a mutação podem ser realizados com relativa facilidade.


Exemplo de Problema: Encontrar uma função que aproxime um dado par de valores
O problema: São dados os valores de entrada e de saída. A tarefa é encontrar uma função que forneça a melhor saída (isto é, a que dê o resultado mais próximo do desejado) para todas as entradas.
Codificação: Cromossomas são funções representadas em uma árvore.


bom vou fica por aqui (: no proximo artigo vamos continuar com cruzamento e mutação dos genes (:
bons estudos e ate a proxima!
[]'s




0 comentários:

Postar um comentário