![](https://csdnimg.cn/release/download_crawler_static/85711412/bg1.jpg)
一、遗传算法的基本概念
遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗
传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解
的方法,它最初由美国 Michigan 大学 J.Holland 教授于 1975 年首先提出来的,
并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》,
GA 这个名称才逐渐为人所知,J.Holland 教授所提出的 GA 通常为简单遗传算法
(SGA)。遗传算法(Genetic Algorithm )是一类借鉴生物界的进化规律 (适
者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法。其主要特点是
直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的
隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和
指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。
二、遗传算法定义
遗传算法是从代表问题可能潜在的解集的一个种群( population )开始的,
而一个种群则由经过基因( gene )编码的一定数目的个体 (individual) 组成。
每个个体实际上是染色体 (chromosome) 带有特征的实体。染色体作为遗传
物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基
因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中
控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型
到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往
进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰
的原理,逐代( generation )演化产生出越来越好的近似解,在每一代,根
据问题域中个体的适应度( fitness )大小选择( selection )个体,并借助于
自然遗传学的遗传算子( genetic operators )进行组合交叉( crossover )和
变异( mutation ),产生出代表新的解集的种群。这个过程将导致种群像自
然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体
经过解码( decoding ),可以作为问题近似最优解。
遗传算法有 5 个基本组成部分 :
1. 问题的解的遗传表示
2. 创建解的初始种群的方法
3. 根据个体适应值对其进行优劣判定的评价函数
4. 用来改变复制过程中产生的子个体遗传组成的遗传算子
5. 遗传算法的参数值
遗传算法的基本运算过程如下:
a) 初始化:设置进化代数计数器 t=0,设置最大进化代数 T,随机生成 M
个个体作为初始群体 P(0)。
b) 个体评价:计算群体 P(t)中各个个体的适应度。
c) 选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接
遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择
操作是建立在群体中个体的适应度评估基础上的。
d) 交叉运算;将交叉算子作用于群体。所谓交叉是指把两个父代个体
的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心
作用的就是交叉算子。
评论0
最新资源