本文共 5967 字，大约阅读时间需要 19 分钟。

前言

  该笔记主要记录两个问题：

  （1）基于deap库的遗传算法程序框架大致什么样？   （2）在框架的基础上如何实现经典的配词问题？

基于deap的程序框架

  经过一段时间的入门学习，本人总结出基于deap库的遗传算法框架大致如以下代码所示：

import numpy as npfrom deap import base, tools, creator, algorithmsimport random# 问题定义；定式creator.create('Fitness...', base.Fitness, weights=(...1.0,)) #　最大化问题creator.create('Individual', list, fitness=creator.Fitness...)# 个体编码；主要依靠人为设计geneLength=...toolbox = base.Toolbox()toolbox.register('个体实现方法的名称',...)toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.个体实现方法的名称, n=geneLength)#print(toolbox.individual())#打印检查个体#创建种群；定式N_POP = ...#种群内个体数量，参数过小，则搜索速度过慢toolbox.register('population',tools.initRepeat,list,toolbox.individual)pop = toolbox.population(n=...)#创建一个种群pop#for ind in pop:#打印一个种群检查#   print(ind)#评价函数；主要依靠人为设计def evaluate(ind):   ...    return ...,    #注册各种工具，人为选择具体的方法；写法定式toolbox.register('evaluate', evaluate)#评价函数toolbox.register('select', tools...)#选择toolbox.register('mate', tools...)#交叉toolbox.register('mutate', tools...)#突变#超参数设置；人为根据理论与经验设定NGEN = ...#迭代步数，参数过小，则在收敛之前就结束搜索CXPB = ...#交叉概率，参数过小，则族群不能有效更新MUTPB = ...#突变概率，参数过小，则容易陷入局部最优#开始工作，先对初始的种群计算适应度；定式invalid_ind = [ind for ind in pop if not ind.fitness.valid]fitnesses = toolbox.map(toolbox.evaluate,invalid_ind)for ind ,fitness in zip(invalid_ind,fitnesses):    ind.fitness.values = fitness    #循环迭代，近似定式，但是可以自行增加一些提高遗传算法性能的方法for gen in range(NGEN):    offspring = toolbox.select(pop,N_POP)#先选择一次    offspring = [toolbox.clone(_) for _ in offspring]#再克隆一次，克隆是必须的    for ind1,ind2 in zip(offspring[::2],offspring[1::2]):#交叉操作        if random.random() < CXPB:#交叉            toolbox.mate(ind1,ind2)            del ind1.fitness.values            del ind2.fitness.values    for ind in offspring:#变异操作        if random.random() 

  由以上的程序框架可知：

  （1）个体编码方式、评价函数基本依靠个人根据实际问题设计。   （2）选择方法注册工具、迭代运算等基本是定式。   （3）迭代运算虽然可以当做定式用，但是适当增加一些诸如精英选择策略这样的代码可以明显提高算法性能。   

配词问题

  配词问题内容比较简单，比如有个字符串‘woshidaxuesheng’，希望能用随机算法经过寻优将等长的随机字母序列生成同样的内容。在遗传算法里就等于是生成一个拥有很多随机字母个体的种群，经过运算后得到一个个体内容最接近于‘woshidaxuesheng’。

  先贴上完整的源代码，再分析问题。这里可以看到配词问题代码用了两种评价函数：一种是将配词问题转化为最小化问题，令个体的内容与目标字符串差异最小；一种是将配词问题转化为最大化问题，令个体的内容与目标字符串相同性最强。   本代码将最小化思路程序片段进行了注释，使用最大化思路程序。

import numpy as npfrom deap import base, tools, creator, algorithmsimport random# 问题定义#creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #　最小化问题#creator.create('Individual', list, fitness=creator.FitnessMin)creator.create('FitnessMax', base.Fitness, weights=(1.0,)) #　最大化问题creator.create('Individual', list, fitness=creator.FitnessMax)# 个体编码geneLength = 14#字符串内有14个字符toolbox = base.Toolbox()toolbox.register('genASCII',random.randint, 97, 122)#英文小写字符的ASCII码范围为97~122toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.genASCII, n=geneLength)#print(toolbox.individual())#创建种群N_POP = 100#种群内个体数量，参数过小，则搜索速度过慢toolbox.register('population',tools.initRepeat,list,toolbox.individual)pop = toolbox.population(n=N_POP)#for ind in pop:#打印一个种群检查#   print(ind)#评价函数#def evaluate(ind):#    target = list('zzyshiwodedidi')#    target = [ord(item) for item in target]#    return (sum(np.abs(np.asarray(target) - np.asarray(ind)))),def evaluate(ind):    target = list('zzyshiwodedidi')#需要匹配的字符串    target = [ord(item) for item in target]#将字符串内的字符都转换成ASCII码    return (sum(np.abs(np.asarray(target) == np.asarray(ind)))),    #注册各种工具toolbox.register('evaluate', evaluate)#评价函数toolbox.register('select', tools.selTournament, tournsize=2)#锦标赛选择toolbox.register('mate', tools.cxUniform, indpb=0.5)#均匀交叉toolbox.register('mutate', tools.mutShuffleIndexes, indpb=0.5)#乱序突变#超参数设置NGEN = 300#迭代步数，参数过小，则在收敛之前就结束搜索CXPB = 0.8#交叉概率，参数过小，则族群不能有效更新MUTPB = 0.2#突变概率，参数过小，则容易陷入局部最优#开始工作，先对初始的种群计算适应度invalid_ind = [ind for ind in pop if not ind.fitness.valid]fitnesses = toolbox.map(toolbox.evaluate,invalid_ind)for ind ,fitness in zip(invalid_ind,fitnesses):    ind.fitness.values = fitness    #循环迭代for gen in range(NGEN):    offspring = toolbox.select(pop,N_POP)#先选择一次    offspring = [toolbox.clone(_) for _ in offspring]#再克隆一次    for ind1,ind2 in zip(offspring[::2],offspring[1::2]):#交叉        if random.random() < CXPB:#交叉            toolbox.mate(ind1,ind2)            del ind1.fitness.values            del ind2.fitness.values    for ind in offspring:#变异        if random.random() 

  

程序设计

个体设计

  首先考虑个体是如何设计编码的。

  我们要得到一个与’zzyshiwodedidi‘最相近的字符串，显然这个个体也得是个小写字母的字符串，而且长度得和’zzyshiwodedidi'相同，所以个体的基因长度肯定是14。   综上，个体应该是个长度为14的随机小写字母列表。

# 个体编码geneLength = 14#字符串内有14个字符toolbox = base.Toolbox()toolbox.register('genASCII',random.randint, 97, 122)#英文小写字符的ASCII码范围为97~122toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.genASCII, n=geneLength)#print(toolbox.individual())

  小写英文字母的ASCII码范围是97~122，而且ASCII码肯定是整数，所以随机函数应该是随机生成整形（int），所以注册函数写成：

toolbox.register('genASCII',random.randint, 97, 122)

  再将这个注册函数代入到个体的注册函数里面即可。

toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.genASCII, n=geneLength)

评价函数设计

  我们想要评价一个个体和’zzyshiwodedidi‘的相似程度，自然要进行比较，字符显然不方便直接比，但是转换成ASCII码（数字）显然就方便的多。

  于是评价函数的设计思路就是：将目标’zzyshiwodedidi'转化为ASCII码，然后与个体的基因依次对比（个体本身就是ASCII码）。

def evaluate(ind):    target = list('zzyshiwodedidi')#需要匹配的字符串    target = [ord(item) for item in target]#将字符串内的字符都转换成ASCII码    return (sum(np.abs(np.asarray(target) == np.asarray(ind)))),

  使用ord函数将字符串里的字符依次转换为ASCII码。

target = list('zzyshiwodedidi')#需要匹配的字符串    target = [ord(item) for item in target]#将字符串内的字符都转换成ASCII码

  依次转换完成后需要依次比对，这里需要注意一件事，将目标字符串转换为ASCII码序列，与直接的随机数列表个体的数据形式不同。

        由上图可见，第一行个体是列表格式，元素之间用,割开；而第二行目标字符串转换完后是矩阵形式，是一个行向量。   因此需要将个体使用np.asarry函数转换为矩阵形式：

return (sum(np.abs(np.asarray(target) == np.asarray(ind)))),

  当然只需要转换个体就行了：

return (sum(np.abs(target == np.asarray(ind)))),

精英选择策略

  精英选择策略，即在每一轮迭代循环中，将父代与交叉变异后的子代整一块，形成一个双倍于之前规模的大种群，随后在这个大种群中提取出一半适应度最优的个体。

  说白了就是父代子代一起评，前一半的全提走，后一半的全踢走。   显然，这样的做法会加速收敛，快速得到一个充满高适应度个体的精英种群。   这个策略以后也可以叫内卷策略。

#精英选择策略，加速收敛     combinedPop = pop + offspring#将子代与父代结合起来    pop = tools.selBest(combinedPop,N_POP)#再从子代与父代的结合中选择出适应度最高的一批作为新的种群

转载地址：http://oalm.baihongyu.com/