遗传算法学习作业.docVIP

遗传算法学习总结 1.1 概述 遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的自适应概率性随机化迭代有哪些信誉好的足球投注网站算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想，它的基本思想是基于Darwin进化论和Mendel的遗传演说。Darwin进化论最重要的是适者生存的原理，它认为每一代种群总是向着前进方向发展，越来越适应环境。每一个个体都有继承前代的特性，但不是完全继承，会产生一些新特性。最终只有适应环境的特征才能被保留下来。Mendel遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。一条染色体中存在很多基因，每个基因有自己的位置并控制着外部特征；基因的产生和变异直接影响到个体的特性是否能适应环境。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 遗传算法正是借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。 与自然界相似，遗传算法对求解问题的本身一无所知，从代表问题可能潜在解集的一个种群(population)开始，每一个种群则由经过基因(gene)编码(coding)的一定数目的个体 (individual)构成。每个个体实际上是染色体(chromosome)带有特征的实体。把问题的解表示成染色体，并基于适应值来选择染色体，遗传算法所需要的仅是对算法所产生的每个染色体进行评价，使适应性好的染色体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也就是假设解。然后，把这些假设解置于问题的“环境”中，也即在一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制，淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，直到最适合环境的值。 1.2遗传算法的基本原理和特点 1.2.1 算法原理 在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群，再对这个新种群进行下一轮进化，这就是遗传算法的基本原理。 遗传算法的主要步骤如下： 1)随机产生一个由确定长度的特征串组成的初始群体； 2)对串群体迭代地执行步骤(1)和(2)，直到满足停止准则： (1)计算群体中每个个体的适应值。 (2)应用复制、杂交和变异算子产生下一代群体。 3)把在任一代中出现的最好的个体串指定为遗传算法的执行结果。这个结果可以表示问题的一个解(或近似解)。 基本遗传算法的流程图如图1-1，其中GEN是当前代数，M为每代种群中最大个体数。 图1-1 基本遗传算法的流程图 1.2.2 算法特点 遗传算法的特点如下： 1) 遗传算法中不包含待解决问题所持有的形态。它是从改变基因的配置来实现问题的整体优化的，因而属于自下而上的优化方法； 2) 类似于生物的进化过程，遗传算法处理的是变量集合的编码而非变量本身。它直接对结构对象进行操作，不存在求导和函数连续性的限定； 3) 遗传算法具有内在的隐并行性和更好的全局寻优能力； 4) 遗传算法采用概率化的寻优方法，能自动获取和指导优化的有哪些信誉好的足球投注网站空间，自适应地调整有哪些信誉好的足球投注网站方向，不需要确定的规则。 遗传算法的这些特点已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。 1.3 基本遗传算法的步骤 1.3.1 染色体编码（Chromosome Coding）与解码(Decode) 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值{0，1}所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：x=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。 （1）编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码。设某一参数的取值范围为[U1，U2]，我们用长度为k的二进制编码符号来表示该参数，则它总共产生2k种不同的编码，可使参数编码时的对应关系为： 000000…0000=0→U1 000000…0001=1→U1+ 000000…0010=2→U1+2 … 111111…1111=2k-1→U2 其中，=。 （2）解码：假设某一个体的编码为bkbk-1bk-2…b2b1,则对应的解码公式为 ① 例如：设有参数X∈[2，4]，现用5位二进制编码对X进行编码，得25=32个二进制串（染色体）： 00000,00001,000