遗传算法字符串猜测

Question

我试图理解如何实现一个遗传算法，并写了一个简单的字符串猜测。我很难理解为什么这个解决方案不起作用。在

我相信我的问题在于我的新一代人的繁衍？新一代人似乎没有提高健身价值。我也不确定我是否正确地做了交叉和突变率。任何帮助都将非常感谢！在

POP_SIZE = 300;
CROSSOVER_RATE = 0.7;
MUTATION_RATE = 0.01
GENESET = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"
target = "Hello World"
RAND_NUM = random.random()

def generateBasePopulation(population_size):
    population = dict()

    for _ in range(POP_SIZE):
        gene = generateParent(len(target))
        population[gene] = 0

    return population


def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while(len(newPopulation) <= POP_SIZE):
        child_one, child_two = crossover(child_one, child_two)
        child_one = mutate(child_one)
        child_two = mutate(child_two)


    newPopulation[child] = 0
    newPopulation[child_two] = 0
    return newPopulation



def assignFitness(population):
    for x in population:
        population[x] = getFitness(x)


def generateParent(length):
    genes = list("")
    for i in range(0,length):
        random_gene = random.choice(GENESET)
        genes.append(random_gene)
    return(''.join(genes))

def getFitness(candidate):
    fitness = 0
    for i in range(0, len(candidate) - 1):
        if target[i] == candidate[i]:
            fitness += 1
    return(fitness)

def mutate(parent):
    gene_index_to_mutate = random.randint(0, len(parent) - 1)
    mutation_value = random.choice(GENESET)
    genes = list(parent)
    genes[gene_index_to_mutate] = mutation_value
    return(''.join(genes))

def crossover(parentA, parentB):
    if(RAND_NUM < CROSSOVER_RATE):
        random_index = random.randint(0, len(target))
        parentASlice = parentA[:random_index]
        parentBSlice = parentB[random_index:]

        return (parentASlice + parentBSlice), (parentBSlice + parentASlice)
    return parentA, parentB


def chooseChild(population):
    fitnessSum = sum(population.values())
    pick = random.uniform(0, fitnessSum)
    current = 0
    for pop in population:
        current += population[pop]
        if current >= pick:
            return pop


def main():
    population = generateBasePopulation(POP_SIZE)

    targetNotFound = True

    while(targetNotFound):
        assignFitness(population)
        if target in population:
            print("target found!")
            targetNotFound = False
        if(targetNotFound):
            tempPopulation = generateNewPopulation(population, POP_SIZE)
            population.clear()
            population = tempPopulation

Answer 1

generateNewPopulation函数有一些问题。在

child_one和{}在赋值之前被引用

你需要从人群中选出两个进行交叉。有几种选择算法，但为了给出一个想法，您可以从tournament selection的形式开始：

def extractFromPopulation(population):
    best = random.choice(list(population.keys()))

    for _ in range(4):
        gene = random.choice(list(population.keys()))
        if population[gene] > population[best]:
            best = gene

    return best

这里选择压力（range(4)）是固定的。这是你在实际情况下必须调整的参数之一。在

现在我们有了：

^{pr2}$

代码仍然不起作用，因为

新的个体不会被插入newPopulation

只需缩进两行：

newPopulation[child] = 0
newPopulation[child_two] = 0

（它们必须是while循环的一部分）

修订后的generateNewPopulation函数如下：

def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while len(newPopulation) <= POP_SIZE:
        child_one = extractFromPopulation(population)
        child_two = extractFromPopulation(population)

        child_one, child_two = crossover(child_one, child_two)
        child_one = mutate(child_one)
        child_two = mutate(child_two)

        newPopulation[child_one] = 0
        newPopulation[child_two] = 0

    return newPopulation

---

crossover函数不能基于固定的RAND_NUM值

删除RAND_NUM = random.random()赋值，并更改crossover函数，以便在每次调用时使用新的随机值：

def crossover(parentA, parentB):
    if random.random() < CROSSOVER_RATE:
        random_index = random.randint(0, len(target))
        parentASlice = parentA[:random_index]
        parentBSlice = parentB[random_index:]

        return (parentASlice + parentBSlice), (parentBSlice + parentASlice)

    return parentA, parentB

另外，由于第二个父对象的模式没有被保留，所以代码不能正确地执行单点交叉。在

---

您可以更改许多细节来提高性能，但是作为一个开始的例子，它可能已经足够了（…它起作用了）。在

找到一个解决方案的平均代数大约是158（在200运行时的平均数）。在

---

编辑（感谢alexis为comment设计的）

MUTATION_RATE未使用，并且总是发生突变。mutate函数应该类似于：

def mutate(parent):
    if random.random() < MUTATION_RATE: 
        gene_index_to_mutate = random.randint(0, len(parent) - 1)
        mutation_value = random.choice(GENESET)
        genes = list(parent)
        genes[gene_index_to_mutate] = mutation_value
        return ''.join(genes)

    return parent

如果您保持轮盘赌选择算法（chooseChild通常在没有修正的情况下不会收敛），那么这个修正就特别重要。在