遺伝子解析に基づく遺伝的アルゴリズムの開発とシステム設計への応用

基于基因分析的遗传算法的开发及其在系统设计中的应用

基本信息

批准号：
15700175
负责人：
棟朝雅晴
金额：
$ 2.11万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

本研究においては、これまでに提案されたリンケージ同定に基づく遺伝的アルゴリズムをさらに発展させ、より一般的な枠組みとして、遺伝子解析に基づく遺伝的アルゴリズムを開発することを目的とし、さらにそのシステム設計問題への応用をはかっている。バイオインフォマティクスの分野では、遺伝子解析に関する手法が数多く提案されているが、それらを参考にリンケージの同定、ビルディングブロックの検出、交叉手法の改良などを行い、より高性能で高い信頼性を有する遺伝的アルゴリズムを開発する。本年度においては、分布推定手法の改良を図るとともに、効率的な並列化手法を開発することで、大規模な問題への対応を図った。具体的には、割り当て関数による重み付けを行うことで精度を向上させ分布推定に要する計算コストを削減するための手法を開発するとともに、ベイジアンネットワークに基づく確率モデル構築を行う分布推定アルゴリズムにおいて、ネットワーク構築の効果的な並列化手法を開発した。さらには、リンケージ同定と分布推定アルゴリズムの双方の利点を組み合わせたアルゴリズムD^5の開発を行い、問題規模の増大に対するスケーラビリティに優れた手法を開発した。さらに、D^5の実数値問題への適用についても議論するとともに、その性能について評価を行った。提案手法の適用例として、特に、蛋白質の構造エネルギー最小化問題へ、並列化した分布推定による探索手法を適用することで、本研究で開発した手法の有効性を検証している。

这项研究旨在基于迄今为止提出的连锁识别的遗传算法进一步开发遗传算法，并基于遗传分析作为更一般的框架开发遗传算法，并将它们进一步应用于系统设计问题。在生物信息学领域，已经提出了许多方法进行遗传分析，并使用这些方法作为参考，我们将使用链接识别，构建块检测和交叉技术开发更有效且高度可靠的遗传算法。在今年，我们已经努力改善分布估算方法，并通过开发有效的并行化方法来解决大规模问题。具体而言，我们已经开发了一种方法来通过使用分配函数加权并减少分配估计所需的计算成本来提高准确性，并在分布估计算法中用于网络构建的有效并行化方法，该方法基于贝叶斯网络构建了概率模型。此外，我们开发了一种算法D^5，该算法结合了连锁识别和分布估计算法的优势，并开发了一种高度可扩展的方法，可扩展到增加问题量表。此外，还讨论了D^5到实现问题的应用，并评估了其性能。作为提出方法的一个例子，我们通过使用并行分布估计的搜索方法来验证了本研究中开发的方法的有效性，以尤其是最大程度地减少蛋白质的结构能量。