遺伝的アルゴリズムを用いた配置決定とその応用に関する研究

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

本研究の目的は、遺伝的アルゴリズム(GA)を用いた最適配置決定手法についての検討である。GAを用いた最適配置決定手法は様々な手法が提案されているが、提案手法では、交叉や突然変異によって致死遺伝子を発生することがなく、効率よく最適解を探索できるようなGA空間の構成方法等について検討を行い、新しいGAを用いた最適配置決定手法を確立することである。本年度は、以下の最適配置決定問題について検討を行った。1.方形ピースジグソーパズル問題2.ネットワークノード配置問題3.SBH(Sequencing By Hybridization)によるDNA配列決定問題1.および2.は、N×Mの最適配置を決定する問題であり、このような最適配置決定問題において、交叉や突然変異によって致死遺伝子を発生することがなく、効率よく最適解を探索するようなGAの提案を行った。また、他手法と比較することにより、提案手法の有効性を示すことができた。3.は、DNAチップより得られた部分塩基配列から、できるだけ多くの塩基部分が一致するように、部分配列の並びを計算する問題であり、各部分配列の最適な配置を決定する問題と置くことができる。このような最適配置決定問題においても、交叉によって致死遺伝子が発生することなく、効率よく探索できるようなGAを用いた新しい手法を提案し、実際のDNA配列を用いてシミュレーションを行った結果、従来提案されている手法よりも、よい結果を得ることができた。これらの成果は、学会発表および論文誌にて公表した。