时间戳

首页 > 解决方案 > 遗传算法：收敛问题

python - 遗传算法：收敛问题

问题描述

我试图用遗传算法找到最大问题的解决方案，但它没有收敛，而是最大适应度越来越低。我不明白为什么它不起作用；我尝试自己执行这些函数并且它们起作用了，但我不确定主要的调用。最大的一个问题是当你有一个长度为 m 的二进制个体（1/0）的种群 N 时，并且您想优化您的人口，以便您生成至少一个仅包含 1 的个体（在我的情况下为 0）

这是我的代码：

import random

def fitness(individual):
    i = 0
    for m in individual:
        if m == 0:
            i += 1
    return i

def selection(pop):
    chosen = []
    for i in range(len(pop)):
        aspirants = []
        macs = []
        for j in range(3):
            aspirants.append(random.choice(pop))
        if fitness(aspirants[0]) > fitness(aspirants[1]):
            if fitness(aspirants[0]) > fitness(aspirants[2]):
                macs = aspirants[0]
            else: macs = aspirants[2]
        else:
            if fitness(aspirants[1]) > fitness(aspirants[2]):
                macs = aspirants[1]
            else: macs = aspirants[2]
        chosen.append(macs)
    return chosen

def crossover(offspring):
    for child1, child2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < 0.7:
            child1[50:100], child2[50:100]=child2[50:100], child1[50:100]

def mutate(offspring):
    for mut in offspring:
        if random.random() < 0.3:
            for i in range(len(mut)):
                if random.random() < 0.05:
                    mut[i] = type(mut[i])(not mut[i])

def gen_individ():
    ind = []
    for s in range(100):
        ind.append(random.randint(0, 1))
    return ind

def gen_pop():
    pop = []  
    for s in range(300):
        pop.append(gen_individ())
    return pop

g = 0
popul = gen_pop()
print("length of pop = %i "% len(popul))
fits = []
for k in popul:
    fits.append(fitness(k))    
print("best fitness before = %i"% max(fits))
while(max(fits) < 100 and g < 100):   
    g += 1
    offspring = []
    offspring = selection(popul)
    crossover(offspring)
    mutate(offspring)
    popul.clear()
    popul[:] = offspring
    fits.clear()
    for k in popul:
    fits.append(fitness(k))
print("lenght of pop = %i "% len(popul))
print("best fitness after = %i"% max(fits))  
print("generation : %i"%g)

标签： pythonalgorithmgenetic-algorithm

解决方案

问题似乎在于，在您的所有功能中，您总是只修改相同的个体而不是创建副本。例如，在selection函数中，您反复选择三个中最好的（以相当复杂的方式），然后将同一列表的多个引用插入到chosen列表中。稍后，当您使用mutate其中任何一个时，您会改变所有引用。最后，您甚至可能只N引用同一个列表，此时显然无法进行更多实际选择。

相反，您应该创建列表的副本。这可能发生在不同的地方：在你的 main 方法中，在mutateandrecombine中，或者selection在下一次迭代中。我将其放入selection，主要是因为该功能也可以通过其他方式进行改进：

def selection(pop):
    chosen = []
    for i in range(len(pop)):
        # a lot shorter
        aspirants = random.sample(pop, 3)
        macs = max(aspirants, key=fitness)
        # create COPIES of the individual, not multiple references
        chosen.append(macs[:])
    return chosen

这样，您每次应该获得 100 的质量。

推荐阅读