> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/ji-qi-xue-xi/you-hua-suan-fa/yi-chuan-suan-fa/yi-chuan-suan-fa-yuan-li.md).

# 遗传算法原理

## 引入

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

## 算法原理

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

首先介绍概念.

### 编码与译码

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

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

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

### 适应度函数

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

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

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

### 选择

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

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

### 交叉

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

### 变异

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

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

### 精英主义选择(Elitism Strategy)

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

### 插入

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

### 算法过程

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

## 参考资料

[大白话讲解遗传算法](http://blog.jobbole.com/110913/)

[遗传算法系列之一遗传算法简介](http://www.algorithmdog.com/), 这是一个系列, 由浅入深

[遗传算法系列之四:遗传算法的变种](http://www.algorithmdog.com/遗传算法系列之四遗传算法的变种)