Algoritmos Genéticos são inspirados na teoria da evolução de Darwin. Solução de um problema através de algoritmos genéticos utiliza um processo evolucionário (a solução é desenvolvida).
O algoritmo começa um um conjunto de soluções (representadas por cromossomas) chamados população. Soluções de uma população são utilizadas para formar uma nova população. Isto é motivado pela esperança que a nova população será melhor do que a primeira. Soluções que são selecionadas para formar novas gerações de soluções são selecionadas de acordo com sua adequação - quanto melhores, mais chances de reprodução terão.
Esse processo é repetido até que alguma condição é satisfeita (por exemplo o número de populações ou o aperfeiçoamento da melhor solução).
Exemplo
Como você já sabe se viu o capítulo sobre espaço de soluções, a solução de problemas pode freqüentemente ser expressa como a procura pelo extremo de uma função. Nós resolveremos aqui exatamente esse problema - dada uma função o algoritmo genético tenta achar o mínimo dessa função.
Experimente rodar o algoritmo genético no applet a seguir apertando o botão "Start". O gráfico representa o espaço de soluções e as linhas verticais representam soluções (pontos no espaço de soluções). A linha vermelha é a melhor solução e as verdes são as outras.
O botão "Start" inicia o algoritmo, o botão "Step" executa um passo (isto é, produz uma nova geração), o botão "Stop" pára o algoritmo e o botão "Reset" reinicia a população.
Como você viu, a estrutura deste Algoritmo Genético Básico é bastante geral. Há muitos parâmetros e ajustes que podem ser implementados de forma diferente em variados problemas.
A primeira questão a ocorrer é como criar cromossomas e que tipo de codificação escolher.. Nós veremos então Cruzamento e Mutação, os dois operadores básicos dos Algoritmos Genéticos. A codificação do cruzamento e da mutação serão introduzidos no próximo capítulo.
A próxima questão é: como selecionar os pais para o cruzamento? Isso pode ser feito de muitas formas, mas a idéia principal é selecionar os melhores pais (os melhores sobreviventes), na suposição que os melhores pais produzirão as melhores descendências.
Você pode achar que gerando as populações apenas de dois pais, pode fazer com que se perca os melhores cromossomas da última população. Isto é verdade, e portanto, o elitismo é usado com freqüência. Isto significa que pelo menos uma cópia sem alterações da melhor solução da geração é passada para a nova população, de forma que a melhor solução possa sobreviver às sucessivas gerações.
Você deve estar querendo saber por que os Algoritmos Genéticos funcionam. Isso pode ser explicado parcialmente pelo Teorema do Esquema de Holland, entretanto, esse Teorema tem sido criticado ultimamente. Se você deseja saber mais, veja outras fontes.