Skip to content
返回搜索结果

遗传算法 — 进化优化

提出者
John Henry Holland
年份
1975
类型
Population-based metaheuristic

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

遗传算法(GA)是由 John Henry Holland (1975) 引入的一种基于种群的元启发式优化方法,它模仿自然选择的原理。它维护一个候选解的种群,并通过选择、交叉和变异算子迭代地改进它们,这使得它在经典基于梯度的方​​法失效的不连续、非凸和多模态搜索空间中尤其强大。

方法背后的直觉

想象一下,你有一个棘手问题的数千种可能的答案,但没有找到最佳答案的公式。遗传算法将每个候选答案视为种群中的一个个体。在每一代中,它会保留最适应的个体,将它们杂交以混合它们的优良性状,并偶尔对后代进行变异以注入新颖性。经过许多代,种群会朝着越来越好的解决方案漂移——不是通过遵循梯度,而是通过模仿进化随时间塑造生物体的方式。

历史学

遗传算法由 John Henry Holland 在其 1975 年的著作《自然和人工系统适应》中提出,该书形式化了模式(构建块)的概念,并提供了交叉和选择为何能驱动搜索趋向更优区域的奠基性理论分析。Holland 的学生——尤其是 David Goldberg——在 20 世纪 80 年代通过工程应用推广了 GA。Kalyanmoy Deb 后来将该框架扩展到多目标设置,最终形成了被广泛采用的 NSGA-II 算法(2002)。如今,GA 仍然是进化计算中的标准工具,混合方法的研究活跃,将进化搜索与局部精炼相结合。

何时使用

当搜索空间大、不连续、不可微或高度多模态时,遗传算法是合适的——这些是基于梯度的求解器无法操作或陷入局部最优解的条件。它们适用于连续、分类、二进制和有序变量类型,并且不施加正态性或分布假设。唯一的要求是可计算的适应度函数。对于存在解析或凸公式的问题,经典方法(线性规划、梯度下降)更快,应该优先使用。需要足够的迭代次数(通常远超 1,000 代)才能有意义地收敛;运行代数太少是最常见的失败模式。

局限与注意事项

  • 不保证收敛到全局最优解;结果可能因运行而异。
  • 计算成本高昂:每一代都需要评估整个种群,当适应度函数很慢时,这是 prohibitive 的。
  • 性能对超参数选择敏感——种群大小、交叉概率和变异率——这些通常需要针对特定问题进行调整。
  • 对于平滑、凸形或结构良好的问题,经典的基于梯度或线性方法会更快、更可靠。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 适用于梯度下降方法失效的不连续、不可微和多模态目标景观。
  • 不施加分布假设——唯一需要输入的只是一个可计算的适应度函数。
  • 自然地处理各种变量类型:连续、二进制、分类和有序。
  • 种群多样性允许同时探索搜索空间的多个区域,降低了过早陷入局部最优解的风险。
  • 高度可扩展:特定于域的交叉和变异算子、约束处理和多目标变体(例如,NSGA-II)在文献中已得到充分确立。

应用

  • 工程设计优化:寻找结构、电路或机械系统的最佳参数配置。
  • 调度和路由问题:作业车间调度、车辆路径和时间表安排,其中组合搜索空间对于穷举搜索来说太大。
  • 机器学习:超参数调优、神经网络架构搜索和特征选择。
  • 运筹学:供应链优化、投资组合分配和复杂约束下的资源分配。
  • 生物信息学:序列比对、蛋白质结构预测和基因调控网络推断。

使用方式

使用方式

1

创建一个候选解(个体)的种群,通常在搜索空间内随机生成。每个个体编码一个潜在的解决方案——例如,作为二进制字符串、实值向量或排列——种群大小是一个关键参数,它决定了从一开始就对搜索空间进行多大范围的采样。

2

种群中的每个个体都由一个适应度函数进行评分,该函数量化了该解决方案相对于问题目标的优劣程度。适应度函数是用户必须提供的唯一特定于域的组件;它可以是任何可计算的度量——模拟输出、成本公式或模型误差指标。

3

具有更高适应度的个体被优先选择成为下一代的父代。常见的选择机制包括锦标赛选择、轮盘赌(适应度比例)选择和基于排名的选择。选择压力控制着高质量解决方案的利用与种群多样性的维持之间的权衡。

4

选定的父代通过交叉(重组)产生后代,其中将两个父代编码的片段组合起来形成一个新的个体,并通过变异产生后代,其中对单个基因进行小的随机更改。交叉概率和变异率是关键的调整参数:变异太少会导致过早收敛,变异太多则会将搜索变成随机游走。

5

评估 → 选择 → 繁殖的循环会持续设定的代数,或者直到满足收敛标准(例如,在一系列代数中没有改进)。在所有代数中找到的最佳个体被作为解决方案返回。由于不能保证收敛到全局最优解,因此建议对高风险问题进行多次独立运行。

常见陷阱

  • 运行代数太少是最常见的错误:代数不足会导致算法不收敛,因此在只有少量迭代预算可用时,应优先选择解析或基于梯度的方法。
  • 过早收敛——种群过早失去多样性——会产生局部最优但全局次优的结果;维持足够大的种群大小和变异率以抵消这一点。
  • 使用定义不当或错误指定的适应度函数,无论算法是否正确,都会产生误导性结果;在运行 GA 之前独立验证适应度函数。
  • 将 GA 应用于平滑、凸形问题,而梯度下降或线性规划就足够了,这会浪费计算资源并引入不必要的随机性。
  • 将单次运行报告为解决方案而不检查可重复性;对于高风险应用,多次运行算法并报告结果的分布。

常见问题

遗传算法与梯度下降有何不同?

梯度下降需要可微目标函数并沿着局部梯度下降。遗传算法只需要为任何候选解计算适应度;它通过演化种群而不是遵循梯度来搜索,因此它可以处理梯度下降失败或卡住的不连续、不可微和多模态景观。

我需要多少代和多大的种群?

没有普遍规则;两者都取决于搜索空间的复杂性。种群太小或运行时间太短都有过早收敛的风险。作为实际的起点,文献中常见的种群大小为 50-200,代数为 100-1000,但具有挑战性的问题通常需要更多。始终检查收敛曲线,而不是固定任意停止标准。

遗传算法保证能找到全局最优解吗?

否。GA 是启发式方法,在有限时间内不保证收敛到全局最优解。对于确定性保证,您需要精确方法,例如整数规划求解器。对于高风险决策,多次运行 GA,报告结果的分布,并将最佳解决方案与任何已知界限进行比较。

何时应选择 GA 而非模拟退火或粒子群优化?

当解决方案自然编码为组合结构(排列、二进制字符串)或需要多目标扩展时,通常倾向于选择 GA。粒子群优化在连续单峰问题上通常更快。模拟退火对于具有明确定义的邻域的组合问题实现起来更简单。实际上,在承诺选择一种方法之前,在小型问题实例上对两种或三种方法进行基准测试是明智的。

相关方法

参考文献

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    打开出版物文献
    已复制。
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN:9780471873396
    已复制。