发布时间 : 星期二 文章DNA进化算法及其改进研究更新完毕开始阅读ee197a242f60ddccda38a04a
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页
第四轮1个体0第二轮2第六轮34第五轮5第一轮6第三轮 0.180.340.490.620.730.820.951.00 图2 轮盘赌选择法
(4)交叉 对于选中的用于繁殖后代的每一对DNA链个体，将其中部分内容进行互换。交叉位置是随机产生的。通过交叉这种方法，凭借交叉点，产生了新的DNA链，基因得以极大的改变，交叉分为单点交叉以及多点交叉等好几种方式。而多点交叉又有即n?点交叉和标准交叉两种方式。图三给出的是一个简单单点交叉的例子，如图：
|
···AGTATGAACT|GCACGCCGTACTACT···
···TGAGGCCGTAGTACGATACGTAGAT···
?
| ···AGTATGAACT|GTACGATACGTAGAT···
图4 单点交叉示意图
···TGAGGCCGTAGCACGCCGTACTACT···
(5)变异 在DNA群体中以相应的概率随机的选取若干个DNA链个体，对其中选中的DNA链个体，随机的选取某一位进行DNA链中的碱基排列顺序的变化。DNA链中的变化有碱基的替换、丢失和嵌入。碱基的取代有以下两种：一种是相同类型的碱基之间的转换变异，如嘌呤替换嘌呤，嘧啶代替嘧啶，A替换G，T替换C；另一类是异类型碱基的互相替换：嘌呤被嘧啶替换，如A被T替换。图四是一个染色体中碱基T变成A的变异例子： ···TGAGGCCGTAGTACGATACGTAGAT···
?
图4 点变异例子
···TGAGGCCGTAGTACGAAACGTAGAT···
(6)倒位 从DNA群中以一定的概率随机选取若干个DNA链个体，选中这些DNA链个体后，随机的选中某两点位置，把他们之间的碱基顺序进行互
第12页 共27页