遗传算法(GA)是一种通过随机搜索操作的启发式优化方法。优化问题的可能的解决方案集合被看成是个体的种群。一个个体对于它的环境的适应程度由其适应度指定。
搜索空间中一个个体的座标被表示为染色体,实质上是一个字符串集合。一个基因是一个染色体的一个片段,它编码了一个要被优化参数的值。一个基因的典型编码包括二进制或整数。
通过对重组、变异和选择的模拟,比父辈平均适应度更好的新一代搜索点将被找到。
根据comp.ai.genetic FAQ,GA并非是一个纯粹的随机搜索。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 |
+===+=====================================+