Algoritmos Genéticos

 


    Sumário

  Introdução

Histórico

Aplicando a Técnica

Links

Operadores Genéticos

Exemplos

Software

Aplicações

Parâmetros Genéticos

Definições e Características Gerais

Bibliografia

Composição

Como Programar um AG

Algoritmos Meméticos

 

 


Introdução
 
Os algoritmos Genéticos formam a parte da área dos Sistemas Inspirados na Natureza; simulando os processos naturais e aplicando-os à solução de problemas reais. São m étodos generalizados de busca e otimização que simulam os processos naturais de evolução, aplicando a idéia darwiniana de seleção. De acordo com a aptidão e a combinação com outr os operadores genéticos, são produzidos métodos de grande robustez e aplicabilidade. Estes algoritmos estão baseados nos processos genéticos dos organismos biológicos, codificando uma possível soluç& atilde;o a um problema de "cromossomo" composto por cadeia de bits e caracteres. Estes cromossomos representam indivíduos que são levados ao longo de várias gerações, na forma similar aos problemas naturais, evoluindo de acordo com os princípios de seleção natural e sobrevivência dos mais aptos, descritos pela primeira vez por Charles Darwin em seu livro "Origem das Espécies". Emulando estes processos, os Algoritmos Genéticos s&at ilde;o capazes de "evoluir" soluções de problemas do mundo real.
Na natureza os indivíduos competem entre si por recursos como comida, água e refúgio. Adicionalmente, entre os animais de uma mesma espécie, aqueles que não obtêm êxito tendem provavelmente a ter um número reduzido de descendentes, tendo portanto menor probabilidade de seus genes serem propagados ao longo de sucessivas gerações. A combinação entre os genes dos indivíduos que perduram na espécie, pod em produzir um novo indivíduo muito melhor adaptado às características de seu meio ambiente. Os Algoritmos Genéticos utilizam uma analogia direta deste fenômeno de evolução na natureza, onde cada indiv&iacut e;duo representa uma possível solução para um problema dado. A cada indivíduo se atribui uma pontuação de adaptação, dependendo da resposta dada ao problema por este indivíduo. Aos mais adapta dos é dada a oportunidade de reproduzir-se mediante cruzamentos com outros indivíduos da população, produzindo descendentes com características de ambas as partes. Se um Algoritmo Genético for desenvolvido correta mente, a população (conjunto de possíveis respostas) convergirá a uma solução ótima para o problema proposto. Os processos que mais contribuem para a evolução são o crossover e a adapta ção baseada na seleção/reprodução. A mutação também tem um papel significativo, no entanto, seu grau de importância continua sendo assunto de debate.
O Algoritmo Genético pode convergir em uma busca de azar, porém sua utilização assegura que nenhum ponto do espaço de busca tem probabilidade zero de ser examinado. Toda tarefa de busca e otimizaç&atil de;o possui vários componentes, entre eles: o espaço de busca onde são consideradas todas as possibilidades de solução de um determinado problema, e a função de avaliação (ou funç&atild e;o de custo), uma maneira de avaliar os membros do espaço de busca. As técnicas de busca e otimização tradicionais iniciam-se com um único candidato que, iterativamente, é manipulado utilizando algumas heur&iacut e;sticas (estáticas) diretamente associadas ao problema a ser solucionado. Por outro lado, as técnicas de computação evolucionária operam sobre uma população de candidatos em paralelo. Assim, elas podem faz er a busca em diferentes áreas do espaço de solução, alocando um número de membros apropriado para a busca em várias regiões. Os Algoritmos Genéticos (AGs) diferem dos métodos tradicionais de busca e otimização, principalmente em quatro aspectos:
  1. AGs trabalham com uma codificação do conjunto de parâmetros e não com os próprios parâmetros;
  2. AGs trabalham com uma população e não com um único ponto;
  3. AGs utilizam informações de custo ou recompensa e não derivadas ou outro conhecimento auxiliar;
  4. AGs utilizam regras de transição probabilísticas e não determinísticas.
Algoritmos Genéticos são muito eficientes para busca de soluções ótimas, ou aproximadamente ótimas, em uma grande variedade de problemas, pois não impõem muitas das limitaçõ es encontradas nos métodos de busca tradicionais. Os pesquisadores referem-se a "algoritmos genéticos" ou a "um algoritmo genético" e não "ao algoritmo genético", pois AGs são uma classe de procedimentos com muito s passos separados, e cada um destes passos possui muitas variações possíveis. Os AGs não são a única técnica baseada em uma analogia da natureza. Por exemplo, as Redes Neurais estão baseadas no comportamento dos neurônios do cérebro. Podendo ser utilizadas em uma grande variedade de problemas de classificação, como reconhecimento de padrões no processo de imagens.
voltar
 
Histórico
Século XIX: os naturalistas acreditam que cada espécie havia sido criada separadamente por um ser supremo ou através de geração espontânea. O trabalho do naturalista C arolus Linnaeus levou a acreditar na existência de uma certa relação entre as espécies. Por outro lado, Thomas Robert Malthus propôs que fatores ambientais tais como doenças e carência de alimentos limitavam o crescimento de uma população. Século XX: após anos de observações e experimentos, Charles Darwin apresentou em 1858 sua teoria de evolução através de seleção natural. Por volta de 1900, a moderna teoria da evolução combina a genética e as idéias de Darwin e Wallace sobre a seleção natural, criando o princípio básico de Genética Populacional: a variabilidade entre ind ivíduos em uma população de organismos que se reproduzem sexualmente é produzida pela mutação e pela recombinação genética. Este princípio foi desenvolvido durante os anos 30 e 40, por biólogos e matemáticos de importantes centros de pesquisa. Nos anos 50 e 60, muitos biólogos começaram a desenvolver simulações computacionais de sistemas genéticos. Entretanto, foi John Holland quem come&c cedil;ou, seriamente, a desenvolver as primeiras pesquisas no tema. Holland foi gradualmente refinando suas idéias e em 1975 publicou o seu livro "Adaptation in Natural and Artificial Systems", hoje considerado a Bíblia de Algoritmos Genéticos. Nos anos 80 David Goldberg, aluno de Holland, consegue primeiro sucesso em aplicação industrial de Algoritmos Genéticos. Desde então, estes algoritmos vêm sendo aplicados com sucesso nos mais diversos problemas de otimização e aprendizado de máquinas.
 
voltar
 


Grupo Anterior:
Weber L. Alvarenga
Célio Augusto Rezende
Leonardo Braga Ravazzi
Cláudio da Silva Júnior
 
Grupo atual:
Alexandra Carniel Perdigao Maia
Roberto Michelan