基于遗传算法的分类方法的探究-控制理论与控制工程专业论文.docx

摘要破译世界上最巨量信息的“天书”——“人类DNA序列”是= 摘要 破译世界上最巨量信息的“天书”——“人类DNA序列”是= 十一世纪最重要的任务之一，对人类DNA序列进行分类又是这一任务 中的重要组成部分。本文选择对人类DNA序列进行分类作为研究的内 容，主要解决了以下三个问题： ①将遗传算法应用于分类系统中，构造出新的分类方法； ②对遗传算法进行改进，并将其应用于分类系统中，使分类系 统的性能有了很大的改善； ③用实现的分类系统对DNA序列进行分类。 在分类方法中，分类的准确率是至关重要的。为了提高分类的 准确率，本文从以下方面进行了深入的研究：首先利用遗传算法的优 点，将遗传算法应用于分类系统中，得到了基于基本遗传算法的分类 方法，提高了分类的准确率，使该分类方法具有很强的适应性和可扩 充性．然后提出了对基本遗传算法的改进方案——优化遗传算法，并 将其用于分类系统，得到了基于优化遗传算法的分类方法，进一步提 高了分类的准确率。最后将两种分类方法用于“DNA序列的分类”。 下面是基于基本遗传算法的分类算法的基本思想： (1)编码方法，编码采用二进制编码，从位串空间转换到编码空 间。 (2)分类器，是由一组特定形式的知识构成的。为了便于遗传算 法操作，规则的条件部分按字符集10，】。撑}编码。 (3)遗传算予设计：遗传算子首先采用传统的算子，然后针对传 统算予进行改进。 ①选择算予，采用按适应度比例的轮盘赌选择法，其中每个个体 被选择的期望数量与其适应值和群体平均适应值的比例有关。首先计 算每个个体的适应值，然后计算出此适应值在群体适应值总和中所占 的比例，作为该个体在选择过程中被选中的概率。轮盘赌选择的具体 实施过程为，将个体选择概率按由高到低排序。然后计算他们的累积 概率，并产生一个[O，l】之间的随机数，当累积概率大于随机数时，就得 概率，并产生一个[O，l】之间的随机数，当累积概率大于随机数时，就得 到了被选择的个体。②交叉算子，通常采用的方法包括一点交叉、两 点交叉、多点交叉、一致交叉等。③变异算于，通常在遗化算法·I，， 按变异概率P。随机翻转某位等位基因的二进制字符值来实现变异算 子。 (4)群体设定，根据模式定理，群体规模对遗传算法的性能影响 很大。若群体规模为n，则遗传算子可以从这r1个个体中生成和检测 O(n3)个模式。群体规模越大，群体中个体的多样性越高，算法陷入局 部解的危险就越小；但随着群体规模的增大，计算量也显著增加；若 群体规模太小，使遗传算法的搜索空间受到限制，则可能产生未成熟 收敛的现象。 (5)遗传算法迭代过程终止方法一般有： ①设定最大代数：②根据群体的收敛程度来判断：③根据算法的 立即性能和再现性能的变化进行判定；④在采用精英保留选择策略的 情况下，按每代最佳个体的适应值的变化情况确定。 (6)遗传算法执行的流程是：①初始化(包括遗传参数、分类器、 环境、信任分配参数、循环次数)；②对生成的初始群体进行检测生成 初始的消息；③检查消息是否匹配分类器。若匹配，将其放入桶队列 中；④执行信任分配算法；⑤对分类器执行遗传操作(选择、交叉、 变异)：⑥判断是否符合结束条件。若是，结束；否则，转到第③步继 续执行。 为了进一步提高分类的准确率，本文提出的基于优化遗传算法的 分类方法，其主要策略如下： 首先让父个体进行交叉、变异操作，得到下一代个体(即予个体)： 然后将子个体的适应值与其父个体的适应值进行比较，如果子个体的 适应值大于父个体的适应值，则用子个体替代父个体作为下一代群体 中的个体：否则，保留父个体到下一代群体中，作为群体中的个体。 对于选择算子，首先对群体中的各个个体按适应度进行排序(降 序)，然后再进行选择。 对于变异算子，如果对染色体位串的等位基囚按变异概率进行反 对于变异算子，如果对染色体位串的等位基囚按变异概率进行反 转，山于变异概率较小，变异操作很少发生，使得计算机的时M人jf} 浪费在这上面，遗传算法的效率很低。因此可以对个体进行判断是否 发生变异，若变异，则对该个体随机选择等位纂冈进行变异操作，这 样可以大大提高算法的效率。 最后本文将基于遗传算法的分类系统用于DNA序列的分类rh并 对其分类效果进行分析。 基于基本遗传算法的分类算法应用于DNA序列的分类中分类准确 率为97．80％。而采用优化遗传算法的分类系统对DNA序列进行分类， 分类准确率为：99．45％。另外，对改进后的算法的动态分析发现，其 动态性能非常好，随遗传代数的增加，分类准确率会进一步提高，并 且会接近于100％。而基于基本遗传算法的分类系统，随分类次数的增 加，分类准确率一般会稳定在95％左右，出现局部收敛现象。 通过实验可以看出，本文提出的优化遗传算法能够在一定程度上 提高分类器的分类准确率，