论文部分内容阅读
DNA计算是一种基于DNA分子的并行计算模型,是在计算科学和分子生物学的基础上发展起来的一个新颖而极具发展潜力的交叉学科。在不需要任何外部条件干预下,这些经过设计的DNA分子能精确自组装,求解复杂的组合优化NP完全问题。然而,如果DNA分子编码质量不高,DNA分子间出现了非特异性杂交或解链温度不一致,都容易导致DNA计算过程的失败。为了提高DNA计算的有效性、可靠性、以及可求解问题的规模,都需要设计高质量的DNA编码。DNA分子的设计需要满足各种汉明距离约束、热力学约束和生物约束等条件,是典型的多目标优化问题。而传统的多目标优化问题候选解的适应度函数值通常相互独立,也就是任何一个候选解的适应度函数值只跟目标函数相关,跟其它候选解无关。然而,DNA编码问题需要求解一组相互约束且不发生非特异性杂交的DNA分子集合,其适应度函数值的计算依赖于其它DNA分子。因此,传统的多目标优化算法无法较好的适用于求解DNA编码问题。本文结合多目标粒子群算法和DNA编码问题的特性,提出了一种新颖的动态多目标粒子群DNA编码设计方法。该算法维持一个寻优种群和一个精英种群,每次迭代只更新寻优种群中的粒子,通过基于最小曼哈顿距离的动态精英选择算法从寻优种群和精英种群中选择出下一代的精英种群,直到达到最大迭代次数,精英种群中的粒子即为算法生成的一组DNA编码序列。本文实验产生了7条长度为20的DNA序列、14条长度为20的DNA序列、20条长度为15的DNA序列,并与已知DNA编码算法文献的结果进行了对比,实验结果表明了本文算法是有效可行的,可以产生高质量DNA分子集,有效提高DNA计算的规模和可靠性。