| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-05-09 15:30 遺伝的アルゴリズムとドロネー三角形分割に基づくシュタイナー木問題の解法 ○張 立萍・右田剛史・高橋規一（岡山大）  NLP2024-6 |
|
| 抄録 | （和） | 本報告では，ユークリッド平面上のシュタイナー木問題を解くための，遺伝的アルゴリズムとドロネー三角形分割を組み合わせた方法を提案する．提案する方法は，まず，与えられたすべての端点に対してドロネー三角形分割を行う．次に，得られた各三角形の重心とそれを中心とする円周上に非端点を生成する．そして，著者らが以前に提案した遺伝的アルゴリズムに基づく方法を利用して，すべての端点といくつかの非端点を結び，かつ辺の長さの総和が短い木を構築する．最後に，構築した木に含まれる非端点の位置をWeiszfeldの方法を用いて最適化する．いくつかのベンチマーク問題を用いた実験により提案手法の性能を評価する． |
| （英） | In this report, we propose an approach based on the genetic algorithm and the Delaunay triangulation for solving the Euclidean Steiner tree problem. This approach first performs the Delaunay triangulation for all the given terminal points. It then generates non-terminal points at the centroid of each triangle obtained and on a circle which takes the centroid as the center. It next finds a tree that connects all terminal points and some of the non-terminal points, and has a short total length of edges, utilizing a genetic algorithm-based method developed by the authors. It finally optimizes the location of the non-terminal points in the tree using Weiszfeld's method. We evaluate the performance of the proposed approach through experiments using some benchmark problems. | |
| キーワード | （和） | シュタイナー木問題 / ユークリッド平面 / 遺伝的アルゴリズム / ドロネー三角形分割 / / / / |
| （英） | Steiner tree problem / Euclidean plane / genetic algorithm / Delaunay triangulation / / / / | |
| 文献情報 | 信学技報, vol. 124, no. 13, NLP2024-6, pp. 25-30, 2024年5月. | |
| 資料番号 | NLP2024-6 | |
| 発行日 | 2024-05-02 (NLP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NLP2024-6 |
|
| 研究会情報 | |
| 研究会 | NLP |
| 開催期間 | 2024-05-09 - 2024-05-10 |
| 開催地（和） | 香川県社会福祉総合センター |
| 開催地（英） | Kagawa Prefecture Social Welfare Center |
| テーマ（和） | NLP，一般 |
| テーマ（英） | Nonlinear Problems, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NLP |
| 会議コード | 2024-05-NLP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 遺伝的アルゴリズムとドロネー三角形分割に基づくシュタイナー木問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | An Euclidean Steiner Tree Problem Solver based on Genetic Algorithm and Delaunay Triangulation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | シュタイナー木問題 / Steiner tree problem |
| キーワード(2)（和/英） | ユークリッド平面 / Euclidean plane |
| キーワード(3)（和/英） | 遺伝的アルゴリズム / genetic algorithm |
| キーワード(4)（和/英） | ドロネー三角形分割 / Delaunay triangulation |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 張 立萍 / Liping Zhang / チョウ リツヘイ |
| 第1著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 右田 剛史 / Tsuyoshi Migita / ミギタ ツヨシ |
| 第2著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 高橋 規一 / Norikazu Takahashi / タカハシ ノリカズ |
| 第3著者 所属（和/英） | 岡山大学 (略称： 岡山大) Okayama University (略称： Okayama Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-05-09 15:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NLP |
| 資料番号 | NLP2024-6 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.13 |
| ページ範囲 | pp.25-30 |
| ページ数 | 6 |
| 発行日 | 2024-05-02 (NLP) |
[研究会発表申込システムのトップページに戻る]