如何使用数组查找对函数进行矢量化

Question

我正在尝试为最小向量覆盖遗传算法向量化我的适应度函数，但我不知道如何去做。

现在的情况：

vert_cover_fitness = [1 if self.dna[edge[0]] or self.dna[edge[1]] else -num_edges for edge in edges]

dna是一个一维二进制数组，大小为[0..n]，其中每个索引对应一个顶点，它的值表示我们是否选择与否。 edges是一个二维正整数数组，其中每个值对应dna中的一个顶点（索引）。两者都是 ndarrays.

简单解释 - 如果由一条边连接的顶点之一是 "selected"，那么我们得到一分。如果不是，则函数受到 -num_edges.

的惩罚

我已经尝试过 np.vectorize 尝试使用 lambda 函数来降低成本：

fit_func = np.vectorize(lambda edge: 1 if self.dna[edge[0]] or self.dna[edge[1]] else -num_edges)
vert_cover_fitness = fit_func(edges)

此 returns IndexError: invalid index to scalar variable.，因为此函数应用于每个值，而不是每一行。

为了解决这个问题，我尝试了 np.apply_along_axis。这行得通，但它只是一个循环的包装器，所以我没有得到任何加速。

如果任何 Numpy 向导能看到一些明显的方法来做到这一点，我将非常感谢您的帮助。我猜问题出在问题的表示上，改变 dna 或 edges 形状可能会有所帮助。我只是不够熟练，看不到我应该做什么。

Answer 1

我想出了这段 numpy 代码，它在我随机生成的数据上的运行速度比你的 for 循环快 30 倍。

import numpy as np
num_vertices = 1000
num_edges = 500
dna = np.random.choice([0, 1], num_vertices)
edges = np.random.randint(0, num_vertices, num_edges * 2).reshape(-1, 2)

vert_cover_fitness1 = [1 if dna[edge[0]] or dna[edge[1]] else -num_edges for edge in edges]

vert_cover_fitness2 = np.full([num_edges], -num_edges)
mask = (dna[edges[:, 0]] | dna[edges[:, 1]]).astype(bool)
vert_cover_fitness2[mask] = 1.0

print((vert_cover_fitness1 == vert_cover_fitness2).all()) # this shows it's correct

这里是用于测量加速比的 timeit 代码。

import timeit

setup = """
import numpy as np
num_vertices = 1000
num_edges = 500
dna = np.random.choice([0, 1], num_vertices)
edges = np.random.randint(0, num_vertices, num_edges*2).reshape(-1, 2)
"""

python_loop = "[1 if dna[edge[0]] or dna[edge[1]] else -num_edges for edge in edges]"

print(timeit.timeit(python_loop, setup, number=1000))

vectorised="""
vert_cover_fitness2 = np.full([num_edges], -num_edges)
mask = (dna[edges[:, 0]] | dna[edges[:, 1]]).astype(bool)
vert_cover_fitness2[mask] = 1.0
"""

print(timeit.timeit(vectorised, setup, number=1000))

# prints:
# 0.375906624016352
# 0.012783741112798452

如何使用数组查找对函数进行矢量化

How to vectorize a function with array lookups

python

numpy

vectorization