下载文档原格式
1 遗传算法1.1 遗传算法的定义遗传算法(GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。
遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。
这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。
另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。
然后形成初始的种群，最后进行选择、交叉和变异的操作。
1.2遗传算法的重要应用在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。
在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。
其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。
1.3 遗传算法的特点遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。
遗传算法的概念
遗传算法（Genetic Algorithm）是基于生物学进化理论的一种优化算法。
它是模拟自然界的进化过程，通过筛选、交叉、变异等元素不断筛选出能够适应环境的个体，最终得到最优解或次优解的一种算法。
遗传算法的基本思想是将问题看作一个个体，使用种群的方式不断迭代，将群体中优劣个体进行适应度评估并进行优胜劣汰，简单来说就是不断筛选出最优的解决方案来。
遗传算法被广泛应用于各类优化问题，例如旅行商问题、机器学习和函数优化等。
什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。
举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。
同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。
遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。
现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
它是现代有关智能计算中的关键技术之一。
1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。
这种学说认为，生物要生存下去，就必须进行生存斗争。
生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。
在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。
遗传算法发展前景概况
（华北电力大学电气与电子工程学院，北京102206）
摘要：遗传算法是一种基于生物进化自然选择和群体遗传机理的，适合于复杂系统优化的自适应概率优化技术，近年来，因为遗传算法求解复杂优化问题的巨大潜力和在工业工程领域的成功应用，这种算法受到了国内外学者的广泛关注，本文介绍了遗传算法研究现状和发展的前景，概述了它的理论和技术，并对遗传算法的发展情况发表了自己的看法。
关键词：遗传算法; 遗传算子；进化计算；编码
GENERAL GENETIC ALGORITHM DEVELOPMENT PROSPECT
(North China Electric Power University Electrical And Electronic Engineering Institute,Beijing102206) ABSTRACT: Genetic algorithm is a kind of natural selection and based on biological evolution of genetic mechanism, group suitable for complex system optimization adaptive probability optimization technique, in recent years, because genetic algorithm for solving complex optimization problem in the huge potential and the successful application of industrial engineering, this algorithm was wide attention of scholars at home and abroad, this paper introduces the current research status and development of genetic algorithm, summarizes the prospect of its theory and technology of genetic algorithm and the development of published opinions of his own.
KEY WORD: Genetic algorithm; Genetic operator; Evolutionary computation; coding
1.引言
现在，遗传算法正在迅速发展，遗传算法与其很强的解决问题能力和适合于复杂系统的自适应优化技术渗透到研究和工业工程领域，在电力系统，系统辨识,最优控制，模式识别等领域有了很广泛的应用，取得了很好的效果。
2.遗传算法基本思想
遗传算法是建立在自然选择和群体遗传学基础上的随机，迭代和进化，具有广泛适用性的搜索方法，所有的自然种类都是适应环境而生存，这一自然适用性是遗传算法的主要思想。
遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则经过基因编码的一定数目的个体组成。
每个个体实际上是染色体带有特征的实体。
染色体作为遗传物质的主要载体，其内部基因决定了个体的外部表现。
因此，在一开始就要实现外部表现到内部基因的映射，即编码工作，通常采用二进制码。
初始种群产生之后，按照适者生存和优胜劣汰的原则，逐代演化产生出越来越好的近似解。
在每一代，根据问题域中个体的适应度大小选择个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集和种群，这种过程将导致种群像自然进化那样产生比前代更适应于环境的后代种群，末代种群中的最有个体经过解码，可以作为问题近似最优解。
遗传算法采纳了自然进化模型，如选择，交叉，变异等，计算开始时，种群随机初始化产生一定数目的N个个体，并计算每个个体的适应度函数，如果不满足优化准则，就开始新一代的计算。
为了产生下一代，按照适应度选择个体父代进行基因重组二产生子代。
所有的子代按一定的概率进行变异，子代取代父代构成新一代，然后重新计算子代的适应度。
这一过程循环执行，直到满足优化准则为止。
3.遗传算法基本操作
（1）编码。
由于遗传算法不能直接处理解空间的解数据，因此在搜索之前必须先通过编码把解空间变量表示成遗传空间的位串结构数据，即染色体。
（2）生成初始化种群。
生成初始群体遗传算法是群体型操作算法，在对解空间变量进行编码后，紧接着就随机产生N个染色体，构成遗传算法的初始种群，然后以这个初始种群为起始点开始迭代搜索。
（3）评价个体适应度。
遗传算法在搜索进化过程中一般不需要外部信息，仅用适应度函数值来评价个体或解的优劣，并作为以后遗传操作的依据。
适应度函数表明个体对环境适应度的强弱，不同的问题，适应度函数的定义方式也不同，对函数优化问题，一般取目标函数作为适应度函数。
（4）选择。
选择的目的是为了从当前群体中选出生命力强的染色体，使它有机会保留以繁殖后代。
判断染色体优良与否的准则就是各自的适应度值，个体适应度值越大，其被选择机会就越多。
选择操作体现了生物进化的思想。
选择的方法根据不同的问题，采用不同的选择算法。
（5）交叉。
交叉是把两个父代个体的部分结构加以替换重组而生成新个体的操作，也称基因重组。
交叉的目的是为了能在下一代中产生新个体，通过交叉操作，遗传算法的搜索能力得到飞跃的提高。
交叉是遗传算法得到新优良个体的最重要的手段。
交叉的方法有很多。
如单点交叉，多点交叉，均匀交叉。
（6）变异。
即交叉之后子代的变异。
变异操作时模拟自然界生物进化中染色体上基因发生突变的现象，从而改变染色体的结构和物理性状。
在遗传算法中，变异算子通过按变异概率P随机反转某位等位基因的二进制字符值来实现。
选择和交叉基本上完成了遗传算法的大部分搜索功能，二变异则增加了遗传算法找到接近最优解的能力。
变异首先在群体中随机的选择一个个体，以一定的概率随机的改变基因串中某个字符的值，变异操作是按位进行的，变异发生的概率极低，它本身是一种随机搜索，但与选择，交叉算子结合在一起，就能避免由复制和交叉算子引起某些信息丢失，从而保证的遗传算法的有效性。
4.遗传算法的研究发展进展和应用
遗传算法研究兴起是在20世纪80年代末和90年代初期，但它的历史起源可追溯至20世纪60年代初期。
早期的研究大多以对自然系统的计算机模拟为主。
如Fraser的模拟研究，他提出了和现在遗传算法十分相似的概念和思想。
Holland和DeJong的创造性研究成果改变了早期遗传算法研究无目的性和理论指导的缺乏。
进入20世纪80年代，遗传算法迎来了兴盛发展时期，无论是理论研究和应用研究都成了很热门的课题。
尤其是遗传算法的应用领域不断扩大。
自从遗传算法出现以来为提高遗传算法解决问题的能力的改进研究一直在进行，包括改善基本操作方法，改善编码方法，改善种群的多样性等三大类。
5.个人对遗传算法发展趋势的几点看法
从自然现象来看，生物演化的目的并非取得某一限制条件下的某些参数优化，而是适应环境。
从这一点来看，虽然目前工程实践上遗传算法的主要应用是用于优化，但真正的结果并非如此。
借鉴遗传算法和生物演化现象的紧密关系，人工生命和复杂性科学的研究与遗传算法有极其密却的联系。
从长远来看。
遗传算法还有以下发展空间：
（1）协同进化。
进化的目标不是形成一个超级物种，一个生态环境进化的结果是物种与环境的相互适应的复杂系统。
因此，应该研究多个物种早共同的生态环境中的协同进化。
对应到遗传算法，可以用于多目标的优化。
（2）学习与进化的相互作用。
可以将学习分为以下几种，（1）宗亲学习：通过血亲遗传祖先的特征遗传给后代。
（2）社团学习：经验和知识在群体中共享。
（3）个体学习：个体生存过程中的学习。
个体学习获得某种所需特性的机会。
但是除了生物界的有性生殖，突变，染色体互换和倒置等等基于生理结构的进化机制外，人类社会还存在基于社会文化的进化机制，个体在社会学
习中得到特有的更高级的进化。
6.结束语
随着计算机技术的高速发展，遗传算法将会更加广泛地应用于国民经济的各个领域，如故障诊断，工业控制，电力系统，系统辨识，神经网络，路径规划，网络通信，社会科学等。
随着遗传算法的深入研究以及与其他学科的互相融合，必将在智能领域占有越来越重要的地位。
随着理论研究的不断深入和应用领域的不断扩展，遗传算法将得到长足的发展。
参考文献
[1]吴启迪，康琦，汪镭，陆金山.自然计算导论[M].上海：上海科学技术出版社，2011
[2]张文修，梁怡.遗传算法的数学基础[M].西安：西安交通大学出版社，2000
[3]李敏强，寇纪淞，林丹，李书全.遗传算法的基本理论与应用[M].北京：科学出版社，2002
[4]巩敦卫，郝国生，周勇，郭一楠.交互式遗传算法原理及其应用[M].北京：国防工业出版社，2007
[5]赵宜鹏，孟磊，彭承靖.遗传算法原理与发展方向综述[J].昆明：云南民族大学学报，2004。
