遗传算法框架 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框架初体验)