A rede neural com uma ameba resolveu o problema do vendedor ambulante em 8 cidades

Soluções do problema do vendedor ambulante obtido por um sistema de computação baseado em ameba. Exemplos de passeios de vendedor em quatro, cinco, seis, sete e oito cidades, obtidos em experimentos, onde cada passeio é pintado de vermelho nos canais correspondentes da figura à direita. Os painéis esquerdos mostram as imagens de luz transmitidas dos estados iniciais (

Um grupo de pesquisadores japoneses da Universidade Keio, em Tóquio, demonstrou que a ameba é capaz de gerar soluções aproximadas para um problema matemático surpreendentemente complexo conhecido como problema do vendedor ambulante .

A tarefa do vendedor é uma das mais famosas tarefas de otimização combinatória, que consiste em encontrar a rota mais lucrativa que atravessa essas cidades pelo menos uma vez e depois retorna à cidade original.

A declaração de otimização do problema pertence à classe de problemas difíceis de NP, no entanto, como a maioria de seus casos especiais. A versão do “problema de decisão” (ou seja, aquela na qual a questão é levantada se a rota existe não mais que o valor especificado de k) pertence à classe de problemas NP-completos.

A dificuldade de calcular a solução certa aumenta exponencialmente à medida que mais cidades são adicionadas à tarefa. Por exemplo, para quatro cidades existem três soluções e para seis cidades - 360. No futuro, o crescimento exponencial continua.

Apesar da grande complexidade computacional, há um grande número de algoritmos heurísticos e precisos que podem resolver completamente alguns casos com dezenas de milhares de cidades, e mesmo problemas com milhões de cidades podem ser aproximados em 0,05% . O link indicado contém tentativas de resolver, por exemplo, 1.904.711 cidades da Terra a partir da base da Sociedade Geográfica Nacional.


Base da Sociedade Geográfica Nacional de 1.904.711 cidades

No momento, o recorde para a distância mínima para as cidades da Terra é de 7 515 772 107 km, foi estabelecido em 13 de março de 2018 usando o algoritmo heurístico LKH .

O problema clássico do vendedor em ciência da computação é usado como referência para algoritmos de otimização.

Ameba são organismos unicelulares que não têm idéia da complexidade da otimização combinatória. Eles não têm nada nem remotamente parecido com o sistema nervoso central, o que os torna candidatos menos adequados para resolver problemas de tal complexidade. No entanto, pesquisadores japoneses descobriram que um certo tipo de ameba pode ser usado para calcular soluções quase ótimas para o problema dos vendedores ambulantes em oito cidades.


Segundo um artigo científico , uma ameba chamada Physarum polycephalum , que já havia sido usada como computador biológico em vários outros experimentos, participou dos experimentos. Essa criatura é considerada especialmente útil na computação biológica porque pode expandir várias áreas do corpo em busca de uma maneira mais eficiente de obter comida, e odeia a luz.

Para transformar esse mecanismo natural de nutrição em um computador, pesquisadores japoneses colocaram a ameba em um prato especial com 64 canais, na direção em que o animal poderia esticar o corpo. A ameba está constantemente tentando expandir o corpo para cobrir a maior área possível da placa nutritiva. No entanto, cada canal na placa pode ser iluminado, o que faz com que a ameba saia desse canal de uma sensação de aversão à luz.

Para simular o problema do vendedor ambulante, cada um dos 64 canais na placa recebeu um código de cidade entre A e H, além de um número de 1 a 8, que indica a ordem das cidades (a ordem das cidades corresponde à ordem em que foram visitadas pelo vendedor).

Para programar a ameba, os pesquisadores usaram uma rede neural que incluía dados sobre a posição atual da ameba e a distância entre as cidades para iluminar canais específicos. A rede neural tinha maior probabilidade de iluminar cidades (canais) com maiores distâncias entre elas.

Quando o algoritmo e a ameba interagem, o último assume uma forma que representa soluções aproximadas para o problema do vendedor ambulante. O mais interessante é que a quantidade de tempo que a ameba leva para obter essas soluções quase ótimas cresce linearmente , embora o número de opções de solução aumente exponencialmente . Em um futuro próximo, os pesquisadores farão chips com dezenas de milhares de canais para que a ameba possa tentar resolver o problema do vendedor ambulante em centenas de cidades.

O artigo científico foi publicado em 19 de dezembro de 2018 na revista Royal Society Open Science (doi: 10.1098 / rsos.180396).