IEICE TRANSACTIONS on Information
A Fully-Parallel Annealing Algorithm with Autonomous Pinning Effect Control for Various Combinatorial Optimization Problems
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E106-D No.12 pp.1969-1978
- Publication Date
- 2023/12/01
- Publicized
- 2023/09/19
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2023PAP0003
- Type of Manuscript
- Special Section PAPER (Special Section on Forefront Computing)
- Category
Authors
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
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
