Você está visualizando atualmente Algoritmos Bioinspirados: algoritmos inspirados na natureza
Algoritmos inspirados na natureza

Algoritmos Bioinspirados: algoritmos inspirados na natureza

Ao começar a programar, é comum ter a impressão que o mundo que vivemos é altamente artificial, porém, a natureza ainda inspira os programadores a construir soluções para o mundo moderno. Os algoritmos bioinspirados são soluções criadas por cientistas da computação que mimetizam comportamentos, por exemplo, de animais.

Nesse post quero te mostrar a beleza de olhar para o mundo de forma diferente, consequentemente, olhar para soluções incríveis que sem a ajuda da natureza seriam insolucionaveis.

Tamjid Hossen sabbir, CC BY-SA 4.0, via Wikimedia Commons

Olhando para tela do seu celular, usando um notebook com processadores ultra avançados e placas de vídeo maravilhosas, toda a computação pode parecer muito distante da natureza. Uma pessoa nascida depois de 2010, dificilmente vai conseguir imaginar como era a vida antes da internet, celulares, computadores etc. No entanto, nós humanos temos uma característica muito comum de todos os animais, nossas ideias são influenciadas por aquilo que vemos (experiências). Mas calma ai, não quero entrar aqui na brisa filosófica do mundo das ideia, etc. Meu objetivo aqui é apenas mostrar a beleza da natureza sendo reproduzida por algoritmos computacionais.

Nesse artigo quero te mostrar 3 algoritmos/tecnologias que foram inspiradas na natureza e mudaram a sua vida sem você saber. 

1- Redes neurais

As redes neurais em ciência da computação são algoritmos bioinspirados, ou seja, modelos computacionais inspirados pelo sistema nervoso central de um animal (em particular, o cérebro), que são capazes de realizar o aprendizado de máquina bem como o reconhecimento de padrões. Esse tipo de sistema é apresentado geralmente como sistemas de “neurônios interconectados, que podem computar valores de entradas”, simulando o comportamento de redes neurais biológicas.

Esse tipo de tecnologia vem revolucionando a área da computação e executando tarefas incríveis. Por exemplo, uma rede neural é capaz de reconhecer a escrita manual através de um conjunto de neurônios de entrada, que podem ser ativados pelos pixels de uma imagem. Os dados adquiridos por essa ativação dos neurônios são então repassados​​, ponderados e transformados por uma função determinada pelo designer da rede. Este processo é repetido até que, finalmente, um neurônio de saída é ativado determinando qual caractere foi lido [1].

Mas não é só isso, essas redes têm se tornado tão poderosas que estão aprendendo a dirigir, jogar, traduzir textos e muito mais.

2- Algoritmos genéticos

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. Esse tipo de algoritmo foi fundamentado principalmente pelo americano John Henry Holland e atualmente é 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).

Esse tipo de algoritmo tem sido usado em larga escala para diversas finalidades: predição de quantidade de mortos por COVID-19 [2], Jogos Educativos computadorizados utilizando [3] Projetos de engenharia [4], etc.

Um bom exemplo de algoritmo que utiliza conceitos de genética para evolução das espécies são as próprias redes neurais como, por exemplo, o NEAT. Em resumo esse algoritmo busca gerar várias redes neurais aleatórias na primeira geração de indivíduos e aqueles que se sairem bem são selecionados para sofrer uma pequena mutação e evoluir. Ao repetir esse processo multiplas vezes a rede consegue compreender quais os melhores pesos a serem atribuidos (dada determinada situação) e tomar uma decisão adequada (output).

3- Colônias de formigas

No mundo real, as formigas andam sem rumo (pelo menos inicialmente) até que, encontrada comida, elas retornam à colônia deixando um rastro de feromônio. Se outras formigas encontram um desses rastros, elas tendem a não seguir mais caminhos aleatórios. Em vez disso, seguem a trilha encontrada, retornando, e, inclusive, enfatizando se acharam alimento.  

O comportamento das formigas já foi reproduzido no mundo virtual que modelaram isso em termos computacionais:

Com o transcorrer do tempo, entretanto, as trilhas de feromônio começam a evaporar, reduzindo, assim, sua força atrativa. Quanto mais formigas passarem por um caminho predeterminado, mais tempo será necessário para o feromônio da trilha evaporar. Analogamente, elas marcharão mais rapidamente sobre um caminho curto, o que implica aumento da densidade de feromônio depositado antes que ele comece a evaporar.

A evaporação do feromônio também possui a vantagem de evitar a convergência para uma solução local ótima: se a evaporação não procedesse, todas as trilhas escolhidas pelas primeiras formigas tornar-se-iam excessivamente atrativas para as outras e, neste caso, a exploração do espaço da solução delimitar-se-ia consideravelmente. Quando uma formiga encontra um bom (curto) caminho entre a colônia e a fonte de alimento, outras formigas tenderão a segui-lo, gerando assim feedback positivo, o que eventualmente torna um determinado caminho mais interessante.

A ideia do algoritmo da colônia de formigas é imitar este comportamento através de “formigas virtuais”, que caminham por um grafo que representa o problema a ser resolvido

Algorítmos de otimização – Wikipedia

Interessante esse comportamento, certo?

Esse GIF foi produzido usando um código em Python que basicamente é dividido em 3 partes: 1) a manipulação de imagens; 2) a criação dos objetos formiga e interface; 3) a criação da simulação.

Criando um algoritmo bioinspirado

Aqui no nosso site já exploramos a criação de imagens usando a biblioteca matplotlib, portanto, eu sugiro fortemente que você acesse o nosso tutorial. Mas, em resumo teremos 3 funções simples para manipular a interface:

import numpy as np
from matplotlib import pyplot as plt
import random

##############  manipulação de imagens ###################
    
def criarNovaImagem(width, height, greyPoints):
    mat = []
    x1 = []
    for i in range(0, width):
        x1.append(greyPoints)
    for i  in range(0,height):
        mat.append(x1)
    return mat
    
def escrevePonto(img, x,y, intensity):
    img = np.array(img)
    img[y, x] = intensity
    return img

def mostrarImagem(mapa):
     ni = np.array(mapa)
     plt.imshow(ni, cmap='gray')
     plt.show()

##################################################     

Agora eu posso criar uma interface e também objetos para representar minhas formigas:


class Interface:
    framerate = 30
    tela = []
    form = [0,0]
    alim = [0,0]
    encontrou = 0

    
    def mostrarTela(self):
        mostrarImagem(self.tela)
        
    def ajustarFramerate(self, fr):
        self.framerate = fr
        
    def criaNovaInterface(self, width, height):
        self.tela  = criarNovaImagem(width,height,15)
        
    def criarFormigueiro(self):
        #self.form = [random.randint(0, 10), random.randint(0, 10)]
        self.tela = escrevePonto(self.tela, self.form[0], self.form[1] , 0)
    
    def criarAlimento(self):
        self.form = [random.randint(40, 50), random.randint(40, 50)]
        self.tela = escrevePonto(self.tela, self.form[0], self.form[1] , 0)


class Formiga:
    comida = False
    x = 0
    y = 0
    ux = 0
    uy = 0
    
    def setFormiga(self, t):
        self.x = t.form[0]
        self.y = t.form[1]        
    
    def moveRandom(self, t):
        if(t.encontrou == 1):
            tempx = self.x
            tempy = self.y
            if t.alim[0] > self.x:
                self.x += 1
            elif t.alim[0] < self.x:
                self.x -= 1
            elif t.alim[1] < self.y:
                self.y -= 1
            elif t.alim[1] > self.y:
                self.y += 1
            t.tela = escrevePonto(t.tela, tempx, tempy, 15)
            t.tela = escrevePonto(t.tela, self.x, self.y, 0)
            self.ux = tempx
            self.uy = tempy
            return t
            
                
        if(self.x == t.alim[0] and self.y == t.alim[1]):
            t.encontrou = 1
            return t
        while(1==1):
            tempx = self.x
            tempy = self.y
            rand = random.randint(0, 5)
            if rand == 0 or rand == 4:
                self.y = self.y -1
            if rand == 1 or rand == 5:
                self.x = self.x - 1
            if rand == 2:
                self.y = self.y + 1
            if rand == 3:
                self.x = self.x + 1
        
            if checarValor(self.x,self.y) == 1 and self.ux != self.x and self.uy != self.y:
                t.tela = escrevePonto(t.tela, tempx, tempy, 15)
                t.tela = escrevePonto(t.tela, self.x, self.y, 0)
                self.ux = tempx
                self.uy = tempy
                return t
            else:
                self.x = tempx
                self.y = tempy
        

Por fim, podemos criar nosso objeto main:


   
def checarValor(x, y):
    if x >= 50 or y >= 50 or x < 0 or y < 0:
        return 0
    return 1



#### bloco prinpal (main)        

t = Interface()
t.criaNovaInterface(50, 50)
t.criarFormigueiro()
t.criarAlimento()
t.mostrarTela()

f = Formiga()
f.setFormiga(t)
f1 = Formiga()
f1.setFormiga(t)
f2 = Formiga()
f2.setFormiga(t)
for r in range(0,500):
    t = f.moveRandom(t)
    t = f1.moveRandom(t)
    t = f2.moveRandom(t)
    t.mostrarTela()

O resultado fica mais ou menos assim (dependendo do comportamento aleatório adotado pelas formigas):

Exemplo de simulação simples de colônia de formigas | fonte: Autoria própria

É claro que esse algoritmo não chega nem perto das simulações mais complexas onde os feromônios são liberados e as formigas conseguem compreender isso. No entanto, é uma boa oportunidade para entender a complexidade e a beleza de algorítmos assim.

Essa modalidade de algoritmos bioinspirados tem sido utilizada para produzir soluções quase ótimas. No vídeo abaixo você encontra uma simulação do comportamento humano quando grandes aglomerações acontecem. Isso também pode ser considerado como bioinspiração.

  • Veja o vídeo sobre simulações de grandes multidões aqui.

A computação bioinspirada não é uma novidade, ela já é estudada há algum tempo. Diversos cientistas mostram como a natureza ainda é soberana sobre as ciências e como devemos aprender com ela. 

E você? consegue imaginar um algoritmo que você pode codificar baseando-se na natureza?

Quer ver nosso código completo?

Veja nosso Github

Referências

Vinicius dos Santos

Apenas um apaixonado por Ciência da Computação e a forma com que ela pode transformar vidas!

Deixe um comentário

15 − doze =