我正在用Python编写一个遗传算法,然而,我的运算符(MMX)对于具有300万个权重的个体(每个个体是一个包含3.000.000个元素的列表)执行起来太长(10秒)。
下面是运算符的代码:
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是一个列表列表,假设它的形状是73000000。单个()是一个自定义类。它基本上继承了“列表”,并添加了一些属性来存储适应值。
分开做numpy.amax和numpy.amin看起来就像做了额外的工作。此外,可能还有一种更具pythonic风格的方法来执行"calc_gen()“循环。
PD:" gen1“依赖于" gen2 ":在一定范围内随机获取的gen1,然后通过寻找对称点来获得gen2。
PD2:关于MMX操作符的更详细的解释可以在original paper上找到,但是,您可以假设代码是正确的,并执行它必须做的事情。doi为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]
EDIT 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)]
注意:如果您想要重用,则单个继承自列表
注意:如果g=phiC,那么rec1 * g_pop + rec11=0,always,rec1和rec11保证了这一点!因此,也许做数学计算比三重选择更好?
发布于 2018-07-19 04:40:57
尝试将cxMMX()
中的for循环替换为以下内容:
hijo1, hijo2 = map(Individual, numpy.vectorize(calc_gen)(max_genes, min_genes, rec1, rec2, phiC))
并从您的numpy.amin()
和numpy.amax()
中删除.tolist()
。
这将使您的calc_gen函数向量化,避免多个.append()
调用的zip和函数开销,总体上应该会快得多。
编辑:
还可以考虑将calc_gen()
转换为直接在numpy数组上工作。将对random.uniform()
的调用替换为numpy.random.uniform()
、min()
或max()
替换为numpy.minimum()
或numpy.maximum()
,然后完全消除for循环/映射+矢量化。这最终将是最快的选择。
发布于 2018-07-19 03:17:33
您是否尝试过使用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)
附注:你不需要在你的原始代码中使用enumerate
,因为你似乎并没有使用i
https://stackoverflow.com/questions/51409330
复制相似问题