遗传算法

定义

遗传算法是计算数学中用于求解最优化问题的搜索算法，属于进化算法的一支，其设计思路取自生物界的选择、繁殖、杂交和基因突变等现象^[1]。《数学辞海》将其列为一种全局随机寻优算法，并说明其基本做法是用二进制数串充当染色体来表示复杂结构数据^[3]。

在算法中，待求解问题的一个候选解称为个体，用变量序列表示，这一序列称为染色体或基因串；把问题参数转换为这种串的过程称为编码。较常见的表示方式是定长的 0、1 二进制串，也可以采用实数编码等与具体问题相匹配的形式^[1][4]。

原理

算法运行前先定义适应度函数，用它衡量个体对问题的优劣程度；适应度一般由目标函数映射得到，需要取非负值并便于比较排序^[2]。随后随机生成一定数量的个体构成初始种群，也可借助问题先验知识改进初始种群的分布^[1]。

每一代的计算流程大体分为：评价种群中各个体的适应度；按适应度高低以随机方式挑选个体进入下一代；让被选中的个体两两配对，在随机选定的交叉点交换染色体片段；再以较小概率改动个别基因位的取值^[2][1]。交叉和变异产生的新个体组成下一代种群，如此循环，直至达到预设代数、耗尽计算资源，或种群适应度不再明显提高为止^[1]。

适应度高的个体被选中的机会更大，但适应度较低者仍保留一定机会，以免种群过早丧失多样性。交叉概率通常设在 0.6 至 1 之间，变异概率则往往取 0.1 或更小^[1]。程序结构可概括为下面的循环：

flowchart TD

A[随机生成初始种群] --> B[计算各体适应度]

B --> C{满足终止条件}

C -->|否| D[按适应度选择个体]

D --> E[交叉产生子代]

E --> F[按概率变异]

F --> B

C -->|是| G[输出适应度最高的个体]

霍兰德提出的模式理论认为，算法中的个体同时隐式地代表大量模式，适应度高的模式在种群中所占比例会随代数增长而上升，这被用来解释算法的搜索能力，称为隐并行性^[5]。

发展历程

遗传算法的思想可追溯到 20 世纪 60 年代初期。1967 年，密歇根大学学者霍兰德的学生巴格利在博士论文中首次使用「遗传算法」这一名称，并讨论了它在博弈问题中的应用^[2]。

1975 年，霍兰德出版专著《自然系统和人工系统的适配》，系统阐述了遗传算法的基本理论与方法，并提出了对后续研究影响很大的模式理论，此书被视为该算法成型的标志^[2][3]。他给出的这一版本后来常被称为简单遗传算法。

20 世纪 80 年代以后，遗传算法进入较快的发展阶段，应用范围扩展到自动控制、生产计划、图像处理和机器人等方向^[2]。围绕该算法的理论研究与改进工作持续展开，与进化策略、进化编程、遗传编程等一同归入进化计算的范畴。

应用

在组合优化与运筹类问题中，遗传算法被用于选址、路径与调度等决策场景，例如为物资仓库确定位置、为收集中心规划运输路线。已有研究将其与粒子群优化等元启发式方法对比，在小规模算例上得到的结果与精确解法相差约 7% 以内^[6]。

在机器学习与数据挖掘方面，算法可用于特征选择、参数搜索和样本处理。有研究把聚类方法与遗传算法结合，用遗传操作生成新的少数类样本，以改善类别不平衡数据上的分类效果^[7]。

在工程与设计领域，遗传算法被用于结构优化、控制器整定和图像处理等任务，也被用作演化机器人控制器的设计工具，通过演化神经网络来完成迷宫行走等行为^[8]。此外，它还被归入人工生命与生物信息学的常用计算手段之列，例如从基因表达数据中筛选与疾病相关的关键基因^[4][8]。

局限

算法的求解质量受问题规模和编码方式制约。当被变异的元素数量很多时，搜索空间会随规模呈指数扩张，直接对整台发动机或整栋建筑这类复杂对象编码很难奏效，通常只能把对象拆解为风扇叶片、建筑外形等更简单的表示后再搜索^[9]。

遗传算法容易向局部最优甚至任意一点收敛，而不是全局最优，即所谓早熟；是否发生与适应度地形的形状有关。可通过改进适应度函数、提高变异率或采用维持种群多样性的选择策略加以缓解，但无免费午餐定理表明并不存在通用的解决办法^[9]。

对动态数据集，算法往往在早期就收敛到此后不再有效的解，需要靠提高变异概率或引入随机新个体来保持多样性^[9]。若问题的适应度只有对错两种取值，缺少可供逐步爬升的梯度，算法难以向解收敛，此时随机搜索的效率可能与之相当^[9]。

所谓「更好」的解只是在种群内部相对而言，因此终止判据在许多问题上并不明确；与模拟退火、粒子群优化、蚁群优化或整数线性规划等方法相比，遗传算法在收敛速度上也未必占优，其适用性取决于对问题已有知识的多少^[9]。

参见

• 进化算法 —— 遗传算法所属的上位算法类别，还包括进化策略与遗传编程等。

• 模拟退火 —— 另一种不依赖梯度的随机搜索优化方法，常与遗传算法比较或混合使用。

• 粒子群优化 —— 基于种群的元启发式算法，在选址、调度等问题上与遗传算法互为参照。

• 蚁群优化 —— 借鉴群体行为的搜索方法，与遗传算法同属群智能与元启发式研究领域。

• 约翰·霍兰德 —— 系统提出遗传算法理论框架与模式理论的学者。