Research on Annealing Processors for Large-Scale Combinatorial Optimization Problems

• 資料種別: 博士論文
• タイトル: Research on Annealing Processors for Large-Scale Combinatorial Optimization Problems
• 著者・編者: 山本, 佳生
• 著者標目: 山本, 佳生
• 出版事項: Hokkaido University
• 出版年月日等: 2020-03-25
• 出版年（W3CDTF）: 2020-03-25
• 並列タイトル等: 大規模組合せ最適化問題のためのアニーリングプロセッサに関する研究
• 寄与者: 浅井, 哲也; 末岡, 和久; 葛西, 誠也; 池辺, 将之
• 授与機関名: 北海道大学
• 授与年月日: 2020-03-25
• 授与年月日（W3CDTF）: 2020-03-25
• 報告番号: 甲第14133号
• 学位: 博士(工学)
• 博論授与番号: 甲第14133号
• 本文の言語コード: eng
• NDC: 500
• 対象利用者: 一般
• 一般注記: This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem.In order to realize a smart society, optimization of people and thingssuch as transportation networks, power networks, human resource allocationand routes is indispensable. Many of these problems are called combinatorial optimization problems and are known as very important problems in modern society. However, it is known that the combinatorial optimization problem is NP-hard and it is difficult to efficiently solve it with a conventional Neumann computer.In recent years, the miniaturization of the process of manufacturing computer chips is approaching the physical limit. Therefore, especially in the solution by the full search, the improvement in speed due to the calculation speed of the computer cannot be expected. From such a background, dedicated hardware capable of solving a combination optimization problem at high speed and with low power consumption has been attracting attention.The annealing processor is a general-purpose combination optimization solver that utilizes the property that the ground state of the optimization problem expressed by using the Ising model and the optimal solution of the combination optimization problem match. The Ising model is a ferromagnetic model in statistical physics expressed by spins having an upward and downward state, spin-spin interactions occurring between the spins, and an external magnetic field acting on each spin. The Ising model can express a combinatorial optimization problem by expressing a control target and a cost using these parameters. The annealing processor updates the spin state while slowly lowering the temperature parameters based on simulated annealing,which is an optimization method learned from natural phenomena generally called annealing. Eventually, the spin will reach the ground state with a high probability and obtain the optimal solution.Annealing processors are classified into two types, the nearest neighbor type and the fully connected type, depending on the shape of the Ising model simulated on the hardware. In the nearest neighbor type, the coupling between spins is limited to only between adjacent spins, and in the full coupling type, coupling exists between arbitrary spins. The nearest neighbor type realizes high parallel processing by reducing the data spin required by simulated annealing by reducing the proximity spin. In addition, since data transfer is limited to adjacent spins, the scalability is high. However, since the spin-to-spin interaction is sparse, there is a problem that the class of combinatorial optimization problems that can be dealt with is limited, or that the problem requires deformation processing to match the Ising model of hardware. The fully connected type can solve any class of problems as long as the number of spins permits, however it requires connections between arbitrary spins.Therefore, scalability is low. Because there there is a dependency on all spins,the number of spins that can be updated at one time is always limited to only one regardless of the total number of spins. Therefore, it takes time to converge to the ground state.In this research, we propose a method of increasing the number of spins for this annealing processor by using (1) a spatially-expanded time-division processing mechanism architecture based on a loosely-coupled type, (2) An algorithm for applying a fully coupled Ising network to a more complex Ising network using the nearest neighbor Ising network and an annealing method that can be updated in parallel, (3)We conducted a study on the architecture of a fully coupled annealing processor for parallel updating annealing.As described above, the research described in this paper contributes to the improvement of the efficiency of the annealing processor for solving the large-scale combinatorial optimization problem from both the fundamental algorithm and the hardware architecture. I hope that this research will solve the combinatorial optimization problem that is expected to increase in demand in the future and contribute to the development of human society.; (主査) 教授 浅井 哲也, 教授 末岡 和久, 教授 葛西 誠也（量子集積エレクトロニクス研究センター）, 教授 池辺 将之（量子集積エレクトロニクス研究センター）; 情報科学研究科（情報エレクトロニクス専攻）
• DOI: 10.14943/doctoral.k14133; https://doi.org/10.14943/doctoral.k14133
• 国立国会図書館永続的識別子: info:ndljp/pid/11551878; https://dl.ndl.go.jp/pid/11551878
• コレクション（共通）: 障害者向け資料
• コレクション（障害者向け資料：レベル1）: テキストデータ
• コレクション（個別）: 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• 収集根拠: 博士論文（自動収集）
• 受理日（W3CDTF）: 2020-10-06T21:18:06+09:00
• 作成日（W3CDTF）: 2020-03
• 記録形式（IMT）: PDF
• オンライン閲覧公開範囲: 国立国会図書館内限定公開
• デジタル化資料送信: 図書館・個人送信対象外
• 遠隔複写可否（NDL）: 可
• 掲載誌（URI）: http://dx.doi.org/10.14943/doctoral.k14133; http://hdl.handle.net/2115/79228
• 参照（URI）: http://hdl.handle.net/2115/78520
• 連携機関・データベース: 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

• 要約等: This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem. In order to realize a smart socie...