进化算法（EA）是一类基于种群的元启发式优化技术，其灵感来源于生物进化机制，如繁殖、突变、重组和选择。它们用于寻找困难优化问题的近似解，在这些问题中，精确或满意的方法未知。作为进化计算和计算智能的一部分，EA对候选解种群进行操作，通过适应度函数评估其质量，并迭代应用进化算子以在世代间改进种群。其关键优势在于对底层适应度景观的假设很少，从而能够处理各种问题，尽管其计算复杂性通常源于适应度评估成本。
通用算法
典型的进化算法遵循迭代过程：
- 随机生成初始个体种群（第一代）。
- 评估种群中每个个体的适应度。
- 检查是否达到目标；若达到，则终止。
- 选择个体作为父代，优先选择适应度较高的个体。
- 通过交叉（模拟繁殖）和可选突变产生后代。
- 对后代应用突变操作。
- 选择个体进行替换，优先选择适应度较低的个体，以形成下一代。
- 返回步骤2并重复，直到终止。
这一通用框架在各种EA类型中有所调整，每种类型具有特定的表示和算子。
进化算法的类型
存在多种EA变体，它们在遗传表示和实现细节上有所不同：
- 遗传算法（GA）：最流行的类型，其中解表示为数字字符串（通常为二进制）。应用重组和突变等算子。GA广泛用于优化问题。
- 遗传编程（GP）：解为计算机程序，适应度由其解决计算问题的能力决定。变体包括笛卡尔遗传编程、基因表达编程、语法进化、线性遗传编程和多表达编程。
- 进化策略（ES）：由Ingo Rechenberg、Hans-Paul Schwefel及其同事在20世纪60年代和70年代开发，ES专注于数值和工程优化。它操作于实值向量，使用突变、重组和确定性选择。一个显著特征是突变分布的自我适应，形式包括(1+1)-ES、(μ, λ)-ES和(μ+λ)-ES。后来的发展包括协方差矩阵适应（CMA-ES）和自然进化策略。
- 差分进化（DE）：基于向量差异，主要适用于数值优化。
- 进化多目标优化：将EA扩展到具有多个冲突目标的问题，维护一个近似帕累托前沿上权衡解的种群。
- 协同进化算法：解根据与其他解的交互进行评估，这些交互可以是竞争或合作的。适用于动态或竞争性适应度景观。
- 神经进化：基因组表示人工神经网络，编码结构和连接权重，直接或间接进行。
- 学习分类器系统（LCS）：解为分类器（规则）的集合。Michigan-LCS进化单个分类器，而Pittsburgh-LCS进化分类器集合的种群。适应度通过强化学习或监督学习确定。
- 质量-多样性（QD）算法：同时追求高质量和多样性的解，在问题空间中探索各种解。
理论基础
无免费午餐定理
优化的无免费午餐定理指出，当考虑所有可能的优化问题时，所有优化策略同样有效。这意味着没有一种进化算法在所有问题上从根本上优于另一种。然而，在实践中，问题集是受限的，EA可以通过利用问题特定知识来改进，例如选择合适的表示和算子。
计算复杂性
在大多数实际应用中，EA的计算复杂性是一个重要因素，主要源于适应度函数评估的成本。适应度近似技术可以缓解这一问题。有趣的是，简单EA通常能解决复杂问题，这表明算法复杂性与问题复杂性之间没有直接联系。
应用与局限性
进化算法应用于多个领域，包括工程设计、调度、机器学习（如神经进化）和多目标优化。当搜索空间大、非线性或了解不足时，它们特别有价值。然而，其性能依赖于参数调整和问题表示。EA技术也用于建模生物微观进化和细胞过程，尽管存在局限性。