论文部分内容阅读
计算机技术被认为是20世纪三大科学革命之一,电子计算机为社会的发展起到了巨大的促进作用,但是量子物理学已经成功地预测出芯片微处理能力的增长不能长期地保持下去。基于这一原因,科学家们正在寻找其他全新的计算机结构,如人工神经网络计算机、量子计算机、光学计算机以及DNA计算机模型等,其中DNA计算机倍受科学界的关注。本文对DNA计算的DNA编码和遗传算法进行了研究。全文由“导论”、“DNA序列编码和优化模型”、“遗传算法编码与优化模型”、“总结和展望”四个部分组成。本文的研究主要包括二方面的内容:DNA计算中的编码问题和模型研究。由于在DNA计算中,信息总是通过特定长度的DNA序列来表示的,因此,选择高质量的方式来表示DNA序列就成为一个重要的问题。本文给出了一个改进的DNA序列的图表示:在2维直角坐标系内用四个特定的向量分别表示DNA序列中的四个碱基,从而使DNA序列可以用一个平面内的有向路表示。文中给出了一个例子说明该方法的有效性,可以证明该种改进的DNA序列图表示方法具有较低的退化度甚至没有退化。我们给出了DNA计算中序列设计的支持系统:计算由多个评价指标的线性和组成的适应值函数的最小值。我们的系统不仅可以搜索好的序列,而且可以得出每个评价指标对于适应值函数的贡献度。通过简化适应值函数,可以减少各评价指标的数目。这有助于为DNA计算的序列设计找到好的评判标准。本文提出了一个适合生物学特征的实数的编码方案,该方案的编码有固定长度。根据问题的特征,提出了一个求解最小支撑树问题的DNA算法。仿真验证了所提出的方法的有效性,同时也讨论了该方法的优点和缺点。在模型研究中,本文主要就如下几个问题给出了有效的算法模型。首先给出了图的关联着色和文件传输问题的遗传算法。文中对一个关联色数是6的图进行了仿<WP=5>真,得到了该图的关联色数。同时给出了文件传输问题的边着色模型。给出了一个例子来说明算法的收敛性和收敛效率。其次给出了基于Elmore模型的Steiner树问题的遗传算法。给出了一个表示解的染色体新构造方法。分析了算法的时间复杂性和空间复杂性。