遗传算法框架 deap 简介与使用

简介: deap(Distributed Evolutionary Algorithms in Python)是用于创建遗传算法实现的python库,框架支持使用遗传算法以及其他进化计算技术快速开发解决方案。DEAP提供了各种数据结构和工具,这些数据结构和工具在实现各种基于遗传算法的解决方案时必不可少。

deap框架介绍

目前,有许多可用于遗传算法的 Python 框架 —— GAFT,DEAP,Pyevolve 和 PyGMO 等。

其中,deap (Distributed Evolutionary Algorithms in Python) 框架支持使用遗传算法以及其他进化计算技术快速开发解决方案,得到了广泛的应用。deap 提供了各种数据结构和工具,这些数据和工具在实现各种基于遗传算法的解决方案时必不可少。

creator模块

creator 模块可以作为元工厂,能够通过添加新属性来扩展现有类。

例如,已有一个名为 Employee 的类。使用 creator 工具,可以通过创建 Developer 类来扩展 Employee 类:

importdeapimportcreatorcreator.create("Developer",Employee,position="Developer",programmmingLanguage=set)

传递给 create() 函数的第一个参数是新类的名称。第二个参数是要扩展的现有类,接下来是使用其他参数定义新类的属性。如果为参数分配了一个类(例如 dict 或 set ),它将作为构造函数中初始化的实例属性添加到新类中。如果参数不是类(例如字符串),则将其添加为静态 (static) 属性。

因此,创建的 Developer 类将扩展 Employee 类,并将具有一个静态属性 position,设置为 Developer,以及一个实例属性,类型为 set 的 programmingLanguages,该属性在构造函数中初始化。因此实际上等效于:

classDeveloper(Employee):
position="Developer"def__init__(self):
self.programmmingLanguage=set()

这个新类存在于 creator 模块中,因此需要引用时使用 creator.Developer。

使用 deap 时,creator 模块通常用于创建 Fitness 类以及 Individual 类。

创建适应度类

使用 deap 时,适应度封装在 Fitness 类中。在 deap 框架中适应度可以有多个组成部分,每个组成部分都有自己的权重(weights)。这些权重的组合定义了适合给定问题的行为或策略。

定义适应度策略

为了快速定义适应度策略,deap 使用了抽象 base.Fitness 类,其中包含 weights 元组,以定义策略并使类可用。可以通过使用 creator 创建基础 Fitness 类的扩展来完成,类似于创建 Developer 类:

creator.create("FitnessMax",base.Fitness,weights=(1.0,))

上述代码将产生一个 creator.FitnessMax 类,该类扩展了 base.Fitness 类,并将 weights 类属性初始化为 (1.0,)值。需要注意的是:weights 参数是一个元组。

FitnessMax 类的策略是在遗传算法过程中最大化单目标解的适应度值。相反,如果有一个单目标问题,需要使适应度值最小的解,则可以使用以下定义来创建最小化策略:

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

还可以定义具有优化多个目标且重要性不同的策略:

creator.create("FitnessCompound",base.Fitness,weights=(1.0,0.2,-0.5))

这将产生一个 creator.FitnessCompound 类,它拥有三个不同的适应度组成部分。第一部分权重为 1.0,第二部分权重为 0.2,第三部分权重为 -0.5。这将倾向于使第一和第二部分(或目标)最大化,而使第三部分(或目标)最小化。

适应度存储方式

虽然权重元组定义了适应度策略,但是一个对应的元组(称为 values )用于将适应度值存储在 base.Fitness 类中。这些值是从单独定义的函数(通常称为 evaluate() )获得的。就像 weights 元组一样,values 元组存储每个适应度组件(对象)值。

元组 wvalues 包含通过将 values 元组的每个分量与其 weights 元组的对应分量相乘而获得的加权值。只要得到了实例的适应度值,就会计算加权值并将其插入 wvalues 中。这些值用于个体之间的适应度的比较操作。

创建个体类

在 deap 中,creator 工具的第二个常见用途是定义构成遗传算法种群的个体。遗传算法中的个体使用可以由遗传算子操纵的染色体来表示,通过扩展表示染色体的基类来创建 Individual 类。另外,deap 中的每个个体实例都需要包含其适应度函数作为属性。

为了满足这两个要求,利用 creator 来创建 creator.Individual 类:

creator.create("Individual",list,fitness=creator.FitnessMax)

该代码片段具有以下两个效果:

  • 创建的 Individual 类扩展了 Python 的 list 类,这意味着使用的染色体是列表类型
  • 创建的 Individual 类的每个实例将具有之前创建的 FitnessMax 属性

Toolbox类

deap 框架提供的第二种高效创建遗传算法的机制是 base.Toolbox 类。Toolbox 用作函数(或操作)的容器,能够通过别名机制和自定义现有函数来创建新的运算符。

假设有一个函数 sumOfTwo():

defsumOfTwo(a,b):
returna+b

使用 toolbox,可以创建一个新的运算,incrementByFive(),该运算符利用 sumOfTwo() 函数创建:

importbasetoolbox=base.Toolbox()
toolbox.register("incrementByFive",sumOfTwo,b=5)

传递给 register() 函数的第一个参数是新运算符所需的名称(或别名),第二个参数是被定制的现有函数。创建完成后,每当调用新运算符时,其他参数都会自动传递给创建的函数,如:

toolbox.incrementByFive(10)

等效于:

sumOfTwo(10, 5)

这是因为 b 的参数已由 incrementByFive 运算符定义为5。

创建遗传算子

为了快速构建遗传流程,可以使用 Toolbox 类定制 tools 模块的现有函数。tools 模块包含许多便捷的函数,这些函数包括选择、交叉和变异的遗传算子以及程序的初始化等。

例如,以下代码定义了三个别名函数,用作遗传算子:

fromdeapimporttoolstoolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.02)

这三个别名函数的详细说明:

  1. select 注册为 tools 函数 selTournament() 的别名,且 tournsize 参数设置为 3。这将创建 toolbox.select 运算符,其为锦标赛规模为 3 的锦标赛选择算子
  2. mate 注册为 tools 函数 cxTwoPoint() 的别名,这将创建执行两点交叉的toolbox.mate算子
  3. mutate 注册为 tools 函数 mutFlipBit() 的别名,并将 indpb 参数设置为 0.02,这将创建一个翻转每个特征的概率为 0.02 的位翻转突变算子

tools 模块提供了各种遗传算子的实现,以下列示常用遗传算子的实现函数。

选择算子主要包括:

selRoulette()               #轮盘选择selStochasticUniversalSampling()    #随机遍历采样(SUS)selTournament()             #锦标赛选择

交叉算子主要包括:

cxOnePoint()        #单点交叉cxUniform()     #均匀交叉cxOrdered()     #有序交叉cxPartialyMatched() #实现部分匹配交叉

突变算子主要包括:

mutFlipBit()    #位翻转突变mutGaussian()   #正态分布突变

创建物种

tools 模块的 init.py 文件包含用于创建和初始化遗传算法的函数,其中包括initRepeat(),它接受三个参数:

  1. 要放置结果对象的容器类型
  2. 用于生成将放入容器的对象的函数
  3. 要生成的对象数

如:

#产生含有30个随机数的列表,这些随机数介于0和1之间randomList=tools.initRepeat(list,random.random,30)

此示例中,list 是用作要填充的容器的类型,random.random 是生成器函数,而 30 是调用生成器函数以生成填充容器的值的次数。

如果想用 0 或 1 的整数随机数填充列表,则可以创建一个使用 random.radint() 生成随机值 0 或 1 的函数,然后将其用作 initRepeat() 的生成器函数:

defzeroOrOne():
returnrandom.randint(0,1)
randomList=tools.initRepeat(list,zeroOrOne,30)

或者,可以利用 Toolbox:

#创建zeroOrOne运算符,使用参数0、1调用random.radint()toolbox.register("zeroOrOne",random.randint,0,1)
randomList=tools.initRepeat(list,tools.zeroOrOne,30)

计算适应度

虽然 Fitness 类定义了确定其策略(例如最大化或最小化)的适应度权重,但实际的适应度是从单独定义的函数中获得的。该适应度计算函数通常使用别名 evalidate 来注册到 Toolbox 模块中:

defsomeFitnessCalculationFunction(individual):
"""算给定个体的适应度"""return_some_calculation_of_of_the_fitness(individual)
#将evaluate注册为someFitnessCalculationFunction()的别名toolbox.register("evaluate",someFitnessCalculationFunction)

使用deap框架解决OneMax问题

遗传算法实践详解 (deap框架初体验)


相关文章
|
1月前
|
存储 算法 安全
【加密算法】AES对称加密算法简介
【加密算法】AES对称加密算法简介
|
1月前
|
机器学习/深度学习 算法 安全
【加密算法】RSA非对称加密算法简介
【加密算法】RSA非对称加密算法简介
|
17天前
|
机器学习/深度学习 算法 TensorFlow
机器学习算法简介:从线性回归到深度学习
【5月更文挑战第30天】本文概述了6种基本机器学习算法:线性回归、逻辑回归、决策树、支持向量机、随机森林和深度学习。通过Python示例代码展示了如何使用Scikit-learn、statsmodels、TensorFlow库进行实现。这些算法在不同场景下各有优势,如线性回归处理连续值,逻辑回归用于二分类,决策树适用于规则提取,支持向量机最大化类别间隔,随机森林集成多个决策树提升性能,而深度学习利用神经网络解决复杂模式识别问题。理解并选择合适算法对提升模型效果至关重要。
185 4
|
1月前
|
缓存 算法 安全
Java集合框架:深入探究数据结构与算法的精华
Java集合框架:深入探究数据结构与算法的精华
|
1月前
|
算法 Java vr&ar
保持无损连接和函数依赖的3NF合成算法(详细简介)期末必备
保持无损连接和函数依赖的3NF合成算法(详细简介)期末必备
23 0
|
1月前
|
缓存 算法 Java
Linux内核新特性年终大盘点-安卓杀后台现象减少的背后功臣MGLRU算法简介
MGLRU是一种新型内存管理算法,它的出现是为了弥补传统LRU(Least Recently Used)和LFU(Least Frequently Used)算法在缓存替换选择上的不足,LRU和LFU的共同缺点就是在做内存页面替换时,只考虑内存页面在最近一段时间内被访问的次数和最后一次的访问时间,但是一个页面的最近访问次数少或者最近一次的访问时间较早,可能仅仅是因为这个内存页面新近才被创建,属于刚刚完成初始化的年代代页面,它的频繁访问往往会出现在初始化之后的一段时间里,那么这时候就把这种年轻代的页面迁移出去
|
1月前
|
算法 关系型数据库 C语言
卡尔曼滤波简介+ 算法实现代码(转)
卡尔曼滤波简介+ 算法实现代码(转)
27 4
|
1月前
|
机器学习/深度学习 自然语言处理 算法
深度学习算法简介(二)
深度学习算法简介(二)
|
1月前
|
机器学习/深度学习 自然语言处理 算法
深度学习算法简介(一)
深度学习算法简介(一)
|
1月前
|
机器学习/深度学习 监控 算法