Skip to content
返回搜索结果

随机遗传算法 — 优化问题的随机进化搜索

提出者
Holland, J. H.
年份
1975
类型
Stochastic evolutionary metaheuristic
类别
Simulation / optimization

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

字号

它有什么作用?

随机遗传算法 (Stochastic Genetic Algorithm, SGA) 是一种基于群体的元启发式算法,它模仿生物进化过程——选择、交叉和变异——以在复杂、非线性或组合空间中搜索近优解。其随机算子使其对局部最优解具有鲁棒性,并广泛应用于工程、调度、机器学习和运筹学领域。

方法背后的直觉

设想一个由候选解组成的群体在竞争生存。更好的解更有可能被选为亲本;它们的后代继承并重组优良性状,而偶尔的随机变异则引入新颖性。经过多代,该过程会收敛到搜索空间的高质量区域,而无需梯度信息。“随机”一词强调选择、交叉和变异都涉及概率抽样,这正是其与罕见的确定性变体区分开来的地方,并赋予其全局搜索能力。

历史学

John Holland 于 1975 年在密歇根大学提出了遗传算法的理论基础,借鉴了 Fraser (1957) 关于模拟遗传系统的早期工作。David Goldberg 1989 年的教科书普及了 GA 在工程优化中的应用。选择的随机性通过模式定理形式化,该方法成为进化计算和计算智能的基石。

何时使用

当满足以下条件时,使用随机遗传算法:(1) 搜索空间大、多峰或不连续,基于梯度的方​​法失败或不适用;(2) 目标函数是黑盒、有噪声或评估成本高,但可以通过群体级采样处理;(3) 组合或混合整数问题缺乏有效的精确求解器;(4) 在合理评估次数内找到近优解即可接受。不应使用 SGA 的情况:问题是凸的或梯度可用且成本低——经典优化收敛更快;当函数评估成本极高(数十或数百次)时,基于群体的方​​法可能会耗尽预算;或当需要可证明的最优解时,因为 GA 不提供最优性保证。

局限与注意事项

  • 不能保证找到全局最优解;解的质量取决于群体大小、算子选择和代数。
  • 与光滑、低维问题上的基于梯度的方法相比,计算成本高——需要大量的函数评估。
  • 超参数调整(群体大小、交叉率、变异率)取决于问题,通常需要实验。
  • 选择压力过高或变异率过低可能导致过早收敛,将搜索困在次优区域。

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

优势

  • 不需要梯度信息——适用于黑盒、不连续或不可微的目标。
  • 通过适当的编码自然处理组合、混合整数和排列搜索空间。
  • 天生可并行化:群体可以并行评估,减少实际运行时间。
  • 由于群体多样性和随机探索,对局部最优解具有鲁棒性。
  • 高度可扩展:算子、编码和选择方案可以针对特定领域的约束进行定制。

应用

  • 制造业和物流中的作业车间和流程车间调度
  • 机器学习管道中的特征选择和超参数调优
  • 机械和土木工程中的结构和拓扑优化
  • 运筹学中的旅行商问题和车辆路径问题
  • 生物信息学中的蛋白质结构预测和药物发现
  • 神经网络架构搜索和权重优化

使用方式

使用方式

1

随机或通过启发式种子生成 N 个候选解(染色体)的初始群体。每个染色体编码决策空间中的一个可行点——根据所选问题表示形式,可以是二进制字符串、实数向量、排列或树。

2

使用目标函数(或代理函数)计算群体中每个个体的适应度 f(x_i)。适应度量化了解的质量;适应度越高表示解越好。对于最小化问题,适应度通常定义为成本函数的倒数或变换。

公式
f(x_i), \quad i = 1, \ldots, N
3

应用随机选择算子选择亲本。轮盘赌选择(适应度比例选择)为每个个体分配与其适应度成比例的概率。锦标赛选择、排序选择和精英主义是控制选择压力的常见变体。

公式
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

以 p_c 的概率(通常为 0.6–0.9)重组选定的亲本对以产生后代。单点、两点或均匀交叉在亲本染色体之间交换遗传物质,生成继承了双亲性状的子代。该算子驱动对优良构建块的开发。

5

以低概率 p_m(通常每基因 0.001–0.05)随机改变每个子代染色体中的单个基因。变异保持遗传多样性,防止过早收敛,并确保算法能够逃离局部最优解。变异率是针对问题调整的关键参数。

6

通过群体替换(世代替换)或稳态更新替换当前群体。再次评估适应度,并从选择步骤重复,直到满足停止标准——最大代数、适应度阈值或在设定的代数内无改进。

常见陷阱

  • 变异率过高实际上会使算法退化为随机搜索,并破坏累积的适应度增益。
  • 在替换策略中忽略精英主义可能导致在世代之间丢失找到的最佳解。
  • 将实值交叉算子应用于二进制编码问题(反之亦然)会破坏编码并产生不可行的子代。
  • 过早停止——代数不足——是实践中解的质量差的最常见原因。
  • 忽略约束处理:无约束的交叉和变异经常违反问题约束;必须显式地内置惩罚函数或修复算子。

常见问题

随机遗传算法与标准遗传算法有何不同?

“随机”一词强调所有核心算子——选择、交叉和变异——都涉及概率抽样。Holland 提出的经典 GA 本质上是随机的。该术语在模拟/优化文献中使用,以区别于罕见的确定性变体(例如,确定性拥挤),并阐明算法的行为由于随机性而在不同运行中有所不同。

群体应该有多大?

对于中等维度的问​​题,通常从 50–200 个个体开始。更大的群体可以提高多样性并减少过早收敛,但会增加每代的计算成本。存在基于染色体长度的经验法则(例如,基因数量的 10 倍),但通常需要进行经验调整或元优化。

何时应选择粒子群优化或模拟退火而非遗传算法?

粒子群优化 (Particle Swarm Optimization, PSO) 在连续实值问题上通常更快,因为它利用了速度信息。模拟退火 (Simulated Annealing, SA) 实现起来更简单,并且对于单解轨迹搜索可能有效。当搜索空间是组合式的、交叉能够有意义地重组解结构,或者群体多样性对于多峰景观很重要时,则倾向于使用 GA。

随机遗传算法能扩展到高维问题吗?

在非常高的维度(数百到数千个变量)下,性能会下降,因为群体必须足够大才能充分采样空间。专门的变体——例如,学习链接的 GA、分布估计算法或具有迁移的岛屿模型——可以解决可扩展性问题,但会增加复杂性。

如何在遗传算法中处理约束?

主要有三种策略:(1) 惩罚函数,降低违反约束的适应度;(2) 修复算子,将不可行的子代投影回可行区域;(3) 专门的编码和算子,仅通过构造生成可行解。基于惩罚的方法最容易实现,但需要仔细校准惩罚系数。

相关方法

参考文献

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

    ISBN:978-0262581110
    已复制。
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    ISBN:978-0201157673
    已复制。