基于DEAP库的python进化算法–遗传算法实践–非线性函数寻优 原创

1147-柳同学

发表文章数:593

首页 » 算法 » 正文

一.前言

前面是python的DEAP库的基础知识,从本节开始,总结遗传算法的应用案例

二.非线性函数寻优问题

为了验证遗传算法的寻优能力,这里用常用的非线性函数Beale Function进行测试。
目标函数为:
基于DEAP库的python进化算法--遗传算法实践--非线性函数寻优
                    原创
该函数在搜索域内的最小值已知为f(3,0.5)=0
函数在搜索域内的图像如下:
基于DEAP库的python进化算法--遗传算法实践--非线性函数寻优
                    原创
用遗传算法求解优化问题的一个关键在于如何对问题的搜索空间进行编码,合理的编码方式能够大幅加快收敛速度,甚至编码的合理与否决定了算法能否寻找到最优解。

对于该问题,有两种编码思路:

  • 一种是对两个变量分别用实数进行编码,这样也省去了解码的繁琐,所见即所得;
  • 另一种思路是用二进制编码对搜索空间进行离散化,在给定需要的精度的情况下,可以用有限位的二进制编码描述搜索空间。

1.实数编码

用实数对变量进行编码,一个变量对应于一个实数
遗传算法操作如下:

  1. 个体编码:实数编码
  2. 评价函数:直接使用原函数值进行评价
  3. 育种选择:锦标赛选择
  4. 变异算法:交叉-模拟二值交叉,变异-有界多项式突变
  5. 环境选择:采用精英保存策略,加速收敛
    代码如下
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: 实数编码.py
@time: 2020/11/28 13:41
"""
import random
import numpy as np
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)

# 个体编码
gen_size = 2
lb = [-4.5] * gen_size
up = [4.5] * gen_size
# 在上界与下界用均匀分布生成实数向量
def uniform(lb,up):
    return [random.uniform(a,b) for a,b in zip(lb,up)]

# 生成个体
toolbox = base.Toolbox()
toolbox.register('Attr_float',uniform,lb,up)
toolbox.register('Individual',tools.initIterate,creator.Individual,toolbox.Attr_float)
# 生成种群
toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)

# 定义评价函数
def eval(ind):
    f = np.square(1.5-ind[0]+ind[0]*ind[1]) + np.square(2.25 - ind[0] + ind[0]*ind[1]*ind[1])+np.square(2.625-ind[0]+ind[0]*ind[1]**3)
    return f,

# 注册评价函数
toolbox.register('evaluate',eval)
# 注册遗传算法工具箱-选择、交叉、变异
toolbox.register('select',tools.selTournament,tournsize=2)
toolbox.register('mate',tools.cxSimulatedBinaryBounded,eta=20,low=lb,up=up)
toolbox.register('mutate',tools.mutPolynomialBounded,eta=20,low=lb,up =up,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 = 50
cxpb = 0.8  # 交叉概率
mutpb = 0.5 # 突变概率

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

# 评价初代种群
fitnesses = map(toolbox.evaluate,pop)
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+1):
    # 育种选择
    selectTour = toolbox.select(pop,pop_size)
    # 复制
    selectInd = list(map(toolbox.clone,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 = 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)

    # 记录数据
    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_fitness = logbook.select('min')
avg_fitness = logbook.select('avg')

fig = plt.figure(figsize=(10,10))
fig.add_subplot()
plt.plot(gen,min_fitness,'r-',label='MIN_FITNESS')
plt.plot(gen,avg_fitness,'b-',label='AVG_FITNESS')
plt.xlabel('gen')
plt.ylabel('fit')
plt.legend(loc = 'upper right')
plt.tight_layout()
plt.show()

运行结果

gen	avg        	std        	min        	max        
0  	8198.47    	25245.5    	0.0658272  	174806     
1  	28.5164    	27.4648    	0.0658272  	124.675    
2  	6.58344    	5.45893    	0.0658272  	16.0455    
3  	1.29481    	1.07369    	0.00934788 	3.31311    
4  	0.319412   	0.336374   	0.00342676 	1.27555    
5  	0.099673   	0.0736203  	0.00342676 	0.25643    
6  	0.0440874  	0.0206456  	0.00342676 	0.077893   
7  	0.0262034  	0.0117404  	0.00342676 	0.0396657  
8  	0.0173531  	0.0101289  	0.00342676 	0.032724   
9  	0.00899366 	0.00191718 	0.00342676 	0.0115913  
10 	0.00805542 	0.00236732 	0.00339565 	0.00934788 
11 	0.00623439 	0.00282093 	0.00332513 	0.00934788 
12 	0.00345702 	4.86984e-05	0.00331963 	0.00363282 
13 	0.00341989 	2.32944e-05	0.003288   	0.0034553  
14 	0.00341353 	2.69547e-05	0.003288   	0.00342676 
15 	0.00339472 	3.90865e-05	0.003288   	0.00342553 
16 	0.00336469 	4.25248e-05	0.00328466 	0.00341162 
17 	0.00333274 	3.83488e-05	0.00328105 	0.00339564 
18 	0.00330617 	1.74874e-05	0.00328095 	0.00333432 
19 	0.00327235 	0.000163752	0.00164339 	0.00330406 
20 	0.00320996 	0.000370319	0.000957577	0.00328934 
21 	0.00311671 	0.000506652	0.000957577	0.00328862 
22 	0.00286243 	0.000734954	0.000955768	0.00328643 
23 	0.00262658 	0.000844323	0.000375873	0.00328283 
24 	0.00198722 	0.000809283	0.000375873	0.00328089 
25 	0.00138844 	0.00037368 	8.54633e-05	0.00174383 
26 	0.00110416 	0.000433796	6.51641e-05	0.00163612 
27 	0.000732725	0.000349145	6.51641e-05	0.00113525 
28 	0.000435754	0.000292935	6.51369e-05	0.000912787
29 	0.000218533	0.000136372	5.0054e-05 	0.000375873
30 	9.03701e-05	3.87092e-05	4.61449e-05	0.000237072
31 	6.82337e-05	7.59414e-06	4.61449e-05	8.10387e-05
32 	6.1814e-05 	6.40116e-06	4.58844e-05	6.51641e-05
33 	5.65182e-05	7.82439e-06	4.4722e-05 	6.51637e-05
34 	4.95622e-05	3.89206e-06	4.4722e-05 	6.3112e-05 
35 	4.6264e-05 	9.87726e-07	4.47124e-05	5.004e-05  
36 	4.58565e-05	3.47451e-07	4.47124e-05	4.61424e-05
37 	4.56737e-05	3.81071e-07	4.46149e-05	4.59697e-05
38 	4.54769e-05	4.35087e-07	4.46114e-05	4.58528e-05
39 	4.51161e-05	4.37749e-07	4.46114e-05	4.5723e-05 
40 	4.47243e-05	5.03236e-08	4.46108e-05	4.49247e-05
41 	4.46896e-05	4.24606e-08	4.46042e-05	4.4722e-05 
42 	4.46623e-05	4.70643e-08	4.45853e-05	4.47127e-05
43 	4.4618e-05 	1.95394e-08	4.45853e-05	4.46816e-05
44 	4.44942e-05	1.14725e-06	3.30793e-05	4.46117e-05
45 	4.4261e-05 	1.96679e-06	3.30736e-05	4.46112e-05
46 	4.40289e-05	2.50584e-06	3.30736e-05	4.46096e-05
47 	4.32034e-05	3.77574e-06	3.21165e-05	4.46044e-05
48 	4.05308e-05	5.50942e-06	3.21107e-05	4.46042e-05
49 	3.70445e-05	5.45119e-06	3.21107e-05	4.45856e-05
50 	3.29702e-05	3.3387e-07 	3.21103e-05	3.34867e-05
最优解为: [2.992885275090831, 0.49720582445885575]
对应的函数最小值为: 3.2110322054014203e-05

可视化
基于DEAP库的python进化算法--遗传算法实践--非线性函数寻优
                    原创

2.二进制编码

二进制编码方式
在给定了需求的精度,例如小数点后6位时,可以用一定长度的二进制编码来代表变量。在需求精度为小数点后6位时,我们将每单位区间分割为1*10^6个数字,需要编码的长度为:
基于DEAP库的python进化算法--遗传算法实践--非线性函数寻优
                    原创
解码方式
在评价个体时,我们需要将二进制编码转换为十进制编码,然后再转换为落在搜索区间范围内的实数。
十进制转换为区间内实数可以根据下式完成:
基于DEAP库的python进化算法--遗传算法实践--非线性函数寻优
                    原创
遗传算法操作

  1. 个体编码-二进制编码
  2. 评价函数-解码后在转换为区间内实数
  3. 育种选择:锦标赛选择
  4. 变异算法:交叉-两点交叉,突变-位翻转突变
  5. 环境选择:采用精英保存策略,加速收敛

代码实现

#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: 二进制编码.py
@time: 2020/11/28 15:48
"""
import random
import numpy as np
from deap import creator,base,tools,algorithms

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

# 生成个体
# 二进制编码
gen_size = 48   #基因长度
toolbox = base.Toolbox()
# np.random.randint ≠ random.randint  前面不包括high,后面包括b
toolbox.register('Binary',random.randint,0,1)
toolbox.register('Individual',tools.initRepeat,creator.Individual,toolbox.Binary,n=gen_size)
# 生成种群
toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)

# 二进制编码的解码
def decode(ind,gen_size):
    '''
    给定一条二进制染色体编码,将其分割为两个变量,并分别转换为对应的十进制数
    :param ind: 染色体
    :param gen_size: 基因长度
    :return: 返回两个十进制编码
    '''
    len = int(gen_size / 2)
    x1 = int(''.join(str(_) for _ in ind[:len]),2)
    x2 = int(''.join(str(_) for _ in ind[len:]),2)
    return x1,x2,len

low = [-4.5,-4.5]
up = [4.5,4.5]

# 将十进制转换为区间内实数
def rescaled(ind,low,up):
    x1,x2,len = decode(ind,gen_size)
    x1_rescaled = low[0] + x1 * (up[0] - low[0]) / (2**len - 1)
    x2_rescaled = low[1] + x2 * (up[1] - low[1]) / (2**len - 1)
    return x1_rescaled,x2_rescaled

# 定义评价函数
def eval(ind):
    x0,x1 = rescaled(ind,low,up)
    f = np.square(1.5 - x0 + x0 * x1) + np.square(2.25 - x0 + x0 * x1 * x1) + np.square(
        2.625 - x0 + x0 * x1 ** 3)
    return f,

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

# 创建统计对象
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)

# 评价初代种群
fitnesses = list(map(toolbox.evaluate,pop))
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+1):
    # 育种选择
    selectTour = toolbox.select(pop,pop_size)
    # 复制
    selectInd = list(map(toolbox.clone,selectTour))
    # selectInd = list(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)

    # 记录数据
    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))

# 可视化
import matplotlib.pyplot as plt

avg = logbook.select('avg')
min = logbook.select('min')
gen = logbook.select('gen')
plt.plot(gen,avg,'r-',label = 'AVG_FITNESS')
plt.plot(gen,min,'b-',label = 'MIN_FITNESS')
plt.xlabel('gen')
plt.ylabel('fitness')
plt.legend(loc = 'upper right')
plt.tight_layout()
plt.show()

运行结果

gen	avg       	std        	min       	max       
0  	4821.5    	12439.2    	0.588177  	78722.2   
1  	22.8393   	22.3968    	0.588177  	92.9485   
2  	6.29688   	4.2416     	0.0748978 	13.6468   
3  	2.67486   	1.95861    	0.0748978 	7.74037   
4  	1.12305   	0.620651   	0.00498706	2.29809   
5  	0.680888  	0.332906   	0.00298025	1.14765   
6  	0.452356  	0.333448   	0.00245132	0.824045  
7  	0.117411  	0.107443   	0.0024037 	0.531097  
8  	0.0400457 	0.0307519  	0.0024037 	0.0749015 
9  	0.00848608	0.00983891 	0.00226571	0.0440805 
10 	0.00273489	0.000242343	0.00199651	0.00312234
11 	0.00249444	0.000178334	0.00192859	0.0027165 
12 	0.00234914	0.00016083 	0.00192001	0.00245132
13 	0.00223035	0.000185709	0.00191322	0.0024037 
14 	0.00202449	7.21414e-05	0.00191322	0.00219393
15 	0.00197621	2.88766e-05	0.00187646	0.00199651
16 	0.00194917	3.49937e-05	0.00186473	0.00197935
17 	0.00190687	2.39714e-05	0.00186441	0.00197204
18 	0.00188267	1.69822e-05	0.00186436	0.00191322
19 	0.00186683	3.27605e-06	0.00186436	0.00187646
20 	0.00186526	5.33196e-07	0.00186436	0.00186565
21 	0.00186411	5.36915e-06	0.00181081	0.00186565
22 	0.0018622 	1.06143e-05	0.00180949	0.0018644 
23 	0.0018573 	1.82615e-05	0.00180831	0.00186436
24 	0.00184231	2.70445e-05	0.00179611	0.00186436
25 	0.00181496	1.75488e-05	0.00179608	0.00186436
26 	0.00180763	3.09599e-06	0.00179603	0.00180963
27 	0.00180555	3.52887e-06	0.00179566	0.00180829
28 	0.00180274	4.55861e-06	0.00179566	0.00180614
29 	0.00179838	3.88443e-06	0.00179566	0.00180606
30 	0.00179604	1.20606e-07	0.00179566	0.00179611
31 	0.00179598	1.63083e-07	0.00179566	0.00179608
32 	0.00179584	1.84513e-07	0.00179563	0.00179605
33 	0.00179566	5.60006e-09	0.00179561	0.00179566
34 	0.00179566	8.81583e-09	0.00179561	0.00179566
35 	0.00179566	1.43202e-08	0.00179561	0.00179566
36 	0.00179565	2.01743e-08	0.00179561	0.00179566
37 	0.00179563	2.41815e-08	0.00179561	0.00179566
38 	0.00179561	2.1684e-19 	0.00179561	0.00179561
39 	0.00179561	2.1684e-19 	0.00179561	0.00179561
40 	0.00179404	1.56839e-05	0.00163798	0.00179561
41 	0.00179404	1.56839e-05	0.00163798	0.00179561
42 	0.00179043	2.96782e-05	0.00159296	0.00179561
43 	0.00177335	5.80035e-05	0.00159296	0.00179561
44 	0.00173946	8.44482e-05	0.00158734	0.00179561
45 	0.00165236	8.16557e-05	0.00158658	0.00179561
46 	0.00159235	1.72408e-06	0.0015862 	0.00159311
47 	0.00159139	2.38939e-06	0.0015862 	0.00159296
48 	0.0015897 	2.73829e-06	0.00158494	0.00159234
49 	0.0015867 	5.37437e-07	0.00158494	0.00158734
50 	0.00158598	2.88214e-06	0.0015577 	0.00158658
最优解为: [1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1]
对应函数的最小值为: 0.00155770323857606

可视化
基于DEAP库的python进化算法--遗传算法实践--非线性函数寻优
                    原创

小结

  • 对于这种简单的非线性函数寻优问题,实数编码与二进制编码都可以在一定精度上求得最优解;虽然在上述答案中实数编码得到的答案似乎更接近全局最优,但是考虑到遗传算法的随机性,多运行几次,二进制编码也可以得到很好的结果
  • 对于同一个问题,遗传算法对于个体的编码方式并不是唯一固定的。我们可以多尝试寻找最优的编码方式。例如在本题中,二进制编码相对于实数编码,不但需要更大的存储空间,而且还额外多了一个解码的过程,因此,并非是最优的选择。

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

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录