遗传算法综述

《遗传算法综述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法(综述)一、什么是GA遗传算法(GeneticAlgorithms简称GA)是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。维基百科。二、GA的起源及发展50年代末60年代初,生物学家A．S．Fraser和H．J．Bremermann等人试图通过计算的方法来模拟生物界“遗传与选择”的进化过程,这便是GA的雏形。1967年Bagley在其博士论文中首次提出了“遗传算法”这一术语。到60年代中

2、期，美国Michigan大学的JohnHol－land在A．S．Fraser和H．J．Bremermann等人工作的基础上提出了位串编码技术。这种编码既适于变异操作，又适于交配（即杂交）操作，并且强调将交配作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“AdaptationinNaturalandArtificialSystems”．之后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传

3、算法的通用编码技术和简单有效的遗传操作为其广泛、成功的应用奠定了基础。http://blog.csdn.net/neupioneer/archive/2004/09/24/115989.aspx20世纪80年代中期以来是遗传算法和进化计算的蓬勃发展期,多个相关国际会议在世界各地定期召开。1985年,在美国卡耐基·梅隆大学召开第一届国际遗传算法会议ICGA’85,以后每两年举行一次。1989年Goldberg所著的《搜索、优化和机器学习中的遗传算法》对遗传算法理论及其多领域的应用展开了较为全面的分析和例证

4、。1992年,Michalewicz出版了《演化程序———遗传算法与数据编码的结合》,推动了遗传算法应用于最优化问题。1997年5月,IEEE的TransactionsonEvolutionaryComputation创刊。我国对于GA的研究起步较晚,不过从20世纪90年代以来一直处于不断上升中。一、遗传算法理论遗传算法的研究主要包括三个领域：遗传算法的理论与技术；用遗传算法进行优化；用遗传算法进行分类系统的机器学习。其中，遗传算法的理论与技术研究主要包括编码、交叉运算、变异运算、选择运算以及适应度评价

5、等问题。1.理论基础遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们

6、往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优

7、解。百度百科。Holland的遗传算法常被称为简单遗传算法（SGA），其操作对象是一群二进制串（称为染色体、个体），即种群（population）。在此，每个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此一代代演化下去，直到满足期望的终止条件。需要指出的是，目前的遗传算法已不再局限于二进制编码。Z．Michalewicz将不同的编码策略（即不同的数据结构）与遗传算法的结合称为演化程序（EvolutionProgram）。遗

8、传算法的基础理论主要以收敛性分析为主,即群体收敛到优化问题的全局最优解的概率。从整体上讲,可以分为基于随机过程的收敛性研究和基于模式理论的收敛性分析。1)随机模型理论对于有限的编码空间和有限的群体,遗传算法的搜索过程可以表示为离散时间的马尔可夫链模型,从而可以采用已有的随机过程理论进行严密分析:①RudolphRudolphG.ConvergencePropertiesofCaucricalGGeneticAlgorithems[j].IE