| 講演名 | 2011-03-10 カオス的低相互相関ダイナミクスを用いた組合せ最適化アルゴリズムの有効性とその解析 加藤 智洋, 福田 晋也, 長谷川 幹雄, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | カオスを組合せ最適化手法の有効性が,これまでに多くの結果から示されてきた.本稿では,理想的なカオス的非同期探索ダイナミクスを実現するLebesgue Spectrum Filter(LSF)を用いた手法について,その理論に基づいた数値実験解析を行なう.従来のカオスノイズを用いた最適化手法において,負の自己相関を持つカオスを用いることで,相互結合型ニューラルネットワークや非同期的探索アルゴリズムの性能を向上可能であることが分かっていた.非同期カオスCDMAの従来研究においては,そのような負の自己相関を持つ時系列を用いることにより,非同期な時系列間の相互相関が最小化可能であることが示されていた.近年,その低い相互相関を持つ時空間ダイナミクスによる探索が,探索アルゴリズムの性能向上に非常に有効であることが分かってきており,LSFを用いて負の自己相関を持たせるカオス的アルゴリズムの有効性も示されている.本稿では,非同期探索解法であるHopfield Neural Network及び2-opt法に対してLSFを適用したアルゴリズムについて,その性能の解析を行なう.その結果,負の自己相関を持たせることで非同期相互相関が最小化され,またそれによって高い解法能力を実現できていることを,数値実験結果によって示す. |
| 抄録(英) | Effectiveness of the chaotic dynamics for combinatorial optimization has been shown by many research results. In this paper, we analyze effectiveness of a new chaotic methods, which utilizes ideal spatio-temporal chaotic dynamics generated by Lebesgue Spectrum Filter (LSF). In the previous research on chaotic noise, it has been shown that the chaotic sequences with negative autocorrelation improve the performance of the asynchronously updated optimization algorithms, such as the Hopfield-Tank neural networks. Its effectiveness can be understood by theoretical research result on chaotic CDMA, which showed that the cross-correlation between the sequences with negative autocorrelation becomes low. Such spatio-temporal chaotic searching dynamics with such low cross-correlation has been shown effective to improve asynchronously updated combinatorial optimization algorithms. In this paper, as such asynchronously updated combinatorial optimization algorithms, we introduce the Hopfield-Tank neural network and the 2-opt method, and improve the performance of them by applying the LSF. We analyze their spatio-temporal searching dynamics by numerical experiments. Our simulation results clarifies that the negative autocorrelation makes lowest cross-correlation dynamics, which ideally improves the performance of the asynchronous combinatorial optimization algorithms. |
| キーワード(和) | 組合せ最適化問題 / カオス / ニューラルネットワーク / 非線形ダイナミクス / ルベーグスペクトラムフィルタ |
| キーワード(英) | Combinatorial Optimization Problems / Chaos / Neural Networks / Nonlinear Dynamics / Lebegue Spectrum Filter |
| 資料番号 | NLP2010-164 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2011/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | カオス的低相互相関ダイナミクスを用いた組合せ最適化アルゴリズムの有効性とその解析 |
| サブタイトル（和） | |
| タイトル（英） | Performance Analysis of Chaotic Optimization Algorithm with Low Cross Correlation Dynamics |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ最適化問題 / Combinatorial Optimization Problems |
| キーワード(2)（和/英） | カオス / Chaos |
| キーワード(3)（和/英） | ニューラルネットワーク / Neural Networks |
| キーワード(4)（和/英） | 非線形ダイナミクス / Nonlinear Dynamics |
| キーワード(5)（和/英） | ルベーグスペクトラムフィルタ / Lebegue Spectrum Filter |
| 第 1 著者 氏名（和/英） | 加藤 智洋 / Tomohiro KATO |
| 第 1 著者 所属（和/英） | 東京理科大学工学部 Department of Engineering, Tokyo University of science |
| 第 2 著者 氏名（和/英） | 福田 晋也 / Shinya HUKUDA |
| 第 2 著者 所属（和/英） | 東京理科大学工学部 Department of Engineering, Tokyo University of science |
| 第 3 著者 氏名（和/英） | 長谷川 幹雄 / Mikio HASEGAWA |
| 第 3 著者 所属（和/英） | 東京理科大学工学部 Department of Engineering, Tokyo University of science |
| 発表年月日 | 2011-03-10 |
| 資料番号 | NLP2010-164 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 465 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |