Python自定义列表构建优化

Question

我正在 Python 中编写遗传算法，但是，我的运算符 (MMX) 需要很长时间（10 秒）才能执行具有 300 万权重的个体（每个个体都是 3.000 的列表。 000 个元素）。

这是运算符的代码：

def calc_gen(maxel, minel, rec1, rec2, phiC):
    g = maxel - minel
    phi = 0
    if g > phiC:
        # Recta 2
        phi = rec2[0] * g + rec2[1]
    elif g < phiC:
        # Recta 1
        phi = rec1[0] * g + rec1[1]
    #Hay que asegurarse que no nos salimos del rango:
    maxv = min(1, maxel - phi)
    minv = max(0, minel + phi)
    gen1 = random.uniform(minv, maxv)  # Guardar el gen del primer hijo
    # Si C es el centro y A el elemento que ya tenemos y B el simétrico de A: C - A + C = B -> 2C - A = B
    # C = (maxv + minv) / 2; 2C - A = B -> maxv + minv - A = B
    # center = (maxv + minv) / 2
    gen2 = maxv + minv - gen1
    return gen1, gen2
    #return gen1, maxv + minv - gen1

def cxMMX(poblacion, rec1, rec2, phiC):
    start = timer()
    # Calcular el maximo y el minimo de cada gen en toda la población
    max_genes = numpy.amax(poblacion, axis=0).tolist()
    min_genes = numpy.amin(poblacion, axis=0).tolist()
    gis = timer()
    hijo1 = Individual()
    hijo2 = Individual()
    # Iterar dos listas a la vez (zip) con su indice (enumerate). Así crearemos los hijos simultáneamente en un loop
    for i, (maxel, minel) in enumerate(zip(max_genes, min_genes)):
        gen1, gen2 = calc_gen(maxel, minel, rec1, rec2, phiC)
        hijo1.append(gen1)
        hijo2.append(gen2)
    end = timer()
    #print("Tiempo Gi: %f Tiempo init: %f Tiempo calc gen: %f Tiempo mate total: %f" % (gis-start, init-gis, end-init, end-start))
    return [hijo1, hijo2]

rec1、rec2 和 phiC 是决定如何完成交叉的参数，您不必理会它们。它们在整个算法中具有相同的值。

poblacion 是一个列表列表，假设它的形状是 [7,3000000]。 Individual() 是自定义 class。基本就是继承"list"，增加一些属性来存储适应度值

分别做numpy.amax和numpy.amin似乎是在做额外的工作。此外，可能还有一种更 pythonic 的方式来执行 "calc_gen()" 循环。

PD: "gen1" 取决于"gen2": 在一个范围内随机获取gen1，然后寻找对称点获取gen2。

PD2：关于 MMX 运算符的更详细解释可以在 original paper, however, you can assume the code is okay and does what it has to do. The doi is https://doi.org/10.1007/3-540-44522-6_73

上找到

PD: enumerate() 和 i 是旧代码的，忘记删除它们了！

编辑：使用 Dillon Davis 的解决方案减少了 20% 的时间。这是一个非常干净的解决方案，可以与任何自定义列表构建函数一起使用，前提是您通过执行一个函数来获取列表的每个值：

def calc_gen_v2(maxel,minel, rec1m, rec1b, rec2m, rec2b, phiC):
    g = maxel - minel
    phi = 0
    if g > phiC:
        # Recta 2
        phi = rec2m * g + rec2b
    elif g < phiC:
        # Recta 1
        phi = rec1m * g + rec1b
    #Hay que asegurarse que no nos salimos del rango:
    maxv = min(1, maxel - phi)
    minv = max(0, minel + phi)
    gen1 = random.uniform(minv, maxv)  # Guardar el gen del primer hijo
    # Si C es el centro y A el elemento que ya tenemos y B el simétrico de A: C - A + C = B -> 2C - A = B
    # C = (maxv + minv) / 2; 2C - A = B -> maxv + minv - A = B
    # center = (maxv + minv) / 2
    gen2 = maxv + minv - gen1
    return gen1, gen2

def cxMMX_v3(poblacion, rec1, rec2, phiC):
    start = timer()
    # Calcular el maximo y el minimo de cada gen en toda la población
    max_genes = numpy.amax(poblacion, axis=0)
    min_genes = numpy.amin(poblacion, axis=0)
    gis = timer()
    hijo1, hijo2 = map(Individual, numpy.vectorize(calc_gen_v2)(max_genes, min_genes, rec1[0], rec1[1], rec2[0], rec2[1], phiC))
    end = timer()
    #print("Tiempo Gi: %f Tiempo init: %f Tiempo calc gen: %f Tiempo mate total: %f" % (gis-start, init-gis, end-init, end-start))
    return [hijo1, hijo2]

编辑 2：正如 Dillon Davis 建议的那样，我用纯 numpy 实现了它，将时间减少到 3.5 秒！（节省 65% 的时间）

def cxMMX_numpy(poblacion, rec1, rec2, phiC):
    # Calculate max and min for every gen in the population
    max_genes = numpy.amax(poblacion, axis=0)
    min_genes = numpy.amin(poblacion, axis=0)
    g_pop = numpy.subtract(max_genes, min_genes)
    phi_pop = numpy.where(g_pop < phiC, numpy.multiply(g_pop, rec1[0]) + rec1[1], numpy.where(g_pop > phiC, numpy.multiply(g_pop, rec2[0]) + rec2[1], 0))
    maxv = numpy.minimum(numpy.subtract(max_genes, phi_pop), 1)
    minv = numpy.maximum(numpy.sum([min_genes, phi_pop], axis=0), 0)
    hijo1 = numpy.random.uniform(low=minv, high=maxv, size=minv.size)
    hijo2 = numpy.subtract(numpy.sum([maxv, minv], axis=0), hijo1)
    return [Individual(hijo1), Individual(hijo2)]

注意：如果您想重复使用，Individual 继承自列表

注意：如果 g=phiC，则 rec1[0] * g_pop + rec1[1]=0，总是，rec1[0] 和 rec1[1] 保证！所以也许做数学运算而不是三重选项更好？

Answer 1

您尝试过使用 multiprocessing.Pool 吗？

您需要先为 calc_gen 制作一个包装器：

# after calc_gen def
def get_calc_gen(rec1, rec2, phiC):
    return lambda maxel, minel: calc_gen(maxel, minel, rec1, rec2, phiC)

然后，您可以执行以下操作，而不是 for 循环：

# replacing for loop section
cgen = get_calc_gen(rec1, rec2, phiC)
minmax_genes = zip(max_genes, min_genes)
pool = multiprocessing.Pool()
mapped_genes = pool.map(cgen, minmax_genes)
for gen1, gen2 in mapped_genes:
    hijo1.append(gen1)
    hijo2.append(gen2)

P.S。您不需要 enumerate 在您的原始代码中，因为您似乎没有使用 i

Answer 2

尝试将 cxMMX() 中的 for 循环替换为：

hijo1, hijo2 = map(Individual, numpy.vectorize(calc_gen)(max_genes, min_genes, rec1, rec2, phiC))

并从 numpy.amin() 和 numpy.amax() 中删除 .tolist()。

这将矢量化您的 calc_gen 函数，避免 zip 和来自多个 .append() 调用的函数开销，总体上应该会快很多。

编辑：

还考虑将 calc_gen() 转换为直接在 numpy 数组上工作。将对 random.uniform() 的调用替换为 numpy.random.uniform()、min() 或 max() 以及 numpy.minimum() 或 numpy.maximum()，然后完全消除 for 循环/map + vectorize .这最终将是最快的选择。

Python自定义列表构建优化

Python custom list building optimization

python

optimization

artificial-intelligence

genetic-algorithm