遗传算法概述

遗传算法概述摘要：遗传算法（geneticalgorithms,GA）是人工智能的重要新分支，是基于达尔文进化论，在微型计算机上，模拟生命进化机制而发展起来的一门学科。它根据适者生存、优胜劣汰等自然进化规则来进行搜索计算机和问题求解。对许多用传统数学难以解决或明显失效的非常复杂的问题，特别是最优化问题，GA提供了一个行之有效的新途径。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业控制工程领域的成功应用，这种算法受到了广泛的关注。本文旨在阐述遗传算法的基本原理、操作步骤和应用中的一些基本问题，以及为了改善SGA的鲁棒性而逐步发展形成的高级遗传算法（refinegeneticalgorithms,RGA）的实现方法。一、遗传算法的基本原理和特点遗传算法将生物进化原理引入待优化参数形成的编码串群体中，按着一定的适值函数及一系列遗传操作对各个体进行筛选，从而使适值高的个体被保留下来，组成新的群体，新群体包含上一代的大量信息，并且引入了新一代的优于上一代的个体。这样周而复始，群体中各个体适值不断提高，直至满足一定的极限条件。此时，群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂的空间进行全局优化搜索，并且具有较强的鲁棒性；另外，遗传算法对于搜索空间，基本上不需要什么限制性的假设（如连续性、可微及单峰等）。同常规优化算法相比，遗传算法有以下特点。（1）遗传算法是对参数编码进行操作，而非对参数本身。遗传算法首先基于一个有限的字母表，把最优化问题的自然参数集编码为有线长度的字符串。例如，一个最优化问题：在整数区间【0，31】上求函数f(x)=x2的最大值。若采用传统方法，需要不断调节x参数的取值，直至得到最大的函数值为止。而采用遗传算法，优化过程的第一步的是把参数x编码为有限长度的字符串，常用二进制字符串，设参数x的编码长度为5，“00000”代表0，“11111”代表31，在区间【0，31】上的数与二进制编码之间采用线性映射方法；随机生成几个这样的字符串组成初始群体，对群体中的字符串进行遗产操作，直至满足一定的终止条件；求得最终群体中适值最大的字符串对应的十进制数，其相应的函数值则为所求解。可以看出，遗传算法是对一个参数编码群体进行的操作，这样提供的参数信息量大，优化效果好。（2）遗传算法是从许多点开始并行操作，并非局限于一点，从而可有效防止搜索过程收敛于局部最优解。（3）遗传算法通过目标函数计算适值，并不需要其他推导和附加信息，因而对问题的依赖性较小。（4）遗传算法的寻优规则是由概率决定的，而非确定性的。（5）遗传算法在解空间进行高效启发式搜索，而非盲目的穷举或完全随机搜索。（6）遗传算法对求解的优化问题没有太多的数学要求。由于它的进化特性，它在解的搜索中不需要了解问题的内在性质。遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的，甚至是混合的搜索空间。（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度。二、遗传算法的模式理论1、模式一个模式（schemata）就是一个描述种群在位串的某些确定位置上具有相似性的一组符号串。为了描述一个模式，在用以表示位串的两个字符｛0，1｝中加入一个通配符“*”，就构成了一个表示模式用的3个字符的符号表｛0，1，*｝。因此用三个元素符号表｛0，1，*｝可以构造出任意一种模式。当一个模式与一个特定位串相匹配时，意味着该模式中的1与位串中的1相匹配，模式中的0与位串中的0相匹配，模式中的“*”与位串中的0或1相匹配。例如，模式00*00匹配了两个位串，即｛00100，00000｝；模式*111*可以和｛01110，01111，11110，11111｝中的任何一个相匹配；模式0*1**则匹配了长度为5，第一位为0、第三位为1的八个位串，即｛00100，00101，00110，00111，01100，01101，01110，01111｝。模式的思路提供了一种简单而有效的方法，使能够在有限符号表的基础上讨论有限长位串的严谨定义的相似性。应强调的是，“*”只是一个代表其他符号的一个元符号，它不能被遗传算法直接处理，但可以据此计算出所有可能的模式。一般地，假定符号表的基数是k，例如｛0，1｝的基数是2，则定义在该符号表上的长度为l的位串中，所有可能包含的最大模式数为（k+l）l,原因是在l个位置中的任何一个位置上即可以取k个字符中的任何一个又可以取通配符“*”，即共有k+l个不同的表示，则l个位置的全排列数为（k+l）l。例如，对长度l=5,k=2(对应0，1)，则会有3×3×3×3×3=35=243=（k+l）l种不同的符号串，而位串的数量仅为kl=25=32。可见，模式的数量要大于位串的数量。对于由0、1和*定义且长度为l的符号串所能组成的最大模式数为（2+l）l。对于任一长度为l的给定位串，当任一位置上只有两种不同表示时，所含模式数为2l个，因此对于含有n个位串个体的种群可能包含的模式数在2l~n×2l之间。不难看出，遗产算法正是利用种群中位串之间的众多的相似性以及适值之间的相关性，来引导遗传算法进行有效地搜索。为了区分不同类型的模式，对模式H定义两个量：模式位数（order）和模式的定义长度（defininglength）分别表示为O(H)和(H)。O(H)是H中有定义的非“*”位的个数，模式定义长度(H)是指H中左右两端有定义位置之间的距离。这两个量为分析位串的相似性及分析遗传操作对重要模式的影响提供了基本手段。2、复制对模式的影响设在给定时间（代）t，种群A（t）包含m个特定模式H，记为m=m(H，t)在复制过程中，A（t）中的任何一个位串Ai以概率Pi=fi/∑fi被选中并进行复制。假如选择是有放回的抽样，且两代种群之间没有交叠（即若A（t）的规模为n，则在产生A（t+1）时，必须从A（t）中选n个位串进匹配集），可以期望在复制完成后，在t+1时刻，特定模式H的数量为：m(H,t+1)=m(H,t)nf(H)/∑fi其中，f(H)是在t时刻对应模式H的位串的平均适值，因为整个群的平均适值f=∑fi/n,则上式又可写为m(H,t+1)=m(H,t)fHf)(经过复制操作后，下一代中特定模式的数量H正比于所在位串的平均适值与种群平均适值的比值。若f(H)f,则H的数量将增加，若f(H)f，则H的数量将减少。即若包含H的个体位串的平均适值高于当前种群中所有个体位串的平均适值，则种群包含特模式的下一代中的数量将增加；反之，减少。操作中模式的增减在复制中是并行的，这恰恰表现了遗传算法隐含的并行性。为了进一步分析高于平均适值的模式数量的增长，假设fcfHf)(（c是一个大于零的常数），则上式可写为：),()1(),()1,(tHmcfcftHmtHm从原始种群开始（t=0），并假定是一个稳态的值，则有)1)(0,()1,(cHmtHmt可见，对于高于平均适值的模式数量将按指数规律增长（c0）。从对复制的分析可以看到，虽然复制过程成功的以并行方式控制着模式数量以指数规模增减，但由于复制只是将某些高适值个体全盘复制，或者淘汰某些低适值个体，而决不会产生新的模式结构，因而性能的改进是有限的。2、交叉对模式的影响交叉过程是位串之间有组织的随机的信息交换。交叉操作对一个模式H的影响与模式的定义长度(H)有关，(H)越大，模式H被分裂的可能性越大，因为交叉操作要随机选择出进行匹配的一对位串上的某一随机位置进行交叉。显然(H)越大，H的跨度就越大，随机交叉点落入其中的可能性就越大，从而H的存活率就降低。例如位串长度l=7，有如下包含两个模式的位串A为A=01111000H1=*1****0,(H1)=5H2=***10**,(H2)=1随机产生的交叉位置在3和4之间A=1000011H1=0****1*,Pd=5/6H2=**10***,Pd=1/6模式H1定义长(H1)=5，若交叉点始终是随机地从l-1=7-1=6个可能的位置选取，则模式H1被破坏的概率为Pd=(H1)/(l-1)=5/6它的存活概率为Ps=1-Pd=1/6类似的，模式H2的定义长度(H2)=1，它被破坏的概率为Pd=1/6,它存活的概率为Ps=1-Pd=5/6.因此，模式H1比模式H2在交叉中更容易受到破坏。一般情况下可以计算出任何模式的交叉存活概率的下限为Ps1)(1lH在上面的讨论中，均假设交叉的概率为1。若交叉的概率为Pc(即在选出进匹配集的一对位串上发生交叉操作的概率)，则存活率为Ps1)(1lHPc在复制交叉之后，模式的数量则为PsfHftHmtHm)(),()1,(即1)(1)(),()1,(lHPcfHftHmtHm因此，在复制和交叉的综合作用之下，模式H的数量变化取决于其平均适值的高低和定义长度的长短，f(H)越大，(H)越小，则H的数量就越多。3、变异对模式的影响变异是对位串中的单个位置以概率Pm进行随机替换，因而它可能破坏特定的模式。一个模式H要存活，意味着它所有的确定位置都存活。因此，由于单个位置的基因值存活的概率为1-Pm，而且由于每个变异的发生是统计独立的，因此，一个特定模式仅当它的O（H）个确定位置都存活是才存活，从而得到经变异后，特定模式的存活率为（1-Pm）O(H),即（1-Pm）自乘O(H)次，由于一般情况下Pm1,H的存活率可表示为（1-Pm）O(H)≈1-O(H)Pm综合考虑复杂、交叉和变异操作的共同作用，则模式H在经历复制、交叉、变异操作之后，在下一代中的数量可表示为PmHOlHPcfHftHmtHm)(11)(1)(),()1,(也可近似表示为PmHOlHPcfHftHmtHm)(1)(1)(),()1,(由上述分析可以得出结论：定义长度短的、确定位数少的、平均适值高的模式数量将随着代数的增加呈指数增长。这个结论称为模式理论或遗传算法基本定理。根据模式理论，随着遗传算法一代一代地进行，那些定义长度短的，位数少的，高适值的模式将越来越多，因而可期望最后得到的位串的性能越来越得到改善，并最终趋向全局最优点。三、遗传算法中适值的调整为了使遗传算法有效的工作，必须保持种群内位串的多样性和位串之间的竞争机制。现将遗传算法的运行分为开始、中间和结束三个阶段来考虑：在开始阶段，若一个规模不太大的种群内有少数非凡的个体（适值很高的位串），按通常的选择方法，这些个体会被大量的复制，在种群中占有大的比重，这样就会减少种群的多样性，导致多早收敛，从而可能丢失一些有意义的搜索点或最优点，而进入局部最优；在结束阶段，即使种群内保持了很大的多样性，但若所有或大多数个体都有很高的适值，从而种群的平均适值和最大值相差无几，则平均适值附近的个体和具有最高适值的个体被选中的机会相同，这样选择就成了一个近乎随机的步骤，适值的作用就会消失，从而使搜索性能得不到明显的改进。因此，有必要对种群内各位串的适值进行有效的调整，既不能相差太大，又要拉开档次，强化位串之间的竞争性。1、窗口法它是一种简单有效的适值调整方法，调整后的个体适值为Fj=fj-(fmin-a)其中，fj为原来个体的适值；为每代种群中个体适值的最小值；a为一常数。在进化的后期窗口法增加了个体之间的差异。2、函数归一法该法是将个体适值转换到最大值与最小值之间成一定比例的范围之内，这一范围由选择压力ksp决定。具体步骤如下：（1）根据给定的选择压力ksp,求种群中适值调整后的适值最小值为kspffF1maxminmin其中fmin和fmax是调整前种群个体适值的最小值和最大值。适值调整后种群中适值最大值为Fmax=kspFmin（2）计算线性适值转换的斜率为△F=minmaxminmaxffFF（3）计算每个个体的新适值为minFFj△min)(ffjF其中，fj为调整前第j个个体适值。在进化的早期，函数归一