Uma Breve Introdução à Computação Evolucionária

Por Bruno Vieira





A teoria da evolução proposta por Darwin em 1859 possui um potencial explanatório tão grande que seus pressupostos ultrapassam a barreira do estudo de organismos vivos e alcança ramos tão diferentes como a literatura, direito, economia, linguística e computação. Por meio desse pequeno artigo busca-se apresentar ao leitor a computação evolucionária, primeiro explicando de forma sucinta a teoria darwiniana que, aliada à genética mendeliana, introduz os conceitos de genes, cromossomos e hibridização a e posteriormente aplicando tais conceitos à computação.


1. A Teoria da Evolução


Quando o biólogo inglês Charles Darwin, escreveu seu icônico livro “A origem das espécies” em 1859, ele sequer podia imaginar a dimensão de suas descobertas. Hoje, o Darwinismo é aplicado em campos que inicialmente não guardam qualquer relação com a Biologia, como a Literatura, Linguística, Economia e Direito.


O filósofo Daniel Dennett eloquentemente descreveu a Teoria da Evolução de Charles Darwin como “a melhor ideia que alguém já teve”. Para Dennet, Darwin unificou “o reino da vida, significado e propósito com o reino do espaço e tempo, causa e efeito, mecanismo e lei física” (Dennett, 1995, p. 21). O apreço de Dennet pela teoria de Darwin é justificado. Embora o século 19 tenha visto uma profusão de ideias evolutivas, com naturalistas de peso, como Lamarck, Saint-Hilaire, Grant e Chambers, todos desenvolvendo hipóteses convincentes para a transmutação das espécies, foi a Teoria Darwiniana que se destacou.


Um dos principais argumentos de Darwin, e que ganhou apreço entre a comunidade científica da época, é que a evolução é o resultado da descendência com modificação, ou seja, é um processo onde as modificações - ou mutações - são selecionadas, retidas e, em seguida, transmitidas à descendência de um organismo.


Assim, para Darwin a evolução seria um processo com três fatores principais, i.e. variação, seleção e hereditariedade. Resumidamente, isso significa que, em primeiro lugar, ocorrem mutações genéricas e aleatórias em um organismo. Essas mutações, ou variações, podem ajudar o organismo a sobreviver na luta por recursos ou contra predadores. Elas são úteis para a conservação de energia ou seu uso eficiente, a sobrevivência contra predadores ou para se adaptar aos diferentes alimentos disponíveis. Essas mutações são selecionadas naturalmente por meio da competição e sobrevivência. No estágio final, essas mutações selecionadas são transmitidas à prole e, portanto, retidas no acervo genético do organismo.


Embora a Teoria da Evolução já tenha avançado consideravelmente desde a brilhante intervenção de Darwin, principalmente por meio da teoria sintética da evolução, nos focaremos inicialmente em um dos principais aspectos da teoria Darwiniana: a seleção natural.


1.1.A Seleção Natural


Antes de apresentar sua proposição sobre a seleção natural em seu livro de 1859, Darwin já estava familiarizado com a seleção artificial de pássaros e plantas. Ao menos desde 1855, em uma carta enviada para o naturalista Thomas Campbell Eyton, Darwin expressa seu interesse na domesticação e experimentação em pombos (Burkhardt, 1996, p. 148). O objetivo de Darwin com os pombos era direcionar o surgimento de novas espécies selecionando ele mesmo características (ou mutações) específicas nos espécimes, como plumagem, bico, nanismo ou gigantismo. Essa seleção por mãos humanas é o que conhecemos por seleção artificial. Nessa situação, a seleção de características pode não representar qualquer vantagem à espécie, mas servir a algum propósito humano, como uma raça de cachorro mais dócil ou um alimento mais aprazível.


Não obstante seja possível o surgimento de espécies diferentes por meio da seleção artificial, para Darwin (1996, p. 84) não há limites “para a quantidade de mudanças, a beleza e infinita complexidade das coadaptações entre todos os seres orgânicos, entre eles e com suas condições física de vida” que não possam ser, no longo prazo, afetadas pela seleção natural.


A seleção natural conforme observa Darwin, é uma ininterrupta e implacável luta pela sobrevivência, onde mutações aleatórias podem ou não ajudar um organismo a obter alimentos mais facilmente, fugir, esconder ou até mesmo enfrentar um predador. O organismo que é “agraciado” com uma mutação benéfica, e.g., um bico mais forte que o ajuda a abrir castanhas e nozes e um ambiente onde essas abundam, ou um sistema de camuflagem que o ajuda a se esconder de predadores, terá a oportunidade de passar essa mutação à sua prole. Dessa forma, podemos falar que o um organismo é mais apto a sobreviver às condições a qual é exposto.


1.2. A Introdução da Genética Mendeliana


Embora a seleção natural de Darwin tenha revolucionado a biologia, sua teoria ainda não explicava como essas mutações ocorriam e como eram transmitidas. A explicação coube a Gregor Mendel (1865), que usando estatística pode prever a probabilidade de um “elemento celular” (Zellelemente) ser preservado em gerações futuras. Esse elemento celular é o que hoje se conhece por gene. Basicamente, o gene é uma unidade de hereditariedade feita de DNA. DNA, ou ácido desoxirribonucleico, por sua vez contém informações, ou instruções, de todas as características para o desenvolvimento de um indivíduo. O DNA, por sua vez, juntamente com moléculas proteicas forma o cromossomo.


Conforme exposto acima, a teoria Darwiniana explica de maneira satisfatória, mas não completa a transmutação das espécies no decorrer do tempo. A lacuna em sua teoria estava na ausência de uma explicação consistente sobre onde as mutações eram “armazenadas” e transmitidas para os herdeiros de um organismos. Essa lacuna pode ser suprida pela genética mendeliana. É nessa aproximação entre a Teoria de Darwin e a explicação de Mendel que surge a Teoria sintética da Evolução. Para essa teoria, a seleção artificial seleciona aquelas mutações genéticas que auxiliam a adaptação do organismo para o ambiente e que são transferidos para os seus herdeiros.


2. A Computação Evolucionária


Conforme exposto acima, a teoria da evolução de Darwin tem um potencial explanatório inigualável, que é útil não somente ao estudo da biologia, mas também em ramos bem diferentes das ciências naturais, por exemplo, na ciência da computação. Desde a década de 50 a teoria da evolução já não era estranha à computação. Já em Turing (1950, p. 456) é possível ver, ainda que de forma incipiente, a utilização da teoria da evolução ao menos como analogia para explicar o processo de aprendizado de máquina. É importante pontuar, também, o trabalho de Nils Barricelli (1954), que simulou, por meio de algoritmos o processo evolucionário.


Antes de avançamos, é importante pontuar que, embora a computação evolucionária e todo o aprendizado de máquina sejam impressionantes, não há de fato até o momento, maquinas que verdadeiramente evoluem. A computação evolucionária é, em última análise, o uso de matemática e estatística para resolverem problemas usando a meta-heurística. Talvez a principal utilização da computação evolucionária seja para criar redes neurais e inteligência artificial.


Não obstante, a computação evolucionária pode ser definida, de uma forma geral, como “uma área da ciência da computação que usa ideias da evolução biológica para resolver problemas computacionais” (Mitchell; Taylor, 1999). Essa interseção entre as duas áreas é realizada por meio dos algoritmos evolucionários.


Lembremo-nos dos pressupostos básicos para a evolução vistos acima: mutação, seleção e hereditariedade. Ao aplicarmos esses pressupostos à computação, o processo evolucionário do algoritmo pode ser assim descrito:


O primeiro componente do algoritmo consiste em população de possíveis soluções com mutações diferentes. Essas mutações, que geralmente são expressas em bits são os genes nesse processo. Cada indivíduo na população, por sua vez, é um cromossomo. Assim, um cromossomo poderia ser composto dos seguintes genes na seguinte ordem: 000000, sendo cada zero um gene ou um bit. Um segundo cromossomo por sua vez, teria os seguintes genes: 111111. Um terceiro cromossomo os genes: 111001. Cada indivíduo na população terá uma codificação diferente, sendo a população do tamanho da combinação de cada bit (0 ou 1) com o tamanho da variável que armazena esses bits.


Aqui faço uma pequena digressão para aqueles que ainda não tem familiaridade com programação. Bits são unidades de informação armazenadas e transmitidas por um computador. Os bits somente podem ter dois valores: 0 e 1. Variáveis, por sua vez, são espaços na memória de um computador que armazenam diversos tipos de informação diferentes, como números inteiros ou reais, caracteres, datas ou boolean (verdadeiro ou falso). Todas essas informações dentro de uma variável podem ser “traduzidas” para bits.

Voltando à nossa explicação original, cada indivíduo ou cromossomo, é uma combinação de genes difere. Cada cromossomo é então avaliado pela sua capacidade de resolver o problema ou ao menos de chegar mais próximo de uma solução. Assim, aquele cromossomo mais capaz, ou em termos biológicos, mais apto a prover uma solução ao problema computacional sobrevive.


Esses cromossomos “sobreviventes” são então selecionados e podem “procriar”. A próxima geração carregará os genes dos cromossomos antepassados por meio de um crossover, com a recombinação de genes dos cromossomos sobreviventes. Por fim, a nova geração de cromossomos sofrerá mutações randômicas que não resolver o problema de forma mais eficiente.


Esse processo todo ocorre até que a convergência de toda a população. Há convergência quando não há divergência significativa entre os descendentes produzidos e os ascendentes. Quando isso ocorre, teremos um conjunto de soluções possíveis ao nosso problema matemático.

Abaixo é possível ver um pouco de um algoritmo genético escrito na linguagem de programação Java:




3. Conclusão


Embora a computação evolutiva seja uma forma matemática requintada de solucionar um problema computacional, ao utilizar a teoria da evolução ela consegue apresentar soluções elegantes e eficientes. O potencial dos algoritmos evolucionários é enorme, podendo ser utilizados na criação de jogos (Aqui há um exemplo prático), engenharia (Slowik; Kwasnicka, 2020) ou até mesmo no próprio estudo da evolução biológica, como por exemplo, na criação de árvores filogenéticas (Warnow, 2017). Tendo demonstrado brevemente o que a computação evolucionária, é importante observar que ainda é cedo abstrairmos qualquer conclusão exacerbada sobre o futuro da computação evolucionária, sendo esta simplesmente uma forma elegante de utilizar a matemática para resolver problemas cotidianos.


Referencias


BARRICELLI, Nils A. Esempi Numerici di processi di evoluzione. Methodos, p. 45-68, 1954.

BURKHARDT, Frederick, Ed. Charles Darwin's Letters: A Selection 1825-1859. Cambridge: Cambridge University Pressed. 1996.


DARWIN, Charles. On the origin of species. Oxford: Oxford University Press, 1996.


DENNETT, D. C. Darwin's dangerous idea: evolution and the meanings of life. New York: Simon & Schuster, 1995. 586 p.


MENDEL, Gregor. Versuche über Pflanzen-Hybriden. Verhandlungen des naturforschenden Vereins, v. IV, p. 3-47, 1865.


MITCHELL, Melanie; TAYLOR, Charles E. Evolutionary Computation: An Overview. Annual Review of Ecology and Systematics, v. 30, n. 1, p. 593-616, 1999.


SLOWIK, Adam; KWASNICKA, Halina. Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications, v. 32, n. 16, p. 12363-12379, 2020/08/01 2020. ISSN 1433-3058.


TURING, A. M. Computing Machinery and Intelligence. Mind, v. 59, n. 236, p. 433-460, 1950.

WARNOW, Tandy. Computational Phylogenetics: An Introduction to Designing Methods for Phylogeny Estimation. Cambridge: Cambridge University Press, 2017.