遗传算法分析

遗传算法分析摘要:遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。本文分析了遗传算法选择、交叉、变异三个重要算子的作用，并给出了遗传算法的基本流程，同时对遗传算法的优点和缺点进行了分析。关键字:遗传算法；选择；交叉；变异引言遗传算法是一种基于自然选择和基因遗传学原理的优化搜索方法，它在计算机上模拟生物的进化过程和基因的操作，并不需要对象的特定知识，也不需要对象的搜索空间是连续可微的，它具有全局寻优的能力。一些用常规的优化算法有效解决的问题，采用遗传算法寻优技术往往能得到较好的效果。遗传算法将“优胜劣汰，适者生存”的生物进化原理引入待优化参数形成的编码串群体中，按照一定的适配值函数及一系列遗传操作对各个个体进行筛选，从而使适配值高的个体被保留下来，组成新的群体。新群体包含上一代的大量信息，并且引入了新的优于上一代的个体，这样周而复始，群体中各个个体的适应度不断提高，直至满足一定的极限条件。此时群体中适配值最高的个体即为待优化参数的最优解。正是由于遗传算法独具的工作原理，使它能够在复杂空间进行全局优化搜索，并且具有较强的鲁棒性。常规的优化算法，如解析法，只能得到局部最优而非全局最优，且要求目标函数连续光滑及可微信息；枚举法虽然克服了这些缺点，但计算效率太低，对于一个实际问题常常由于搜索空间太大而不能将所有的情况都搜索到，即使使用“动态规划”，也会遇到“指数爆炸”的问题，它对于中等规模和适度复杂性问题，也常常无能为力；遗传算法通过对参数空间编码并采用随机选择作为工具来引导搜索过程朝着更有效的方向发展。1遗传算法的基因编码遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的个体，这就是基因编码。目前的常用的编码技术有二进制编码，浮点数编码[1]。二进制编码是目前遗传算法中最常用的编码方法，即是由二进制字符集{0,1}产生通常的0,1字符串来表示问题空间的候选解。二进制编码符合最小字符集原则，便于用模式定理分析，但存在映射误差，有时不能精确的表示结果。浮点数编码相对简单，是指个体的每个基因值用某一范围内的一个实数来表示，个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以也叫真值编码方法。浮点数编码是遗传算法中在解决连续参数优化问题时普遍使用的一种编码方式，具有较高的精度，在表示连续渐变问题方面具有优势，不存在海明悬崖问题。2遗传算法的基本操作操作简单和作用强大是遗传算法的两个主要特点。一般的遗传算法都包含三个基本操作：选择、交叉、变异。1.1选择选择是从一个旧的种群中选择生命力强的个体单位产生新种群的过程。这是一个优胜劣汰的过程。选择操作是建立在群体中个体的适应度评估基础上的，它是在模仿自然选择现象。在自然群体中，适应度是由一个生物为继续生存而捕食、生长和繁殖后代的过程中克服障碍的能力决定的。在选择过程中适应度是该个体被选择或淘汰的决定性因素。选择操作可以以多种算法的形式实现，一种较为简单的方法是使用轮盘赌的转盘上的成比例的一块区域。在该方法中，各个个体的选择概率和其适应度值成比例。很显然，概率反映了个体的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大，其被选择的概率就越高，在其下一代中产出的后代就越多。1.2交叉在自然界生物进化过程中起核心作用的是生物遗传基因的重组和变异。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。通常交叉算法和基因的编码方式有关。二进制编码常采用的交叉算法有单点交叉、多点交叉、均匀交叉、洗牌交叉等。浮点数交叉算法有离散重组、中间重组、线性重组、扩展线性重组等[3]。1.3变异尽管复制和交叉操作很重要，在遗传算法中是第一位的，但不能保证不会遗漏一些重要的遗传信息。在人工遗传系统中，变异用来防止这种不可弥补的遗漏。遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值[4]。遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。相互配合是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。相互竞争是指当通过交叉已形成所期望的结果时，变异操作有可能破坏这些结果。3遗传算法的求解步骤用遗传算法求解最优化问题的基本步骤都是的一样，只是对于个别环节的实现细节会有一些不同，如编码方式，适应度的计算，采用的交叉和变异算法等。基本步骤如下：1)基因编码，参数初始化。随机生成初始种群P(0)，并设置算法的最大进化代数tmax，种群规模N，初始代数t=0；2)个体评价。用所构造的适应度函数来计算P(t)中每个个体的适应度F(xi)，适应大小表示了该个体的好坏。并以概率Pi从P(t)中随机选取一些个体构成一个种群P(t)。Pi的计算公式如下：Pi=𝐹𝑖∑𝐹𝑗𝑁𝑗=1⁄(𝑖=1,2,…,𝑁)3)选择操作。根据各个体的适应度，选用合适的选择算子，从第t代群体中选择一些个体成为中间群体p(t)；4)交叉操作。将种群p(t)中的个体随机搭配成对，对于每对个体，以概率Pc交换它们之间的基因，得到一个规模为N的杂交后群体；5)变异操作。对杂交后的群体，以概率Pm改变某一个或某一些基因位上的基因值，生成新一代群体P(t+1)；6)终止判断。若终止条件（①最优个体保持20代不变；②t=tmax；③群体平均适应度与最优个体适应度之差小于ε，ε是任意小的正实数；只要满足其中一条就终止）满足，则算法终止，把种群Pt中的最好个体译码，然后作为最优解输出，算法结束；否则，t=t+1，转到2继续迭代[5]。上述步骤的流程图如图1所示。图1遗传算法流程图4对遗传算法的评价作为一种模拟自然界物种进化的优化算法，遗传算法与传统的优化算法有本质的不同。传统优化算法，大多依靠目标函数的梯度等信息，寻找一个确定的搜寻方向，通过步进搜索，逐渐逼近最优解[6]。遗传算法是一种并行随机搜索算法，与传统优化算法相比，有以下特点：1)遗传算法对所求解的优化问题没有太多的数学要求，由于它的进化特性，搜索过程中不需要问题的内在性质，对于任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的都可处理。2)遗传算法是一种群体性优化算法，而不是普通单一个体优化算法。进化算子的各态历经性使得遗传算法能够非常有效地进行概率意义的全局搜素。3)遗传算法具有固有并行性，能够并行计算。4)遗传算法易于同其他算法融合，可扩展性良好。遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。否是开始编码、初始化个体评价选择操作交叉操作变异操作译码得最优解满足条件结束种群P(t+1)5)遗传算法利用概率转移规则，而不是确定性规则实现最优解搜寻。虽然遗传算法有广泛的应用范围，但是其理论基础并不完善，这也导致其“早熟”和局部搜索能力弱的缺点。所谓早熟，即是算法在未搜索到全局最优解时，种群被大量局部最优解占有，导致算法停滞不前，最终不能得到全局最优解。遗传算法中，通常设定变异的概率很小，而选择和交叉算子信息交互量小，会造成适应性较强的解的局部相似性。当种群陷入局部最优解空间附近时，很难跳转到其他解空间，从而形成早熟[7]。采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。局部搜索能力弱，是源于遗传算法本身是一种随机搜索算法，即使搜索到最优解附近，算法依然没有确定的搜索方向，相比其他有确定进化方向的优化算法，遗传算法在靠近最优解附近时，并不能快速的找到最优解。5总结进化论的自然选择过程蕴涵着一种搜索和优化的先进思想。遗传算法正是吸取了自然生物系统“适者生存，优胜劣汰”的进化原理，从而使它能够提供一个在复杂空间中进行鲁棒搜索的方法，为解决许多传统的优化方法难以解决的优化问题提供了新的途径。同时，遗传算法自身也存在一些问题，有待我们去改进和完善。参考文献[1]余有明,刘玉树,阎光伟.遗传算法的编码理论与应用[J].计算机工程与应用,2006,(3).[2]张汝波,刘冠群,吴俊伟.计算智能基础[M].哈尔滨:哈尔滨工业大学出版社,2013.6.[3]郑立平,郝忠孝.遗传算法理论综述[J].计算机工程与应用,2003,(21).[4]王珊珊.遗传算法的理论基础及应用[J].科协论坛,2008,(9):57-58.[5]张春霞,王蕊.基于遗传算法求解TSP问题的算法设计[J].安阳工学院学报,2007,(4):57-60.[6]李响.一种改进遗传算法及软核实现研究[D].西安电子科技大学,2012.[7]石玉,于盛林.一种改进的遗传算法[J].合肥工业大学学报：自然科学版,2002,(3):403-406.