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

Question

我的目标很简单，使用遗传算法重现经典的“Hello, World”字符串。
我的代码基于此 post .代码主要包含4个部分:

1. 生成具有多个不同个体的种群
2. 根据与target的比较，定义评估个体好坏的适应度和等级函数。
3. 过滤种群，留下len(pop)*retain个个体
4. 添加一些其他个体并随机变异
5. parent 的 DNA 会传给 child ，从而构成整个种群。

我修改了代码，显示如下:

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 和循环时间(更多代)。
但是结果总是卡住。有时，增加循环时间可以帮助找到最佳解决方案。但是当我将循环时间更改为更大的数字时，例如 for i in xrange(10000)。结果显示如下错误:

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

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

Answer 1

Python2 中的 chr 函数只接受 0 <= i < 256 范围内的值。

你正在通过:

ord(individual[pos_to_mutate]) + np.random.randint(-1,1)

所以你需要检查

的结果

ord(个体[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))

真正的问题是，为什么提供的代码在达到目标字符串之前不演化随机字符串。

我相信答案是可能的，但需要多次迭代才能实现。

考虑一下，在问题中引用的博客文章中，每次迭代都会生成一个子项，如果该子项更合适，它会替换基因库中最不适合的成员。 child parent 的选择偏向于更适合的 parent ，增加了 child 进入基因库的可能性，增加了基因库的整体“适应度”。因此，基因库的成员在几千次迭代中收敛于所需的结果。

在问题的代码中，突变的概率要低得多，基于初始条件，即 evolve 函数的默认值。

1. 保留的父代只有 1% 的机会发生变异，三分之一的时间“变异”不会导致变化(零是 random.randint(-1, 1 )).

2. 丢弃的 parent 被通过合并两个保留个体创建的个体所取代。由于只保留了 20% 的 parent ，种群可以收敛于局部最小值，其中每个新 child 实际上都是现有 parent 的副本，因此不会引入多样性。

所以除了修复这两个错误之外，更快地收敛到目标的方法是试验初始条件并考虑更改问题中的代码以注入(inject)更多多样性，例如通过像原始中那样改变 child 博客文章，或通过扩展可能的突变范围。