基于遗传算法的DNA计算模型编码方案的设计研究

2023-01-10

一、遗传算法概述

本文利用遗传算法进行DNA编码, 使得编码的方案是最优的。遗传算法, 英文Genetic Alogrithm, 简称GA, 是一种植根于达尔文自然进化论理论和遗传变异理论, 用以求解复杂全局优化问题的智能计算算法。在DNA分子的杂交反应过程中, C与G配对会形成三个氢键, 而A与T配对会形成两个氢键, 三个氢键的结构较之两个氢键的结构更为稳定, 所以DNA编码中C、G含量高将极大的利于DNA分子的杂交。本文利用遗传算法优化DNA计算中的分子编码结构, 最终的目标是无论何种编码方案中, 在遗传算法的优化下尽量使得DNA链中C、G的含量保持高密度。下文将详尽的给出遗传算法的一般步骤。

Step1.对各类参数进行编码;

Step2.建立初始群体空间;

Step3.根据问题的不同特性选择适应度函数;

Step4.基于适应度函数进行计算:

a.计算个体的适应度函数。

b.基于适应度函数, 合理有效应用选择算子、交叉算子及变异算子产生新的种群。

Step5.重复进行Step4的操作, 直到适应度函数值达到最优即得到了问题的解。

二、参数的编码方案

DNA分子有A、G、C、T四种碱基, 所以对问题进行编码的时候智慧出现这四种可能性。为使编码尽量简单, 本文使用了一维染色体编码方案。令G、C=1, A、T=0, 因此, DNA分子的A、G、C、T编码将映射成为一个二值符号集{0, 1}。

三、群体生成

基于上文的参数编码方案设计, 初始的种群空间定义为, 其中|G|=2n。DNA分子的编码将以此为依据生成初始的种群空间。

四、确定适应度函数

适应度函数对于遗传算法而言至关重要, 綦江直接影响选择操作的效能。本文以求解图的最短路径问题为例, 说明适应度函数确定的策略。图的最短路径求解问题中需要权衡的要素包括三点, 分别是边的权值编码信息, C、G产生三个氢键的事实及A、T产生两个氢键的事实。本文的策略是用每条边所包含的氢键数目Ni与该边权值Wi的和同所有边的氢键数目N与所有边的权值和W相加后的比值作为适应度函数, 同时, 设定阈值θ用以进行优胜劣汰。算法定义为:对于初始种群中的所有个体, 令Ni表示该个体所代表的边中氢键的数目, 得到, 其中Xi是个体的0、1编码序列, x是序列中的编码字符, , 那么适应度函数为, 本文的阈值θ取为0.1

五、遗传算子

遗传算子包括选择算子、交叉算子和变异算子, 这个三个算子是遗传算法中实现优胜劣汰的关键与核心。在经过上述编码生成初始种群后, 将根据其环境适应度进行遗传操作, 本文将三个算子的选择策略定义如下:

a.选择算子:

.本文将适应度比例函数的赌轮选择方法确定为淘汰劣质个体的依据, 进而选择算子定义为

b.交叉算子:

交叉算子是驱动种群进化的核心, 经经过选择算子选定的个体进行单点交叉生成新的个体, 交叉过程的机理如下图所示。

c.变异算子:

基于上文编码策略的阐述, 本文采用的是二维编码, 即{0, 1}, 变异算子继而变得较为简单, 即若原编码为0, 则变异为1, 反之相同, 且本文推荐的变异概率为0.001.

综上, 依据本文给出的遗传算法步骤, 经过上述操作, 将生成新一代的DNA分子编码作为初始种群, 并重复执行选择操作、交叉操作及变异操作, 这样将不断提高群体的平均适应度和个体的适应度, 直到得到最优解。但DNA计算实际执行的是DNA分子的生化反应, 故而需要对经过遗传算法编码的结构进行解码, 即将0分别转换为A、T, 而将1分别转换为C、G, 最终得到优化的DNA分子的编码结构。

摘要：DNA计算是一种全新的智能计算模式, 极大的扩充了智能计算的研究领域。DNA计算的核心思想是将拟解决问题进行合理编码后的DNA生物链作为输入数据, 在完备的生物化学反应控制下, 利用高度的冗余计算将问题的全部解空间呈现在溶液中, 继而利用生物技术进行解分离, 已达到最终计算的目的。可见, DNA计算模式下, 问题的DNA分子编码是关键。遗传算法已经高度成熟并得到广泛应用, 善于解决优化问题。本文研究了一种基于遗传算法的DNA问题编码方案, 给出了详细的算法流程, 并在模拟实验环境下验证了方案的可行性。

关键词：DNA计算,遗传算法,生化反应