sexta-feira, janeiro 16, 2009

,

Algoritimos Genéticos [AG] I


Vamos abordar então neste artigo um pouco sobre Programação Genética pra ser mais especifico falar um pouco sobre o algotimo genético e mostrar a vocês passo a passo de como se fazer tal programação,para isso é utilizado algoritimos genéticos,que são estruturas de possibilidades e resoluções que o programdor vai desenvolver!mas você me pergunta: "Dr que finalidade vou ter isso na area de saude?" é simples a programação genética ela é uma técnica automática de programação que propicia a evolução de programas de computadores que resolvem (ou aproximadamente resolvem) problemas. Ela manipula soluções corretas e incorretas, encoraja inconsistências e abordagens contraditórias, não apresenta uma variabilidade dinâmica lógica, é predominantemente probabilística, produz soluções não-parcimoniosas e não apresenta um critério de terminação claramente definido.Como qualquer outro sistema computacional inspirado na natureza, a programação genética tem dois propósitos básicos:
  1. Servir de ferramenta para a solução de problemas de engenharia;
  2. Servir de modelo científico simplificado para processos naturais.

Na prática, qualquer implementação de programação genética vai envolver, ao menos parcialmente, ambos os propósitos básicos mencionados acima.

Na programação genética, os indivíduos da população não são seqüências de bits, mas sim programas de computador armazenados na forma de árvores sintáticas. Tais programas é que são os candidatos à solução do problema proposto. A programação genética não usa o operador mutação e a recombinação se dá pela troca de subárvores entre dois indivíduos candidatos à solução.

Algoritmos genéticos são parte da computação evolucionária, que é uma área em crescimento da inteligência artificial. Como você pode advinhar, algoritmos genéticos são inspirados na teoria da evolução de Darwin. Falando simplesmente, os problemas são resolvidos através de um processo evolutivo que resulta na melhor (mais adequada) solução (a sobrevivente) - ou em outras palavras, a solução é desenvolvida.

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 objeto de nossa otimização. Pode ser um problema de otimizaçã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 otimizar. A grande vantagem dos algoritmos genéticos esta no fato de não precisarmos saber como funciona esta função objetivo, 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 seqüências de bits. Por exemplo, para otimizaçõ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 seqüência de bits, ou trabalhar com mais de um "cromossomo", 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.

A seleção também é outra parte chave do algoritmo. Em geral, usa-se o algoritmo de seleção por "roleta", onde os indivíduos são ordenados de acordo com a função-objetivo 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 seleção podem ser aplicadas dependendo do problema a ser tratado

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 objetivo permitir maior variabilidade genética na população, impedindo que a busca fique estagnada em um mínimo local

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 laço e condicionais, típicas de uma linguagem de programação comum.

bom termino por aqui a introdução sobre algoritimos geneticos bem ate a proxima!(:
Bons estudos!

0 comentários:

Postar um comentário