A simplicidade matemática pode estar na base da velocidade da evolução.

Cientistas da computação buscam inspiração na biologia evolutiva para encontrar soluções ideais em conjuntos de dimensões astronômicas

Estudando os vastos espaços de possíveis soluções para o problema, somos confrontados com o fato de que a maioria dos caminhos será um beco sem saída. Mas a evolução pode ter encontrado maneiras de aumentar as chances de sucesso.

Os criacionistas adoram insistir que a evolução teria que coletar até 300 aminoácidos na ordem correta, apenas para criar uma única proteína humana de tamanho médio. E como em cada posição um dos 20 aminoácidos possíveis poderia ser localizado, parece que existem mais de ^20.300 opções de pesquisa, o que é muitas ordens de magnitude maior que o número de átomos no Universo observável. Mesmo se encontrarmos redundância devido à qual algumas dessas opções serão equivalentes, a probabilidade de a evolução ter tropeçado na combinação certa por acidente e mutações aleatórias parece monstruosamente pequena, mesmo com bilhões de anos passados.

A principal desvantagem de tais argumentos é que a evolução não experimentou essas seqüências por acaso: o processo de seleção natural eliminou o desnecessário. Além disso, é provável que a natureza tenha descoberto outras soluções alternativas, maneiras de reduzir um grande número de probabilidades a pequenos subconjuntos estudáveis ​​com maior probabilidade de fornecer soluções úteis.

Os cientistas da computação têm problemas semelhantes, que incluem encontrar soluções ótimas entre as muitas opções de tamanho astronômico. Alguns deles recorrem à biologia em busca de inspiração - apesar do fato de os próprios biólogos estarem apenas tentando entender como isso acontece na natureza.

Os algoritmos genéticos, métodos de otimização que são populares há várias décadas, usam os princípios da seleção natural para criar novos designs (para robôs, drogas e sistemas de transporte, entre outras coisas), treinar redes neurais ou criptografar e descriptografar dados. Essa tecnologia começa com o fato de que soluções aleatórias para o problema são consideradas alguns "organismos" que possuem certas características ou elementos que são "geneticamente" definidos em seu código. Essas soluções não são particularmente boas, mas passam por várias mutações aleatórias (e às vezes outras alterações que copiam o processo de embaralhamento de genes) e produzem a segunda geração de organismos, que por sua vez testam sua utilidade na solução do problema. Como resultado, após muitas repetições, esse processo leva ao surgimento de um indivíduo ou decisão extremamente bem adaptada.

Alguns especialistas levam esse método para o próximo nível, fazendo programação genética para obter programas que podem escrever programas e produzir soluções eficazes (aqui os “genes” podem ser linhas de código). Esse objetivo acabou sendo especialmente difícil de alcançar, porque os pesquisadores precisam considerar certos tipos de dados e estruturas, bem como muitas outras condições.

É interessante notar que esses métodos de pensamento baseados na evolução (em particular na programação genética) se cruzam conceitualmente com uma teoria matemática que sempre esteve na periferia da biologia e da ciência da computação. Recentemente, alguns cientistas têm tentado usá-lo para entender como a evolução, natural e artificial, pode funcionar com eficiência, criar algo novo e aprender a aprender. O principal aqui era um conceito especial de complexidade, aleatoriedade e informação, que não tinha aplicações práticas - até hoje.

Macacos atrás dos teclados

Essa teoria, inventada na década de 1960, trabalha com o que é chamado de informação algorítmica. Começa com uma maneira intuitiva de pensar sobre probabilidade e complexidade: a idéia de que, para alguns dados de entrada, será mais computacionalmente difícil descrever como criar algo do que criá-lo. Tome a conhecida analogia com um macaco, pressionando as teclas aleatoriamente. As chances de que ela imprima os primeiros 15.000 dígitos do número π são ridiculamente pequenas - e diminuem exponencialmente com o aumento do número de dígitos.

Porém, se interpretarmos as teclas digitadas como texto aleatório para um programa de computador que exibe o número π, as chances de sucesso ou "probabilidade algorítmica" são radicalmente aprimoradas. O código para exibir os primeiros 15.000 dígitos do número π no idioma C, por exemplo, você pode espremer um total de até 133 caracteres.

Em outras palavras, a teoria algorítmica da informação diz que a probabilidade de fornecer alguns tipos de saída é muito maior quando processos aleatórios operam no nível do programa que descreve esses dados do que no nível dos dados em si, uma vez que o programa será curto. Nesse sentido, estruturas complexas - por exemplo, fractais - são muito mais fáceis de obter por acidente.

No entanto, logo surgiu um problema com essa abordagem: os matemáticos descobriram que a complexidade algorítmica (também conhecida como complexidade Kolmogorov , nomeada após Andrei Nikolaevich Kolmogorov , um dos fundadores da teoria) dos dados de saída fornecidos - a duração do programa mais curto possível que os produzirá - não pode ser calculada . Portanto, os cientistas da computação não conseguem encontrar a maneira perfeita de comprimir uma corda ou outro objeto.


A complexidade algorítmica da rede à esquerda é alta, porque para descrevê-la, é necessário listar todas as arestas que conectam os vértices. No meio, a complexidade é menor, porque ao descrever essa rede, podemos escrever que o vértice A se conecta a todas as outras. A rede correta tem a menor dificuldade, pois sua descrição consiste no fato de que todos os vértices são conectados em pares por arestas.

Como resultado, a teoria algorítmica da informação foi desenvolvida principalmente no campo da matemática pura, onde é usada para estudar teoremas relacionados e determinar os conceitos de aleatoriedade e estrutura. Seu uso prático parecia inacessível. "Matematicamente, essa é uma medida simples e bonita de complexidade", disse o famoso matemático Gregory Chaitin, um dos fundadores da teoria, que trabalhou no Centro IBM Thomas J. Watson e na Universidade Federal do Rio de Janeiro. "Mas, do ponto de vista da aplicabilidade no mundo real, parecia inexpugnável."

Mas isso não o fez recuar. Ele esperava que essa teoria pudesse ser usada para formalizar a idéia de que o DNA se comporta como um programa. Em 2012, ele publicou um livro onde descreveu como a evolução pode ser representada como um passeio aleatório pelo espaço do programa. Ele escreveu que as mutações que ocorrem nesse caminho não estão sujeitas a uma distribuição de probabilidade estatisticamente aleatória; eles obedecem a uma distribuição baseada na complexidade de Kolmogorov. Mas ele não pôde verificar.

Agora, alguns cientistas esperam reviver essa teoria nesse contexto e conectá-la à biologia e à ciência da computação ao mesmo tempo.

O desejo de simplicidade

Hector Zenil , especialista em TI do Instituto Karolinska, na Suécia, é um dos que estão tentando reviver essa teoria. Ele trabalha em conjunto com outros pesquisadores para usar a complexidade de Kolmogorov como uma métrica para analisar a complexidade das redes biológicas - por exemplo, redes reguladoras de genes ou a interação de proteínas nas células. Os pesquisadores estimam aproximadamente o conteúdo algorítmico da rede (o valor exato não é computável), depois modificam a rede e verificam o quanto isso afetou a complexidade de Kolmogorov. Eles esperam que esse método lhes dê uma idéia da importância relativa dos vários elementos da rede e de sua resposta funcional às mudanças intencionais.


O famoso matemático Gregory Chaitin, um dos fundadores da teoria algorítmica da informação

Em um trabalho recente publicado no arxiv.org, eles descreveram que se você fizer a rede avançar para aumentar a complexidade de Kolmogorov - introduzir mutações que aumentem o programa de descrição da rede - isso geralmente leva a um aumento no número de funções que ele pode executar rede, tornando-o mais sensível a distúrbios. Quando forçaram a rede a se tornar mais simples, as funções ficaram menores e a estabilidade aumentou.

No entanto, ainda não está claro se a complexidade de Kolmogorov pode desempenhar um papel maior do que uma ferramenta simples - por exemplo, como Chaytin acredita, ser a principal força motriz da mudança. Apesar de todos os problemas, a informação algorítmica parece uma teoria atraente para a biologia. Tradicionalmente, para descrever a dinâmica evolutiva, a matemática era usada no campo da genética populacional - modelos estatísticos descrevendo a frequência dos genes na população. No entanto, a genética populacional tem suas próprias limitações: não descreve a origem da vida e outros processos transitórios biológicos básicos, nem o aparecimento de genes completamente novos. "Nessa bela teoria matemática, a idéia de criatividade biológica foi perdida de alguma forma", disse Chaitin. Mas se levarmos em conta as informações algorítmicas, ele disse, "a criatividade naturalmente se encaixa no cenário geral".

Assim como a ideia de que o processo evolutivo melhora com o tempo e aumenta a eficiência. "Estou convencido de que a evolução está aprendendo", disse Daniel Polanyi , especialista em TI e professor de inteligência artificial da Universidade de Hertfordshire, na Inglaterra. "Não ficarei surpreso se isso puder ser expresso através de uma diminuição assintótica da complexidade algorítmica".

Zenil e a equipe decidiram testar experimentalmente as consequências biológicas e computacionais da influência da plataforma de complexidade algorítmica. Usando a mesma técnica para estimar a complexidade usada para analisar e perturbar redes, eles realizaram a “evolução” de redes genéticas artificiais em direção a objetivos específicos - matrizes de zeros e denotando interações genéticas - escolhendo mutações que produziram matrizes com menor complexidade algorítmica. Em outras palavras, eles fizeram uma seleção em favor de estruturas maiores.


Hector Zenil, Especialista em Ciência da Computação, Caroline Institute

Recentemente, eles publicaram resultados na revista Royal Society Open Science, da qual se conclui que, comparada com mutações estatisticamente aleatórias, sua seleção de mutações levou a uma aceleração significativa do desenvolvimento de redes em busca de soluções. Outras características também apareceram, por exemplo, estruturas constantes e regulares - seções de matrizes que já haviam atingido um certo grau de simplicidade, que as novas gerações dificilmente poderiam melhorar. "Regiões individuais eram mais ou menos suscetíveis a mutações simplesmente porque já haviam atingido um certo nível de simplicidade", disse Zenil. "Era muito parecido com os genes." Essa memória genética ajudou a grandes estruturas a emergir mais rapidamente - os pesquisadores acreditam que se segue que mutações algoritmicamente prováveis ​​podem levar a surtos de diversidade e extinção.

"Isso significa", disse Zenil, "que será bastante proveitoso considerar os processos computacionais no estudo da evolução". Ele espera usar esse entendimento de aleatoriedade e complexidade para identificar caminhos de troca que possam ser mais suscetíveis a mutações ou para entender por que certas interações genéticas podem estar associadas a doenças como o câncer.

Evolução do programa

O Zenil espera entender se a evolução biológica funciona de acordo com as mesmas regras computacionais, mas a maioria dos especialistas tem dúvidas. Não está claro qual mecanismo natural poderia ser responsável por uma estimativa aproximada da complexidade algorítmica ou forçar mutações a se desenvolverem propositadamente. Além disso, "acreditar que a vida é completamente codificada em quatro letras seria errado", disse Giuseppe Longo , matemático do Centro Nacional Francês de Pesquisa Científica. "O DNA é extremamente importante, mas não faz sentido fora da célula, organismo, ecossistema". Outras interações funcionam, e o uso de informações algorítmicas não pode cobrir toda essa complexidade.

No entanto, esse conceito despertou algum interesse - principalmente porque essas visões sobre evolução e processos computacionais têm algo em comum, pelo menos um tema comum, com o objetivo da programação genética - de obter um programa que possa evoluir.

Já havia alusões bastante intrigantes à possível conexão entre as idéias de Chaitin e Zenil relacionadas à complexidade de Kolmogorov e aos métodos de programação genética. Por exemplo, em 2001, uma equipe de pesquisadores relatou que a complexidade da produção de um programa genético é limitada pela complexidade Kolmogorov do programa original.

Mas, na maior parte, a complexidade de Kolmogorov não teve participação nas tentativas dos cientistas da computação de entender essas idéias. Eles tentaram outras maneiras de mudar genética e mutações. Alguns grupos mudaram a velocidade das mutações, outros forçaram o sistema a tender para mutações que substituíram grandes partes do código. "As pessoas criaram dezenas, e possivelmente centenas, de diferentes versões de mutações e genótipos", disse Lee Spector , especialista em TI do Hampshire College, em Massachusetts. Spector liderou recentemente uma equipe que demonstrou os benefícios de adicionar e remover mutações em todo o genoma do corpo sobre a substituição direta de um gene por outro. Esse novo tipo de operador genético aumentou exponencialmente o número de caminhos no espaço da pesquisa genética e, finalmente, levou a melhores soluções.


Lee Spector, Especialista em Informática no Hampshire College, Massachusetts

No entanto, muitos pesquisadores foram na direção oposta, em busca de maneiras inteligentes de acelerar o processo, estreitando o campo de pesquisa, mas não o limitando tanto que a busca perderia ótimos resultados. Uma idéia era tornar a simplicidade um objetivo: na década de 1960, Eugene Wigner observou "a eficácia irracional da matemática nas ciências naturais", e os cientistas da computação descobriram que modelos mais simples e elegantes são mais eficientes e mais aplicáveis. "A questão é", disse Spector, "esse fato nos diz algo profundo sobre a estrutura do Universo, ou não?" E será útil para nós?

Ele também adverte que tentar empurrar programas em evolução para a simplicidade pode ser destrutivo: programas recompensadores por brevidade podem reduzir o que parece ser lixo agora, mas podem ser úteis para as gerações futuras, resultando em soluções ótimas sacrificadas. "E estamos presos", disse ele.

No entanto, a simplicidade continua sendo uma meta sedutora que, além disso, demonstrou sua utilidade. Em um artigo publicado no ano passado, Spector e colegas descobriram que, se você reduzir o tamanho dos programas - às vezes em apenas 25% do tamanho original - após aplicar técnicas de programação genética, os programas poderão se sair melhor com novos dados e poderão ser usados ​​em uma ampla gama de informações gerais. problemas

Em particular, por isso, ele monitora o trabalho no campo da teoria algorítmica da informação, embora ele diga que seu impacto nessa área de pesquisa ainda está para ser visto.

Aprendendo com a vida

Talvez a equipe Zenil tenha dado o primeiro passo na busca por essa influência - no entanto, para uma aplicação realista de seu trabalho, é necessário primeiro testar seu método em outros tipos de problemas de busca.

E, no entanto, "eles demonstraram convincentemente a necessidade de restrições baseadas na estrutura", disse Larisa Albantakis , neurocientista e teórica da Universidade de Wisconsin, que também trabalhou para acelerar os algoritmos genéticos, limitando o espaço de pesquisa. "A natureza é estruturada, e se você tomar isso como ponto de partida, seria tolice tentar testar todas as possíveis mutações homogêneas". E acrescentou: "Tudo o que faz sentido para nós é de alguma forma estruturado".

E embora Spector esteja cético em relação ao fato de o trabalho de Zenil poder ser aplicado a algo além de resolver um problema específico que ele estudou, "a teoria da informação subjacente a seus conceitos é uma coisa intrigante e potencialmente muito importante", disse ele. "Parece-me interessante em parte porque parece de alguma forma estranho." Talvez haja idéias que os camaradas da nossa comunidade desconhecem. ” De fato, a informação algorítmica refere-se a uma ampla gama de idéias que alguns especialistas em programação genética podem não incluir em seu trabalho, por exemplo, a natureza ilimitada da evolução.

"Tenho um forte senso de algo importante nessa área", disse Spector. No entanto, ele acrescentou, até agora "há uma grande distância entre o trabalho deles e as aplicações práticas".

"A idéia de imaginar a vida como um programa em evolução é muito proveitosa", disse Chaitin, embora seu valor ainda seja muito cedo para determinar. Quer falemos de vida artificial ou biológica, "precisamos ver até onde podemos ir".