我在三维空间中有一组点,我需要从中找到帕累托边界。在这里,执行速度非常重要,而且随着我添加测试点,时间增长得非常快。
点集如下所示:
[[0.3296170319979843, 0.0, 0.44472108843537406], [0.3296170319979843,0.0, 0.44472108843537406], [0.32920760896951373, 0.0, 0.4440408163265306], [0.32920760896951373, 0.0, 0.4440408163265306], [0.33815192743764166, 0.0, 0.44356462585034007]]
现在,我使用这个算法:
def dominates(row, candidateRow):
return sum([row[x] >= candidateRow[x] for x in range(len(row))]) == len(row)
def simple_cull(inputPoints, dominates):
paretoPoints = set()
candidateRowNr = 0
dominatedPoints = set()
while True:
candidateRow = inputPoints[candidateRowNr]
inputPoints.remove(candidateRow)
rowNr = 0
nonDominated = True
while len(inputPoints) != 0 and rowNr < len(inputPoints):
row = inputPoints[rowNr]
if dominates(candidateRow, row):
# If it is worse on all features remove the row from the array
inputPoints.remove(row)
dominatedPoints.add(tuple(row))
elif dominates(row, candidateRow):
nonDominated = False
dominatedPoints.add(tuple(candidateRow))
rowNr += 1
else:
rowNr += 1
if nonDominated:
# add the non-dominated point to the Pareto frontier
paretoPoints.add(tuple(candidateRow))
if len(inputPoints) == 0:
break
return paretoPoints, dominatedPoints
在这里找到:http://code.activestate.com/recipes/578287-multidimensional-pareto-front/
在一组解中找到非支配解集的最快方法是什么?或者,简而言之,Python能比这个算法做得更好吗?
dominates
的定义不正确。当且仅当A在所有维度上都优于或等于B,并且在至少一个维度上严格地优于B时,A支配B。2019年8月更新
这里是另一个简单的实现,对于适度的维度来说非常快。假设输入点是唯一的。
我们首先根据坐标之和对点进行排序。这很有用,因为
x
的坐标和大于点y
,则y
不能支配x
。下面是一些与Peter的答案相关的基准,使用
np.random.randn
。凸壳启发式
我最近研究了这个问题,发现了一个有用的启发式方法,如果有许多独立分布的点,而维度很少,那么这个方法就可以很好地工作。
其思想是计算点的凸壳。由于凸壳的维数少,且顶点独立分布,使得凸壳的顶点数很小。直观地说,我们可以期望凸壳的一些顶点支配许多原始点。此外,如果凸壳中的一点不受凸壳中任何其他点的支配,则它也不受原始集合中任何点的支配。
这给出了一个简单的迭代算法。我们反复
我为维度3添加了一些基准。对于某些点的分布,这种方法似乎能产生更好的渐近性。
结果
原始帖子
我试着用一些微调来重写同样的算法。我认为你的大部分问题来自
inputPoints.remove(row)
。这需要搜索点列表;通过索引删除将更有效。 我还修改了dominates
函数,以避免一些多余的比较。这在更高的维度上可能很方便。如果你担心实际的速度,你肯定想使用numpy(因为巧妙的算法调整可能比使用数组操作带来的收益要小得多)。这里有三个解,它们都计算同一个函数。在大多数情况下,
is_pareto_efficient_dumb
解决方案的速度较慢,但随着成本的增加而变快,is_pareto_efficient_simple
解决方案在许多点上比哑解决方案的效率要高得多,并且最终的is_pareto_efficient
函数可读性较差,但速度最快(因此所有函数都是帕累托有效的!)。分析测试(使用从正态分布中提取的点):
有10000个样品,2个成本:
有1000000个样品,2项费用:
有10000个样品,15个成本:
请注意,如果您担心效率问题,那么可以通过预先重新排序数据来进一步提高2倍左右的速度,请参见here。
相关问题 更多 >
编程相关推荐