python - 使用 numpy 的帕累托边界指数

Question

我正在尝试标记一些 numpy 向量(矩阵 M)，以便标签显示 Pareto 边界指数。

例如，非支配向量集 (v0) 将被标记为 Pareto 边界索引 0，非支配向量集 v1 (v1 = M - v0) 将标有索引 1，即非支配向量的下一组/边界 v2 (v2 = M - v0 - v1) 2 依此类推，直到矩阵 M 的所有向量都被标记。

我已经将几个测试用例放在一起，但无论我想出什么，要么效率极低(目前不要太在意)，要么根本不起作用。

mat1 = np.asarray([
    [1, 2, 3, 4, 5, 7],
    [1, 2, 3, 4, 5, 6],
    [1, 2, 3, 4, 5, 6],
])

calc_fronts(mat1) == [0, 1, 1]

mat2 = np.asarray([
    [1, 2, 3, 4, 5, 7],
    [1, 2, 3, 4, 5, 6],
    [1, 22, 3, 4, 5, 6],
])

calc_fronts(mat2) == [0, 1, 0]


mat3 = np.asarray([
    [1, 2, 3, 4, 5, 7],
    [1, 2, 3, 4, 5, 5],
    [1, 2, 2, 4, 5, 4],
])

calc_fronts(mat3) == [0, 1, 2]


mat4 = np.asarray([
    [0, 2, 3, 4, 5, 7],
    [1, 2, 3, 4, 5, 6],
    [1, 22, 2, 4, 5, 6],
])

calc_fronts(mat4) == [0, 0, 0]

向量 x 支配 y 如果 foreach a in x, b in y: a >= b AND there exists at least one a in x 对于 a > b。

这是我的尝试:

def calc_fronts_2(vecs):
    n = vecs.shape[0]
    # find the most dominating
    m = np.zeros(vecs.shape, dtype=bool)
    dominates = []
    for i, vec in enumerate(vecs):
        for x in xrange(n):
            m[x] = i != x
        mvecs = np.ma.masked_array(vecs, mask=~m)
        # print 'i=', i
        # print 'all better  \n', np.all(vec >= mvecs, axis=1)
        # print 'at least one\n', np.any(np.all(vec > vecs[m], axis=0))
        # print 'at least one\n', vec > mvecs
        # print 'at least one\n', np.any(vec > mvecs, axis=1)

        dom = np.where(np.all(vec >= mvecs, axis=1) & np.any(vec > mvecs, axis=1))
        dom = dom[0]
        dominates.append(dom.tolist())
    # print dominates

    dominated_by = [[j for j in xrange(n) if i in dominates[j]] for i in xrange(n)]

    print 'domin:\n', dominates
    print 'dom by\n', dominated_by
    ranks = np.empty(n, dtype=int)
    ranks.fill(-1)
    for r in xrange(n):
        remove = set()
        for i in xrange(n):
            if ranks[i] == -1 and len(dominated_by[i]) == 0:
                ranks[i] = r
                remove.add(i)
        for ranked in remove:
            for domby in dominated_by:
                if ranked in domby:
                    domby.remove(ranked)
        if np.all(ranks == -1):
            break
    return ranks

Answer 1

这是我相当繁重的尝试，希望能提供一些新想法。请注意，创建了一个 (m,m,n) 临时数组(当 M 为 (m,n) 形状时)。

import numpy as np

def calc_fronts(M):
    i_dominates_j = np.all(M[:,None] >= M, axis=-1) & np.any(M[:,None] > M, axis=-1)
    remaining = np.arange(len(M))
    fronts = np.empty(len(M), int)
    frontier_index = 0
    while remaining.size > 0:
        dominated = np.any(i_dominates_j[remaining[:,None], remaining], axis=0)
        fronts[remaining[~dominated]] = frontier_index

        remaining = remaining[dominated]
        frontier_index += 1
    return fronts

演示:

In [217]: M = np.array([[ 0, 18,  1],
     ...:               [ 4,  8, 11],
     ...:               [ 3, 19,  3],
     ...:               [18,  1, 19],
     ...:               [16,  7, 13],
     ...:               [ 3, 18,  3],
     ...:               [15, 13, 19],
     ...:               [13,  5, 13],
     ...:               [ 2, 16, 16],
     ...:               [ 9, 14, 17]])

In [218]: calc_fronts(M)
Out[218]: array([2, 1, 0, 0, 0, 1, 0, 1, 0, 0])