1. 首页
  2. 文章中心
  3. 深度学习不得不了解的技巧

GEAP 遗传算法/遗传编程 genetic programming + python(deap库)实现前言1.优化问题的定义2.个体编码3 初始种群建立4 评价5 配种选择6 变异7 突变8 环境选择

63 阅读 0 评论
我是靠谱客的博主 落寞帅哥，最近开发中收集的这篇文章主要介绍GEAP 遗传算法/遗传编程 genetic programming + python(deap库)实现前言1.优化问题的定义2.个体编码3 初始种群建立4 评价5 配种选择6 变异7 突变8 环境选择，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

  • 前言
  • 1.优化问题的定义
    • 单目标优化
    • 多目标优化
  • 2.个体编码
    • 实数编码
    • 二进制编码
    • 序列编码(Permutation encoding)
    • 粒子(Particles)
  • 3 初始种群建立
    • 一般族群
    • 同类群
    • 粒子群
  • 4 评价
  • 5 配种选择
  • 6 变异
  • 7 突变
  • 8 环境选择

喜欢的话请关注我们的微信公众号~《 你好世界炼丹师》。

  • 公众号主要讲统计学，数据科学，机器学习，深度学习，以及一些参加Kaggle竞赛的经验。
  • 公众号内容建议作为课后的一些相关知识的补充，饭后甜点。
  • 此外，为了不过多打扰，公众号每周推送一次，每次4~6篇精选文章。

微信搜索公众号：你好世界炼丹师。期待您的关注。

前言

本文不介绍原理的东西，主要是实现进化算法的python实现。
原理介绍可以看这里，能学习要很多，我也在这里写了一些感受心得：
遗传算法/遗传编程 进化算法基于python DEAP库深度解析讲解

1.优化问题的定义

单目标优化

creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))

  • 在创建单目标优化问题时，weights用来指示最大化和最小化。此处-1.0即代表问题是一个最小化问题，对于最大化，应将weights改为正数，如1.0。

  • 另外即使是单目标优化，weights也需要是一个tuple，以保证单目标和多目标优化时数据结构的统一。

  • 对于单目标优化问题，weights 的绝对值没有意义，只要符号选择正确即可。

多目标优化

creator.create('FitnessMulti', base.Fitness, weights=(-1.0, 1.0))
  • 对于多目标优化问题，weights用来指示多个优化目标之间的相对重要程度以及最大化最小化。如示例中给出的(-1.0, 1.0)代表对第一个目标函数取最小值，对第二个目标函数取最大值。

2.个体编码

实数编码(Value encoding)：直接用实数对变量进行编码。优点是不用解码，基因表达非常简洁，而且能对应连续区间。但是实数编码后搜索区间连续，因此容易陷入局部最优。

实数编码

from deap import base, creator, tools
import random
IND_SIZE = 5
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #优化目标：单变量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #创建Individual类，继承list
toolbox = base.Toolbox()
toolbox.register('Attr_float', random.random)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)
ind1 = toolbox.Individual()
print(ind1)
# 结果：[0.8579615693371493, 0.05774821674048369, 0.8812411734389638, 0.5854279538236896, 0.12908399219828248]

二进制编码

from deap import base, creator, tools
from scipy.stats import bernoulli
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #优化目标：单变量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #创建Individual类，继承list
GENE_LENGTH = 10
toolbox = base.Toolbox()
toolbox.register('Binary', bernoulli.rvs, 0.5) #注册一个Binary的alias，指向scipy.stats中的bernoulli.rvs，概率为0.5
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Binary, n = GENE_LENGTH) #用tools.initRepeat生成长度为GENE_LENGTH的Individual
ind1 = toolbox.Individual()
print(ind1)
# 结果：[1, 0, 0, 0, 0, 1, 0, 1, 1, 0]

序列编码(Permutation encoding)

from deap import base, creator, tools
import random
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)
IND_SIZE=10
toolbox = base.Toolbox()
toolbox.register("Indices", random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register("Individual", tools.initIterate, creator.Individual,toolbox.Indices)
ind1 = toolbox.Individual()
print(ind1)
#结果：[0, 1, 5, 8, 2, 3, 6, 7, 9, 4]

粒子(Particles)

import random
from deap import base, creator, tools
creator.create("FitnessMax", base.Fitness, weights=(1.0, 1.0))
creator.create("Particle", list, fitness=creator.FitnessMax, speed=None,
smin=None, smax=None, best=None)
# 自定义的粒子初始化函数
def initParticle(pcls, size, pmin, pmax, smin, smax):
part = pcls(random.uniform(pmin, pmax) for _ in range(size))
part.speed = [random.uniform(smin, smax) for _ in range(size)]
part.smin = smin
part.smax = smax
return part
toolbox = base.Toolbox()
toolbox.register("Particle", initParticle, creator.Particle, size=2, pmin=-6, pmax=6, smin=-3, smax=3) #为自己编写的initParticle函数注册一个alias "Particle"，调用时生成一个2维粒子，放在容器creator.Particle中，粒子的位置落在（-6,6）中，速度限制为（-3，3）
ind1 = toolbox.Particle()
print(ind1)
print(ind1.speed)
print(ind1.smin, ind1.smax)
# 结果：[-2.176528549934324, -3.0796558214905]
#[-2.9943676285620104, -0.3222138308543414]
#-3 3
print(ind1.fitness.valid)
# 结果：False
# 因为当前还没有计算适应度函数，所以粒子的最优适应度值还是invalid

3 初始种群建立

一般族群

  • 这是最常用的族群类型，族群中没有特别的顺序或者子族群。
from deap import base, creator, tools
from scipy.stats import bernoulli
# 定义问题
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) # 单目标，最小化
creator.create('Individual', list, fitness = creator.FitnessMin)
# 生成个体
GENE_LENGTH = 5
toolbox = base.Toolbox() #实例化一个Toolbox
toolbox.register('Binary', bernoulli.rvs, 0.5)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Binary, n=GENE_LENGTH)
# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
toolbox.Population(n = N_POP)
# 结果：
# [[1, 0, 1, 1, 0],
# [0, 1, 1, 0, 0],
# [0, 1, 0, 0, 0],
# [1, 1, 0, 1, 0],
# [0, 1, 1, 1, 1],
# [0, 1, 1, 1, 1],
# [1, 0, 0, 0, 1],
# [1, 1, 0, 1, 0],
# [0, 1, 1, 0, 1],
# [1, 0, 0, 0, 0]]

同类群

  • 同类群即一个族群中包含几个子族群。在有些算法中，会使用本地选择(Local selection)挑选育种个体，这种情况下个体仅与同一邻域的个体相互作用。
toolbox.register("deme", tools.initRepeat, list, toolbox.individual)
DEME_SIZES = 10, 50, 100
population = [toolbox.deme(n=i) for i in DEME_SIZES]

粒子群

  • 粒子群中的所有粒子共享全局最优。在实现时需要额外传入全局最优位置与全局最优适应度给族群。
creator.create("Swarm", list, gbest=None, gbestfit=creator.FitnessMax)
toolbox.register("swarm", tools.initRepeat, creator.Swarm, toolbox.particle)

4 评价

  • 评价部分是根据任务的特性高度定制的，DEAP库中并没有预置的评价函数模版。

  • 在使用DEAP时，需要注意的是，无论是单目标还是多目标优化，评价函数的返回值必须是一个tuple类型。

from deap import base, creator, tools
import numpy as np
# 定义问题
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #优化目标：单变量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #创建Individual类，继承list
# 生成个体
IND_SIZE = 5
toolbox = base.Toolbox()
toolbox.register('Attr_float', np.random.rand)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)
# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
pop = toolbox.Population(n = N_POP)
# 定义评价函数
def evaluate(individual):
return sum(individual), #注意这个逗号，即使是单变量优化问题，也需要返回tuple
# 评价初始族群
toolbox.register('Evaluate', evaluate)
fitnesses = map(toolbox.Evaluate, pop)
for ind, fit in zip(pop, fitnesses):
ind.fitness.values = fit
print(ind.fitness.values)
# 结果：
# (2.593989197511478,)
# (1.1287944225903104,)
# (2.6030877077096717,)
# (3.304964061515382,)
# (2.534627558467466,)
# (2.4697149450205536,)
# (2.344837782191844,)
# (1.8959030773060852,)
# (2.5192475334239,)
# (3.5069764929866585,)

5 配种选择

  • selTournament() 锦标赛选择
  • selRoulette() 轮盘赌选择（不能用于最小化或者适应度会小于等于0的问题）
  • selNSGA2() NSGA-II选择，适用于多目标遗传算法
  • selSPEA2() SPEA2选择，目前版本(ver 1.2.2)的该函数实现有误，没有为个体分配距离，不建议使用。
  • selRandom() 有放回的随机选择
  • selBest() 选择最佳
  • selWorst() 选择最差
  • selTournamentDCD() Dominance/Crowding distance锦标赛选择，目前版本的实现也有些问题
  • selDoubleTournament() Size+Fitness双锦标赛选择
  • selStochasticUniversalSampling() 随机抽样选择
  • selLexicase() 词典选择，参考这篇文章
  • selEpsilonLexicase() 词典选择在连续值域上的扩展
from deap import base, creator, tools
import numpy as np
# 定义问题
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #优化目标：单变量，求最小值
creator.create('Individual', list, fitness = creator.FitnessMin) #创建Individual类，继承list
# 生成个体
IND_SIZE = 5
toolbox = base.Toolbox()
toolbox.register('Attr_float', np.random.rand)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, n=IND_SIZE)
# 生成初始族群
N_POP = 10
toolbox.register('Population', tools.initRepeat, list, toolbox.Individual)
pop = toolbox.Population(n = N_POP)
# 定义评价函数
def evaluate(individual):
return sum(individual), #注意这个逗号，即使是单变量优化问题，也需要返回tuple
# 评价初始族群
toolbox.register('Evaluate', evaluate)
fitnesses = map(toolbox.Evaluate, pop)
for ind, fit in zip(pop, fitnesses):
ind.fitness.values = fit
# 选择方式1：锦标赛选择
toolbox.register('TourSel', tools.selTournament, tournsize = 2) # 注册Tournsize为2的锦标赛选择
selectedTour = toolbox.TourSel(pop, 5) # 选择5个个体
print('锦标赛选择结果：')
for ind in selectedTour:
print(ind)
print(ind.fitness.values)
# 选择方式2: 轮盘赌选择
toolbox.register('RoulSel', tools.selRoulette)
selectedRoul = toolbox.RoulSel(pop, 5)
print('轮盘赌选择结果：')
for ind in selectedRoul:
print(ind)
print(ind.fitness.values)
# 选择方式3: 随机普遍抽样选择
toolbox.register('StoSel', tools.selStochasticUniversalSampling)
selectedSto = toolbox.StoSel(pop, 5)
print('随机普遍抽样选择结果：')
for ind in selectedSto:
print(ind)
print(ind.fitness.values)
#结果：
#锦标赛选择结果：
#[0.2673058115582905, 0.8131397980144155, 0.13627430737326807, 0.10792026110464248, 0.4166962522797264]
#(1.741336430330343,)
#[0.5448284697291571, 0.9702727117158071, 0.03349947770537576, 0.7018813286570782, 0.3244029157717422]
#(2.5748849035791603,)
#[0.8525836387058023, 0.28064482205939634, 0.9235436615033125, 0.6429467684175085, 0.5965523553349544]
#(3.296271246020974,)
#[0.5243293164960845, 0.37883291328325286, 0.28423194217619596, 0.5005947374376103, 0.3017896612109636]
#(1.9897785706041071,)
#[0.4038211036464676, 0.841374996509095, 0.3555644512425019, 0.5849111474726337, 0.058759891556433574]
#(2.2444315904271317,)
#轮盘赌选择结果：
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)
#[0.5448284697291571, 0.9702727117158071, 0.03349947770537576, 0.7018813286570782, 0.3244029157717422]
#(2.5748849035791603,)
#[0.630305953330188, 0.09565983206218687, 0.890691659939096, 0.8706091807317707, 0.19708949882847437]
#(2.684356124891716,)
#[0.5961060867498598, 0.4300051776616509, 0.4512760237511251, 0.047731561819711055, 0.009892120639829804]
#(1.5350109706221766,)
#随机普遍抽样选择结果：
#[0.2673058115582905, 0.8131397980144155, 0.13627430737326807, 0.10792026110464248, 0.4166962522797264]
#(1.741336430330343,)
#[0.4038211036464676, 0.841374996509095, 0.3555644512425019, 0.5849111474726337, 0.058759891556433574]
#(2.2444315904271317,)
#[0.630305953330188, 0.09565983206218687, 0.890691659939096, 0.8706091807317707, 0.19708949882847437]
#(2.684356124891716,)
#[0.40659881466060876, 0.8387139101647804, 0.28504735705240236, 0.46171554118627334, 0.7843353275244066]
#(2.7764109505884718,)
#[0.42469039733882064, 0.8411201950346711, 0.6322812691061555, 0.7566549973076343, 0.9352307652371067]
#(3.5899776240243884,)

6 变异

  • cxOnePoint() 单点交叉 实数、二进制
  • cxTwoPoint() 两点交叉 实数、二进制
  • cxUniform() 均匀交叉 实数、二进制
  • cxPartialyMatched() 部分匹配交叉PMX 序列
  • cxUniformPartialyMatched() PMX变种，改两点为均匀交叉 序列
  • cxOrdered() 有序交叉 序列
  • cxBlend() 混合交叉 实数
  • cxESBlend() 带进化策略的混合交叉
  • cxESTwoPoint() 带进化策略的两点交叉
  • cxSimulatedBinary() 模拟二值交叉 实数
  • cxSimulatedBinaryBounded() 有界模拟二值交叉 实数
  • cxMessyOnePoint() 混乱单点交叉 实数、二进制
from deap import base, creator, tools
import random
# 创建两个序列编码个体
random.seed(42) # 保证结果可复现
IND_SIZE = 8
creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))
creator.create('Individual', list, fitness = creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register('Indices', random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register('Individual', tools.initIterate, creator.Individual, toolbox.Indices)
ind1, ind2 = [toolbox.Individual() for _ in range(2)]
print(ind1, 'n', ind2)
# 结果：[1, 0, 5, 2, 7, 6, 4, 3] 
# [1, 4, 3, 0, 6, 5, 2, 7]
# 单点交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxOnePoint(child1, child2)
print(child1, 'n', child2)
#结果：[1, 4, 3, 0, 6, 5, 2, 7] 
# [1, 0, 5, 2, 7, 6, 4, 3]
# 可以看到从第四位开始被切开并交换了
# 两点交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxTwoPoint(child1, child2)
print(child1, 'n', child2)
# 结果：[1, 0, 5, 2, 6, 5, 2, 3] 
# [1, 4, 3, 0, 7, 6, 4, 7]
# 基因段[6, 5, 2]与[7, 6, 4]互换了
# 均匀交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxUniform(child1, child2, 0.5)
print(child1, 'n', child2)
# 结果：[1, 0, 3, 2, 7, 5, 4, 3] 
# [1, 4, 5, 0, 6, 6, 2, 7]
# 部分匹配交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxPartialyMatched(child1, child2)
print(child1, 'n', child2)
# 结果：[1, 0, 5, 2, 6, 7, 4, 3] 
# [1, 4, 3, 0, 7, 5, 2, 6]
# 可以看到与之前交叉算子的明显不同，这里的每个序列都没有冲突
# 有序交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxOrdered(child1, child2)
print(child1, 'n', child2)
# 结果：[5, 4, 3, 2, 7, 6, 1, 0] 
# [3, 0, 5, 6, 2, 7, 1, 4]
# 混乱单点交叉
child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxMessyOnePoint(child1, child2)
print(child1, 'n', child2)
# 结果：[1, 0, 5, 2, 7, 4, 3, 0, 6, 5, 2, 7] 
# [1, 6, 4, 3]
# 注意个体序列长度的改变

7 突变

from deap import base, creator, tools
import random
# 创建一个实数编码个体
random.seed(42) # 保证结果可复现
IND_SIZE = 5
creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))
creator.create('Individual', list, fitness = creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register('Attr_float', random.random)
toolbox.register('Individual', tools.initRepeat, creator.Individual, toolbox.Attr_float, IND_SIZE)
ind1 = toolbox.Individual()
print(ind1)
# 结果：[0.6394267984578837, 0.025010755222666936, 0.27502931836911926, 0.22321073814882275, 0.7364712141640124]
# 高斯突变
mutant = toolbox.clone(ind1)
tools.mutGaussian(mutant, 3, 0.1, 1)
print(mutant)
# 结果：[3.672658632864655, 2.99827700737295, 3.2982590920597916, 3.339566606808737, 3.6626390539295306]
# 可以看到当均值给到3之后，变异形成的个体均值从0.5也增大到了3附近
# 乱序突变
mutant = toolbox.clone(ind1)
tools.mutShuffleIndexes(mutant, 0.5)
print(mutant)
# 结果：[0.22321073814882275, 0.7364712141640124, 0.025010755222666936, 0.6394267984578837, 0.27502931836911926]
# 有界多项式突变
mutant = toolbox.clone(ind1)
tools.mutPolynomialBounded(mutant, 20, 0, 1, 0.5)
print(mutant)
# 结果：[0.674443861742489, 0.020055418656044655, 0.2573977358171454, 0.11555018832942898, 0.6725269223692601]
# 均匀整数突变
mutant = toolbox.clone(ind1)
tools.mutUniformInt(mutant, 1, 5, 0.5)
print(mutant)
# 结果：[0.6394267984578837, 3, 0.27502931836911926, 0.22321073814882275, 0.7364712141640124]
# 可以看到在第二个位置生成了整数3

8 环境选择

DEAP中没有设定专门的reinsertion操作。可以简单的用python的list操作来完成选择

最后

以上就是落寞帅哥为你收集整理的GEAP 遗传算法/遗传编程 genetic programming + python(deap库)实现前言1.优化问题的定义2.个体编码3 初始种群建立4 评价5 配种选择6 变异7 突变8 环境选择的全部内容，希望文章能够帮你解决GEAP 遗传算法/遗传编程 genetic programming + python(deap库)实现前言1.优化问题的定义2.个体编码3 初始种群建立4 评价5 配种选择6 变异7 突变8 环境选择所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(42)

相关文章

今天大雪,可是一点雪都没看到
今天大雪,可是一点雪都没看到
【机器学习实例】
【机器学习实例】
单调栈 ---[ 数据结构 ]
单调栈 ---[ 数据结构 ]
[NEFU锐格 数据结构]实验七 查找有关的操作[NEFU锐格 数据结构]实验七 查找有关的操作
[NEFU锐格 数据结构]实验七 查找有关的操作[NEFU锐格 数据结构]实验七 查找有关的操作
GEAP 遗传算法/遗传编程 genetic programming + python(deap库)实现前言1.优化问题的定义2.个体编码3 初始种群建立4 评价5 配种选择6 变异7 突变8 环境选择
GEAP 遗传算法/遗传编程 genetic programming + python(deap库)实现前言1.优化问题的定义2.个体编码3 初始种群建立4 评价5 配种选择6 变异7 突变8 环境选择
python黑色星期五_Python数据分析：亚马逊黑色星期五
python黑色星期五_Python数据分析：亚马逊黑色星期五
黑色星期五
黑色星期五
数据结构学习线性表栈队列树图
数据结构学习线性表栈队列树图

评论列表共有 0 条评论

立即
投稿
返回
顶部