Computação biogeográfica

Uma parte dos esforços em se desenvolver novas ferramentas computacionais para a solução de problemas complexos é no sentido de entender mecanismos, comportamentos e dinâmicas de sistemas naturais (químicos, físicos e biológicos) e implementar algoritmos inspirados ou baseados nestas ideias. A linha de pesquisa que emprega esta filosofia pode ser denominada de Computação natural, mais especificamente sua sub-área denominada de Computação Inspirada na Biologia ou Computação bio-inspirada. Esta sub-área consiste no estudo de fenômenos naturais, comportamentos de organismos vivos e modelos teóricos de sistemas naturais de modo a criar ferramentas computacionais inspiradas nestes sistemas. Neste contexto estão inseridas as Redes neurais artificiais, a Computação evolutiva, os Sistemas imunológicos artificiais e a Inteligência de enxame.

Em todas as áreas citadas é possível encontrar mecanismos, definições e conceitos básicos e avançados que constituem suas respectivas estruturas conceituais (framework). Através dessas estruturas conceituais, é possível projetar algoritmos de diversos tipos para a resolução de diferentes classes de problemas. Embora nem sempre essas estruturas sejam formalizadas e unificadas, é possível encontrar esforços nesse sentido, por exemplo, a Engenharia Imunológica. como uma estrutura conceitual formal para os Sistemas Imunológicos Artificiais; e os volumes organizados por Bäck et al. que apresentam os elementos básicos de projeto de algoritmos para a Computação Evolutiva.

Com o objetivo de abstrair conceitos, definições e mecanismos, a Computação Biogeográfica propõe uma estrutura conceitual básica baseada em processos presentes na ciência da Biogeografia. Antes de descrever qualquer teoria, entretanto, é preciso fazer a seguinte pergunta: dentre tantas bioinspirações distintas e tantas técnicas resultantes, porque escolher a Biogeografia?. Em outras palavras, porque utilizar a Biogeografia como fonte de inspiração?

Para iniciar a resposta a essa pergunta, considere a seguinte frase, extraída do livro de Brown e Lomolino: “Os seres vivos são extremamente multi-formes. Há provavelmente algo entre 5 e 50 milhões de espécies, menos de 2 milhões foram formalmente reconhecidas e estão catalogadas. Milhões ou talvez bilhões de espécies viveram em algum lugar do passado, mas agora estão extintas”. Indo um pouco além, Brown e Lomolino usam um exemplo interessante: “todas as espécies de plantas verdes terrestres que já viveram até o presente com-partilham um ancestral comum: uma simples alga verde que viveu há 500 milhões de anos”. A pergunta chave é: Como foi possível atingir esse elevado nível de diversidade de espécies na história do planeta Terra, muitas vezes partindo de um único ancestral? Entender esses padrões de biodiversidade é o papel da Biogeografia, uma ciência multidisciplinar fundamentada em ecologia, biologia de populações, sistemática, biologia evolutiva e ciências da Terra. Portanto, o que se busca com o estudo da Biogeografia é compreender e modelar processos espaço-temporais voltados para a geração e manutenção de diversidade. Espera-se que conceitos fundamentais da Biogeografia possam auxiliar a concepção de algoritmos que tratem de forma eficiente problemas de engenharia em geral, como otimização e mineração de dados.

Gerar diversidade, sob o ponto de vista de resolução de problemas, é crucial em alguns casos, merecendo destaque os seguintes:

1. Problemas de tomada de decisão;
2. Problemas de otimização multi-objetivo;
3. Problemas de otimização dinâmica;
4. Problemas de classificação.

Esses exemplos motivam a criação de mecanismos voltados à diversidade de soluções, pois muitas vezes se beneficiam com a proposição de múltiplas alternativas de solução.

Obter soluções diversas não é uma tarefa trivial, sendo que técnicas distintas são empregadas nas mais variadas classes de algoritmos. A capacidade de lidar com múltiplas soluções de boa qualidade em paralelo é um dos diferenciais dos algoritmos bioinspirados, embora nem sempre a diversidade seja um mecanismo inerente às ferramentas bioinspiradas. Os algoritmos evolutivos, em sua forma padrão, não são capazes de manter uma diversidade de soluções, pois apenas com operadores de mutação e reprodução convencionais essa tarefa não é possível. Para isso são introduzidos operadores genéticos como fitness sharing, crowding, reinício da população, dentre outros ou inserção de populações estruturadas como Island Models e Cellular Genetic Algorithms. Em contrapartida, os algoritmos inspirados nos Sistemas Imunológicos Artificiais apresentam a diversidade como parte inerente do seu modelo básico. Isso se deve à própria bioinspiração. Mas mesmo os Sistemas Imunológicos Artificiais, inspirados na operação de conjuntos de componentes distribuídos e em circulação pelo organismo, não possuem ainda um formalismo espaço-temporal abrangente para sustentar os seus modelos computacionais. Este é o principal diferencial da Biogeografia e são seus mecanismos de especiação, fluxo gênico e ocupação de habitats, dentre outros, que são explorados na proposição da Computação Biogeográfica.

Breves Conceitos da Biogeografia

No contexto da Computação Biogeográfica, o conceito de espécie é tratado de forma específica, vinculado ao conceito de espécie biológica, que define uma espécie como sendo uma população de organismos que apresentam isolamento reprodutivo em relação a outras populações, representando uma linhagem evolutiva separada. Adicionalmente, tem-se o conceito de habitat, o qual engloba uma ou mais espécies, no sentido de definir locais e condições ambientais onde o estabelecimento de populações é viável.

A Biogeografia estuda os padrões de diversidade de espécies e como surge a biodiversidade. Para descrever como ocorrem esses padrões, utiliza-se definições de processos biogeográficos. A taxonomia dos processos da Biogeografia é definida basicamente em três tipos distintos de processos: (1) Geográficos; (2) Ecológicos; e (3) Evolutivos. Sendo esse último subdividido em processos Macro e Microevolutivos, a principal diferença entre eles é a escala. A microevolução lida com mudanças evolutivas dentro de populações, que ocorrem como resultado de nascimentos, mortes e movimentos diferenciais de indivíduos com certas características herdáveis. Em contrapartida, a macroevolução lida com mudanças frequentemente causadas pela proliferação diferencial e extinção de espécies, de forma que tais mudanças alteram substancialmente a diversidade das linhagens.

Uma única espécie pode explorar todo um ecossistema, transpondo barreiras ecológicas, evoluindo e dando origem a diversas espécies descendentes, que podem ter diferenças genéticas, em relação à espécie ancestral. Ao expandir sua amplitude, uma espécie poderá ou não se adaptar a novos ambientes. Se a adaptação for necessária, vários são os processos evolutivos que permitem a evolução e adaptação. As relações entre adaptação, evolução e o meio em que as espécies vivem podem ser explicadas pela taxonomia dos processos biogeográficos: os processos geográficos e ecológicos exercem uma pressão sobre o ecossistema. Caso as espécies necessitem de readaptação ao meio, os processos evolutivos se encarregarão da evolução, se esta for um sucesso, novas espécies surgem, caso contrário a extinção é inevitável.

Um conceito interessante que complementa a noção de adaptação a habitats distintos é o de superfície adaptativa de Wright. Esse conceito descreve o mapeamento genético dos indivíduos em uma função de aptidão (fitness). A combinação de genes resulta em organismos pouco adaptados que estariam povoando os vales da função, enquanto que os mais bem adaptados povoam os picos da função. Cada pico equivale a uma região de alta aptidão para um determinado habitat. O domínio que compreende a função de aptidão delimita as possibilidades de adaptação da biodiversidade dentro de um ecossistema arbitrário.

A seguir são feitas breves explicações a respeito dos processos biogeográficos. Para informações detalhadas a respeito dos processos e padrões biogeográficos consulte:

Processos Geográficos e Processos Ecológicos

Vicariância e dispersão

Vicariância é um processo geográfico e dispersão é um processo ecológico, então qual é a relação entre eles? Ambos estão relacionados com barreiras ecológicas. Enquanto a vicariância é a divisão de uma espécie pelo surgimento de uma barreira, a dispersão implica a transposição de uma barreira. Em ambos os casos, o isolamento implica eventos de especiação. Em uma definição mais detalhada, vicariância ou efeito vicariante é o mecanismo no qual ocorre uma fragmentação de uma área biótica, separando populações de determinadas espécies. Já a dispersão possui uma explicação mais ampla. Todos os organismos possuem alguma capacidade de se mover dos locais de nascimento para novos locais. O movimento da prole para longe dos pais faz parte do ciclo de vida de todos os animais e plantas. Em termos gerais a dispersão se refere ao movimento dos organismos para fora de seus pontos de origem.

Mudanças Ambientais

Mudanças ou perturbações ambientais são definidas como qualquer alteração significativa e de longa duração que ocorre no meio ambiente, ecossistemas em geral. Entende-se aqui o termo longa duração como tempo suficiente para que a vida seja afetada por essas mudanças. Cada região possui padrões heterogêneos particulares e uma história biogeográfica imposta pelas condições ambientais e os demais processos biogeográficos. Os regimes de perturbação encontrados em toda superfície são influenciados por um conjunto enorme de fatores ambientais, da ordem de mudanças climáticas, geográficas, ecológicas dentre outras (Brown & Lomolino, 2006; Huston, 1994) que alteram as oportunidades ecológicas e fazem com que as espécies precisem se readaptar às novas condições. Ao falhar em sua readaptação, a extinção é conseqüência certa.

Competição Interespecífica

A interação interespecífica como próprio nome diz está relacionada a qualquer interação entre espécies distintas. Os principais tipos de interações ecológicas entre as espécies são competição, predação e mutualismo. Entretanto, para a Computação Biogeográfica, o enfoque será nas interações que envolvem algum tipo de competição, o que resulta no desfavorecimento de alguma das espécies que estão participando do processo de interação.

Competição Intraespecífica

A interação intra-específica é a interação entre organismos da mesma espécie. Novamente, aqui estamos interessados na competição entre indivíduos de uma mesma espécie. Quando falamos de competição por recursos, essa competição está diretamente relacionada o processo de seleção natural, no qual as espécies mais adaptadas ao meio terão maior probabilidade de sobrevivência.

Processos Microevolutivos

Reprodução

A reprodução é o processo através do qual todos os seres vivos produzem descendentes, dando continuidade a sua espécie. Pode ser de dois tipos: assexuada e sexuada. No primeiro caso, a reprodução ocorre sem a partilha de material genético entre dois indivíduos. Um exemplo desse caso é a própria divisão celular. Já no outro caso, os descendentes são resultados do compartilhamento de material genético entre dois indivíduos distintos da mesma espécie, denominado de macho e fêmea.

Mutação

A mutação é definida como qualquer alteração da seqüência do material genético de um organismo. Mutações geram variações no conjunto de genes da população. São consideradas o mecanismo que permite a ação da seleção natural. Mutações desfavoráveis podem ter sua freqüência reduzida na população por meio da seleção natural, enquanto mutações favoráveis podem se acumular, resultando em mudanças evolutivas adaptativas.

Seleção Natural

O conceito básico de seleção natural é que características favoráveis que são hereditárias tornam-se mais comuns em gerações sucessivas de uma população de organismos que se reproduzem, e que características desfavoráveis que são hereditárias tornam-se menos comuns. A seleção natural age no fenótipo, ou nas características observáveis de um organismo, de tal forma que indivíduos com fenótipos favoráveis têm mais chances de sobreviver e reproduzir-se do que aqueles com fenótipos menos favoráveis. Se esses fenótipos apresentam uma base genética, então o genótipo associado com o fenótipo favorável terá sua freqüência aumentada na geração seguinte. As populações tendem a divergir caso exista variação suficiente no ambiente para selecionar características diferentes para lidar com diferentes condições ambientais, o seja, pode resultar na emergência de novas espécies.

Adaptação

O conceito de adaptação está intrinsecamente ligado ao de seleção natural, pois complementa a noção de melhora gradativa. O grau de adaptação ao meio ambiente é o que determina o caminho pelo qual seguirá o processo da seleção natural: uma resposta à seleção ocorre sempre que uma característica herdável está relacionada com o sucesso reprodutivo, o resultado é a melhora de desempenho ao longo de gerações de reprodução e diferenciação. Essa melhora de desempenho é o processo que chamamos de adaptação através da evolução e com a ajuda da reprodução.

Fluxo Gênico

Os indivíduos que migram para uma nova área carregam seus genes com eles e se subseqüentemente têm reprodução bem sucedida, eles introduzem seus genes na população local. O fluxo gênico age contra a adaptação das espécies a determinados locais, pois indivíduos externos podem introduzir genes que desfavorecem a especialização aos habitats da espécie local, produzindo até mesmo hibridizações pouco adaptadas.

Efeito do Fundador

Novas populações, muitas vezes, são fundadas por um pequeno grupo de indivíduos de alguma determinada espécie. Seja por migração ou por qualquer outro evento que tenha causado o isolamento do subconjunto de indivíduos. A freqüência genética desse grupo, geralmente bem menor que a população toda, difere consideravelmente da freqüência da população parental. Alguns alelos podem estar completamente ausentes, outro raros na população parental, podem adquirir freqüências muito altas na nova população simplesmente porque estavam presentes nos indivíduos que a formaram. Esse processo é denominado de efeito do fundador e os indivíduos que constituem a nova população, isolada da população parental, são denominados de fundadores.

Processos Macroevolutivos

As perspectivas macro e microevolutivas são complementares, ambas são necessárias para compreender a influência dos processos ecológicos e geográficos nos processos evolutivos e a influência destes nas distribuições dos organismos. Todavia, é mostrado que uma profunda compreensão dos processos macroevolutivos também requer uma perspectiva microevolutiva sobre como as populações respondem às mudanças ambientais no tempo e espaço. A Radiação adaptativa (ou Irradiação adaptativa) é a diversificação das espécies para preencher uma ampla variedade de habitats. Ela ocorre quando uma única espécie ancestral dá origem, através de repetidos episódios de especiação, a numerosos descendentes que se tornam ou permanecem simpátricos (mantém contato, não estão isolados). Essas espécies tendem a divergir na utilização de recursos ecológicos, ocupando outros habitats. Existe também a possibilidade dessas espécies virem a ser separadas por barreiras (por eventos vicariantes, por exemplo) e se tornarem alopátricas, podendo ainda assim até ter trocas genéticas por meio de fluxo gênico. O surgimento de uma nova espécie é um grande passo evolutivo, mas nada garante o futuro de recém espécies formadas. Os diversos tipos de especiação dependem dos processos e mecanismos naturais o quais forçaram o seu surgimento.

Especiação Alopátrica e Peripátrica

É o processo de especiação mais simples e freqüente. Ocorre quando as populações são geograficamente isoladas, a tal ponto que o fluxo gênico entre elas é quase todo ou inteiramente interrompido. Assim essas populações isoladas que vivem em regiões (habitats) distintas, tendem a se diferenciar. Se o ambiente é heterogêneo, e as populações regionais forem suficientemente isoladas, tal que o fluxo gênico é totalmente interrompido ou drasticamente reduzido, elas se tornarão unidades evolutiva completamente independentes. Pode-se distinguir duas maneiras distintas de se ocorre o isolamento, a primeira delas é através do surgimento de barreiras, ou seja, por efeito vicariante, neste caso o isolamento se dá em populações grandes, ou seja, ambos os isolados possuem um número grande de indivíduos. A segunda maneira é através de dispersão, onde se dá o efeito do fundador, nesse caso temos a especiação peripátrica. A especiação peripátrica é um tipo em particular de especiação alopátrica.

Especiação Simpátrica

A especiação não ocorre apenas quando há isolamento geográfico, ela pode, frequentemente, ocorrer dentro de populações espacialmente contíguas, em outras palavras, a espécie começa a divergir dentro do mesmo habitat. A especiação simpátrica pode ocorrer através de alterações cromossômicas e mutações. Durante o processo de fertilização ou de desenvolvimento do embrião, existe uma chance de ocorrer rearranjo do material genético. Esses indivíduos mutantes geralmente têm fertilidade prejudicada quando se acasalam com um indivíduo que possui o arranjo genético original e, às vezes, podem estar restritos ao cruzamento apenas com indivíduos do novo arranjo. Se uma população que apresenta o novo arranjo se estabelecer, será geneticamente isolada de sua população original e pode divergir rapidamente para uma nova espécie.

Especiação Parapátrica ou Competitiva

Fortes pressões seletivas fazem com que uma determinada população se adapte a dois ou mais regimes ambientais diferentes, a especiação competitiva ou parapátrica é a expansão de uma espécie de um único habitat para outro habitat inexplorado. A expansão ocorre devido à falta de competição para usar a oportunidade ecológica inexplorada. A separação em duas espécies ocorre devido à grande pressão competitiva nos indivíduos, entre aqueles que são melhores em explorar a velha e a nova oportunidade. Nas regiões de ocupação entre os dois habitats existem indivíduos híbridos, que são pouco adaptados, essa é a chamada zona de hibridização.

Extinção e Seleção de Espécies

A extinção é o total desaparecimento de espécies, subespécies ou grupos de espécies. O processo de extinção pode ser visto como a eliminação total de uma espécie devido a diversos fatores. Dentre esses fatores podemos citar o de espécies pouco adaptadas às condições ambientais ou ainda competição entre espécies por um mesmo habitat. A sobrevivência diferencial e a proliferação de espécies no tempo geológico foram denominadas seleção de espécies.

Estrutura Conceitual da Computação Biogeográfica

Definição: A Computação Biogeográfica (CB) é uma linha de pesquisa que tem o objetivo de abstrair processos presentes na Ciência da Biogeografia e formalizá-los através de uma estrutura con-ceitual capaz de permitir o desenvolvimento de ferramentas computacionais voltadas para a solução de problemas complexos.

Processos centrais da Biogeografia são descritos abstratamente e em alto nível para compor a Computação Biogeográfica. Através da Computação Biogeográfica é possível simular computacionalmente esses processos, permitindo observar o comportamento evolutivo das espécies, no espaço e no tempo. Como diferenciais da Computação Biogeográfica, destacam-se:

1. Busca multimodal;
2. Geração e manutenção de diversidade;
3. Multipopulação através de espécies;
4. Controle dinâmico do tamanho da população de indivíduos e espécies;
5. Inicia-se com apenas dois indivíduos e uma espécie; e
6. Maior autonomia no processamento de informação, no auto-ajuste de processos internos e na resposta a cenários variados e não-antecipáveis.

Figura1. Passos da concepção da Estrutura Conceitual da Computação Biogeográfica

A concepção da estrutura conceitual envolve a abstração de processos, definições e padrões da Biogeografia, a formalização matemática e computacional desses processos, e por fim, o conjunto completo dessa formalização dá origem a todo arcabouço que Computação Biogeográfica oferece (Figura 1). Através da estrutura conceitual pode-se extrair os mais diversos subconjuntos de processos com o objetivo de conceber algoritmos e ferramentas computacionais para a resolução de diversas classes de problemas complexos, com maior autonomia no processamento de informação, no auto-ajuste de processos internos e na resposta a cenários variados e não-antecipáveis. Os seguintes processos estão propostos dentro da Computação Biogeográfica:

1. Reprodução
2. Mutação
3. Fluxo Gênico
4. Seleção Natural
5. Competição Interespecífica
6. Seleção de Espécies
7. Especiação Simpátrica
8. Especiação Competitiva
9. Especiação Alopátrica
10. Especiação Peripátrica

Embora a explicação biológica de cada processo tenha sido descrita na seção anterior, a abstração computacional faz com que alguns processos sejam simplificados de modo a serem aplicados na construção das ferramentas computacionais. A formalização matemática e estrutural da Computação Biogeográfica e de todos os processos pode ser conferida no seguinte trabalho: Computação Biogeográfica: Formalização e Proposição de uma Meta-Heurística Espaço-Temporal

Vale salientar que, embora a Computação Biogeográfica tenha sido proposta primariamente com o objetivo de resolver problemas de engenharia e computação, seus processos podem também ser aplicados na construção de simulações comportamentais da natureza, com o objetivo de investigar comportamentos pontuais ou emergentes de interesse.

Um Exemplo de Algoritmo da Computação Biogeográfica

Figura2. Evolução espacial. Curvas de nível da função Griewank. Após 200 iterações, cada espécie ocupa um ótimo local. O “X” equivale ao indivíduo com melhor adaptação de cada espécie. Os diferentes símbolos representam indivíduos de espécies distintas.

Figura3. Evolução temporal. Número de espécies ao longo de 500 iterações.

Figura4. Evolução temporal. Número de indivíduos ao longo de 500 iterações.

Com o objetivo de exemplificar a potencialidade da Computação Biogeográfica, a partir de um subconjunto dos processos descritos, é mostrado um exemplo de algoritmo biogeográfico. Esse algoritmo foi desenvolvido para resolver problemas de otimização e foi aplicado em problemas simples de otimização em espaços contínuos. O principal objetivo é observar a geração e manutenção de diversidade junto a problemas multimodais. O pseudocódigo abaixo mostra um exemplo simples de algoritmo da Computação Biogeográfica, sendo que esse usa os seguintes processos: Reprodução, Mutação, Fluxo Gênico, Especiação Simpátrica e Competição Interespecífica.

• Início do algoritmo. Sejam:
• n_i o número de iterações
• B o conjunto Biodiversidade contendo todas as espécies
• V_i uma espécie qualquer pertencente a B
• x_i e x_j dois indviduos arbitrários pertecente a uma espécie qualquer
• Repita os passos a seguir, de n_i = 1 até um número máximo de iterações
  • Para cada espécie V_i ∈ B

• Escolha um número de reproduções a serem realizadas
• Para cada par de indivíduos

• Faça reprodução entre x_x e x_y e gere x_z
• Faça mutação em x_z
• Verifique a espécie a qual pertence x_z através da especiação por mutação

• Fim Para
• Escolha uma espécie V_a aleatoriamente
• Faça o fluxo gênico entre V_i e V_a e gere x_z
• Faça mutação em x_z
• Verifique a espécie a qual pertence xz através da especiação por mutação
• Faça seleção natural

• Fim Para
• Faça competição por habitats para toda espécie V_i ∈ B

Aplicando à função multimodal de Griewank no domínio [-10, 10], a Figura 2 ilustra o comportamento típico espacial do algoritmo em uma execução. Nessa execução, podemos visualizar que o algoritmo foi capaz de encontrar os 17 mínimos locais (incluso o mínimo global), com exatamente 17 espécies. O “X” indica o indivíduo mais bem adaptado de cada espécie. Um dos diferenciais do algoritmo, que é o ajuste automático do número de indivíduos e espécies pode ser observado nas Figuras 3 e 4 através de uma execução do algoritmo para a função de Griewank. A Figura 3 representa o número de espécies ao longo de 500 iterações. A Figura 4 representa o número de indivíduos.