59.2. 遗传算法

遗传算法(GA)是一种启发式优化方法，通过随机搜索进行操作。优化问题的可能解决方案的集合被视为“个体”的“人口”。个体对环境的适应程度由其* fitness *决定。

搜索空间中个体的坐标由* chromosomes *表示，本质上是一组字符串。 * gene 是染色体的一个小节，它编码要优化的单个参数的值。基因的典型编码可以是 binary 或 integer *。

通过仿真进化操作* recombination ， mutation 和 select *，发现了新一代搜索点，它们的平均适应度高于其祖先。

根据 comp.ai.genetic 常见问题解答，不能过分强调 GA 不是纯随机搜索问题的解决方案。遗传算法使用随机过程，但结果显然是非随机的(优于随机的)。

图 59.1. 遗传算法的结构图

+=========================================+
|>>>>>>>>>>>  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                          |
+===+=====================================+