遗传此算法为基础，通过改变其编码进制数和增加DNA链之间的操作来进行研究的。
2.2 基于DNA计算的进化算法
DNA的基本元素是核苷酸。核苷酸分为4 类碱基: 腺嘌呤(A ) 、 鸟嘌呤(G) 、 胞嘧啶(C) 和胸腺嘧啶(T )。DNA 是由两条很长的核苷酸链组成的。每条染色体则是一段呈双股螺旋状的DNA , A、T、C 和G 在DNA链中的不同排列序列造成了其能够表述大量丰富的遗传信息。DNA 指导蛋白质的形成过程如下： 先从DNA的一条链 上转录，接着逆转录成mRNA。在mRNA 中不间断排列着由3 个相邻碱基为一组构成的密码子，这些密码子对应着不同的氨基酸，总共 4*4*4=64 种密码子对应20 种基本的氨基酸。氨基酸作为基本物质构成蛋白质。
若把上述原理数学化，单股DNA 无疑可看做4个字母的集合
?{A,T,C,G},DNA 串的不同碱基可视为译码信息, 各种酶的操作便视之为
在DNA 序列上的操作, 各种酶作为相应类型的操作算子, 对DNA链进行分子水平上的操作。即DNA计算模型可建立在形式表达?{A,T,C,G}且对其进行分子操作的基础上[5]。
DNA 遗传算法是基于DNA 编码遗传模型进行遗传操作的。DNA 遗传算法的结构与常规遗传算法的结构类似。 2.2.1 DNA计算中的基本术语
下面简单介绍一下DNA进化算法中使用的基本概念和术语。
(1)DNA链(染色体) 遗传物质的主要载体，是多个遗传因子的集合，由A、T、C、G编码集合组成。
(2)遗传因子(基因) 控制生物性状遗传物质的功能和结构的基本单位，可对应于待求解问题的某个参数和多个参数的组合。
(3)遗传子座 DNA链上遗传因子的位置。各个位置决定所遗传的信息。 (4)基因型 遗传因子组合的模型，是性状DNA链的内部表现。 (5)表现型 由DNA链决定性状的外部表现，或者说，是根据基因型形成的个体。
(6)个体 指DNA链带有特征的实体。
(7)DNA汤(群体) DNA链带有特征的个体的集合，该集合内的DNA链的多少为DNA汤的大小。
(8)适应度 一条DNA链所代表的外部表现对外部环境的适应程度。 (9)编码 从表现型到基因型的映射。 (10)译码 从基因型到表现型的映射。
第7页 共27页
(11)选择 指以一定的概率从DNA汤中选择若干对DNA链的操作。选择的目的是使适应度大的DNA链有更多繁殖后代的机会，从而使优良特性得以遗传，他体现了自然界适者生存的思想。
(12)交叉 将两条DNA链进行互换重组的操作。交叉是DNA进化算法的核心。只有不断的交叉，才能不断的产生新的个体，从而得到优秀的个体。从信息论的观点看，交叉是一种信息交换并产生新信息的过程，交叉的同时也创造了新的信息。交叉的方式有单点、多点以及最近遗传学讨论的基因转移等多种方式。
(13)变异 让DNA链中的遗传因子以一定的概率突然变化的操作。变异的目的是使DNA进化算法具有局部随机搜索功能，维持DNA汤多样性，避免出现早熟现象而过早地收敛。DNA链的变异主要有碱基的突变和碱基序列的变化等。
(14)倒位 在DNA链中两个随机选择位置之间的某些碱基的顺序进行倒位。它可以使在父代中离得很远的位在后代中靠在一起，相当于重新定义基因块。
2.2.2 有关对DNA进化算法的假设
DNA进化算法(DNA-GA)采取模仿DNA链编码，增加遗传算法的操作，与遗传算法的模型有着参考借鉴的关系，故与遗传算法类似，可以对该模型提出下列假设：
(1) 每条DNA链是由A、T、C和G四种碱基不同的排列组成的一个固定(或可变)长度的字符串，其中每一位都具有有限数目的等位基因。
(2) DNA汤(群体)由有限条DNA链组成。
(3) 对任意一条DNA链都可进行不同的遗传操作。
(4) 每一条DNA链对应一相应的适应度，表示该DNA链生存与复制的能力。适应度越大，表示其生存能力越强。 2.2.3 DNA进化算法的结构
如上所述，DNA进化算法(DNA-GA)的结构类似于常规遗传算法。以下为DNA-GA求解具体问题的基本步骤。
(1)种群初始化及DNA链编码 使用n个具有随机编码的DNA链的群体组成的初始世代群体(DNA汤)P(t)。每条DNA链由A、T、C、G四种碱基结合构成，可表示不同的基因。DNA-GA初始化时，实际求解问题的设计参数是通过?{A,T,C,G}来编码形成每一条DNA链。DNA编码是整个算法的关键环节，后续的计算完全是基于初始编码的基础上完成的，DNA链的长度和汤池的大小也决定了最终问题求解的收敛速度和精度。DNA-GA的任务就是从初始化后的
第8页 共27页
DNA汤出发，模拟进化过程，经过多次的迭代计算选择出优秀的群体和个体，最终满足求解问题的要求。
起始初始化实际问题的DNA链编码计算适应度得到解？是否选择交叉变异结束倒位
图1 DNA进化算法流程图
编码 本设计在DNA链编码过程中，用0代表A，用1代表T，用2代表C，用3代表G。这样就把DNA链实现为一条四进制的数字码串，在实现算法时，首先初始化DNA汤的过程中，利用MATLAB中Rand函数随机产生0.0至1.0之间的数据，不同范围内的数据统一规定为相应不同的碱基。如本算法
第9页 共27页
主程序中若随机数在0.0与0.25之间，碱基对应为0；若随机数在0.25与0.5之间，碱基对应为1；若随机数在0.5与0.75之间，碱基定义为2，若随机数在0.75与1.0之间，碱基对应为3。
编码机制 遗传算法中，常用的有二进制编码和浮点数编码两种机制，本设计中采用二进制编码的原理，只是相应的改变为四进制编码。另浮点数编码在这里不再表述。
1,2，?，n?。假设群众中个体的数目为n，xti表示第t代的第i个个体，i??每个个体用l位四进制表示。这样每个个体xti??IB?，IB??0,1?,这样每个个体
ml基因位数目L?ml。个体xti可以表示为ml维的行向量，即
xti=xt?xtxt?i(1)i(l)i(l?1)n?ml的矩阵Xt= xt1xt2?xtn。个体xti的第k个长度为l的四进制码串化为实数
??xti(2l)?xti((m?1)l?1)?xti(ml)。第t代种群Xt可以表示为一个
??T的解码函数?为
tvk?uki(kl?j)j?1?（x,k）?uk?(x?4) (1) ?tl4?1j?1式中vk和uk分别为第k个实数范围的上限和下限。
it(2)适应度函数
常用的适应度函数有如下三种：
? 直接把要求的目标函数视之为适应度函数，即：
如目标函数为最大化问题 Fit(f(x))?f(x) (2) 如目标函数为最小问题 Fit(f(x))??f(x) (3) 显然采取这种适应度函数既简单又直观，但是也存在两个问题，一是一般的轮盘赌选择中，对于概率有着非负的要求，这一点可能不能够满足；另有时候待求解的函数在函数值的分布上相差较大，从而得到的平均适应度偏离理论值较远，对种群的平均性能不利，影响算法的性能。
? 若目标函数为最小问题，则
Fit(f(x))??cmax?f(x),f(x)?cmax0,其他 (4)
式中cmax为f(x)的最大值估计。 若目标函数为最大问题，则
Fit(f(x))??f(x)?cmi,nf(x)?cm0,其他in (5)
式中cmax为f(x)的最小值估计。
这种方法是对第一种方法的改进，可以称之为“界限构造法”，但存在的问题是有时候存在界限预先估计困难，以至于不可能精确。
? 若目标函数为最小问题
第10页 共27页
Fit(f(x))?
1，c?0,c?f(x)?01?c?f(x) (6)
1,c?0,c?f(x)?0 (7)
1?c?f(x) 若目标函数为最大问题 Fit(f(x))?该方法类似于第二种方法，c为目标函数界限的保守估计值。 本设计直接采用的是第一种适应度计算策略。
(3)选择 以适当的概率从DNA汤中P(t)选择出m个DNA链个体并作为父本母本用于繁育后代，而产生的新个体投入到下一代P(t?1)。选择的意义在于使那些适应度函数值大的DNA链有更多更大的留下来并参与下一代的机会，这样优良特性便可以遗传下去，体现了大自然优胜劣汰的原理，与常规的标准遗传算法类似，DNA-GA算法选择操作常用的方法有适应度比例法、期望值法、排位次序法、精华保存法和轮盘赌法。下面简单介绍一下常用的两种：
按比例的适应度分配：按比例的适应度也可称之为选择的蒙特卡罗法，是利用比例于各个个体适应度的概率决定其子孙的去留的可能性，若某个个体i，其适应度为fi ，则其被选取的概率表示为：
pi?fi?i?1m
fi (8)
轮盘赌选择法(roulette wheel selection ) 这是一种最简单的选择策略，表1表示了11个个体适应度、不同个体的选择概率和累积概率。为了选择出可作为父本母本的个体，要对种群进行进行多轮选择。在每一轮中利用函数产生一个[0,1]均匀随机数，并将该随机数的大小作为选择指针来确定哪些是被选个体，如图2所示，如果第一轮随机数为0.81，第6个个体累积概率为0.82，则它被选中，若第二产生的轮随机数为0.32，则第二个个体累积概率为0.34的被选中；依此原理类推，如第3、4、5、6轮随机数为0.96，0.01,0.65,0.42，则第9,1,5,3个个体以此被选中。因为其对应的累积概率分别为0.98、0.18、0.73、0.49。这样经过这种办法选择产生的交配种群由以下个体组成：1、2、3、5、6、9。
表1 轮盘赌选择法的选择概率计算 个体 适应度 选择概率 累积概率
0.18
0.34
0.49
0.62
0.73
0.82
0.89
0.95
0.98
1.00
1.00
0.18
0.16
0.15
0.13
0.11
0.09
0.07
0.06
0.03
0.02
0.0
1 2.0
2 1.8
3 1.6
4 1.4
5 1.2
6 1.0
7 0.8
8 0.6
9 0.4
10 0.2
11 0.1
第11页 共27页