权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

使用混沌动力学开发离散优化技术-从基因组序列中提取基序-

基本信息

批准号：
08J06863
负责人：
松浦隆文
金额：
$ 0.77万
依托单位：
Saitama University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2008
资助国家：
日本
起止时间：
2008 至 2009
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08J06863/
关键词：
カオスダイナミクスバイオインフォマティクス組合せ最適化問題タブーサーチソフトタブーサーチ巡回セールスマン問題モチーフ抽出問題バイオインフォマティックス組み合わせ最適化問題サロゲート解析モチーフ柚出問題

项目摘要

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.ソフトタブーサーチ法の提案タブーサーチ法は,組合せ最適化問題に対して強力なメタヒューリスティック解法として認識されている.しかし,共通モチーフ抽出問題のようなパターン抽出問題においては,タブーサーチ法のタブー効果が強すぎるために,効果的な探索が行われないことも分かっている.そこで,タブーサーチ法のタブー効果を弱めたソフトタブーサーチ法を提案し,巡回セールス問題に対しソフトタブーサーチ法を用いた手法を開発した.ソフトタブーサーチ法は,一度択された解の再選択を,一定期間完全に禁止にするのではなく,困難にすることで局所解を回避する手法である.タブーサーチ法を用いた手法との性能比較を含む計算機シミュレーションを行なった結果,巡回セールスマン問題に対してもソフトタブーサーチ法はタブーサーチ法よりも優れた解探索性能を有することを確認した.

1. The application of Chaotic Motif Sampler method is improved, and the analysis of chaotic motifs is improved. Chaotic Motif Sampler method (hereinafter CMS method) is used to extract the possibility of high accuracy of chaotic motifs. In addition, the CMS method can not be adjusted. The CMS method automatically adjusts the value of the adjustment method. Specifically, the fire rate of each switch is adjusted according to the change in the value of the switch. The result is that the initial value of the problem is determined by the probability of extraction. 2. The solution of the problem is developed by the solution of the problem. The NP problem is represented by the combinatorial optimization problem. In the 20th year of Heisei, the bureau explored the implementation of the 2-opt method and the Or-opt method, and proposed the optimal solution to the problem. 2-opt'method and Or-opt method, and the same method is used to control it. (1)2-opt method and Or-opt method control each other independently,(2)2-opt method and Or-opt method control each other and develop each other.TSPLIB's selection problem is the result of computer system operation. This proposal is based on the assumption that the performance of the service method will be exceeded. 3. The proposal of the service method will be based on the assumption that the optimization problem will be solved by the powerful solution. The problem of extraction is difficult to solve, and the problem of extraction is difficult to solve. For example, if you want to make a proposal, you can make a proposal to make a proposal to make a proposal. The method of solving the problem once and for all is prohibited completely for a certain period of time, and the method of solving the problem is difficult. The method of searching for the best solution