Programação genética

Programação genética é 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.

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. Na programação genética, a recombinação se dá pela troca de subárvores entre dois indivíduos candidatos à solução.

A implementação de programação genética é conceitualmente imediata quando associada a linguagens de programação que permitem a manipulação de um programa computacional na forma de uma estrutura de dados, inclusive por possibilitar que novos dados do mesmo tipo e recém-criados sejam imediatamente executados como programas computacionais.

No entanto, qualquer linguagem computacional capaz de implementar (mesmo que indiretamente) a mesma estrutura de dados pode ser potencialmente empregada.

• linguagem original da programação genética: LISP
• linguagem mais utilizada nas aplicações recentes: C

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.

O campo de estudo vem sendo aplicado em diversas áreas do conhecimento, como Engenharia de Software, Circuitos Digitais, Mineração de Dados, Biologia Molecular e outras.

Os algoritmos genéticos foram popularizados por Holland [Holland, 1975]. Ele utilizou o conceito de cromossomos como estrutura básica do indivíduo, representado computacionalmente por cadeias binárias. Em 1992 John Koza usou algoritmos genéticos para desenvolver programas para realizar certas tarefas. Ele chamou seu método de programação genética.

Inicialmente, foram usados programas em LISP porque programas nessa linguagem podem ser expressos na forma de árvores, que são objetos utilizados pelos algoritmos genéticos.

Bibliotecas e frameworks

• deap (Distribuídos Algoritmos Evolucionários em Python) (Python)
• Pyevolve (Programação Genética e Algoritmos Genéticos) (Python)
• pySTEP pySTEP ou Python Strongly Typed gEnetic Programming
• Algoritmos Genéricos Artigo.(Java)[1]
• Beagle - Open BEAGLE, framework para Computação Evolutiva (C++ utilizando STL)

Outras referências externas

• Texto sobre Programação e Algoritmos Genéticos