| 講演名 | 2009-05-15 ダイナミカルノイズを付加したカオスニューラルネットワークを用いた二次割当問題の解法 鈴木 貴行, 本橋 瞬, 松浦 隆文, 池口 徹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 二次割当問題(QAP)は,NP困難な組み合わせ最適化問題の中でも特に難しい問題とされている.QAPを解くために,より良い解を見つけることのできる様々な近似解法が開発されている.近似解法の一つとして,Hopfield-Tankニューラルネットワークを用いた解法が提案されている.この解法は,ニューロダイナミクスの働きによって最急降下的に解を探索する.しかし,この解法は局所最適解に陥ってしまうため,良好な解を得ることは困難である.この問題を克服するために,カオスダイナミクスを用いた手法が提案され,高い性能を有することが示されている.一方,局所最適解を避けるための他の別の試みとして,ダイナミカルノイズを用いる手法が提案されている.そこで本稿では,カオスダイナミクスとダイナミカルノイズの2つの局所最適解脱出戦略を融合した新たな解探索法を提案する.この手法は,微小なダイナミカルノイズを印加したとき,従来法よりも高い解探索性能を示す.更に,ダイナミカルノイズが印加されたときのカオスニューラルネットワークのカオス性と解探索性能の関係を調べるために,リアプノフスペクトラムを計算した. |
| 抄録(英) | The quadratic assignment problem (QAP) is one of the most difficult NP-hard combinatorial optimization problems. To solve the QAP, various approximate algorithms for finding near optimal solutions have already been proposed. Among them, the Hopfield-Tank neural network approach is attractive from a viewpoint of an application of neural dynamics to combinatorial optimization. However, this approach is not so effective because of the local minimum problem. To solve this problem, a method which uses chaotic dynamics has already been proposed. As a result, this method shows good performance. On the other hand, to avoid undesirable local minima, dynamical noise is often used. Then, we proposed a method which uses two approaches for avoiding local minima-chaotic dynamics and dynamical noise. As a result, when a small amount of dynamical noise is added, the proposed method shows higher performance. In this paper, we investigate the reason why chaotic neural network (CNN) with additive dynamical noise searches good solutions. Then, to quantify chaotic dynamics, we calculate Lyapunov spectra of CNN with dynamical noise, and investigate the relation between the solving performance and Lyapunov exponents. |
| キーワード(和) | 二次割当問題 / カオスニューラルネットワーク / ダイナミカルノイズ |
| キーワード(英) | Quadratic Assignment Problem / Chaotic Neural Network / Dynamical noise |
| 資料番号 | NLP2009-11 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2009/5/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ダイナミカルノイズを付加したカオスニューラルネットワークを用いた二次割当問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving Quadratic Assignment Problems by Chaotic Neural Network with Dynamical Noise |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 二次割当問題 / Quadratic Assignment Problem |
| キーワード(2)（和/英） | カオスニューラルネットワーク / Chaotic Neural Network |
| キーワード(3)（和/英） | ダイナミカルノイズ / Dynamical noise |
| 第 1 著者 氏名（和/英） | 鈴木 貴行 / Takayuki SUZUKI |
| 第 1 著者 所属（和/英） | 埼玉大学大学院理工学研究科 Graduate School of Science and Engineering, Saitama University |
| 第 2 著者 氏名（和/英） | 本橋 瞬 / Shun MOTOHASHI |
| 第 2 著者 所属（和/英） | 埼玉大学大学院理工学研究科 Graduate School of Science and Engineering, Saitama University |
| 第 3 著者 氏名（和/英） | 松浦 隆文 / Takafumi MATSUURA |
| 第 3 著者 所属（和/英） | 埼玉大学大学院理工学研究科 Graduate School of Science and Engineering, Saitama University |
| 第 4 著者 氏名（和/英） | 池口 徹 / Tohru IKEGUCHI |
| 第 4 著者 所属（和/英） | 埼玉大学大学院理工学研究科 Graduate School of Science and Engineering, Saitama University |
| 発表年月日 | 2009-05-15 |
| 資料番号 | NLP2009-11 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 30 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |