遗传算法原理

引入

遗传算法(Genetic Algorithm, GA)综合了随机自适应全局搜索算法, 达尔文进化理论(自然选择, 优胜劣汰), 孟德尔生物遗传学说(基因)等理论, 得到的一类随机自适应的全局搜索算法, 是对生物进化过程的一种数学仿真, 为难以找到传统数学模型的问题提供了一种解决方法.

算法原理

遗传算法将问题模拟成一个生物进化的过程, 通过复制, 交叉, 突变等操作产生下一代的解, 并逐步淘汰掉适应度函数值低的解, 增加适应度函数值高的解, 从而在迭代若干次之后, 得到函数值很高的解, 就是我们所搜索的解.

首先介绍概念.

编码与译码

遗传算法的第一步就是对问题的所有可能解进行编码. 编码是一个从解空间到编码空间的映射. 很多结构复杂的问题, 都可以转换为简单的位串形式的编码.

染色体/基因型: 把位串形式的编码整体称为染色体或基因型, 或者个体.
- 编码空间也称为基因型空间或搜索空间
表现型: 一个染色体解码后得到的对应解, 即为原问题的一个解, 称为表现型
- 解空间也称为表现型空间

遗传算法不是直接作用在问题的解空间上, 而是交替地作用在编码空间和解空间上, 在编码空间对个体进行遗传操作, 在解空间对问题的解进行评估.

适应度函数

对问题中每个染色体代表的解的适应能力进行度量的函数, 称为适应度函数. 通过这个函数确定染色体的优劣.

对于优化问题, 适应度函数就是目标函数.

接下来是遗传算法的基本操作

选择

选择一些染色体来产生下一代, 这里需要确定选择策略, 常见的有:

比例选择: 个体被选中的概率与其适应度函数值成正比, 表现更好的染色体更容易被选中. 比例选择等价于遗传算法中常说的轮盘赌算法(Roulette Wheel Selection)

交叉

两条染色体交换部分基因, 构造下一代的两条染色体, 这类需要确定交叉策略

变异

对染色体个体中的某些基因执行异响转化.

除此之外, 遗传算法的性能优化还有以下的几种方法.

精英主义选择(Elitism Strategy)

防止进化迭代过程中产生的最优解被交叉和变异破坏, 将每一代的最优解原封不动地复制到下一代中.

插入

在原来的选择, 交叉, 变异三种基本操作的基础上增加一个插入操作, 插入操作将染色体中的某个随机的片段移位到另一个随机的位置.

算法过程

初始化:
- 初始化以下参数
  - $P_c$ : 交叉发生的概率
  - $P_m$ : 变异发生的概率
  - $M$ : 种群规模
  - $G$ : 终止迭代的代数
  - $T_f$ : 进化过程中, 任何一个个体的适应度函数值超过这个值, 就可以停止迭代
- 随机产生第一代种群population
迭代执行
- 计算population中每一个个体的适应度 $f(i)$
- 初始化新的空集合new population, 作为下一代个体的集合
- 迭代生成下一代种群, 每次生成指定数量, 直到种群中个体数量等于种群规模为止
  - 根据适应度, 根据一定的策略(如轮盘赌算法), 从种群中选取两个个体
  - 从0-1均匀分布中生成一个随机数, 如果随机数小于 $P_c$ , 则两个选出的个体进行交叉操作, 产生两个新个体
  - 从0-1均匀分布中生成一个随机数, 如果随机数小于 $P_m$ , 两个个体(可能是原来的, 可能是交叉操作生成的)进行变异操作
  - 将两个新个体添加到new population中
- 用new population取代原来的population
- 如果任何一个染色体的适应度超过 $T_f$ , 或者迭代轮数超过了 $G$ , 停止迭代

参考资料

大白话讲解遗传算法

遗传算法系列之一遗传算法简介, 这是一个系列, 由浅入深

遗传算法系列之四:遗传算法的变种

最后更新于6年前