講演名 | 2008-03-28 カオスダイナミクスを用いた2-opt法とOr-opt法に対する巡回セールスマン問題の解法 松浦 隆文, 池口 徹, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | カオスダイナミクスを用いた,巡回セールスマン問題の解法が提案されている.この解法は,局所探索法である2-opt法の実行をカオスダイナミクスが制御することにより,局所最適解からの脱出を行なっている.その結果,効果的な探索が可能となり優れた性能を有することが示されている.本研究では,カオスサーチ法を拡張した新しい探索法を提案する.具体的には,新たに局所探索法としてOr-opt法を導入することにより,2-opt法と併せた2種類の局所探索法をカオスダイナミクスを用いて駆動する手法である.計算機シミュレーションを行なった結果,これまでに提案されているカオスサーチ法を凌駕する性能を有することを確認した. |
抄録(英) | To find the near optimum solutions of TSPs, a method introducing chaotic neurodynamics for solving TSPs has already been proposed. To avoid a local minimum, in this method, 2-opt algorithm for solving TSP is driven by chaotic neurodynamics. As a result, although 2-opt algorithm is the simplest local search, this method showed good performance. In this paper, we propose a new method to solve TSP introducing Or-opt algorithm, which is one of the powerful local search. In the proposed method, the 2-opt and Or-opt algorithms are driven by the chaotic neurodynamics. As a result, the proposed method shows higher performance than the previous chaotic search methods. |
キーワード(和) | 組み合わせ最適化問題 / 巡回セールスマン問題 / Or-opt法 / カオスニューラルネットワーク / カオスダイナミクス |
キーワード(英) | Combinatorial Optimization Problem / Traveling Salesman Problem (TSP) / Or-opt algorithm / Chaotic Neural Network / Chaotic Dynamics |
資料番号 | NLP2007-173 |
発行日 |
研究会情報 | |
研究会 | NLP |
---|---|
開催期間 | 2008/3/21(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Nonlinear Problems (NLP) |
---|---|
本文の言語 | ENG |
タイトル(和) | カオスダイナミクスを用いた2-opt法とOr-opt法に対する巡回セールスマン問題の解法 |
サブタイトル(和) | |
タイトル(英) | A New Chaotic Algorithm for Solving Traveling Salesman Problems by Using 2-opt and Or-opt Algorithms |
サブタイトル(和) | |
キーワード(1)(和/英) | 組み合わせ最適化問題 / Combinatorial Optimization Problem |
キーワード(2)(和/英) | 巡回セールスマン問題 / Traveling Salesman Problem (TSP) |
キーワード(3)(和/英) | Or-opt法 / Or-opt algorithm |
キーワード(4)(和/英) | カオスニューラルネットワーク / Chaotic Neural Network |
キーワード(5)(和/英) | カオスダイナミクス / Chaotic Dynamics |
第 1 著者 氏名(和/英) | 松浦 隆文 / Takafumi MATSUURA |
第 1 著者 所属(和/英) | 埼玉大学大学院理工学研究科理工学専攻 Graduate School of Science and Engineering, Saitama University |
第 2 著者 氏名(和/英) | 池口 徹 / Tohru IKEGUCHI |
第 2 著者 所属(和/英) | 埼玉大学大学院理工学研究科研究部数理電子情報部門 Graduate School of Science and Engineering, Saitama University |
発表年月日 | 2008-03-28 |
資料番号 | NLP2007-173 |
巻番号(vol) | vol.107 |
号番号(no) | 561 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |