sexta-feira, janeiro 16, 2009

,

Algoritimos Genéticos [AG] II


Bom continuando o artigo sobre Algoritimos Genéticos ,agora que você sabe o que significa,suas classes, e devido uso,vamos abordar aqui um pouco sobre Cromossomos,Espaço de soluções,reprodução,Problemas NP Difíceis.para se fazer programação genética é importante tbem ter um amplo conhecimento na area de saude, principalmente em reprodução,e uma pitad de uma " boa matematica" (-; enfim .... podemos dizer que Todos os organismos vivos são constituídos de células. Em cada célula há um mesmo conjunto de cromossomas. Cromossomas são cadeias de DNA e servem como modelo para todo o organismo.

O cromossoma é constituído de genes, que são blocos de DNA. Cada gene codifica uma determinada proteína. Basicamente, podemos dizer que cada gene codifica uma determinada feição, por examplo cor dos olhos. Conjunto de genes relacionados com determinada feição (por exemplo, olhos azuis, castanhos) são chamados alelos. Cada gene tem sua posição própria dentro do cromossoma. Essa posição é chamada local.

Um conjunto completo de material genético (todos os cromossomas) é chamado genoma. Um conjunto particular de genes de um genoma é chamado genótipo. O genótipo mais o desenvolvimento que ocorre após o nascimento é a base para o fenótipo do organismo, que são suas características físicas e mentais, tais como: cor dos olhos, inteligência, etc.

Reprodução

Durante a reprodução, ocorre inicialmente recombinação (ou cruzamento). Os genes dos pais são combinados para formar um novo cromossoma. Essa descendência recém criada pode sofrer uma mutação. Mutação significa que os elementos do DNA são ligeiramente modificados. Essas mudanças são causadas principalmente por erros na cópia dos genes dos pais.

A adaptação de um organismo é medida pelo sucesso do organismo na vida (sobrevivência).

Se estamos resolvendo um problema, geralmente procuramos por alguma solução que seja melhor que outras. O espaço de todas as soluções possíveis (que é um conjunto entre as quais a solução procurada está) é chamado Espaço das Soluções (ou Espaço de Estados). Cada ponto desse estado representa uma solução possível. Cada uma das possíveis soluções pode ser "marcada" pelo seu valor (ou adequação) para o problema. Com os Algoritmos Genéticos nós procuramos pela melhor solução dentre um número de possíveis soluções - representadas por pontos no Espaço de Soluções.Procurar por uma solução se resume então em procurar por algum valor extremo (um mínimo ou máximo) no espaço de soluções. Às vezes o espaço de soluções pode estar bem definido, mas usualmente nós sabemos apenas poucos pontos do espaço de soluções. No uso dos algoritmos genéticos o processo de encontrar soluções gera outros pontos (possíveis soluções) à medida que a evolução acontece.

O problema é que cada pesquisa pode ser muito complicada. Por exemplo, pode não saber por onde procurar uma solução ou por onde começar. Há muitos métodos que podem ser usados para encontrar uma solução adequada, mas esses métodos não fornecerão nedessariamente a melhor solução. Alguns desses métodos ão: subindo a montanha, pesquisa de tabelas, enrijecimento simulado e os algoritmos geneticos. As soluções encontradas por esses métodos são freqüentemente consideradas boas soluções porque nem sempre é possível provar qual é a ótima.

Problemas NP Difíceis

Um exemplo de classe de problemas que não podem ser resolvidos de modo tradicional são os problemas NP (não polinomiais).

Existem muitas tarefas para as quais podemos usar algoritmos rápidos (polinomiais), entretanto há também problemas que não podem ser resolvidos algoritmicamente.

Existem muitos problemas importantes em que é muito difícil encontrar uma solução, mas que uma vez encontrada, é fácil de ser verificada. Este fato nos leva aos chamados problemas NP-completos. O NP vem de "não polinomial determinístico" e significa que é possível "advinhar" a solução (por algum algoritmo não determinístico) e depois verificá-la.

Se tivermos uma máquina de advinhação, seremos capazes de achar uma solução num tempo razoável.

O estudo de problemas NP-completos é, por simplicidade, restrito aos problemas onde a resposta pode ser sim ou não. Em razão de que existem tarefas com saídas complicadas, uma classe de problemas chamados problemas NP-difíceis começaram a ser estudados. Essa classe de problemas não se limita aos problemas NP-completos.

Uma característica dos problemas NP é que um algoritmo simples, às vezes óbvio à primeira vista, pode ser usado para encontrar soluções úteis. Mas esta abordagem normalmente produz muitas soluções possíveis - testar todas as soluções possíveis é um processo muito lento. Para uma instância ligeiramente maior desse tipo de problema, essa abordagem é inútil.

Atualmente ninguém sabe se existe algum algoritmo rápido para encontrar solução exata para os problemas NP. A descoberta desses algoritmos permanece um desafio em aberto para pesquisadores em geral (talvez você! :-)). Atualmente muitas pessoas acham que tais algoritmos não existem e portanto procuram um método alternativo. Um exemplo de método alternativo são os algoritmos geneticos.

Exemplos de problemas NP são: problema da satisfatoriabilidade, o problema do caixeiro viajante, e o problema da mochila. Uma coleção de problemas NP está disponível aqui.

bom termino por aqui deixando como referencia o exelente trabalho do senhor (c) Marek Obitko, 1998 grande conheçedor em programação genética!

bons estudos ate a proxima (:

0 comentários:

Postar um comentário