Ai - algoritmos geneticos

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1314 palavras )
  • Download(s) : 0
  • Publicado : 27 de setembro de 2011
Ler documento completo
Amostra do texto
ALGORITMOS GENETICOS PARALELOS

UNITAU
4º Sistemas de Informação
Renan Souto de Lucena
Samuel Meireles Korosi



CONCEITO

Os algoritmos genéticos são um conjunto de técnicas heurísticas conhecidas como técnicas evolutivas. Estes algoritmos estão baseados na teoria de evolução de Darwin, imitando o comportamento dos mecanismos de reprodução e seleção natural dentro de umaespécie. Sua grande versatilidade para resolver problemas de diferentes campos tem feito que haja adquirido uma grande popularidade nos últimos anos.

ORIGENS

Como já mencionado, os algoritmos são baseados em mecanismos genéticos de
seleção usada na natureza, nos quais, indivíduos capazes de um povoamento estão sobrevivendo e, portanto, a base para servir gerações.
Um pesquisador daUniversidade de Michigan, John Holland, se interessou por estes mecanismos, espantado com a capacidade da natureza para melhorar seus corpos. No começo dos anos 60, para desenvolver essas ideias e se adaptar às resolução de problemas computacionais. Havia dois objetivos sobre os quais a sua investigação foi centralizada:

• Imitar os processos adaptativos dos sistemas naturais
• Projetar sistemasinformáticos capazes de resolver problemas utilizando os mecanismos.

ALGORITIMOS GENÉTICOS

Algoritmos Genéticos (A.G.) são um método de resolução de problemas inspirado no desenvolvimento de populações de organismos vivos. Nesta metodologia, são efetuadas inúmeras iterações sobre um conjunto de soluções chamado População. A cada iteração, são identificadas as melhores soluções, sendo estasselecionadas para formar novas soluções. A formação de tais soluções se dá através de operações de crossover (criação de uma nova solução através da combinação de duas outras) e mutação (alteração geralmente aleatória em um pequeno trecho da solução). Ao final de uma iteração, um novo conjunto de soluções (população) será obtida. Neste contexto, cada iteração é chamada de Geração.
Devido à inspiração nosambientes naturais, a escolha das soluções (aqui chamadas indivíduos) é randômica, tentando refletir as condições do ambiente real. A escolha da população inicial, no entanto, pode utilizar algume heurística para evitar a geração de soluções pouco aptas e retardar o desenvolvimento da população.



ALGORITMOS GENÉTICOS PARALELOS

Devido às características dos Algoritmos Genéticos, épossível desenvolver versões paralelas do método com bastante facilidade, já que as soluções são independentes entre si. Uma solução simples seria que cada nó de processamento executasse uma cópia do algoritmo genético. Neste esquema, no entanto, pode levar cada nó a obter uma “melhor solução” diferente e, eventualmente, nenhum chegaria a uma solução realmente boa.
Pra evitar tal problema, forampropostos métodos que utilizam comunicação entre os nodos de processamento. Um dos métodos mais conhecidos é o Modelo de Ilha, o qual propõe que cada nodo de processamento seja visto como uma ilha, onde sua população local se desenvolve livremente. No entanto, é possível que em determinados períodos, alguns indivíduos de uma ilha migrem para outra, modificando a população local de uma ilha e evitando quecada ilha convirja para resultados extremamente divergentes.

FUNDAMENTOS DOS ALGORITMOS GENÉTICOS

Os algoritmos genéticos são métodos de resolução de problemas de busca e otimização que fazem uso dos mesmos métodos que serve na natureza, segundo a teoria de Darwin, para a evolução biológica da reprodução, a mutação, e a seleção dos melhores indivíduos de uma população.
Em um algoritmogenético, se parametriza o problema com uma serie de variáveis (xi...xn) que será codificada em um cromossomo. O objetivo será maximizar (ou minimizar) este conjunto de variáveis. Para ele, se cria uma população inicial de indivíduos que são soluções do problema. Normalmente, esta população inicial obterá de manera aleatória, ainda bem que poderá utilizar outros métodos baseados no conhecimento...
tracking img