遗传算法研究综述 文献综述.doc

遗传算法研究综述+文献综述

1遗传算法的定义和起源遗传算法(ic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,由密歇根大学的约翰•霍兰德和他的同事于二十世纪六十年代在对细胞自动机(英文:cellular automata)进行研究时率先提出, 并于1975年出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》,GA这个名称才逐渐为人所知,约翰•霍兰德教授所提出的GA通常为简单遗传算法(SGA)。在二十世纪八十年代中期之前,对于遗传算法的研究还仅仅限于理论方面,直到在伊利诺伊大学召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多,遗传算法逐渐进入实际应用阶段。1989年,纽约时报作者约翰•马科夫写了一篇文章描述第一个商业用途的遗传算法--进化者(英文:Evolver)。之后,越来越多种类的遗传算法出现并被用于许多领域中,财富杂志500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他组合优化问题。8025
遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(inpidual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(ic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解[1]。
遗传算法综述
式中为决策变量,为目标函数式,式2-2、2-3为约束条件,U是基本空间,R是U的子集。满足约束条件的解X称为可行解,集合R表示所有满足约束条件的解所组成的集合,称为可行解集合。
遗传算法的基本运算过程如下:
a)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。
b)个体评价:计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算;将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。
e)变异运算:将变异算子作用于群体。即是对群