Algoritmos bioinspirados

Dada sua complexidade e funcionamento, a natureza, em particular, os seres vivos e processos biológicos, vêm fornecendo muitas inspirações para algoritmos usados na computação executarem tarefas bem sucedidas. Abaixo são exemplificados três desses algoritmos: algoritmos genéticos, redes neurais e colônia de formigas (ACO).

Algoritmos genéticos:

Esse algoritmo se baseia no processo de evolução biológica, que têm acontecido na Terra há milhões de anos, mais especificamente, o processo evolutivo que ocorre em organismos de reprodução sexuada. O processo de evolução biológica compreende a mudança na composição genética de uma população ao longo do tempo, no qual indivíduos transmitem suas características aos descendentes. O processo possui 5 mecanismos, os quais podemos dividir nos mecanismos que geram variação genética e nos que distribuem essa variação genética

Mecanismos que geram variação genética:

Mutação:

O principal mecanismo por gerar novidades genéticas, a mutação se caracteriza, a nível genético, por uma pequena alteração na sequência do material genético de um indivíduo. Esta alteração pode ser repassada à prole do indivíduo portador. A figura abaixo exemplifica uma mutação em uma sequência de DNA, em que uma troca de nucleotídeo (letra) de A por C pode resultar em uma proteína mutante, com funcionalidade totalmente diferente, por exemplo.

Crossing-over/recombinação:

Mecanismo que ocorre em espécies com reprodução sexuada, no qual dois indivíduos ‘embaralham’ seus genes para gerar gametas diferentes (espermatozóides ou óvulos). Esse mecanismo explica por exemplo, porque um homem ou uma mulher adulta podem gerar inúmeros óvulos ou espermatozóides diferentes mesmo tendo apenas um genoma.

Migração: se caracteriza pelo fluxo gênico (entrada de novos genes) na população, que agora possui uma constituição genética mais diversa graças aos indivíduos novos que popularam uma nova área. No algoritmo genético, não há um processo análogo a este.

Mecanismos que distribuem a variação genética:

Seleção natural: Talvez o mecanismo evolutivo mais conhecido de todos. Em um contexto ecológico, indivíduos possuem diferentes capacidades para sobreviver e se reproduzir dadas certas condições ambientais. Aqueles indivíduos que, dada certa situação ambiental, consegue crescer e se reproduzir, passará seus genes adiante, os quais corresponderão a um percentual maior na população. A seleção natural é a força motriz que age sobre o substrato gerado pela variação genética, i.e., diferentes genes e combinações de genes.

Vamos supor que uma espécie de inseto amarelo migra para uma área onde há um predador que facilmente a avista…

No começo, a espécie é facilmente predada. Porém, começam a aparecer alguns insetos com coloração mais esverdeada e mais escura. Esses insetos que possuem uma coloração mais verde e mais escura são menos vistos pelo predador, uma vez que sua cor se mistura à da vegetação.

Conforme as gerações se passam, aqueles indivíduos mais verdes e escuros se reproduzem e passam seus genes adiante, e sua prole também fica cada vez mais verde e mais escura.

Deriva genética: Ao contrário da seleção natural, que seleciona indivíduos que possuem maior fitness adaptativo, a deriva genética constitui na flutuação aleatória de genes na população. Ao longo do tempo, dois genes que não sofrem seleção têm probabilidades iguais de atingir uma frequência de 100% na população dado tempo indefinido se os dois começarem com frequências iguais. Nos algoritmos genéticos, esse processo não é declarado explicitamente, mas é implícito no fato de que a seleção não é absoluta: ou seja, os indivíduos que possuem maior ‘fitness’ ou que apresentam as melhores soluções, não possuem 100% de chance de serem escolhidos e os indivíduos com os piores fitness não possuem 0% de chance de serem escolhidos.

Problemas combinatórios de otimização, como no caso de encontrar a melhor combinação de produtos que cabem em um caminhão de forma a maximizar o lucro, são o tipo de problema melhor abordado por meio de algoritmos genéticos. Nesse problema, temos várias soluções possíveis, que são chamadas de indivíduos.

Cada indivíduo é representado por um cromossomo, que no contexto do problema combinatório são o conjunto de produtos a serem empacotados no caminhão. Esse cromossomo então possui vários genes, que para este problema em específico, são cada produto possível de ser empacotado dentro do caminhão. No algoritmo genético, começamos com uma população de vários indivíduos, que representam as soluções (ou arranjos de produtos) possíveis. O algoritmo então seleciona os melhores indivíduos, ou seja, aqueles que possuem as melhores soluções avaliadas por uma função de fitness, que determina, nesse caso, o lucro obtido com a combinação de itens possíveis. Um detalhe é que a seleção não é absoluta, ou seja, indivíduos que possuem as melhores soluções tem uma grande chance de serem selecionados, mas não 100%. Nessa etapa temos a seleção de forma explícita, e a deriva genética de forma implícita, já que soluções menos eficientes podem ser selecionadas simplesmente pelo acaso, assim como um inseto amarelo possui uma chance não nula de sobreviver e por acaso não ser predado na natureza, embora o inseto verde possua uma chance muito maior de sobreviver.

Posteriormente, para formar a nova geração, geralmente são aplicados operadores genéticos: crossing over e mutação. No contexto desse problema combinatório, o crossing over seria a mistura de dois cromossomos de duas solução. Vamos supor que temos duas soluções: X, com os itens 2,3,5,6,7 e a solução Y, com os itens 1,4,8,10,11. Um dos possíveis crossing over entre as duas soluções seria 2,3,5,10 e 11. Quanto à mutação, seria uma simples troca de um gene (ou produto) por outro que não há no cromossomo. Um exemplo de mutação na solução ou cromossomo X seria 2,3,10,6,7.

O algoritmo segue gerando indivíduos e os selecionando para a próxima geração, onde espera-se as soluções geradas estejam cada vez mais perto da solução ótima.

Redes neurais artificiais

Talvez a estrutura biológica mais complexa que se possa encontrar na natureza é o cérebro dos animais, e, em particular, o cérebro dos vertebrados. Dada sua arquitetura, esse órgão consegue realizar tarefas extremamente complexas, como por exemplo, traçar movimentos de uma presa, coordenar movimentos corporais, processar uma quantidade gigante de estímulos sensoriais e responder a estímulos ambientais em questão de milissegundos. Cada sistema nervoso animal é composto por pequenas unidades celulares que processam estímulos e/ou geram respostas, que são os neurônios.

Cada neurônio possui em sua estrutura dendritos, um corpo celular e um axônio.

Os dendritos são a parte que captam os sinais de outros neurônios ou estímulos externos. O corpo celular processa o estímulo e transmite por meio do axônio até seu terminal. Quando dois neurônios se comunicam para troca de informação, a essa junção dá-se o nome de sinapse, como ilustrado na figura abaixo. Cada sinapse é formada pelos dendritos de um neurônio, que recebem a informação que passa pelo terminal do axônio do neurônio anterior. Dependendo da intensidade do estímulo, neurônios transmitem ou não a informação ao seguinte. Essa condição é determinada pelo limiar excitatório, ou lei do tudo ou nada, na qual passado o limiar de excitação (geralmente 15 milivolts acima do potencial de repouso da membrana), o potencial de ação é disparado.

Nas redes neurais artificias, temos inspiração do mecanismo de transmissão de informação entre neurônios de modo que temos processos análogos entre os dois:

Ao mimetizar o funcionamento e arquitetura de uma rede de neurônios, as redes neurais artificiais podem realizar tarefas bastante complexas atribuídas somente a humanos até pouco tempo atrás, como classificação de imagens, geração automática de imagens, geração de textos, condução de veículos, reconhecimento facial e muitas outras.

ACO – Ant Colony Optimization

Outro algoritmo de otimização bioinspirado que pode ser citado é o chamado ACO (Ant Colony Optimization), que se baseia no comportamento forrageador de uma colônia de formigas.

Quando várias formigas forrageam comida, elas não têm certeza para que direção ou em qual localidade há disponibilidade de alimento ou qual o caminho mais curto. Dessa forma, as formigas deixam rastros de feromônio por onde passam, o que sinaliza outras formigas que aquela direção por onde a formiga anterior passou, pode haver alimento. Quanto mais formigas passam por um determinado local, mais feromônio há nesse local e mais forte será a atração de outras formigas pela região onde há mais feromônio, o que indica uma fonte de alimento mais próxima. Dessa forma, a colônia de formigas forma um sistema dinâmico que consegue encontrar o melhor caminho para fonte de alimentos. Na ilustração abaixo, as setas/triângulos representam os feromônios. Quanto mais escura a cor, mais forte é a concentração de feromônios, e quanto mais clara a cor das setas, mais fraca é a concentração.

Os feromônios deixados como ‘caminho’ possuem a propriedade de evaporar conforme o tempo passa. Dessa forma, caminhos ruins, onde não há fonte de alimento, ou mais longos, são menos atrativos para outras formigas, enquanto caminhos onde mais formigas passam por serem o mais curto, possuem uma concentração maior de feromônio, atraindo ainda mais formigas em um mecanismo de retroalimentação positiva. Dessa forma, eventualmente todos os forrageadores convergem para o local mais próximo de uma fonte alimentos..

Essa propriedade de encontrar os melhores caminhos faz com que esse algoritmo de otimização seja utilizado em muitos problemas que envolvem grafos, como no caso de planejar rotas de um local a outro no GPS, ou planejamento de trânsito urbano. O mais interessante é que esse tipo de algoritmo é flexível e se adapta a mudanças, podendo, por exemplo, traçar rotas novas conforme o destino ou o trajeto mudam, em um sistema de GPS.