遺伝的アルゴリズムによるOrder/Degree問題におけるグリッドグラフの一解法

• Item type: SIG Technical Reports(1)
• 公開日: 2023-11-28
• タイトル: 遺伝的アルゴリズムによるOrder/Degree問題におけるグリッドグラフの一解法
• タイトル / 言語: en
• タイトル: Development of Genetic Algorithm for Grid Graph in Order/Degree Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: AIとグラフ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 関西大学システム理工学部
• 著者所属: 関西大学システム理工学部
• 著者所属: 理化学研究所計算科学研究センター
• 著者所属: 理化学研究所計算科学研究センター
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Kansai University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Kansai University
• 著者所属(英): en
• 著者所属(英): RIKEN Center for Computational Science
• 著者所属(英): en
• 著者所属(英): RIKEN Center for Computational Science
• 著者名: 木村, 弘登; 花田, 良子; 中尾, 昌広; 山本, 啓二
• 著者名(英): Hiroto, Kimura; Yoshiko, Hanada; Masahiro, Nakao; Keiji, Yamamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Order/Degree 問題の一種であるグリッドグラフにおいて遺伝的アルゴリズムによる解法を提案する．グリッドグラフは，頂点数（Order）と最大次数（Degree），および辺の最大長が与えられたもと，2 次元格子の節点上に配置された頂点からなる無向の連結グラフの中で，最小の平均頂点間距離となるものを求める最適化問題である． ODP に関する国際コンペティション GraphGolf で出題された例題を用いて，提案手法の解探索性能を検証する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a genetic algorithm for solving grid graph that is a kind of Order/Degree problems (ODP). Grid graph is an optimization problem to find the minimum average distance between vertices in an undirected connected graph consisting of vertices placed on nodes of a two-dimensional grid, given the number of vertices (Order), the maximum degree (Degree), and the maximum length of edges. We verify the performance of the proposed method using instances presented by Graph Golf, an international ODP competition.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 研究報告システム・アーキテクチャ（ARC）; 巻 2023-ARC-255, 号 22, p. 1-5, 発行日 2023-11-28
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8574
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会