Um organismo amebóide unicelular, um plasmódio de verdadeiro fungo viscoso Physarum polycephalum. Crédito:Masashi Aono
Pesquisadores da Universidade de Hokkaido e da Amoeba Energy, no Japão, inspirado no comportamento de forrageamento eficiente de uma ameba unicelular, desenvolveu um computador analógico para encontrar uma solução confiável e rápida para o problema do caixeiro viajante - um problema representativo de otimização combinatória.
Muitas tarefas de aplicação do mundo real, como planejamento e programação em logística e automação, são matematicamente formuladas como problemas de otimização combinatória. Computadores digitais convencionais, incluindo supercomputadores, são inadequados para resolver esses problemas complexos em tempo praticamente permissível, pois o número de soluções candidatas que eles precisam avaliar aumenta exponencialmente com o tamanho do problema - também conhecido como explosão combinatória. Assim, novos computadores chamados máquinas Ising, incluindo recozedores quânticos, têm sido ativamente desenvolvidos nos últimos anos. Essas máquinas, Contudo, requerem um pré-processamento complicado para converter cada tarefa para a forma que podem manipular e correm o risco de apresentar soluções ilegais que não atendem a algumas restrições e solicitações, resultando em grandes obstáculos às aplicações práticas.
Esses obstáculos podem ser evitados usando a recém-desenvolvida 'ameba eletrônica, 'um computador analógico inspirado por um organismo amebóide unicelular. A ameba é conhecida por maximizar a aquisição de nutrientes de forma eficiente, deformando seu corpo. Ele mostrou encontrar uma solução aproximada para o problema do caixeiro viajante (TSP), ou seja, dado um mapa de um certo número de cidades, o problema é encontrar o caminho mais curto para visitar cada cidade exatamente uma vez e retornar à cidade de origem. Esta descoberta inspirou o professor Seiya Kasai da Universidade de Hokkaido a imitar a dinâmica da ameba eletronicamente usando um circuito analógico, conforme descrito na revista Scientific Reports. "O núcleo da ameba busca uma solução no ambiente eletrônico onde os valores de resistência nas interseções das barras transversais representam restrições e solicitações do TSP, "diz Kasai. Usando as barras transversais, o layout da cidade pode ser facilmente alterado atualizando os valores de resistência sem pré-processamento complicado.
Diagrama do circuito da ameba eletrônica (à esquerda:núcleo da ameba, direita:barra transversal de resistência). Crédito:Amoeba Energy
Kenta Saito, um Ph.D. estudante no laboratório de Kasai, fabricou o circuito em uma placa de ensaio e conseguiu encontrar a rota mais curta para o TSP de 4 cidades. Ele avaliou o desempenho para problemas maiores usando um simulador de circuito. Então, o circuito encontrou de forma confiável uma solução legal de alta qualidade com um comprimento de rota significativamente menor do que o comprimento médio obtido pela amostragem aleatória. Além disso, o tempo necessário para encontrar uma solução jurídica de alta qualidade cresceu apenas linearmente para o número de cidades. Comparando o tempo de pesquisa com um algoritmo TSP representativo "2-opt, "a ameba eletrônica torna-se mais vantajosa à medida que o número de cidades aumenta." O circuito analógico reproduz bem a capacidade de otimização única e eficiente da ameba, que o organismo adquiriu através da seleção natural, "diz Kasai.
Desempenho de busca de solução de TSP da ameba eletrônica em função do número de cidades, N. (Esquerda) O comprimento da rota obtido pela ameba eletrônica (pontos vermelhos) foi normalizado pelo comprimento médio calculado por amostragem aleatória. (À direita) Tempo de busca da solução da ameba eletrônica (pontos vermelhos) e do 2-opt executado em um computador convencional (círculo branco), onde o eixo vertical representa o incremento dos resultados para o TSP de 10 cidades. Crédito:Masashi Aono
“Como o computador analógico consiste em um circuito simples e compacto, pode resolver muitos problemas do mundo real em que as entradas, restrições, e as solicitações mudam dinamicamente e podem ser incorporadas a dispositivos IoT como um microchip de economia de energia, "diz Masashi Aono, que lidera a Amoeba Energy para promover o uso prático dos computadores inspirados em amebas.