为什么这种遗传算法需要太多的迭代？

Question

我正在学习遗传算法，为了更好地理解这些概念，我试图使用python从头开始构建遗传算法，而不使用任何外部模块（只是标准库和一点点麻木）

目标是找到一个目标字符串，所以如果我给它字符串hello并定义26个字符+一个空格，有26 ^ 5种可能性，这是巨大的。因此，需要使用GA来解决这个探针。

我定义了以下函数：

生成总体 ：我们生成给定大小n的群体和目标，我们生成n个具有随机字符的字符串，我们将总体作为str列表返回len(target)

计算适应性分数：如果位置处的字符等于目标位置 i 处的 char，我们将增加分数，下面是代码：i

def fitness(indiv,target):

    score = 0

    #print(indiv," vs ",target)

    for idx,char in enumerate(list(target)):

        if char == indiv[idx]:

            score += 1

        else:

            score = 0

    return score

选择父母，在父母之间杂交并产生新的儿童群体

以下是负责此的函数：

from numpy.random import choice

def crossover(p1,p2):

    # we define a crossover between p1 and p2 (single point cross over)

    point = random.choice([i for i in range (len(target))])

    #print("Parents:",p1,p2)

    # C1 and C2 are the new children, before the cross over point they are equalt to their prantes, after that we swap

    c = [p1[i] for i in range(point)]

    #print("Crossover point: ",point)

    for i in range(point,len(p1)):

        c.append(p2[i])

    #print("Offsprings:", c1," and ", c2)

    c = "".join(c)

    # we mutate c too

    c = mutate(c)

    return c

def mutate(ind):

    point = random.choice([i for i in range (len(target))])

    new_ind = list(ind)

    new_ind[point] = random.choice(letters)

    return "".join(new_ind)

def select_parent(new_pop,fit_scores):

    totale = sum(fit_scores)

    probs = [score/totale for score in fit_scores]

    parent = choice(new_pop,1,p=probs)[0]

    return parent

我通过计算每个个体的概率（个体分数/总体分）来选择父母，然后使用加权随机选择函数来选择父母（这是一个numpy函数）。

对于交叉，我正在生成一个子级和一个随机分割点，此随机点之前的所有字符都是第一个父级字符，拆分点之后的所有字符都是来自父级的字符。c

除此之外，我还定义了一个名为should_stop函数，用于检查我们是否找到了目标，并print_best，该函数从总体中获得最佳个体（最高适应性分数）。

然后，我创建了一个使用上面定义的所有函数的 find 函数：

问题问题在于，生成 hello 需要的迭代次数比预期的要多（大多数情况下超过 200 次迭代），而在此示例中，它只需要很少的迭代：https://jbezerra.github.io/The-Shakespeare-and-Monkey-Problem/index.html

当然，问题不是以相同的方式编码的，我使用了python和一种过程方法来编码事物，但逻辑是相同的。那么我做错了什么？

Answer 1

你100%的时间都会变异。你选择“合适的”父母，这些父母可能会产生一个合适的后代，但随后你应用了一个更有可能“抛弃它”的突变。如果您将突变率提高到 100%，您提供的示例链接的行为方式相同。突变的目的是，如果你似乎被困在局部最优值，就把搜索“推向不同的方向，一直应用它，把它从进化算法变成更接近随机搜索的东西。

Answer 2

遗传算法的思想支持最好的人生存并创造新一代首先，你应该为每一代保留最好的个体（例如，每一代最好的40%继续生活在下一代），你应该相互繁殖这40%，并且每一代只突变有限数量的个体，这些数字应该很低，比如低于5%的个体突变我相信这将减少世代数

Answer 3

我建议在字典中定义字符串并给他们一个数字，然后分析这个数组示例我的字典是I ： 1 吃 ： 23 想 ： 12 至 ： 2所以我想吃转换为[ 1，12，2，23]，这样随机性就会减少一个因素。这里的单词是从字典中推断出来的，所以唯一的变量是顺序和哪些单词出现在你的字符串中。用字典重写算法，你的算法运行时间将提高一个因素。关于特哈