Aplicações e limitações de algoritmos genéticos

Neste ponto da série de programação genética (GP), aprendemos sobre o que é programação genética e como ela representa as informações, como os operadores genéticos funcionam em algoritmos evolutivos e como trabalharam através da evolução de um programa de classificação por meio de regressão simbólica.

Aqui, daremos uma olhada de alto nível no que essa tecnologia pode realizar à medida que se desenvolve.

Considerações práticas de programação genética

Para entender este capítulo final de nossa série, vamos lembrar um exemplo de XOR que discutimos na primeira parte desta série:

  Uma solução perfeita para o problema XOR descoberto pelo GP: (programa defun () (E (OU X1 X2) (NÃO (E X1 X2)) ) ) 

Listagem 1. Resultado XOR.

Vejamos também o exemplo de regressão simbólica do artigo anterior:

 Uma aproximação polinomial de sin (x) no intervalo (0 <=x <=pi / 2) (programa defun () (+ (* (* (* X X) X) (* 0,2283 -0,6535)) X) ) Simplificar o programa acima resulta na seguinte equação equivalente:polysin (x) =-.1492 x 
 3 
 + x Resultados:

x	sin (x)	polysin (x)
0,000	0,000	0,000
0,078	0,077	0,077
0,156	0,155	0,155
0,234	0,231	0,232
0,312	0,306	0,307
0,390	0,380	0,381
0,468	0,451	0,452
0,546	0,519	0,521
0,624	0,584	0,587
0,702	0,645	0,650
0,780	0,703	0,709
0,858	0,756	0,763
0,936	0,805	0,813
1.014	0,848	0,858
1.092	0,887	0,897
1,170	0,920	0,931
1,248	0,948	0,957
1,326	0,970	0,978
1,404	0,986	0,991
1,482	0,996	0,996
1,560	0,999	0,993

Listagem 4. Regressão simbólica.

Observe que tanto o XOR quanto os exemplos de regressão simbólica apresentados aqui retornam um único valor quando avaliados.

Essa característica não precisa ser uma restrição, pois certamente é possível que uma função ou terminal tenha um efeito colateral quando executado. Esse é frequentemente o caso do programa de classificação, que contém uma função com o efeito colateral potencial de trocar um par de elementos em um vetor. Na prática, é comum a presença de efeitos colaterais. Alguns exemplos adicionais de efeitos colaterais úteis são a atribuição de uma variável a outra ou a alteração da direção para a qual o robô está voltado.

Nosso conjunto de funções pode incluir funções condicionais que fornecem aos programas desenvolvidos a capacidade de tomar decisões. As funções condicionais avaliam seletivamente seus argumentos. Como exemplo, considere uma função, com um arity de três, como (if arg1 arg2 arg3). A função é avaliada avaliando o primeiro argumento e se o resultado for verdadeiro, o segundo argumento é avaliado; caso contrário, o terceiro argumento é avaliado. Construções iterativas também são possíveis, pois uma função pode avaliar um de seus argumentos várias vezes. Complexidade adicional é introduzida, no entanto, pela necessidade de limitar o número de iterações e o nível de aninhamento de modo a evitar uma situação em que a avaliação de um indivíduo possa levar um tempo excessivamente longo. Algum trabalho foi feito para permitir formulações recursivas, embora o sucesso nesta área tenha sido um tanto limitado.

Embora os resultados dos sistemas de GP tendam a ser programas semelhantes ao LISP, um sistema de GP não precisa ser implementado no LISP. Muitos sistemas são implementados em C ou C ++. Uma representação linearizada da árvore do programa pode ser empregada e a sobrecarga da memória dinâmica junto com a cara coleta de lixo pode ser evitada. A eficiência da função de fitness merece atenção especial, pois muitas vezes é um gargalo devido ao grande número de vezes que é invocada durante cada geração. Um excelente artigo discutindo várias técnicas de implementação pode ser encontrado em Avanços em Programação Genética (citado na seção Leitura sugerida abaixo).

Como em outros paradigmas de aprendizado de máquina, como redes neurais, existe o potencial de super ajustar os dados de treinamento (casos de teste de GP). O overfitting pode ocorrer quando a solução efetivamente "memoriza" os dados, fornecendo, assim, pouco mais do que uma elaborada tabela de consulta. Uma maneira simples de ajudar a reduzir esse efeito é usando um fator de parcimônia. Um fator de parcimônia é normalmente uma pequena fração multiplicada pelo número de nós na árvore do programa, o resultado do qual é incorporado à função de aptidão. A ideia é recompensar soluções menores, presumivelmente mais gerais. Além disso, você é incentivado a usar técnicas de projeto experimental apropriadas. Por exemplo, se você está tentando desenvolver um modelo para predição, é uma boa ideia restringir a avaliação de aptidão a um subconjunto dos dados disponíveis. Dessa forma, os dados restantes podem medir o desempenho preditivo do modelo resultante.

Como é o caso dos algoritmos evolutivos, o GP não oferece nenhuma garantia de encontrar uma solução exata ou mesmo uma solução aceitável. Os resultados podem variar muito de uma corrida para outra. Freqüentemente, o processo converge prematuramente para mínimos locais. O desempenho é altamente dependente da complexidade do problema, de sua representação caracterizada pela escolha de funções e terminais e das propriedades da função de adequação.

Aplicativos para programação genética

A programação genética foi aplicada com sucesso a problemas que ocorrem em áreas como:

• Projeto de circuito
• Otimização combinatória
• Sistemas de controle
• Ajuste de curva / análise de regressão
• Compressão de dados
• Previsão econômica / modelagem financeira
• Aquisição de estratégia de jogo
• Indução de sequência matemática
• Projeto de rede neural
• Reconhecimento e classificação de padrões
• Geração de número aleatório
• Navegação do robô
• Integração e diferenciação simbólica
• Design tridimensional

Orientações futuras para programação genética

Dependendo da complexidade do problema, várias execuções de GP podem ser necessárias para encontrar uma solução aceitável, se alguma puder ser encontrada. Idealmente, gostaríamos que o GP "aumentasse" à medida que a complexidade do problema aumentasse. Encontrar boas maneiras de atingir esse objetivo é uma área ativa de pesquisa. Como na programação convencional, a noção de construir representações de alto nível por meio de sub-rotinas é uma forma de abordar esse problema. Em Programação Genética II , Koza discute métodos que podem descobrir sub-rotinas reutilizáveis ​​e apresenta resultados que suportam a capacidade de programas hierárquicos e modulares de resolver problemas mais complexos.

Como vimos, a GP acopla as características de auto-organização do algoritmo genético com o poder de representação e generalidade das S-expressões. A elegância desta abordagem simplifica a especificação do problema para fornecer uma função de aptidão específica do domínio e uma função apropriada e conjunto de terminais. Aplicável a uma ampla gama de problemas, o GP continua a ser um terreno fértil para pesquisa.

Ainda em sua infância, descobertas futuras podem nos levar um passo adiante naquele Santo Graal de sistemas capazes de criar seus próprios programas.

Leitura sugerida

• Kinnear, Jr., K. E. (ed.). Avanços na programação genética . Cambridge, Mass .:The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching . Reading, Mass .:Addison-Wesley, 1973
• Koza, J. R. Programação genética . Cambridge, Mass .:The MIT Press, 1992.
• Koza, J. R. Genetic Programming II . Cambridge, Mass .:The MIT Press, 1994.
• Montana, D. J. “Strongly Typed Genetic Programming.” BBN Technical Report # 7866, maio de 1993.
• Mitchell, Melanie, Uma introdução aos algoritmos genéticos , The MIT Press, 1998.