为什么这个遗传算法需要太多次迭代？

Question

我正在学习遗传算法，为了更好地理解我尝试使用 python 从头开始构建遗传算法的概念，而不使用任何外部模块（仅标准库和一点点 numpy )

目标是找到一个目标字符串，所以如果我给它字符串 hello 并定义 26 个字符 + 一个 space，就有 26^5 种可能性，这是巨大的。因此需要使用遗传算法来解决这个问题。

我定义了以下函数：

生成人口：我们生成给定大小 n 的人口和我们生成 n 个具有 len(target) 个随机字符的字符串的目标，我们 return 人口作为 str

的列表

计算适应度得分：如果位置 i 的字符等于目标位置 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

Select parents，在parents之间交叉，生成新的children[=17种群=]

以下是负责该功能的函数：

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

我 selecting parent 通过计算每个人的概率（个人得分/总体得分），然后使用 加权随机选择 函数到 select 一个 parent （这是一个 numpy 函数）。

对于交叉，我生成了一个 child c 和一个随机分裂点，这个随机点之前的所有字符都是前 parent 个字符，之后的所有字符分裂点是 parent.

中的字符

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

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

def find(size,target,pop):
    scores = [fitness(ind,target) for ind in pop]
    #print("len of scores is ", len(scores))
    #good_indiv = select_individuals(pop,scores)
    #print("Length of good indivs is", len(good_indiv))
    new_pop = []
    # corssover good individuals
    for ind in pop:
        pa = select_parent(pop,scores)
        pb = select_parent(pop,scores)
        #print(pa,pb)
        child = crossover(pa,pb)
        #print(type(child))
        new_pop.append(child)
    best = print_best(new_pop,scores)
    print("********** The best individual is: ", best, " ********")
    return (new_pop,best)


n = 200
target = "hello"
popu = generate_pop(n,target)

#find(n,target,popu)


for i in range(1000):
    print(len(popu))
    data = find(n,target,popu)
    popu = data[0]
    print("iteration number is ", i)
    if data[1] == target:

        break

问题问题是生成 hello 的迭代次数超过了应有的次数（大部分时间超过 200 次迭代），而在这个例子中，它只需要几次迭代：https://jbezerra.github.io/The-Shakespeare-and-Monkey-Problem/index.html

确定问题的编码方式不同，我使用了 python 和一种程序化的方式来编码，但逻辑是相同的。那我做错了什么？

Answer 1

你有 100% 的时间变异。您 select 'suitable' parents 可能会产生适合的后代，但随后您将更有可能应用到 "throw it off" 的突变。如果您将突变率提高到 100%，您提供的示例 link 的行为方式相同。

突变的目的是 "nudge" 如果您似乎陷入局部最优，则在不同的方向上进行搜索，始终应用它会将进化算法从进化算法转变为更接近随机的算法搜索。

Answer 2

我建议在字典中定义你的字符串并给它们一个数字然后分析这个数组示例

我的字典是

我：1 吃：23 想要：12 至 : 2

所以我想吃转换为 [ 1 , 12, 2, 23] 所以随机性降低了一个因素。这里的单词是从字典中推断出来的所以唯一的变量是顺序和字符串中出现的单词。

用字典重写你的算法您的算法运行时间将提高一个系数。带着敬意泰加

Answer 3

遗传算法的思想支持最好的算法生存并创造新一代

首先，你应该为下一代保留每一代中最好的（例如，每一代中最好的 40% 在下一代中继续存活）并且你应该将这 40% 彼此繁殖并且只发生变异每一代的个体数量有限这些数字应该很低，比如低于 5% 的个体发生变异，我相信这会减少世代数量

为什么这个遗传算法需要太多次迭代？

Why is this genetic algorithm taking too many iterations?

python

optimization

heuristics

genetic-algorithm