O Algoritmo AmoebaSat

By Design Inteligente Group – (TDI) Facebook

 

 

Os investigadores projetaram e implementaram um algoritmo que resolve problemas de computação usando uma estratégia inspirada na maneira que uma ameba se ramifica para obter recursos. O novo algoritmo chamado AmoebaSAT pode resolver problemas de satisfazibilidade (SAT) [1] (um problema de difícil optimização com muitas aplicações práticas[a]) utilizando ordens de grandeza de menor número de passos do que o número de etapas necessárias por alguns dos mais rápidos algoritmos convencionais.

Os pesquisadores preveem que o sistema de computação inspirado na ameba pode oferecer vários benefícios, tais como a eficiência elevada, a miniaturização e baixo consumo de energia, que poderiam levar a um novo paradigma de computação em nanoescala para resolução de problemas de alta velocidade.

“Nós demonstramos uma maneira de aproveitar o enorme poder computacional dos fenômenos naturais em termos de complexidade e de energia”, disse Aono a Phys.org

Este estudo [2] utilizou-se o mesmo mecanismo básico de um motor molecular biológico para gerar corrente de flutuação de elétrons. Em uma catraca elétrica browniana [3] a energia térmica em um nanofio aleatoriamente faz com que os elétrons movimentem-se em uma direção (por exemplo, para a esquerda, mas não para a direita) ou que fiquem no mesmo lugar. Repetir este processo várias vezes gera um fluxo dirigido de elétrons, tendo por resultado uma corrente elétrica com flutuações estocásticas (aleatórias).

Os testes mostraram que o sistema AmoebaSAT teve uma taxa de sucesso de 100% em encontrar uma solução para vários problemas SAT de 50-variáveis [b], resolvendo estes problemas em média com aproximadamente 3000 passos. Uma versão modificada do algoritmo(direcionado para o objetivo específico), que trata de modo mais eficaz o ruído aleatório de erro-induzido, alcança um resultado ainda melhor, menos de uma média de 1800 passos. Para efeitos de comparação, um dos algoritmos mais rápidos conhecidos de busca local, WalkSAT, requer ordens de magnitude a mais de passos para resolver os mesmos problemas. Além disso, o AmoebaSAT supera WalkSAT mais significativamente à medida que o número de variáveis aumenta.

___________________________________________________________

[1] Problema de Satisfazibilidade Booleana (SAT)
https://pt.wikipedia.org/…/Problema_de_satisfatibilidade_bo…

[2] Aono M, Kasai S, Kim SJ, Wakabayashi M, Miwa H, Naruse M. Amoeba-inspired nanoarchitectonic computing implemented using electrical Brownian ratchets. Nanotechnology. 2015 Jun 12;26(23):234001.
http://iopscience.iop.org/0957-4484/26/23/234001/article

[3] Modelo da Catraca Browniana, proposto por Oster e Peskin em 1993
http://www.bibliotecadigital.ufmg.br/…/camilla.dis.cor..pdf…

Notas

[a] Aplicações: Planejamento automático, a verificação de software e o teste de circuitos, teste de propriedades de algoritmos de criptografia e chaves. Verificação de Equivalência de Circuitos, Geração Automática de Padrões de Teste, Arquitetura de Computadores(alocação de registradores), diagnóstico de carcinomas entre outros.

Lasmar, Fernanda Akl Faria. “Análise de desempenho de algoritmos para o problema da satisfatibilidade booleana.” (2015).

[b] O problema SAT: Dada uma expressão booleana na forma normal conjuntiva, ou seja, produto de somas, deve-se descobrir se existe uma combinação de valores para as variáveis que torne a expressão verdadeira. Se existe ao menos uma combinação, significa que o problema é satisfatível, daí o nome SAT.

Redução de SAT para 3SAT. Eduardo Mayer Terroso, Rafael Coimbra Pinto.
http://www.inf.ufrgs.br/~rcpin…/facul/inf05515/npc/index.htm

Fonte(Reportagem original): http://phys.org/…/2015-06-amoeba-inspired-outperforms-conve…

 

 

(Imagem/Crédito: M. Aono, et al. © 2015 IOP Publishing)