A Complexidade Irredutível nos Algoritmos Genéticos

Algoritmos genéticos necessitam de “informação ativa”.
Dedicado a Diogenes Mota

Este pequeno texto expõe algumas ideias claras para programadores sobre algoritmos genéticos, foi feito a partir de dois e-mails que enviei em 2015.


Uma definição básica do que é um algoritmo genético pode ser encontrada na Wikipédia:

Um algoritmo genético (AG) é uma técnica de busca utilizada na ciência da computação para achar soluções aproximadas em problemas de otimização e busca, fundamentado principalmente pelo americano John Henry Holland. Algoritmos genéticos são uma classe particular de algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade, mutação, seleção natural e recombinação (ou crossing over).

O sucesso do algoritmo genético é enganoso. Até mesmo intuitivamente a noção que o programador tem de economia de complexidade de tempo e complexidade de espaço aponta para um esquiva de tais soluções. Como diz Abel1:

"Métodos computacionais muitas vezes empregam algoritmos genéticos (GA). O apelo a eles é porque são modelados conforme a evolução biológica. Esta última é a principal motivação para se tolerar tal processo desagradável e ineficiente."

Ou seja, a principal motivação é realmente utilizar-se do algoritmo específico, o que depois é utilizado como exemplificação do sucesso da ideia darwiniana. Na verdade o sucesso dos algoritmos é proporcional a utilização do que Ewert et al. chamaram de Informação Ativa2. Normalmente sempre uma entrada anterior de informação determinante no sistema, independente a natureza do experimento, principalmente quando existe esta busca por adequação:

Isto porque, a fim de desenvolver um algoritmo genético bem sucedido, o desenvolvedor faz muitas decisões baseadas no conhecimento do problema que ele está tentando resolver. Como tal, a informação é derivada a partir deste conhecimento prévio do problema de pesquisa. Ajustar um algoritmo genético é outra fonte de informação ativa: é comum simplesmente porque funciona. A razão pela qual ele funciona é porque explora próprio conhecimento do programador no problema a ser resolvido.

Como podemos ver acima a palavra “ajustar” está em negrito. Por que? Agora vem a Complexidade Irredutível presente nos algoritmos genéticos. Um sistema de variáveis aleatórias provavelmente nunca alcançaria qualquer estabilidade dentro dos recursos computacionais, dependendo do tamanho da entrada de dados. Um sistema com variáveis baseadas nas tendências da natureza seria decepcionante demais. A solução é o que chamam de tuning do algoritmo.

O tuning é o “ajuste”. Ele faz “busca” ou “escolha” por parâmetros necessários e suficientes para o funcionamento do Algoritmo Genético. Encontrar os valores de parâmetros adequados para algoritmos evolutivos é um dos grandes desafios que persistem do campo de Computação Evolucionária.

Mas qual a natureza desse tuning?

Encontrar um bom conjunto de valores de parâmetros é uma tarefa de otimização complexa, com uma função não-linear objetiva, variáveis que interagem, múltiplos ótimos locais, ruído (pela natureza estocástica dos Algoritmos Evolutivos serem ajustados), e uma falta de solucionadores de análise. Ironicamente, é exatamente esse tipo de problemas, onde os Algoritmos Evolutivos são solucionadores heurísticos muito competitivos. É, portanto, uma idéia natural para usar uma abordagem evolutiva para otimizar os parâmetros de um algoritmo evolutivo.

Interessante que ele nem percebe que está gerando um algoritmo da mesma natureza para resolver o problema do algoritmo inicial, sendo assim um verdadeiro meta-algoritmo.

Conclusão

Em suma, os algoritmos genéticos necessitam de uma solução qual eles mesmos estão propondo resolver. Isso caracteriza, ironicamente, uma necessidade circular (complexidade irredutível).


Referências

[1] Abel, David L. “The capabilities of chaos and complexity.” International journal of molecular sciences 10.1 (2009): 247-291.

[2] Ewert, Winston, William A. Dembski, and Robert J. Marks II. “Climbing the Steiner Tree–Sources of Active Information in a Genetic Algorithm for Solving the Euclidean Steiner Tree Problem.” BIO-Complexity 2012 (2012).

[3] Smit, Selmar K., and Agoston E. Eiben. “Comparing parameter tuning methods for evolutionary algorithms.” Evolutionary Computation, 2009. CEC’09. IEEE Congress on. IEEE, 2009.


4 Comentários

  1. Nunca analisei algoritmos genéticos dessa forma… Mas quero confirmar isso na prática daqui um tempo e fazer comparações… Muito bom expor esse tipo de problema…

  2. Não costumo comentar esses textos da net, mas acho que esse merece.

    Ao contrário do que o Abel descreveu no trabalho dele, uma das grandes motivações de usar Algoritmos Genéticos (e outras técnicas de computação natural) é o enorme potencial de processamento paralelo e distribuído. O processo é extremamente ineficiente de ser computado serialmente (um indivíduo por vez), mas é muito atrativo se os indivíduos forem computados em paralelo (por exemplo usando GPGPU).

    Algoritmos genéticos são um “princípio de busca” por melhores indivíduos (soluções para o problema) em um espaço de possíveis indivíduos. Por isso, ele é muitas vezes chamado de meta-heurística. Assim como outras meta-heurísticas, algoritmos genéticos dependem da modelagem do problema. Essa técnica é atrativa, pois em muitos problemas é simples modelar o que é um indivíduo (solução do problema), e como combinar duas soluções para gerar outra. Aí é onde entra o conhecimento necessário para o problema, que francamente, exige muito menos esforço de design em relação a outras abordagens para muitos problemas.
    De fato, a aplicação de AG é usada para tantos problemas que no portal ACM (de artigos da computação), há dezenas de milhares de artigos e vários periódicos que abordam o tema.

    Ajuste de parâmetros é em geral um problema para maioria das estratégias de computação natural. Esse problema em geral pode ser resolvido com processamento distribuído e paralelo. Em outras palavras, se você pode processar uma enorme quantidade de indivíduos ao mesmo tempo, não há problema. Há várias técnicas de ajuste e o trabalho [3] citado descreve uma delas (usando o próprio AG). Isso não quer dizer que AG precisa do AG para tunar parâmetros, mas que AG é robusto o suficiente para ser aplicado no problema de tunar parâmetros.

  3. Concordo plenamente com o texto, sem falar que o sistema de elitismo dos “indivíduos” é muito melhor aproveitado se encarado de outra perspectiva.

    No sistema convencional elegemos os “indivíduos” com melhores pontuações (fitness) e depois aplicamos um cruzamento (crossover) e em seguida a mutação para dar início a próxima geração. Se pararmos pra pensar, não é assim que funciona o passar do aprendizado de um indivíduo para outro. Por exemplo se sua mãe e seu pai são ótimos alfaiates, ao terem um filho, não se pega metade do cerebro do pai e metade do do da mãe, junta e mexe um pouquinho (mutação) para fabricar um novo filho que saiba alfaiataria. Conhecimento intelectual não se passa biologicamente. O máximo que pode acontecer é o filho receber uma boa genética neural, ou seja, nascer com uma predisposição a ter mais neurônios ou menos. Mas os neurônios não vem com a informação adquirida pelo oficio dos pais. Essa informação é ensinada com treinamento, o filho aprende vendo seus pais trabalharem, e ao ver mais indivíduos trabalhando com técnicas diferentes, absorve a informação e cria sua própria técnica com base nas melhores que viu. Então se pensarmos por esse lado, é muito mais eficaz selecionar os indivíduos com melhores resultados no sistema do algorítimo genético e construir uma nova geração limpa e treiná-los com o histórico de ações e tomadas de decisões que os pais usam para trabalhar. Assim como se treina uma rede neural simples. Então o conceito de evolução está errado tanto na biologia quanto na computação.

  4. Se alguém acha que os algoritmos inspirados na evolução funcionam porque a evolução, em si, funciona, provavelmente essa pessoa não entende o significado de “inspirado” neste contexto. Qualquer algoritmo computacional bio-inspirado, sejam as redes neurais artificiais, algoritmos evolutivos, enxame de partículas, sistemas imunológicos artificiais, colônia de formigas, etc, abstraem apenas o funcionamento essencial do mecanismo no qual se inspiram. Logo, não representam um modelo matemático completo e preciso do mecanismo.

    Ou seja, os criadores de tais algoritmos se inspiraram na natureza e abstraem a partir daí um modelo matemático. Neste ponto, cessa toda a inspiração e apenas o modelo abstraído importa agora, sobre o qual manipulações matemáticas podem ser realizadas visando a adequabilidade deste modelo a um sistema computacional. Para tanto, inúmeras operações/transformações extras são inseridas no modelo, as quais muitas vezes não tem a mesma inspiração biológica do modelo.

    Por exemplo, é muito comum definir uma taxa de erro mínima, para que o algoritmo não fique executando perpetuamente a procura de soluções ótimas globais, visto que, é esperado que ele encontre as soluções ótimas locais, as quais serão suficiente ou não dependendo dos parâmetros (ajuste conforme especificado no texto) utilizados.

    Por fim, invocar a funcionalidade de qualquer algoritmo para provar teorias evolucionistas só prova a existência de uma mente inteligente, porque afinal de contas, até hoje, e sabemos que isso nunca ocorrerá, não encontramos algoritmos prontos jogados na natureza a espera de alguém que os encontre.

Faça um comentário

Seu e-mail não será publicado.


*