グリッドグラフを対象とするOrder/Degree問題における多段階探索交叉を用いた遺伝的アルゴリズムの提案

• Item type: SIG Technical Reports(1)
• 公開日: 2024-12-09
• タイトル: グリッドグラフを対象とするOrder/Degree問題における多段階探索交叉を用いた遺伝的アルゴリズムの提案
• タイトル / 言語: en
• タイトル: Development of Genetic Algorithm with Multi-Step Search Crossover for Grid Graph in Order/Degree Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 自動最適化
• 資源タイプ / 資源タイプ識別子: 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 Problems（ODP）におけるグリッドグラフは所与の頂点数（Order），次数（Degree），および辺の最大長をもつ 2 次元格子上に頂点が配置された無向連結グラフにおいて，頂点間の平均距離を最小化する組合せ最適化問題である．遺伝的アルゴリズム（GA）を組合せ最適化問題に適用するにあたり，交叉オペレータの設計は重要な課題である．本研究では，ODP グリッドグラフに対して，局所探索性能に優れた交叉手法である dMSXF を導入した GA を提案する．提案手法の探索性能について，ODP のための国際的なコンペティションである Graph Golf で提供されているベンチマーク問題を用いて評価する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Grid graphs in Order/Degree Problems (ODP) are combinatorial optimization problems that minimize the average distance between vertices in an undirected connected graph whose vertices are arranged on a 2-dimensional grid with a given number of vertices (Order), degree (Degree), and maximum edge length. In applying genetic algorithms (GAs) to combinatorial optimization problems, the design of crossover operators is an important issue. In this study, we propose a GA for ODP grid graphs by introducing dMSXF, a crossover method with excellent local search performance. The search performance of the proposed method is evaluated using benchmark problems provided by Graph Golf, an international competition for ODP.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 研究報告システム・アーキテクチャ（ARC）; 巻 2024-ARC-259, 号 1, p. 1-6, 発行日 2024-12-09
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8574
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会