这个代码片段是遗传算法吗？

Question

我正在尝试学习遗传算法和人工智能开发，我从一本书上复制了这段代码，但我不知道它是否是一个合适的遗传算法。这是代码 (main.py):

import random

geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,1234567890-_=+!@#$%^&*():'[]\""
target = input()

def generate_parent(length):
    genes = []
    while len(genes) < length:
        sampleSize = min(length - len(genes), len(geneSet))
        genes.extend(random.sample(geneSet, sampleSize))
    parent = ""
    for i in genes:
        parent += i
    return parent

def get_fitness(guess):
    total = 0
    for i in range(len(target)):
        if target[i] == guess[i]:
            total = total + 1
    return total
    """
    return sum(1 for expected, actual in zip(target, guess)
        if expected == actual)
    """

def mutate(parent):
    index = random.randrange(0, len(parent))
    childGenes = list(parent)
    newGene, alternate = random.sample(geneSet, 2)
    if newGene == childGenes[index]:
       childGenes[index] = alternate
    else:
       childGenes[index] = newGene
    child = ""
    for i in childGenes:
        child += i

    return child

random.seed()
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)
print(bestParent)

while True:
    child = mutate(bestParent)
    childFitness = get_fitness(child)
    if bestFitness >= childFitness:
        continue
    print(str(child) + "\t" + str(get_fitness(child)))
    if childFitness >= len(bestParent):
        break
    bestFitness = childFitness
    bestParent = child

我看到它有适应度函数和变异函数，但是它不生成种群，我不明白为什么。我认为遗传算法需要种群生成和从最佳种群成员到新一代的交叉。这是一个合适的遗传算法吗？

Answer 1

虽然AI领域有很多模棱两可的定义，但我的理解是：

一个 evolutionary algorithm (AE) 是一种算法，它有一个（一组）解决方案并通过某种方式改变它们（交叉在这里也被视为 "mutating"），你最终得到更好的解决方案。
A genetic algorithm (GA) 支持交叉的概念，其中两个或更多 "solutions" 产生新的解决方案。

但这些术语有时会混淆。但是请注意，交叉绝对不是产生新个体的唯一方法（有比遗传算法更多的方法来产生更好的解决方案），例如：

模拟退火 (SA);
禁忌搜索 (TS);
...

但如前所述，关于术语的真正含义的讨论总是很多，大多数关于概率组合优化的论文都清楚地说明了术语的含义。

所以根据上面的定义，你的程序是一种进化算法，而不是遗传算法：它在每次迭代后总是有一个群体。此外，你的程序只接受一个新的 child，如果它比它的 parent 更好，使其成为 Local Search (LS) 算法。局部搜索算法的问题在于 - 如果 some/all 解的突变 space 是解 space 的子集 - 局部搜索算法可能永远陷入局部最优。即使情况并非如此，他们也会在很长一段时间内陷入局部最优。

这不是问题，因为没有局部最优（但这当然是一个简单的问题）。更难（和有趣）的问题通常有（很多）局部最优。

如果局部搜索与其他有助于使系统再次脱离局部最优的技术协作，那么它并不是一个坏技术。其他进化技术，如模拟退火，将以小概率接受更差的解决方案（取决于解决方案有多糟糕，以及我们在进化过程中走了多远）。

这个代码片段是遗传算法吗？

Is this code fragment a genetic algorithm?

python

algorithm

python-3.x

genetic-algorithm