WEKO3
アイテム
Graph Pointer Networkによる行列TSPおよびQAPの高速解法
https://ipsj.ixsq.nii.ac.jp/records/225443
https://ipsj.ixsq.nii.ac.jp/records/2254438f90bda7-b543-4a5f-a1cd-29e64fa2674a
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-ARC23252056.pdf (1.1 MB)
|
Copyright (c) 2023 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.
|
|
| ARC:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-03-16 | |||||||||||
| タイトル | ||||||||||||
| タイトル | Graph Pointer Networkによる行列TSPおよびQAPの高速解法 | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | 最適化 | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 京都大学大学院情報学研究科通信情報システム専攻 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学大学院情報学研究科通信情報システム専攻 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学大学院情報学研究科通信情報システム専攻 | ||||||||||||
| 著者名 |
飯田, 智子
× 飯田, 智子
× 安戸, 僚汰
× 高木, 直史
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 組合せ最適化問題のなかで巡回セールスマン問題 (TSP) および二次割り当て問題（QAP) のように解に順列を求める問題は実用性が高く，近年では機械学習を用いた手法の研究が盛んに行われている．特に，深層強化学習による解法では，現状一般に使われているヒューリスティックな手法より，大きいサイズの問題に対応でき，実行時間が短いため，実用面において優れている．そこで，本研究では，距離行列によって表現された TSP および QAP に取り組むための深層強化学習モデルを提案する. 本提案モデルは，座標表現の TSP のみを入力としていた Graph Pointer Network の拡張を行い，行列 TSP および QAP に対応可能にしたネットワークモデルである．提案ネットワークモデルを NVIDIA GPU で TSPlib および QAPlib のベンチマークを用いて検証を行い，従来の手法を上回る高速性およびスケーラビリティを確かめた． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN10096105 | |||||||||||
| 書誌情報 |
研究報告システム・アーキテクチャ（ARC） 巻 2023-ARC-252, 号 56, p. 1-6, 発行日 2023-03-16 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8574 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
