人工智能-9遗传算法72

计算智能计算智能是信息科学和生命科学相互交叉的前沿领域,是现代科学技术发展的一个重要体现。计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。贝兹德克于1994年提出了一种A，B，C智能模型，从而表示ABC与神经网络、模式识别和智能之间的关系：A：Artificial,表示人工的、符号的（非生物的）B：Biological,表示生物的C：Computational,表示计算的计算智能是一种智力方式的底层认知，它与人工智能的区别是认知层次从中层下降到底层而已。中层系统含有知识，底层系统没有知识。关于A，B，C智能计算智能与人工智能的区别与联系NNNeuralNetwork神经网络PRPatternRecognition模式识别计算智能系统与人工智能系统当一个系统只涉及数值（底层）数据，含有模式识别部分，不应用于人工智能意义上的知识，而且系统能够呈现出：（1）计算适应性（2）计算容错性（3）接近人的计算速度（4）计算误差率与人接近则该系统就是计算智能系统。当一个智能计算系统以非数值方式并加上知识，即为人工智能系统。神经计算（NeuralComputation）神经计算研究的进展1943年麦卡洛奇和皮茨提出神经网络模型的概念（称为MP模型）20世纪60年代威德罗和霍夫提出了自适应线性元件。60年代末到80年代初初与研究的低潮期80年代后又大发展遗传算法遗传算法简称GA（GeneticAlgorithms）是1975年由美国Michigan(密歇根州)大学的J.Holland教授提出的模拟自然界生物遗传学（孟德尔）和生物进化论（达尔文）通过人工方式所构造的一类并行随机搜索最优化方法，是对生物进化过程进行的一种数学仿真，是进化计算的重要形式。1、遗传算法在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性。其主要特点是(1)直接对结构对象进行操作，不存在求导和函数连续性的限定；(2)具有内在的隐含并行性和更好的全局寻优能力；(3)采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关计算智能中的关键技术之一。遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：1、遗传算法（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。如：爱斯基摩人，非洲原始部落2、遗传算法的基本操作为：（1）复制（ReproductionOperator）复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。复制操作可以通过随机方法来实现。首先产生0~1之间均匀分布的随机数，若某串的复制概率为40%，则当产生的随机数在0.40~1.0之间时，该串被复制，否则被淘汰。（2）交叉（CrossoverOperator）复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。交叉体现了自然界中信息交换的思想。交叉有单点交叉、两点交叉、还有一致交叉、顺序交叉和周期交叉。单点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：01010110011110101100:A11100010100101001010:B（3）变异(MutationOperator)变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。17设自变量x介于0～31，求其二次函数的最大值，即：maxf(x)=x2,x∈[0,31]3、遗传算法示例--f(x)=x2极大值问题5001000031xf(x)当然，利用简单的代数运算，很容易求出该问题的解。现在改用遗传算法求解，遗传算法通常包括下述内容：18（1）编码遗传算法首先要对实际问题进行编码，用字符串表达问题。这种字符串相当于遗传学中的染色体。每一代所产生的字符串个体总和称为群体。为了实现的方便，通常字符串长度固定，字符选0或1。本例中，利用5位二进制数表示x值，采用随机产生的方法，假设得出拥有四个个体的初始群体，即：01101，11000，01000，10011。x值相应为13，24，8，19。个体编号初始群体xi适应度f(xi)f(xi)/∑f(xi)f(xi)/fMp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总计∑f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412019（2）计算适应度衡量字符串（染色体）好坏的指标是适应度，它也就是遗传算法的目标函数。本例中适应度比较简单，用x2计算。表中还列出了当前适应度的总和∑f(xi)及平均值f，即：∑f(xi)=f(x1)+f(x2)+f(x3)+f(x4)=1170f=∑f(xi)/4=292.5(293)f(x1)/f=169/293=0.57679...个体编号初始群体xi适应度f(xi)f(xi)/∑f(xi)f(xi)/fMp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总计∑f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412020（2）计算适应度表中第6列的f(xi)/f表示每个个体的相对适应度，它反映了个体之间的相对优劣性。如2号个体的f(xi)/f值最高（1.97），为优良个体，3号个体最低（0.22），为不良个体。个体编号初始群体xi适应度f(xi)f(xi)/∑f(xi)f(xi)/fMp12345671234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总计∑f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412021（3）复制为了将已有的群体变为下一代群体，遗传算法仿效进化论中“自然选择、适者生存”的原则，从旧群体中选择优良个体进行复制。选择的依据是个体适应度的大小，适应度大的个体接受复制，使之繁殖；适应度小的个体则删除掉，遭到淘汰。22（3）复制在本例中，根据相对适应度的大小对个体进行取舍，2号个体性能最优，予以复制繁殖。3号个体性能最差，将它删除，使之死亡，表中的M表示传递给下一代的个体数目，其中2号个体占2个，3号个体为0，1号、4号个体保持为1个。这样，就产生了下一代群体。个体编号初始群体xi适应度f(xi)f(xi)/∑f(xi)f(xi)/fMp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总计∑f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412023（3）复制从表中的第4列可以看出，复制后产生的新一代群体的平均适应度明显增加，由原来的293增加到421。造成平均适应度增加的原因有二：1）淘汰原来最差的个体。使最小适应度由原来的64增加到169。2）增加了优良个体（2号）的个数，使适应度累计值增加。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)1234（1）01101（2）11000（2）11000（4）10011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值1682421576361175443972925624（4）交换通过复制产生的新群体，其性能得到改善，然而它不能产生新的个体。为了产生新的个体，遗传算法仿照生物学中杂交的方法，对染色体（字符串）的某些部分进行交叉换位。被交换的母体都选自经过复制产生的新一代个体（优胜者）。25（4）交换本例中，利用随机配对的方法，决定1号和2号个体、3号和4号个体分别交换，如表中第5列。再利用随机定位的方法，确定这两对母体交叉换位的位置分别从字符长度的第4位及第3位开始。如：3号、4号个体从字符长度第3位开始交换。交换开始的位置称交换点。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)123401101110001100010011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值168242157636117544397292561100010011110111000026（4）交换从表中可以看出，交换后出现优异个体3号，其适应度高达729，大大高于交换前的最大值（576）。与此同时，平均适应度也从原来的421提高到439，说明交换后的群体正朝优良方向发展。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)123401101110001100010011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值1682421576361175443972925627（5）突变遗传算法模仿生物学中基因突变的方法，将个体字符串某位符号进行逆变，即由1变为0或由0变为1。例如，下式左侧的个体于第3位突变，得到新个体如右侧所示。上述（2）～（5）反复执行，直至得出满意的最优解。由上可知，遗传算法参考生物中有关进化与遗传的过程，利用复制、交换、突变等操作，不断循环执行，逐渐逼近全局最优解。遗传算法中，个体是否进行突变以及在哪个部位突变，都由事先给定的概率决定。通常，突变概率很小，约为0.008，本例的第一代中就没有发生突变。100001010028从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发，遵照一定的操作规则，不断迭代计算，逐步逼近最优解。这种搜索技术，有如下特点：4、遗传算法的基本特征从上述简单例子