カオスダイナミクスを用いた離散最適化技法の開発 -ゲノム配列からのモチーフ抽出-

点击翻译按钮获取中文摘要

1.Chaotic Motif Sampler法の実用化に向けた改良・ダイナミクスの解析カオスダイナミクスを用いたChaotic Motif Sampler法(以下,CMS法)はモチーフ配列を高い確率で抽出可能なことが示されている.しかし,効果的にモチーフ抽出を行うには,モチーフ抽出を行う配列データ毎にCMS法のパラメータ値調節が不可欠である.そこで,CMS法のパラメータ値を自動的に調節するパラメータ値調整法の開発を行った.具体的には,各ニューロンの発火率,モチーフ候補が更新される割合を用いてパラメータ値の調整を行った.その結果,初期パラメータ値がどのような場合においても,モチーフ抽出が可能なことを確認した.2.カオスダイナミクスを用いた巡回セールスマン問題の解法を開発巡回セールスマン問題は,NP困難なクラスに属する代表的な組合せ最適化問題である.平成20年度に,局所探索注である2-opt法とOr-opt法の実行をカオスダイナミクスで制御することにより,局所最適解からの脱出を行う手法を提案した.しかし,この手法では異なる局所探索法である2-opt'法とOr-opt法を,同一のカオスダイナミクスを用いて制御している.そこで,(1)2-opt法とOr-opt法を制御するダイナミクスが独立な手法,(2)2-opt法とOr-opt法を制御するダイナミクスが相互に影響を及ぼす手法を開発した.TSPLIBのペンチマーク問題に対して計算機シミュレーションを行った結果,これまでに提案されているカオスサーチ法を凌駕する性能を有することを確認した.3.ソフトタブーサーチ法の提案タブーサーチ法は,組合せ最適化問題に対して強力なメタヒューリスティック解法として認識されている.しかし,共通モチーフ抽出問題のようなパターン抽出問題においては,タブーサーチ法のタブー効果が強すぎるために,効果的な探索が行われないことも分かっている.そこで,タブーサーチ法のタブー効果を弱めたソフトタブーサーチ法を提案し,巡回セールス問題に対しソフトタブーサーチ法を用いた手法を開発した.ソフトタブーサーチ法は,一度択された解の再選択を,一定期間完全に禁止にするのではなく,困難にすることで局所解を回避する手法である.タブーサーチ法を用いた手法との性能比較を含む計算機シミュレーションを行なった結果,巡回セールスマン問題に対してもソフトタブーサーチ法はタブーサーチ法よりも優れた解探索性能を有することを確認した.