发布时间 : 星期一 文章DNA进化算法及其改进研究更新完毕开始阅读ee197a242f60ddccda38a04a
相倒位。倒位的目的在于尝试找到更好的进化特性的基因顺序。倒位操作是可选的，根据问题的需要而定。图五给出的是倒位的例子：
···TGAGGCCGTAGTACGATACGTAGAT···
?
||
|
···TGAGGCCGTAATAGCATGCGTAGAT···
图5 倒位操作的例子
|
(7)循环往复 对于新产生的每一代DNA汤，反复回到步骤(2)，再进行评价、适应度计算、选择、交叉、变异和倒位操作。如此循环，在动态中经历了无数次状态，DNA汤更丰富了，包含了各种情况，群体中个体适应度不断提高，平均适应度不断提高，直到找到最优解后或者达到某一限制后个体的适应度和平均适应度不再提高，此时迭代过程收敛，算法自然结束了。 2.2.4 DNA进化算法与常规遗传算法的比较
基于DNA计算的进化算法是常规遗传算法的发展，自然容纳了常规遗传算法如下的基本特点：
(1)都是对参数构成的编码种群进行进化，而不是对某个特定参数。 (2)由于算法是对编码种群的各种操作，而不受函数性质的限制(诸如连续性、是否存在导数、单多重极值等)，所以可求解一般优化方法难以解决的一些问题。
(3)都是单纯利用适应度大小进行搜索，无需其他任何信息。 (4)都是利用随机操作指导着向最优化方向前进的搜索。 (5)都有智能的特点，即可以自组织和自学习。
(6)都具有隐形并行性，使得相对少的编码覆盖范围很大的解区域。 此外，DNA进化算法还具有普通遗传算法不具备的特性：
(1)DNA编码方法与传统遗传算法使用的二进制编码方法相比有了进步，使得种群信息更丰富，更适合表达较复杂知识，且更加灵活，其长度也较遗传算法大大的缩短。
(2)DNA进化算法中，能够更方便引入分子水平操作，使用各种遗传操作算子，如倒位、异位、交叉等，这极大的扩展了进化方法，如倒位操作，可以使在上一代中相差很远的后代聚集在一起，这样便相当于重新定义了基因群，使得其更加紧凑，不易被交换所分裂。
(3)DNA进化算法中，因为编码的丰富性和译码的多样性，所以即使变异概率较低，仍然能保持一定水平的多样性。
(4)DNA染色体长度可变的特点，使得更容易完成插入和删除碱基序列的操作，更加适合于优化复杂知识。
第13页 共27页
2.2.5 基本DNA算法的实现 基本DNA进化算法的伪码如下所示： ·······················································
初始化，产生DNA链长度为dna_length,种群规模为soap_size的dna汤 For k=1:1:D(迭代数) 解码过程； 计算适应度； 适应度排序； 找出最优解； for i=1:1:soap_size
执行选择操作(采用轮盘赌法)； end
for i=1:2：soap_size if rand For i=1:1:soap_size If rand 执行变异操作(包括碱基的替换，丢失和插入) End End For i=1:1:soap_size If rand · ························································· 3 改进方法研究 根据基本实现算法中采用适应度比例选择、交叉、变异和倒位等特征，我们可以从改进种群初始化产生的方法、选择方法的改进、交叉点的计算、变异概率的选择、插入长度的改进和倒位点的确定等方面加以改进。另外，针对本 第14页 共27页 算法所存在的易出现“早熟”现象和局部搜索能力较差的问题，采取DNA算法和模拟退火算法结合的方法，以获得更好的性能。 3.1 自适应DNA进化算法 本设计在实现基本算法过程中，是通过不断地选择、交叉、变异和倒位操作的迭代过程，最终收敛于最佳解的算法，选择操作使得适应度函数值较高的个体有着更大的复制概率，它能加快算法的收敛速度，因为其种群越来越优秀。交叉操作则是通过重组基因和染色体从而产生更优秀的个体，寻优的搜索功能主要通过它来实现，但是种群中如果发生基因丢失，而这些丢失的基因恰好又是最佳解所包含的信息时，交叉操作则有可能搜索不到最优解，这时候，变异操作则可能恢复丢失的基因。 传统的算法中，交叉在变异之前，且“优秀”的个体和“劣质”的个体经受相同的交叉、变异和倒位操作的概率，这样的话，基本上很难保证丢失的基因的恢复，而且即使是恢复了有效基因的个体的适应度值也不一定高，经过选择操作后又会造成有效基因的丢失[6]。 为此，本设计提出，在算法实现过程中，改变交叉操作和变异操作的先后顺序，同时，对交叉和变异操作以及倒位操作采取自适应概率的方法。 这种算法的特点之一是先进行变异操作，保持了群体的多样性，之后再通过交叉等操作就能有效地找到最优解。DNA算法中的交叉、变异和倒位操作的概率的选取对算法的性能有着很大的影响：如果交叉和变异概率过大，有可能使算法变为随机搜索，而交叉和变异概率太小的话又会使算法早熟，未能找到最优解而陷入了局部最优点。本算法采用的自适应公式如下： ?k1?(k1?k2)(f?fav?fmax?favgPc?? k1,f??favg??')g,f??favg (9) 上式中k1与k2按照经验取值，如本改进后算法中k1=0.9，k2=0.2，f?为参与交叉操作的两个DNA个体中较大适应度值那一个，fmax和favg分别为种群中最大适应度值和平均适应度值。 (k3?k4)(fmax?fk3???fmax?favg????k3,f?favg)Pm ,f?favg(10) 上式中k3和k4同样按照经验取值，本改进后算法设计中k3=0.1，k4=0.05， f为变异个体适应度值，fmax和favg分别为种群中最大适应度值和平均适应度值。 第15页 共27页 (k5?k6)(fmax?fk5???fmax?favgP??i??k5,f?favg),f?favg (11) 上式中k5和k6同样按照经验取值，本改进后算法设计中k5=0.3，k6=0.04， f为变异个体适应度值，fmax和favg分别为种群中最大适应度值和平均适应度值。 在实现DNA进化算法的过程中，最核心的是其仿生优化特性，在算法中体现的就是进化操作，我们认为进化操作有利于种群向好的方向进化，就如同自然界的生物的进化过程一样，是向着更加适应环境的方向进行的。以上给出的自适应算法，在种群中个体适应度较小时，进化操作的概率较大，有利于种群向好的方向进化，种群中个体适应度较大时，进化概率较小，有利于保护现有种群，所以改进后可以较快的找到最优解。总之，通过自适应改进后保护了优秀个体，加速了适应度较差的个体进化速度，有助于算法逐渐靠近最优状态 [7] 。 3.2 与模拟退火算法结合的DNA算法 模拟退火算法 简称SAA (Simulated Annealing Algorithms)),该算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 模拟退火算法最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神 第16页 共27页