获取两个以上目标的帕累托前沿

Question

获取两个以上目标的帕累托前沿

algorithmsearchoptimizationevolutionary-algorithm

3

我有一个具有许多目标的相当易于处理的问题，我将应用多目标进化算法（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，生成 Pareto 前沿。

- STiGMa

通常有一些数据结构可以在插入/删除时维护一组点并允许以多项式对数时间（+当然是最小值的数量）进行枚举。如果您有一个静态集合，应该能够使用范围树剥离几个对数因子（即在d维中找到最小值的O(n log^(d-2) n)）。您需要什么？ - Niklas B.

@NiklasB。我更新了问题，给出了一个简化的例子，说明我想要实现什么。你有没有想到哪些数据结构可能会有用？ - STiGMa

我认为你误用了暴力破解这个术语，这会在这里造成一些混淆。对于静态的三维情况，您可以只在一个维度上对点进行排序，扫描它们并将它们插入到平衡二叉搜索树中进行二维支配检查。该算法的时间复杂度将为O(n log n)。对于d > 3，如果您想要线性对数运行时间，则会变得更加复杂。 - Niklas B.

感谢回复，@NiklasB。嗯，暴力法意味着检查x、y、z的所有可能值（即笛卡尔积），进行评估并找到最佳解决方案或在多个目标的情况下生成帕累托前沿。 - STiGMa

有没有任何源代码/伪代码，我可以查看d=3和d>3的情况？ - STiGMa

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timothy Shields · Accepted Answer

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

以下是一些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)

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