PostgreSQL 9.6.0 手册
上一页上一级章 58. 遗传查询优化器下一页

58.2. 遗传算法

遗传算法（GA）是一种通过随机搜索操作的启发式优化方法。优化问题的可能的解决方案集合被看成是个体的种群。一个个体对于它的环境的适应程度由其适应度指定。

搜索空间中一个个体的座标被表示为染色体，实质上是一个字符串集合。一个基因是一个染色体的一个片段，它编码了一个要被优化参数的值。一个基因的典型编码包括二进制或整数。

通过对重组、变异和选择的模拟，比父辈平均适应度更好的新一代搜索点将被找到。

根据comp.ai.genetic FAQ，GA并非是一个纯粹的随机搜索。GA会使用随机处理，但是结果的确是非随机的（比随机好）。

图 58-1. 一种遗传算法的结构图

P(t)在时刻 t 的祖先代
P''(t)在时刻 t 的后代

+=========================================+
|>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0                       |
+=========================================+
| INITIALIZE P(t)                         |
+=========================================+
| evaluate FITNESS of P(t)                |
+=========================================+
| while not STOPPING CRITERION do         |
|   +-------------------------------------+
|   | P'(t)  := RECOMBINATION{P(t)}       |
|   +-------------------------------------+
|   | P''(t) := MUTATION{P'(t)}           |
|   +-------------------------------------+
|   | P(t+1) := SELECTION{P''(t) + P(t)}  |
|   +-------------------------------------+
|   | evaluate FITNESS of P''(t)          |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+
上一页起始页下一页
将查询处理看成是一个复杂的优化问题上一级PostgreSQL 中的遗传查询优化（GEQO）