满足局部最优解的简单遗传算法

Question

我的目标很简单，用遗传算法来复制经典的“Hello，World”字符串。
我的代码基于这个post。代码主要包括4部分：

1. 产生具有不同个体的群体
2. 根据与^{cd1>}的比较，定义评价个体优劣的适应度和等级函数。
3. 过滤种群并离开^{cd2>}个人
4. 添加其他个体并随机变异
5. 父母的DNA将传递给孩子，以构成整个^{cd3>。

我修改了代码，并显示如下：

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  

但是，结果似乎不太适合^{cd1>}。

我试图更改^{cd5>}和循环时间（更多生成）。
但结果总是被卡住。有时，提高循环时间可以帮助找到一个最佳的解决方案。但是当我将循环时间改为一个更大的数字时，比如^{{cd6>}。结果显示如下错误：

^{pr2}$

无论如何，如何修改我的代码并取得良好的结果。
如有任何建议，请谅解。

Answer 1

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

您正在通过：

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

所以你需要检查

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

将不在该范围之外，并在传递给chr之前执行更正操作（如果它超出该范围）。在

编辑

{256}可能会在传递值之前修正{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) 

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

^{pr2}$

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

答案，我相信，是可能的，但要做到这一点需要很多迭代。在

考虑一下，在这个问题中引用的博客文章中，每次迭代都会生成一个子代，如果这个子代更适合，它将替换基因库中最不适合的成员。孩子父母的选择偏向于更健康的父母，这增加了孩子进入基因库的可能性，并增加了基因库的整体“健康度”。因此，基因库的成员在几千次迭代中收敛到期望的结果。在

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

1. 保留下来的父母只有1%的机会突变，三分之一的时间“突变”不会导致变化（零可能是随机.randint（-1，1））。

2. “丢弃父对象”将由合并两个保留的个体来替换。由于只保留了20%的父母，人口可以收敛到一个局部最小值，即每个新出生的孩子实际上都是现有父母的副本，因此没有引入多样性。

因此，除了修复这两个bug之外，更快地收敛到目标上的方法是试验初始条件，并考虑更改问题中的代码以注入更多的多样性，例如，像最初的博客文章中那样对孩子进行突变，或者扩大可能的突变范围。在