| 講演名 | 2011-06-30 負の自己相関を持つカオス的ダイナミクスを用いたヒューリスティック解法の性能改善 長谷川 幹雄, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 組合せ最適化問題の非同期な探索解法に対して,負の自己相関を持たせることで有効な探索が行えるカオス的最適化手法が提案されている.非同期カオスCDMAの従来研究において,遅れ1で負の値をとり振動減衰する自己相関をもつ系列を用いることで,系列間の非同期な相互相関が最小化されることが示されている.本稿で用いる最適化手法は,非同期な高次元探索アルゴリズムにおける各解更新のダイナミクスに,負の振動減衰自己相関を持たせることで,探索空間内での各次元間に対応する解更新間の相互相関を最小化し,それによって理想的に分散的な解空間内探索を実現している手法である.本稿では,このような時空間探索ダイナミクスを,大規模な問題に適用可能なヒューリスティック解法に持たせた探索手法の有効性を検討する.ヒューリスティック解法としては,巡回セールスマン問題に2-opt法を,二次割り当て問題に2-exchangeをそれぞれ用い,Lebesgue Spectrum Filterを適用することでそれらのアルゴリズムに負の自己相関を持たせる.巡回セールスマン問題においては2000都市以上,二次割り当て問題おいてはサイズ150の大規模な問題に対しても,解更新に負の振動減衰自己相関を持たせることで性能が向上されることを,数値実験結果によって示す. |
| 抄録(英) | Effectiveness of the chaotic dynamics with negative autocorrelation for asynchronous combinatorial optimization algorithms has been shown by recent researches. In asynchronous chaotic CDMA, such time series whose autocorrelation takes negative value at lag 1 and decays with oscillation make asynchronous cross-correlation among the sequences lowest. The optimization methods used in this paper is realized by introducing the negative autocorrelation with damped oscillation to each local search operation of the searching dynamics, that minimizes cross-correlation among the operations, and it has ideally distributive searching ability in the searching space. This paper applies such ideal spatiotemporal dynamics to the heuristic algorithms which is applicable to large scale problems, and evaluates the effectiveness of this combinatorial optimization approach. As the heuristic algorithms, the 2-opt and the 2-exchange methods are introduced for the traveling salesman problem (TSP) and the quadratic assignment problem (QAP), respectively. To realize effective negative auto correlation, the Lebesgue spectrum filter is applied to those algorithms. By computer simulations, effectiveness of this approach has been clarified also for large problems, whose size are larger than 2000 and 150, for the TSP and the QAP, respectively. |
| キーワード(和) | 組合せ最適化 / カオス / ニューラルネットワーク / 非線形ダイナミクス / ルベーグスペクトラムフィルタ |
| キーワード(英) | Combinatorial Optimization / Chaos / Neural Networks / Nonlinear Dynamics / Lebesgue Spectrum Filter |
| 資料番号 | NLP2011-35 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2011/6/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 負の自己相関を持つカオス的ダイナミクスを用いたヒューリスティック解法の性能改善 |
| サブタイトル（和） | |
| タイトル（英） | Improving Performance of Heuristic Methods using Chaotic Dynamics with Negative Autocorrelation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ最適化 / Combinatorial Optimization |
| キーワード(2)（和/英） | カオス / Chaos |
| キーワード(3)（和/英） | ニューラルネットワーク / Neural Networks |
| キーワード(4)（和/英） | 非線形ダイナミクス / Nonlinear Dynamics |
| キーワード(5)（和/英） | ルベーグスペクトラムフィルタ / Lebesgue Spectrum Filter |
| 第 1 著者 氏名（和/英） | 長谷川 幹雄 / Mikio HASEGAWA |
| 第 1 著者 所属（和/英） | 東京理科大学工学部第一部電気工学科 Department of Electrical Engineering, Tokyo University of Science |
| 発表年月日 | 2011-06-30 |
| 資料番号 | NLP2011-35 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 106 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |