WEKO3
アイテム
改良型敵対的生成ネットワークを用いた巡回セールスマン問題の解法
https://ipsj.ixsq.nii.ac.jp/records/231462
https://ipsj.ixsq.nii.ac.jp/records/231462323786f2-df2c-4d23-b2c6-5daa0f4de1f0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MPS23146008.pdf (1.9 MB)
2025年12月4日からダウンロード可能です。
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, MPS:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-12-04 | |||||||||
| タイトル | ||||||||||
| タイトル | 改良型敵対的生成ネットワークを用いた巡回セールスマン問題の解法 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Improved Generative Adversarial Networks for Solving the Traveling Salesman Problem | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 関西大学大学院理工学研究科 | ||||||||||
| 著者所属 | ||||||||||
| 関西大学システム理工学部 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Science and Engineering, Kansai University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Faculty of Engineering Science, Kansai University | ||||||||||
| 著者名 |
李, 鵬龍
× 李, 鵬龍
× 榎原, 博之
|
|||||||||
| 著者名(英) |
Penglong, Li
× Penglong, Li
× Hiroyuki, Ebara
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 本研究では，代表的な組合せ最適化問題の一つである巡回セールスマン問題 (TSP) に注目し，深層学習を適用した解法を提案する．本手法では，TSP の頂点と最適経路で構成されたペア画像を，敵対的生成ネットワーク (GAN) を用いてそれらの対応関係を学習することで，最適経路画像を計算し，生成する．そして生成された画像から得られる各エッジの評価値を求め，それを使って TSP の近似解を計算する．さらに，GAN にアテンション機構を導入することで，生成画像の高精度化を図る．また，従来手法より高解像度な画像を生成して，より大規模な問題例に対しての有効性を検証する． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | In this paper, we focus on the travelling salesman problem (TSP), one of the typical Combinatorial optimization problems, and propose a solution method that applies deep learning. In this method, pair images consisting of vertices and optimal paths of TSP are computed and generated by learning their correspondence using a generative adversarial network (GAN). The evaluation value of each edge from the generated images is then obtained and used to compute an approximate solution for the TSP. Furthermore, by introducing an attention mechanism into the GAN, the generated images are made more accurate. In addition, we will generate higher resolution images than the conventional method to verify the effectiveness of the method for larger problem instances. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN10505667 | |||||||||
| 書誌情報 |
研究報告数理モデル化と問題解決（MPS） 巻 2023-MPS-146, 号 8, p. 1-6, 発行日 2023-12-04 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8833 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
