A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Fully-Parallel Annealing Algorithm with Autonomous Pinning Effect Control for Various Combinatorial Optimization Problems Um algoritmo de recozimento totalmente paralelo com controle de efeito de fixação autônomo para vários problemas de otimização combinatória

Daiki OKONOGI, Satoru JIMBO, Kota ANDO, Thiem Van CHU, Jaehoon YU, Masato MOTOMURA, Kazushi KAWAMURA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

A computação de recozimento atraiu recentemente a atenção, pois pode resolver com eficiência problemas de otimização combinatória usando um modelo de spin-glass de Ising. O recozimento de autômato celular estocástico (SCA) é um algoritmo promissor que pode realizar uma rápida atualização de spin utilizando sua capacidade de computação paralela. No entanto, no SCA, fixar o controle do efeito para suprimir a probabilidade de spin-flip é essencial, tornando o escape dos mínimos locais mais difícil do que os algoritmos de atualização de spin serial, dependendo do problema. Este artigo propõe uma nova abordagem chamada APC-SCA (Autonomous Pinning effect Control SCA), onde o efeito de pinning pode ser controlado de forma autônoma, concentrando-se no spin-flip individual. Os resultados da avaliação usando problemas de max-cut, N-queen e caixeiro viajante demonstram que o APC-SCA pode obter soluções melhores do que o SCA original que usa controle de efeito de fixação pré-otimizado por uma busca em grade. Especialmente na resolução dos problemas do caixeiro viajante, confirmamos que a distância do percurso obtida pelo APC-SCA está até 56.3% mais próxima da mais conhecida em comparação com a abordagem convencional.

Publicação
IEICE TRANSACTIONS on Information Vol.E106-D No.12 pp.1969-1978
Data de publicação
2023/12/01
Publicitada
2023/09/19
ISSN online
1745-1361
DOI
10.1587/transinf.2023PAP0003
Tipo de Manuscrito
Special Section PAPER (Special Section on Forefront Computing)
Categoria

autores

Daiki OKONOGI
  Tokyo Institute of Technology
Satoru JIMBO
  Tokyo Institute of Technology
Kota ANDO
  Hokkaido University
Thiem Van CHU
  Tokyo Institute of Technology
Jaehoon YU
  Tokyo Institute of Technology
Masato MOTOMURA
  Tokyo Institute of Technology
Kazushi KAWAMURA
  Tokyo Institute of Technology

Palavra-chave