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
Pengiraan penyepuhlindapan baru-baru ini menarik perhatian kerana ia boleh menyelesaikan masalah pengoptimuman gabungan dengan cekap menggunakan model kaca putaran Ising. Penyepuhlindapan automata selular stokastik (SCA) ialah algoritma yang menjanjikan yang boleh merealisasikan kemas kini putaran pantas dengan menggunakan keupayaan pengkomputeran selarinya. Walau bagaimanapun, dalam SCA, kawalan kesan menyemat untuk menyekat kebarangkalian spin-flip adalah penting, menjadikan melarikan diri dari minima tempatan lebih sukar daripada algoritma kemas kini putaran bersiri, bergantung pada masalah. Makalah ini mencadangkan pendekatan baru yang dipanggil APC-SCA (Autonomous Pinning effect Control SCA), di mana kesan penyematan boleh dikawal secara autonomi dengan memfokuskan pada spin-flip individu. Keputusan penilaian menggunakan masalah pemotongan maksimum, N-queen dan jurujual perjalanan menunjukkan bahawa APC-SCA boleh memperoleh penyelesaian yang lebih baik daripada SCA asal yang menggunakan kawalan kesan penyematan yang dioptimumkan oleh carian grid. Terutamanya dalam menyelesaikan masalah jurujual perjalanan, kami mengesahkan bahawa jarak lawatan yang diperoleh oleh APC-SCA adalah sehingga 56.3% lebih dekat kepada yang paling terkenal berbanding pendekatan konvensional.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -