47.2. 基因算法

基因算法(GA)是一种启发式的优化法(heuristic optimization method), 它是通过不确定的随机搜索进行操作。 优化问题的可能的解的集合被认为是个体(individuals)组成的种群(population)。 一个个体对它的环境的适应程度由它的适应性(fitness)表示。

一个个体在搜索空间里的参照物是用染色体(chromosomes)表示的, 实际上那是一套字符串。 一个基因 (gene)是染色体的一个片段,基因是被优化的单个参数的编码。 对一个基因的典型的编码可以是二进制(binary)整数(integer)

通过仿真进化过程的重组(recombination)变异(mutation)选择(selection)找到新一代的搜索点, 它们的平均适应性要比它们的祖先好。

根据 comp.ai.genetic FAQ,我们不论怎么强调 GA 在解决一个问题时不是纯随机搜索都不过份。 GA 使用随机处理,但是结果明显不是随机的(比随机更好)。

Figure 47-1. 基因算法的结构化框图

P(t)t 时刻的父代
P''(t)t 时刻的子代

+=========================================+
|>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0                       |
+=========================================+
| INITIALIZE P(t)                         |
+=========================================+
| evalute 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)}  |
|   +-------------------------------------+
|   | evalute FITNESS of P''(t)           |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+