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 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.
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
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Daiki OKONOGI, Satoru JIMBO, Kota ANDO, Thiem Van CHU, Jaehoon YU, Masato MOTOMURA, Kazushi KAWAMURA, "A Fully-Parallel Annealing Algorithm with Autonomous Pinning Effect Control for Various Combinatorial Optimization Problems" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 12, pp. 1969-1978, December 2023, doi: 10.1587/transinf.2023PAP0003.
Abstract: Annealing computation has recently attracted attention as it can efficiently solve combinatorial optimization problems using an Ising spin-glass model. Stochastic cellular automata annealing (SCA) is a promising algorithm that can realize fast spin-update by utilizing its parallel computing capability. However, in SCA, pinning effect control to suppress the spin-flip probability is essential, making escaping from local minima more difficult than serial spin-update algorithms, depending on the problem. This paper proposes a novel approach called APC-SCA (Autonomous Pinning effect Control SCA), where the pinning effect can be controlled autonomously by focusing on individual spin-flip. The evaluation results using max-cut, N-queen, and traveling salesman problems demonstrate that APC-SCA can obtain better solutions than the original SCA that uses pinning effect control pre-optimized by a grid search. Especially in solving traveling salesman problems, we confirm that the tour distance obtained by APC-SCA is up to 56.3% closer to the best-known compared to the conventional approach.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023PAP0003/_p
Copiar
@ARTICLE{e106-d_12_1969,
author={Daiki OKONOGI, Satoru JIMBO, Kota ANDO, Thiem Van CHU, Jaehoon YU, Masato MOTOMURA, Kazushi KAWAMURA, },
journal={IEICE TRANSACTIONS on Information},
title={A Fully-Parallel Annealing Algorithm with Autonomous Pinning Effect Control for Various Combinatorial Optimization Problems},
year={2023},
volume={E106-D},
number={12},
pages={1969-1978},
abstract={Annealing computation has recently attracted attention as it can efficiently solve combinatorial optimization problems using an Ising spin-glass model. Stochastic cellular automata annealing (SCA) is a promising algorithm that can realize fast spin-update by utilizing its parallel computing capability. However, in SCA, pinning effect control to suppress the spin-flip probability is essential, making escaping from local minima more difficult than serial spin-update algorithms, depending on the problem. This paper proposes a novel approach called APC-SCA (Autonomous Pinning effect Control SCA), where the pinning effect can be controlled autonomously by focusing on individual spin-flip. The evaluation results using max-cut, N-queen, and traveling salesman problems demonstrate that APC-SCA can obtain better solutions than the original SCA that uses pinning effect control pre-optimized by a grid search. Especially in solving traveling salesman problems, we confirm that the tour distance obtained by APC-SCA is up to 56.3% closer to the best-known compared to the conventional approach.},
keywords={},
doi={10.1587/transinf.2023PAP0003},
ISSN={1745-1361},
month={December},}
Copiar
TY - JOUR
TI - A Fully-Parallel Annealing Algorithm with Autonomous Pinning Effect Control for Various Combinatorial Optimization Problems
T2 - IEICE TRANSACTIONS on Information
SP - 1969
EP - 1978
AU - Daiki OKONOGI
AU - Satoru JIMBO
AU - Kota ANDO
AU - Thiem Van CHU
AU - Jaehoon YU
AU - Masato MOTOMURA
AU - Kazushi KAWAMURA
PY - 2023
DO - 10.1587/transinf.2023PAP0003
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2023
AB - Annealing computation has recently attracted attention as it can efficiently solve combinatorial optimization problems using an Ising spin-glass model. Stochastic cellular automata annealing (SCA) is a promising algorithm that can realize fast spin-update by utilizing its parallel computing capability. However, in SCA, pinning effect control to suppress the spin-flip probability is essential, making escaping from local minima more difficult than serial spin-update algorithms, depending on the problem. This paper proposes a novel approach called APC-SCA (Autonomous Pinning effect Control SCA), where the pinning effect can be controlled autonomously by focusing on individual spin-flip. The evaluation results using max-cut, N-queen, and traveling salesman problems demonstrate that APC-SCA can obtain better solutions than the original SCA that uses pinning effect control pre-optimized by a grid search. Especially in solving traveling salesman problems, we confirm that the tour distance obtained by APC-SCA is up to 56.3% closer to the best-known compared to the conventional approach.
ER -