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

遗传算法的布局确定及其应用研究

基本信息

批准号：
16700201
负责人：
外山史
金额：
$ 1.15万
依托单位：
Utsunomiya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

项目摘要

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

本研究的目的是研究使用遗传算法（GA）的最佳放置确定方法。已经提出了各种使用 GA 确定最佳放置的方法，但所提出的方法不会因交叉或突变而产生致死基因，并配置 GA 空间，以便可以有效地搜索最佳解决方案。使用新的遗传算法建立最佳放置确定方法。今年，我们研究了以下最佳布局确定问题。 1. 方块拼图问题 2. 网络节点放置问题 3. SBH（杂交测序）DNA 测序问题问题 1. 和 2. 是确定最佳 N×M 放置的问题我们提出了一种有效搜索 N×M 放置的 GA。决策问题的最佳解决方案，不会因交叉或突变而产生致命基因。此外，我们能够通过与其他方法进行比较来证明所提出的方法的有效性。 3.是计算部分序列的排列以使尽可能多的碱基部分与从DNA芯片获得的部分碱基序列匹配的问题，并且这被认为是确定每个部分序列I的最佳排列的问题。能。我们提出了一种使用 GA 的新方法，可以有效地搜索最佳位置，而不会因交叉而产生致死基因，并使用实际 DNA 序列进行模拟，我们能够获得比所提出的方法更好的结果。这些结果发表在学术会议和期刊上。

项目成果

期刊论文数量（2）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Image mosaicing from a set of images without configuration information

DOI：
10.1109/icpr.2004.1334404
发表时间：
2004-08
期刊：
Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004.
影响因子：
0
作者：
Fubito Toyama;K. Shoji;J. Miyamichi
通讯作者：
Fubito Toyama;K. Shoji;J. Miyamichi

遺伝的アルゴリズムを用いた双方向マンハッタンストリートネットワークのノード配置

使用遗传算法的双向曼哈顿街道网络的节点放置