algorithm - 获得超过 2 个目标的帕累托前沿

Question

我有一个相当容易处理的问题，有 >2 个目标，我在其中应用多目标进化算法 (MOEA)，如 PSO、ACO、GA。

我想将这些算法生成的 Pareto 的性能和质量与 Pareto 前沿进行比较。

由于问题中的变量范围是可以枚举的，而且只要问题是易于处理的，我想用蛮力来获得 Pareto 前沿来与 MOEAs 进行比较。

但是，目前还不清楚如何通过暴力破解得到Pareto前沿？是否可以在蛮力中使用优势排名？

欢迎提出任何想法/建议。

示例

考虑一个多目标问题的简化实例:

1. 整数变量 x,y,z [1,100]
2. 目标:objA、objB、objC

目标是在 x、y、z 上运行暴力计算并评估 objA、objB、objC 并生成帕累托前沿。

Answer 1

维护一组正在运行的帕累托最优点，并在您观察到每个新点时逐步更新它。在实践中，这比生成所有点然后进行 O(n²) 蛮力计算以找到帕累托最优点要好得多。

这里有一些 Python 代码来演示这个想法。

S = {}
def update(p):
  if any(q > p for q in S):
    return
  for q in [q for q in S if p > q]:
    S.remove(q)
  S.add(p)

如果 S 在 n 次更新中的平均大小为 k，则复杂度为 O(nk)。