基于DEAP库的python进化算法–遗传算法实践–配词问题 原创

1147-柳同学

发表文章数:593

首页 » 算法 » 正文

一.前言

在非线性函数寻优中,我们看到了编码方式对问题求解的重要性,但是遗传算法的评价函数的设定也对求解有至关重要的作用。如果设定的评价函数不好,可能导致算法无法正确收敛。

二.配词问题

1.问题描述

配词问题(word matching problem)是给定某字符串,以生成同样字符串为目的的问题。

例如对目标短语’to be or not to be’,要求用遗传算法生成该短语。

这里最简单直接的个体编码方式是采用13个ASCII码进行编码(当然用字符编码也是可以的,这里因为探讨的主要问题在于评价函数的选择,因此,不对编码方式做过多探索)。

考虑评价函数时,有两种评价思路:

  • 第一种思路:是将目标函数设定为与给定的字符串的ASCII码差异,此时,配词问题转化为一个目标函数最小化问题。
  • 第二种思路:是将目标函数设定与原文相同的字符个数,此时,配图问题转化为一个目标函数最大化问题。

2.评价方式一 – ASCII码差异

遗传算法操作:

  1. 个体编码:使用ASCII码数字编码,长度为13
  2. 评价函数:与给定的字符串的ASCII码差异的绝对值之和
  3. 育种选择:锦标赛选择
  4. 变异算法:交叉-均匀交叉,变异-乱序突变
  5. 环境选择:精英保留策略
    代码实现
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: ASCII差异.py
@time: 2020/11/28 19:36
"""
import numpy as np
import random
import matplotlib.pyplot as plt
from deap import creator,tools,base,algorithms

# 定义问题
creator.create('FitnessMin',base.Fitness,weights=(-1.0,))
creator.create('Individual',list,fitness = creator.FitnessMin)

# 个体编码-ASCII编码
gen_size = 13
toolbox = base.Toolbox()
# 小写字母“a”到“z”的ASCII码值分别为97到到122
toolbox.register('genASCII',random.randint,97,122)
toolbox.register('Individual',tools.initRepeat,creator.Individual,toolbox.genASCII,n = gen_size)
# 注册种群
toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)

# 评价函数-与给定的字符串的ASCII码差异之和
def eval(ind):
    target  = list('tobeornottobe')
    # ord返回对应ASCII字符串的ASCII数值
    target = [ord(item) for item in target]
    return np.sum(np.abs(np.array(ind) - np.array(target))),

# 注册评价函数
toolbox.register('evaluate',eval)
# 注册遗传算法的操作:选择、交叉、突变
toolbox.register('select',tools.selTournament,tournsize = 2)
toolbox.register('mate',tools.cxUniform,indpb=0.5)
toolbox.register('mutate',tools.mutShuffleIndexes,indpb = 0.3)

# 创建统计学对象
stats = tools.Statistics(key= lambda ind : ind.fitness.values)
stats.register('avg',np.mean)
stats.register('std',np.std)
stats.register('min',np.min)
stats.register('max',np.max)
# 创建日志对象
logbook = tools.Logbook()
logbook.header = 'gen','avg','std','min','max'

# 遗传算法
pop_size =  100
N_GEN = 50
CXPB = 0.8
MUTPB = 0.2

# 生成种群
pop = toolbox.Population(n = pop_size)

# 评价初代种群
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
fitnesses = list(map(toolbox.evaluate,invalid_ind))
for ind,fit in zip(pop,fitnesses):
    ind.fitness.values = fit
record = stats.compile(pop)
logbook.record(gen = 0,**record)

# 遗传算法迭代
for gen in range(1+N_GEN):
    # 配重选择
    selectTour = toolbox.select(pop,pop_size)
    # 复制
    selectInd = list(map(toolbox.clone,selectTour))
    # selectInd = [toolbox.clone(_) for _ in selectTour]

    # 交叉
    for child1,child2 in zip(selectInd[::2],selectInd[1::2]):
        if random.random() < CXPB:
            toolbox.mate(child1,child2)
            del child1.fitness.values
            del child2.fitness.values

    # 变异
    for ind in selectInd:
        if random.random() < MUTPB:
            toolbox.mutate(ind)
            del ind.fitness.values

    # 对于被改变的个体,更改其适应度
    invalid_ind = [ind for ind in selectInd if not ind.fitness.valid]
    fitnesses = list(map(toolbox.evaluate,invalid_ind))
    for ind,fit in zip(invalid_ind,fitnesses):
        ind.fitness.values = fit

    # 精英育种策略
    combinedPop = pop  + selectInd
    pop = tools.selBest(combinedPop,pop_size)

    # 将统计对象应用于pop
    record = stats.compile(pop)
    logbook.record(gen = gen,**record)

# 打印迭代过程
print(logbook)
# 输出结果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
print('最优解为:',str(bestInd))
print('对应的函数最小值为:',str(bestFit))

# 可视化
gen = logbook.select('gen')
min = logbook.select('min')
avg = logbook.select('avg')
plt.plot(gen,min,'b-',label = 'MIN_FITNESS')
plt.plot(gen,avg,'r-',label = 'AVG_FITNESS')
plt.xlabel('gen')
plt.plot('fit')
plt.legend(loc = 'upper right')
plt.show()

运行结果

gen	avg   	std     	min	max
0  	105.15	18.9644 	52 	143
0  	86.53 	11.1234 	52 	100
1  	73.83 	10.1154 	43 	87 
2  	63.96 	7.74328 	43 	73 
3  	54.72 	7.76155 	24 	64 
4  	46.73 	7.13282 	23 	55 
5  	39.71 	6.63369 	21 	48 
6  	32.72 	5.20208 	19 	40 
7  	27.53 	3.71606 	19 	32 
8  	23.44 	3.0243  	14 	28 
9  	19.97 	3.07394 	11 	24 
10 	16.56 	2.63939 	9  	21 
11 	13.7  	2.52784 	5  	17 
12 	10.89 	2.61494 	4  	14 
13 	8.3   	2.35584 	3  	11 
14 	5.68  	1.55486 	2  	8  
15 	3.83  	1.12299 	1  	5  
16 	2.71  	0.919728	0  	4  
17 	1.77  	0.580603	0  	3  
18 	1.27  	0.690724	0  	2  
19 	0.64  	0.48    	0  	1  
20 	0.23  	0.420833	0  	1  
21 	0     	0       	0  	0  
22 	0     	0       	0  	0  
23 	0     	0       	0  	0  
24 	0     	0       	0  	0  
25 	0     	0       	0  	0  
26 	0     	0       	0  	0  
27 	0     	0       	0  	0  
... 
194	0     	0       	0  	0  
195	0     	0       	0  	0  
196	0     	0       	0  	0  
197	0     	0       	0  	0  
198	0     	0       	0  	0  
199	0     	0       	0  	0  
200	0     	0       	0  	0  
最优解为: ['t', 'o', 'b', 'e', 'o', 'r', 'n', 'o', 't', 't', 'o', 'b', 'e']
对应的函数最小值为: 0.0

可视化
基于DEAP库的python进化算法--遗传算法实践--配词问题
                    原创

2.评价方式二 – 与原文相同的字符个数

遗传算法操作

  1. 个体编码:使用ASCII编码,长度为13
  2. 评价函数:与原文相同的字符个数
  3. 育种选择:锦标赛选择
  4. 变异算法:交叉-均匀交叉,变异-乱序突变
  5. 环境选择:精英保留策略

代码实现

#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: ASCII差异.py
@time: 2020/11/28 19:36
"""
import numpy as np
import random
import matplotlib.pyplot as plt
from deap import creator,tools,base,algorithms

# 定义问题
creator.create('FitnessMax',base.Fitness,weights=(1.0,))
creator.create('Individual',list,fitness = creator.FitnessMax)

# 个体编码-ASCII编码
gen_size = 13
toolbox = base.Toolbox()
# 小写字母“a”到“z”的ASCII码值分别为97到到122
toolbox.register('genASCII',random.randint,97,122)
toolbox.register('Individual',tools.initRepeat,creator.Individual,toolbox.genASCII,n = gen_size)
# 注册种群
toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)

# 评价函数-生成的字符串与目标字符串相同的个数
def eval(ind):
    target = list('tobeornottobe')
    # ord返回对应ASCII字符串的ASCII数值
    target = [ord(item) for item in target]
    return np.sum(np.array(ind) == np.array(target)),


# 注册评价函数
toolbox.register('evaluate',eval)
# 注册遗传算法的操作:选择、交叉、突变
toolbox.register('select',tools.selTournament,tournsize = 2)
toolbox.register('mate',tools.cxUniform,indpb=0.5)
toolbox.register('mutate',tools.mutShuffleIndexes,indpb = 0.5)

# 创建统计学对象
stats = tools.Statistics(key= lambda ind : ind.fitness.values)
stats.register('avg',np.mean)
stats.register('std',np.std)
stats.register('min',np.min)
stats.register('max',np.max)
# 创建日志对象
logbook = tools.Logbook()
logbook.header = 'gen','avg','std','min','max'

# 遗传算法
pop_size =  100
N_GEN = 200
CXPB = 0.8
MUTPB = 0.2

# 生成种群
pop = toolbox.Population(n = pop_size)

# 评价初代种群
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
fitnesses = list(map(toolbox.evaluate,invalid_ind))
for ind,fit in zip(pop,fitnesses):
    ind.fitness.values = fit
record = stats.compile(pop)
logbook.record(gen = 0,**record)

# 遗传算法迭代
for gen in range(1+N_GEN):
    # 配重选择
    selectTour = toolbox.select(pop,pop_size)
    # 复制
    selectInd = list(map(toolbox.clone,selectTour))
    # selectInd = [toolbox.clone(_) for _ in selectTour]

    # 交叉
    for child1,child2 in zip(selectInd[::2],selectInd[1::2]):
        if random.random() < CXPB:
            toolbox.mate(child1,child2)
            del child1.fitness.values
            del child2.fitness.values

    # 变异
    for ind in selectInd:
        if random.random() < MUTPB:
            toolbox.mutate(ind)
            del ind.fitness.values

    # 对于被改变的个体,更改其适应度
    invalid_ind = [ind for ind in selectInd if not ind.fitness.valid]
    fitnesses = list(map(toolbox.evaluate,invalid_ind))
    for ind,fit in zip(invalid_ind,fitnesses):
        ind.fitness.values = fit

    # 精英育种策略
    combinedPop = pop  + selectInd
    pop = tools.selBest(combinedPop,pop_size)

    # 将统计对象应用于pop
    record = stats.compile(pop)
    logbook.record(gen = gen,**record)

# 打印迭代过程
print(logbook)
# 输出结果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
bestIndII = []
for each in bestInd:
    bestI = chr(each)
    bestIndII.append(bestI)
print('最优解为:',str(bestIndII))
print('对应的函数最小值为:',str(bestFit))

# 可视化
gen = logbook.select('gen')
min = logbook.select('min')
avg = logbook.select('avg')
plt.plot(gen,min,'b-',label = 'MIN_FITNESS')
plt.plot(gen,avg,'r-',label = 'AVG_FITNESS')
plt.xlabel('gen')
plt.plot('fit')
plt.legend(loc = 'upper right')
plt.show()

运行结果

gen	avg  	std     	min	max
0  	0.51 	0.699929	0  	3  
0  	1.26 	0.687314	0  	3  
1  	1.94 	0.71861 	1  	4  
2  	2.59 	0.664756	2  	5  
3  	3.4  	0.565685	3  	5  
4  	3.98 	0.599667	3  	6  
5  	4.58 	0.750733	4  	7  
6  	5.55 	0.71239 	5  	8  
7  	6.36 	0.793977	5  	9  
8  	7.22 	0.944246	6  	10 
9  	8.15 	0.84113 	7  	11 
10 	9.03 	0.754387	8  	12 
11 	9.77 	0.810617	9  	12 
12 	10.53	0.623779	10 	12 
13 	11.2 	0.489898	10 	12 
14 	11.62	0.485386	11 	12 
15 	12   	0       	12 	12 
16 	12   	0       	12 	12 
17 	12   	0       	12 	12 
18 	12   	0       	12 	12 
19 	12   	0       	12 	12 
...
194	12   	0       	12 	12 
195	12   	0       	12 	12 
196	12   	0       	12 	12 
197	12   	0       	12 	12 
198	12   	0       	12 	12 
199	12   	0       	12 	12 
200	12   	0       	12 	12 
最优解为: ['t', 'o', 'b', 'e', 'o', 'r', 'n', 'o', 't', 'f', 'o', 'b', 'e']

可视化
基于DEAP库的python进化算法--遗传算法实践--配词问题
                    原创

小结

  • 这里给出的评价方法一的结果是多次运行后的一个较优解:[‘t’, ‘o’, ‘b’, ‘f’, ‘o’, ‘q’, ‘n’, ‘p’,
    ‘t’, ‘t’, ‘o’, ‘b’, ‘e’],它显然并非全局最优解 — 并没有能完全复现我们的目标;
  • 评价方法二的结果是多次运行中随便取了一次结果 — 它每次都能以很快的速度收敛到最优解。
  • 两个程序的差别仅仅在于更换了评价函数,别的遗传算法操作完全相同,可以看到评价函数选择对于遗传算法设计的重要性。

未经允许不得转载:作者:1147-柳同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《基于DEAP库的python进化算法–遗传算法实践–配词问题 原创》 发布于2021-02-05

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录