Skip to content
返回搜索结果

多目标遗传算法 (MOGA) — 帕累托最优解的进化搜索

提出者
Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
年份
1984
类型
Population-based evolutionary optimizer
类别
Simulation / optimization

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

字号

它有什么作用?

多目标遗传算法 (MOGA) 是一种进化计算方法,它通过进化候选解种群来趋近帕累托最优前沿,同时优化两个或多个相互冲突的目标函数。它避免了将权衡折叠成单一分数,而是产生一组非支配解供决策者选择。

方法背后的直觉

设想对候选设计进行连续世代的繁衍,只有在所有目标上均未被明显超越的解才能存活和繁殖。经过多代,种群会收敛到一个最佳可能权衡的边界——这个帕累托前沿上的任何解都无法在一个目标上改进而不恶化另一个目标。MOGA 利用遗传操作——选择、交叉和变异——来有效地探索这个边界,即使在高维、非凸或不连续的搜索空间中,经典梯度方法也会失效。

历史学

多目标遗传算法起源于 Schaffer 于 1984 年提出的向量评估遗传算法 (VEGA),这是第一个明确处理多个目标的遗传算法。Goldberg 于 1989 年的教科书将基于帕累托的排序形式化为原则性的适应度分配策略。该领域迅速成熟,涌现了 Fonseca 和 Fleming 的 MOGA (1993)、Srinivas 和 Deb 的 NSGA (1994),以及里程碑式的 NSGA-II (Deb 等人, 2002),后者成为该领域的标准基准,至今仍是最广泛引用的多目标进化算法。

何时使用

当问题有两个或多个相互冲突的目标且不存在单一最优解时,使用 MOGA — 工程设计、供应链配置、投资组合优化和环境规划是典型领域。它适用于基于梯度的梯度方法无法应用的非凸、多模态或黑盒目标景观。当单一明确定义的目标就足够时(改用标准 GA 或数学规划),当种群评估在计算上是禁忌的且没有替代模型可用时,当目标可以通过已知的加权和合法地聚合而不会丢失信息时,或者当一个小的可行集允许穷举枚举时,请勿使用它。

局限与注意事项

  • 计算成本随种群大小和函数评估次数而增加;复杂模拟的每次评估都可能很昂贵。
  • 不能保证收敛到真实的帕累托前沿——结果是启发式近似,对超参数选择(种群大小、交叉率、变异率)敏感。
  • 当目标数量超过三或四个时,性能会下降(多目标优化需要专门的算法,如 NSGA-III 或 MOEA/D)。
  • 需要仔细调整遗传算子和多样性维护,以避免过早收敛或前沿覆盖不佳。
  • 不提供单一的推荐解决方案——帕累托前沿的最终选择仍需要价值判断或二次决策规则。

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

优势

  • 在单次运行中产生一组多样化的帕累托最优解,为决策者提供明确的权衡选项,而不是单一答案。
  • 在非凸、不连续和多模态目标景观上工作,无需梯度或特定于问题的数学结构。
  • 本质上是基于种群的,可以轻松地跨核心或分布式系统进行并行化。
  • 灵活的编码允许在同一框架内同时处理连续变量、整数、二进制字符串和排列。
  • 成熟的软件库(DEAP、pymoo、jMetal)和数十年的基准证据提供了良好的支持。

应用

  • 工程设计优化——同时最小化结构件的重量、成本和应力。
  • 供应链与物流——在网络配置中平衡成本、交货时间和碳排放。
  • 环境与能源政策——为成本、可靠性和排放优化可再生能源组合。
  • 制药与化学过程设计——在最小化反应时间的同时最大化产率和纯度。
  • 机器学习超参数调优——权衡模型准确性与训练时间或可解释性。
  • 城市规划与交通——为覆盖范围、出行时间和基础设施成本优化路线网络。

使用方式

使用方式

1

随机生成 N 个候选解(染色体)的初始种群,或使用领域启发式方法,将每个解编码为决策变量向量。定义 k 个目标函数 f1(x), f2(x), ..., fk(x) 以同时最小化或最大化。

2

评估种群中每个个体的所有 k 个目标函数。适应度反映了跨目标的解的质量以及在目标空间中的覆盖多样性。

3

按非支配性对个体进行排序:如果解 x 在所有目标上至少与解 y 一样好,并且在至少一个目标上严格优于 y,则称 x 支配 y。识别非支配前沿(帕累托前沿候选集),并为支配程度较低的个体分配更高的选择优先级。拥挤距离等多样性度量可防止在前沿的狭窄区域内聚集。

4

应用选择(例如,锦标赛选择)来偏好排名较高的个体,然后应用交叉来组合父代对,并应用变异来引入变异性。精英机制跨世代保留找到的最佳非支配解。

5

为预设的代数重复适应度评估、排序和繁殖,或直到满足收敛标准。最终的非支配集近似帕累托最优前沿,向决策者呈现最优权衡解的谱系。

常见陷阱

  • 将帕累托前沿上的所有解视为同等有效,而不让领域专家参与最终的权衡选择,可能导致任意或不合理的选择。
  • 使用过小的种群会产生稀疏、无代表性的前沿;过大的种群会增加计算量而没有成比例的好处。
  • 忽略约束处理——不可行解必须明确地受到惩罚或修复;未能这样做会扭曲搜索方向,使其趋向不可行区域。
  • 将 MOGA 应用于超过四个目标的问题而不切换到多目标算法,会产生混乱、无信息量的前沿,其中几乎所有解都是非支配的。
  • 仅报告最终的帕累托前沿而没有收敛诊断(例如,跨世代的超体积指标),使得无法评估算法是否真正收敛。

常见问题

MOGA 与使用目标加权和的单目标遗传算法有何不同?

加权和方法使用预先指定的权重将所有目标折叠成一个标量,产生一个依赖于这些权重的单一解决方案。MOGA 同时生成整个非支配解前沿,而无需预先指定权重,允许决策者事后检查权衡并进行选择。

什么是帕累托前沿?它为什么重要?

帕累托前沿是这样的解集:改进任何单一目标必然会恶化至少一个其他目标。它代表了可实现权衡的完整图景。决策者可以检查这个前沿来理解为了在一个目标上获得收益而必须牺牲另一个目标的程度。

MOGA 能有效处理多少个目标?

标准的 MOGA 变体(如 NSGA-II)适用于两个或三个目标。超过四个目标时,非支配解的比例会迅速增长(目标空间中的维度灾难),导致帕累托前沿变大且选择压力减弱。对于四个或更多目标,建议使用多目标算法(NSGA-III、MOEA/D、IBEA)。

我应该使用什么停止标准?

常见的标准包括固定数量的函数评估、最大代数,或连续世代中超体积指标(当前帕累托前沿近似所支配的目标空间体积)的收敛。监测超体积增长是最原则性的方法。

MOGA 能处理约束吗?

是的,通过约束处理技术:惩罚函数(降低不可行解的适应度)、可行性锦标赛选择(可行解在选择中总是优于不可行解),或将不可行解投影回可行区域的修复算子。选择会影响收敛行为,并且必须经过深思熟虑。

相关方法

参考文献

  1. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.

    ISBN:9780201157673
    已复制。
  2. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

    打开 DOI 文献
    已复制。