python - 满足“Hello World”局部最优的简单遗传算法

我的目标很简单，使用遗传算法重现经典的“Hello，World”字符串。
我的代码是基于这个post。本规范主要由四部分组成：
产生具有不同个体的种群
根据与target的比较，定义评估个体好坏的适应度和等级函数。
过滤人口并离开len(pop)*retain个人
添加一些其他个体并随机变异
父母的DNA将传递给孩子，组成整个population。
我修改了代码，显示如下：

import numpy as np
import string
from operator import add
from random import random, randint
def population(GENSIZE,target):
    p = []
    for i in range(0,GENSIZE):
        individual = [np.random.choice(list(string.printable[:-5])) for j in range(0,len(target))]
        p.append(individual)
    return p

def fitness(source, target):
    fitval = 0
    for i in range(0,len(source)-1):
        fitval += (ord(target[i]) - ord(source[i])) ** 2
    return (fitval)

def grade(pop, target):
    'Find average fitness for a population.'
    summed = reduce(add, (fitness(x, target) for x in pop))
    return summed / (len(pop) * 1.0)


def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.01):
    graded = [ (fitness(x, target), x) for x in p]
    graded = [ x[1] for x in sorted(graded)]
    retain_length = int(len(graded)*retain)
    parents = graded[:retain_length]
    # randomly add other individuals to
    # promote genetic diversity
    for individual in graded[retain_length:]:
        if random_select > random():
            parents.append(individual)
    # mutate some individuals
    for individual in parents:
        if mutate > random():
            pos_to_mutate = randint(0, len(individual)-1)
            individual[pos_to_mutate] = chr(ord(individual[pos_to_mutate]) + np.random.randint(-1,1))

    #
    parents_length = len(parents)
    desired_length = len(pop) - parents_length
    children = []
    while len(children) < desired_length:
        male = randint(0, parents_length-1)
        female = randint(0, parents_length-1)
        if male != female:
            male = parents[male]
            female = parents[female]
            half = len(male) / 2
            child = male[:half] + female[half:]
            children.append(child)
    parents.extend(children)
    return parents

GENSIZE = 40
target = "Hello, World"
p = population(GENSIZE,target)
fitness_history = [grade(p, target),]
for i in xrange(20):
    p = evolve(p, target)
    fitness_history.append(grade(p, target))
#     print p
for datum in fitness_history:
   print datum

但结果似乎不能很好地拟合。
我试图改变target和循环时间（更多代）。
但结果总是被卡住有时，增加循环时间有助于找到最优解。但是当我把循环时间改成一个更大的数字，比如GENESIZE。结果显示错误如下：

    individual[pos_to_mutate] = chr(ord(individual[pos_to_mutate]) + np.random.randint(-1,1))
ValueError: chr() arg not in range(256)

无论如何，如何修改我的代码，并得到一个好的结果。
任何建议都将不胜感激。

最佳答案

python2中的chr函数只接受0你路过：
ord(individual[pos_to_mutate]) + np.random.randint(-1,1)
所以你需要检查一下
ord(individual[pos_to_mutate]) + np.random.randint(-1,1)
不会超出该范围，如果超出该范围，则在传递到chr之前采取纠正措施。
编辑
对于valueerror，一个合理的修正方法可能是在传递到chr之前将修正后的值取256模：
chr((ord(individual[pos_to_mutate]) + np.random.randint(-1, 1)) % 256)
还有一个错误：适应度计算没有考虑候选列表的最后一个元素：它应该是：

def fitness(source, target):
    fitval = 0
    for i in range(0,len(source)):  # <- len(source), not len(source) -1
        fitval += (ord(target[i]) - ord(source[i])) ** 2
    return (fitval)

如果源和目标的长度必须相等，则函数可以编写为：

def fitness(source, target):
    return sum((ord(t) - ord(s)) ** 2 for (t, s) in zip(target, source))

真正的问题是，为什么提供的代码在到达目标字符串之前不会演变成随机字符串。
答案，我相信，是可能的，但需要很多迭代才能做到。
考虑一下，在这个问题中引用的博客文章中，每次迭代都会生成一个子代，如果子代更合适，它将替换基因池中最不合适的成员孩子父母的选择偏向于更健康的父母，增加了孩子进入基因库的可能性，增加了基因库的整体“健康度”因此，基因库的成员在几千次迭代中收敛到期望的结果。
在所讨论的代码中，基于初始条件，即evolve函数的默认值，变异概率要低得多。
保留下来的父母只有1%的机会变异，三分之一的时间“变异”不会导致改变（0是random.randint（-1，1）的可能结果）。
丢弃的父代将被合并两个保留的个体所创建的个体所替换由于只有20%的父母被保留，人口可以收敛到一个局部最小值，其中每个新的孩子实际上是现有父母的拷贝，因此没有引入多样性。
因此，除了修复两个错误之外，更快速地收敛于目标的方法是对初始条件进行实验，并考虑改变问题中的代码以注入更多的多样性，例如通过在原始博客帖子中对儿童进行变异，或者通过扩展可能的突变范围。

关于python - 满足“Hello World”局部最优的简单遗传算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36515358/