| 講演名 | 1996/12/14 バイナリニューロンを用いたグラフ分割解法の研究 玉置 康裕, 船曳 信生, 西川 清史, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | グラフ分割問題とは,各グループに属する頂点重みの総和を上限以下として,グループ間の辺重みの総和が最小となる各頂点の分割を求めるNP困難問題である.本論文では,頂点及び辺に重みのあるグラフの2分割問題に対して,バイナリニューロンを用いたニューラルネットワーク解法を提案する.本ニューラルネットワークでは,重みなしグラフ及び重み付きグラフの双方に適用可能なエネルギー関数を定義している.また,解精度向上のため, Shaking項を動作方程式に導入している.本解法の解探索能力の評価のため, KernighanとLinの提案したKL法, FiducciaとMattheysesの提案したFM法と共に,ランダムグラフを用いたシミュレーションを行う.シミュレーションの結果,頂点に重みをランダムに与えたグラフでは,本解法で得られた解が最も優れていることを示す. |
| 抄録(英) | In this paper, we present a neural network algorithm using binary neurons for a graph two-partitioning problem. For a given graph G(V, E), the goal of this NP-hard problem is to find a partition of vertices in V into two groups such that not only the sum of vertex-weights in each group is within the upper bound, but also the sum of edge-weights between groups is minimized. We formulate a new energy function and introduce a shaking term in the motion equation in order to improve the solution quality. We compare the performance of the neural network with two existing typical algorithms through simulations in unweighted and weighted random graphs. The results show that the neural network is comparable with existing algorithms for vertex-unweighted graphs in terms of the solution quality, and that it is much better for vertex-weighted graphs. |
| キーワード(和) | グラフ分割問題 / NP困難問題 / ニューラルネットワーク / shaking項 / 動作方程式 / KL法 / FM法 |
| キーワード(英) | neural network / graph two-partitioning problem / NP hard problem / shaking term |
| 資料番号 | NC96-64 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 1996/12/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | バイナリニューロンを用いたグラフ分割解法の研究 |
| サブタイトル（和） | |
| タイトル（英） | A Binary Neural Network Algorithm for the Graph Partitioning Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ分割問題 / neural network |
| キーワード(2)（和/英） | NP困難問題 / graph two-partitioning problem |
| キーワード(3)（和/英） | ニューラルネットワーク / NP hard problem |
| キーワード(4)（和/英） | shaking項 / shaking term |
| キーワード(5)（和/英） | 動作方程式 |
| キーワード(6)（和/英） | KL法 |
| キーワード(7)（和/英） | FM法 |
| 第 1 著者 氏名（和/英） | 玉置 康裕 / Yasuhiro Tamaki |
| 第 1 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| 第 2 著者 氏名（和/英） | 船曳 信生 / Nobuo Funabiki |
| 第 2 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| 第 3 著者 氏名（和/英） | 西川 清史 / Seishi Nishikawa |
| 第 3 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 1996/12/14 |
| 資料番号 | NC96-64 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 430 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |