论文部分内容阅读
【摘要】针对目前遗传算法所存在的缺点，本文提出了将DNA和遗传算法相混合的DNA遗传算法的新思路。本文所提算法是采用遗传算法的整体结构，借助生物学理论，并借助DNA的双螺旋结构和碱基互补配对原则进行编码运算。并基于这种结构和原则提出了新的算子，提高了算法的收敛性和有效性。然后通过两个特征函数的验证，文中所改进的算法和解决方案是可行的，解得质量也比较好。
【关键词】DNA遗传算法；型遗传算子
DNA计算中的DNA是重要的遗传物质携带着生物体的所有遗传信息，而遗传算法也是采用生物的遗传信息进行操作的算法，其不同是DNA计算是实验室中进行的而遗传算法是在计算机上编程进行的，将二者混合使用可以使遗传算法在生物的遗传调控机理中更深层次的进行模拟，从而使遗传算法的计算性能得到进一步的提升。由于遗传算法的优越性和良好的性能，将其混合到DNA计算中可以突破其计算的局限性[1]【2】。因此学者开始对该混合的DNA遗传算法进行深入的研究，并取得了一定的成果。本文是在前人研究的基础之上，对遗传算法和DNA计算的混合使用中的算子进行了深入的研究。
1.算法中改进的新型算子的提出
1.1 改进算子中的采用技术
受到DNA分子结构的启发，本文将用DNA的四种碱基对问题的潜在解进行编码，由于DNA的编码方式不能直接被计算机处理，本文将使用二进制表示的数0123对碱基进行编码。在这种编码方式中，令0与鸟嘌呤相对应，1与腺嘌呤对应，2与胸腺嘧啶对应，3与胞嘧啶对应，并且0、1、2、3四个整数将采用二进制的形式进行表示。为了在在编码中实现简易的数学和逻辑操作，将二进制数中的第一位作为区分嘌呤和嘧啶的编码位即0代表嘌呤而1代表嘧啶。同时与互补碱基对对应的代码也呈现互补关系，如碱基对C和G互补组合由0（00）与3（11）构成，而1（01）与2（10）构成的A和T碱基对。这样的互补配对关系，有助于新操作算子的设计。
下面是以上面的编码方式为依据的一个n维的最小化问题：
示长度为的四进制数字串，单个个体的编码长度为，每个变量编码精度由求得。
DNA-GA与遗传算法用二进制进行计算编码时的解码方式相似。其均是以n维十进制向量的形式对个体进行解码，其中：
上公式中的为整数串中的第维第列的数字。因为变量取值范围的不同，所以按比例将变量进行转换，这样就可以得到对应问题的解。
按照这种模式进行编码，就可以引入更多的基因操作到遗传算法中，这样就可以设计算法效率更高更有效的算子。
本文所采用的适应度函数和选择算子是原遗传算法中所采用的，这里就不再赘述。
1.2 改进的新型算子
1.2.1 交叉算子
交叉操作是遗传操作中的重要的生物信息遗传操作，故本文对现有的交叉算子进行了改进，在其中加入了DNA计算中的生物操作技术，形成了新的算子。
（1）移位交叉算子
移位交叉的父体为一个，操作过程如图1所示。移位操作是移换个体中的碱基子序列。设父代的基因为ATCGGTACAT，在父代中随机选取一段子序列，这段子序列所包含的碱基数目和所选碱基的位置也是随机选定的。然后将该段子序列移动到一个新的位置，形成一个新的个体。移位交叉算子的执行概率为。如所选子序列是CGGT将其移动到C的后面形成新的个体。
（2）对换交叉算子
对换交叉操作在两个随机配对的个体之间进行，操作过程如图2所示。首先在优质的群体中随机挑选两个个体作为对换交叉操作的父体。然后在两个父体中分别随机选取一段碱基序列，且命名这个碱基序列为转座子。如图2，在两个父体中随机选择两段个数相同的碱基序列，交换这两个父体所选中的碱基序列，形成新的个体。对换交叉操作的执行概率为。
（3）抽换交叉算子
抽换交叉操作是需要从种群中选取两个个体作为父代。而抽换交叉的目的就是改变个体之间的相似性，因此该操作中所选的父代不是随机的，而是选择两个相似的个体。首先在适应度较好的优秀种群中随机选取一个个体作为父代之一，在随机选取两个个体作为候选父代。然后通过对比候选父体与已知父体的相似度，选择与已知父体更相似的个体作为抽换交叉操作的另一个父体。操作过程如图3所示。抽换交叉算子的执行概率为。
以上三种算子，都可以对单个的DNA序列进行操作，而且各有特点。但是同时执行三种算子将大大增加计算复杂度。本文将对换算子作为基本的交叉算子，移位算子和抽换算子则依据概率执行。
1.2.2 新型变异算子
与以往的同变异算子不同，本文所提出的变异算子是以生物体内的DNA转录成RNA并且通过其配对的反密码子决定蛋白质肽链的合成过程，并且计算在反密码子中各个碱基所出现的概率，然后用低概率替换高概率或者高概率替换低概率的最大最小变异算子，最后形成新的DNA分子。生成一个新的个体。其变异概率为。其过程如图4所示。
2.新提算子的运算步骤
步骤1：在运行算法之前，先对算法中所涉及到的参数进行设置，如种群大的大小、终止阙值、最大进化代数和所改进新型算子的运行概率，普通变异概率等。
步骤2：随机产生size个个体，组成初始种群，并将当前的进化代数设置为1.
步骤3：对个体进行编码串解码，求出各个个体的适应度值。
步骤4：按照适应度值的大小将种群中的个体分为高适应度个体和低适应度个体，令交叉后产生的新个体数为Ncnew，并且从第一代交叉算起，不交叉时Ncnew为0。
步骤5：对种群中进行交叉操作，选择个体为父代个体，按其随机产生的概率数与交叉。
概率、，进行比较，所产生的随机数小于哪个交叉算子的概率就执行哪个交叉算子，最后产生新的个体，并且此时产生的新个体数为+1。 步骤6：对经过交叉操作产生的个体以概率进行变异操作。产生新个体。
步骤7：对经过交叉和变异操作产生的个体用精英保留选择机制进行选择保留，选出适应度大的个体，此时进化代数加1.
步骤8：判断是否终止运行，其判断条件是最大进化代数或者是最大进化代数的阙值。满足就结束，输出结果；否则返回步骤3继续进行。
3.实验测试
为了测试出本文所提出的DNA遗传算法的有效性和搜索性能，从以往的文献中选取了两个具有代表性的无约束的函数作为测试函数。本文使用改进的DNA遗传算法求解从文献中选取的测试函数，它们的局部最优点较多，欺骗性很强，一般的算法不易求解到这两个函数的全局最优点。其中，的最优解为3600，在点（0，0）处取得，而的最优解在点（0，0）处取得。
将这两个函数分别用未经过改进的遗传算法、基于进化策略的遗传算法（EGA）[3]和本文所提出的新的混合DNA遗传算法（DNA-GA）进行求解，并将所得到的结果进行比较，三种算法的种群大小均为60，当最大的进化代数时终止运算。
为了对三种算法都进行比较，在三种不同的算法下每个函数都运行了50次，三种算法的对比结果如表1、表2所示。
综上所述，可以发现，本文所设计的遗传算子对提高DNA遗传算法的搜索性能有了很大的作用。对于和两个函数而言，新型的变异算子在算法求解问题的收敛速度等方面提高比新型的交叉算子作用更大，因此将两种新型的算子配合一起来使用，可以进一步提高DNA遗传算法性能。
4.结束语
本文在前人研究的基础前提之上，对已有的算法进行了改进与创新，通过实验函数的验证本文所设计的遗传算子对提高DNA遗传算法的搜索性能有了很大的作用。
但是本文所改进提出的新型算子还是只用于实验研究，需要进一步的使用实践来证明与改进。
参考文献
[1]余文，李人厚.一种有效地双向进化算法[J].小型微型计算机系统，2003，24（3）：527-530.
[2]陈霄.DNA遗传算法及其应用研究[D].浙江科技大学博士论文，2010.
[3]王四春.GP算法中适应度函数的光滑拟合与调整参数方法研究[J].自动化学报，2006（3）：23-30.
[4]陶吉利.基于DNA计算的遗传算法及应用研究[D].杭州：浙江大学博士论文，2007.
[5]Whitley，L.D.，and Vose，M.D.（eds）Foundation of genetic algorithm 3.San Mateo，CA：Morgan Kaufmann，1995.
作者简介：闻玉刚（1987—），男，河北迁安人，辽宁科技大学硕士研究生，研究方向：数据挖掘。
【关键词】DNA遗传算法；型遗传算子
DNA计算中的DNA是重要的遗传物质携带着生物体的所有遗传信息，而遗传算法也是采用生物的遗传信息进行操作的算法，其不同是DNA计算是实验室中进行的而遗传算法是在计算机上编程进行的，将二者混合使用可以使遗传算法在生物的遗传调控机理中更深层次的进行模拟，从而使遗传算法的计算性能得到进一步的提升。由于遗传算法的优越性和良好的性能，将其混合到DNA计算中可以突破其计算的局限性[1]【2】。因此学者开始对该混合的DNA遗传算法进行深入的研究，并取得了一定的成果。本文是在前人研究的基础之上，对遗传算法和DNA计算的混合使用中的算子进行了深入的研究。
1.算法中改进的新型算子的提出
1.1 改进算子中的采用技术
受到DNA分子结构的启发，本文将用DNA的四种碱基对问题的潜在解进行编码，由于DNA的编码方式不能直接被计算机处理，本文将使用二进制表示的数0123对碱基进行编码。在这种编码方式中，令0与鸟嘌呤相对应，1与腺嘌呤对应，2与胸腺嘧啶对应，3与胞嘧啶对应，并且0、1、2、3四个整数将采用二进制的形式进行表示。为了在在编码中实现简易的数学和逻辑操作，将二进制数中的第一位作为区分嘌呤和嘧啶的编码位即0代表嘌呤而1代表嘧啶。同时与互补碱基对对应的代码也呈现互补关系，如碱基对C和G互补组合由0（00）与3（11）构成，而1（01）与2（10）构成的A和T碱基对。这样的互补配对关系，有助于新操作算子的设计。
下面是以上面的编码方式为依据的一个n维的最小化问题：
示长度为的四进制数字串，单个个体的编码长度为，每个变量编码精度由求得。
DNA-GA与遗传算法用二进制进行计算编码时的解码方式相似。其均是以n维十进制向量的形式对个体进行解码，其中：
上公式中的为整数串中的第维第列的数字。因为变量取值范围的不同，所以按比例将变量进行转换，这样就可以得到对应问题的解。
按照这种模式进行编码，就可以引入更多的基因操作到遗传算法中，这样就可以设计算法效率更高更有效的算子。
本文所采用的适应度函数和选择算子是原遗传算法中所采用的，这里就不再赘述。
1.2 改进的新型算子
1.2.1 交叉算子
交叉操作是遗传操作中的重要的生物信息遗传操作，故本文对现有的交叉算子进行了改进，在其中加入了DNA计算中的生物操作技术，形成了新的算子。
（1）移位交叉算子
移位交叉的父体为一个，操作过程如图1所示。移位操作是移换个体中的碱基子序列。设父代的基因为ATCGGTACAT，在父代中随机选取一段子序列，这段子序列所包含的碱基数目和所选碱基的位置也是随机选定的。然后将该段子序列移动到一个新的位置，形成一个新的个体。移位交叉算子的执行概率为。如所选子序列是CGGT将其移动到C的后面形成新的个体。
（2）对换交叉算子
对换交叉操作在两个随机配对的个体之间进行，操作过程如图2所示。首先在优质的群体中随机挑选两个个体作为对换交叉操作的父体。然后在两个父体中分别随机选取一段碱基序列，且命名这个碱基序列为转座子。如图2，在两个父体中随机选择两段个数相同的碱基序列，交换这两个父体所选中的碱基序列，形成新的个体。对换交叉操作的执行概率为。
（3）抽换交叉算子
抽换交叉操作是需要从种群中选取两个个体作为父代。而抽换交叉的目的就是改变个体之间的相似性，因此该操作中所选的父代不是随机的，而是选择两个相似的个体。首先在适应度较好的优秀种群中随机选取一个个体作为父代之一，在随机选取两个个体作为候选父代。然后通过对比候选父体与已知父体的相似度，选择与已知父体更相似的个体作为抽换交叉操作的另一个父体。操作过程如图3所示。抽换交叉算子的执行概率为。
以上三种算子，都可以对单个的DNA序列进行操作，而且各有特点。但是同时执行三种算子将大大增加计算复杂度。本文将对换算子作为基本的交叉算子，移位算子和抽换算子则依据概率执行。
1.2.2 新型变异算子
与以往的同变异算子不同，本文所提出的变异算子是以生物体内的DNA转录成RNA并且通过其配对的反密码子决定蛋白质肽链的合成过程，并且计算在反密码子中各个碱基所出现的概率，然后用低概率替换高概率或者高概率替换低概率的最大最小变异算子，最后形成新的DNA分子。生成一个新的个体。其变异概率为。其过程如图4所示。
2.新提算子的运算步骤
步骤1：在运行算法之前，先对算法中所涉及到的参数进行设置，如种群大的大小、终止阙值、最大进化代数和所改进新型算子的运行概率，普通变异概率等。
步骤2：随机产生size个个体，组成初始种群，并将当前的进化代数设置为1.
步骤3：对个体进行编码串解码，求出各个个体的适应度值。
步骤4：按照适应度值的大小将种群中的个体分为高适应度个体和低适应度个体，令交叉后产生的新个体数为Ncnew，并且从第一代交叉算起，不交叉时Ncnew为0。
步骤5：对种群中进行交叉操作，选择个体为父代个体，按其随机产生的概率数与交叉。
概率、，进行比较，所产生的随机数小于哪个交叉算子的概率就执行哪个交叉算子，最后产生新的个体，并且此时产生的新个体数为+1。 步骤6：对经过交叉操作产生的个体以概率进行变异操作。产生新个体。
步骤7：对经过交叉和变异操作产生的个体用精英保留选择机制进行选择保留，选出适应度大的个体，此时进化代数加1.
步骤8：判断是否终止运行，其判断条件是最大进化代数或者是最大进化代数的阙值。满足就结束，输出结果；否则返回步骤3继续进行。
3.实验测试
为了测试出本文所提出的DNA遗传算法的有效性和搜索性能，从以往的文献中选取了两个具有代表性的无约束的函数作为测试函数。本文使用改进的DNA遗传算法求解从文献中选取的测试函数，它们的局部最优点较多，欺骗性很强，一般的算法不易求解到这两个函数的全局最优点。其中，的最优解为3600，在点（0，0）处取得，而的最优解在点（0，0）处取得。
将这两个函数分别用未经过改进的遗传算法、基于进化策略的遗传算法（EGA）[3]和本文所提出的新的混合DNA遗传算法（DNA-GA）进行求解，并将所得到的结果进行比较，三种算法的种群大小均为60，当最大的进化代数时终止运算。
为了对三种算法都进行比较，在三种不同的算法下每个函数都运行了50次，三种算法的对比结果如表1、表2所示。
综上所述，可以发现，本文所设计的遗传算子对提高DNA遗传算法的搜索性能有了很大的作用。对于和两个函数而言，新型的变异算子在算法求解问题的收敛速度等方面提高比新型的交叉算子作用更大，因此将两种新型的算子配合一起来使用，可以进一步提高DNA遗传算法性能。
4.结束语
本文在前人研究的基础前提之上，对已有的算法进行了改进与创新，通过实验函数的验证本文所设计的遗传算子对提高DNA遗传算法的搜索性能有了很大的作用。
但是本文所改进提出的新型算子还是只用于实验研究，需要进一步的使用实践来证明与改进。
参考文献
[1]余文，李人厚.一种有效地双向进化算法[J].小型微型计算机系统，2003，24（3）：527-530.
[2]陈霄.DNA遗传算法及其应用研究[D].浙江科技大学博士论文，2010.
[3]王四春.GP算法中适应度函数的光滑拟合与调整参数方法研究[J].自动化学报，2006（3）：23-30.
[4]陶吉利.基于DNA计算的遗传算法及应用研究[D].杭州：浙江大学博士论文，2007.
[5]Whitley，L.D.，and Vose，M.D.（eds）Foundation of genetic algorithm 3.San Mateo，CA：Morgan Kaufmann，1995.
作者简介：闻玉刚（1987—），男，河北迁安人，辽宁科技大学硕士研究生，研究方向：数据挖掘。