| 講演名 | 2020-05-15 正則グラフの平均頂点間距離最小化のための遺伝アルゴリズム 林 嶺司(岡山大), 右田 剛史(岡山大), 高橋 規一(岡山大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 与えられた頂点数と次数をもつ正則グラフの中で平均頂点間距離を最小にするものを求める問題に対し，遺伝アルゴリズムを用いた新たな近似解法を提案する．この問題は探索対象が正則グラフに限定されているため，既存の遺伝アルゴリズムを直接適用することはできない．そこで本報告では，グラフの正則性を保証する交叉や突然変異の方法を提案する．また，提案する近似解法の有効性を実験的に評価する． |
| 抄録(英) | For the problem of finding a regular graph with given order and degree that minimizes the average shortest path length, we propose a novel genetic-algorithm-based method for finding an approximate solution. Since the search space consists only of regular graphs, existing genetic algorithms cannot be applied directly. We propose in this report a new crossover technique and a new mutation technique that guarantee regularity of graphs. We also evaluate the effectiveness of the proposed method experimentally. |
| キーワード(和) | 正則グラフ / 平均頂点間距離 / 遺伝アルゴリズム / Havel-Hakimiの定理 |
| キーワード(英) | regular graph / average shortest path length / genetic algorithm / Havel-Hakimi theorem |
| 資料番号 | NLP2020-3 |
| 発行日 | 2020-05-08 (NLP) |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2020/5/15(から1日開催) |
| 開催地（和） | 山口大学（常盤キャンパス） |
| 開催地（英） | Yamaguchi University (Tokiwa campus) |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 黒川 弘章(東京工科大) |
| 委員長氏名（英） | Hiroaki Kurokawa(Tokyo Univ. of Tech.) |
| 副委員長氏名（和） | 夏目 季代久(九工大) |
| 副委員長氏名（英） | Kiyohisa Natsume(Kyushu Inst. of Tech.) |
| 幹事氏名（和） | 木村 貴幸(日本工大) / 立野 勝巳(九工大) |
| 幹事氏名（英） | Takayuki Kimura(Nippon Inst. of Tech.) / Katsumi Tateno(Kyushu Inst. of Tech.) |
| 幹事補佐氏名（和） | 島田 裕(埼玉大) / 佐村 俊和(山口大) |
| 幹事補佐氏名（英） | Yutaka Shimada(Saitama Univ.) / Toshikaza Samura(Yamaguchi Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Nonlinear Problems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 正則グラフの平均頂点間距離最小化のための遺伝アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A Genetic Algorithm for Minimizing Average Shortest Path Length of Regular Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 正則グラフ / regular graph |
| キーワード(2)（和/英） | 平均頂点間距離 / average shortest path length |
| キーワード(3)（和/英） | 遺伝アルゴリズム / genetic algorithm |
| キーワード(4)（和/英） | Havel-Hakimiの定理 / Havel-Hakimi theorem |
| 第 1 著者 氏名（和/英） | 林 嶺司 / Reiji Hayashi |
| 第 1 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 第 2 著者 氏名（和/英） | 右田 剛史 / Tsuyoshi Migita |
| 第 2 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 第 3 著者 氏名（和/英） | 高橋 規一 / Norikazu Takahashi |
| 第 3 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 発表年月日 | 2020-05-15 |
| 資料番号 | NLP2020-3 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | NLP-26 |
| ページ範囲 | pp.11-16(NLP), |
| ページ数 | 6 |
| 発行日 | 2020-05-08 (NLP) |