Evolutionary Algorithms：进化算法； Genetic Algorithm：遗传算法； 这二者经常被一起提起，首先我们需要知道，GA是EA的一个比较著名且流行的子领域之一，进化算法整体上包含了包括遗传算法、进化程序设计、进化规划和进化策略。

①遗传算法 Genetic Algorithm,GA

②进化规划 Evolutionary Programming,EP

③遗传规划 Genetic Programming,GP

④进化策略 Evolution Strategy, ES

虽然这些概念的内涵有一定的差别，它们有各自不同的侧重点，各自有不同的生物进化背景，各自强调了生物进化过程中的不同特性，但本质上都基于进化思想的，都能产生鲁棒性较强的计算机算法，适应面较广，因此又称它们为进化算法或进化计算。

GA是EA种最流行的一种子算法。

https://en.wikipedia.org/wiki/Evolutionary_algorithm除此之外，我们常常听到的粒子群、蚂蚁算法属于群算法，我们可以使用前面描述的贝叶斯优化或者是进化算法来计算逻辑回归的权重系数，只不过一般来说对于凸函数而言，梯度下降法是最高效的，而其它的这些优化算法都是基于不同的理想假设建立起来的启发式模型，它们都无法保证基本的局部最优。对于非凸问题而言（例如超参数优化，当然远远不止如此）则是一种常用的解决方案。

目前来说遗传算法的应用包括了：

1 神经网络超参数优化神经网络超参数优化一直是一个经久不衰的话题，例如神经网络的训练算法的学习率，神经网络每层多少个隐含层节点，这些参数都属于超参数。超参数无疑对神经网络的效果有着极大的影响，传统的基于梯度的算法无法做超参数优化，因为根本无梯度可以求。所以目前主流的超参数优化方法有 网格搜索，贝叶斯优化和进化计算以及大名鼎鼎的NAS（神经架构搜索，强化学习相关）。这里提到的神经网络也可以扩展到广义的机器学习模型，例如逻辑回归的权重系数等等；

2 神经网络结构优化神经网络结构优化：这个肯定是属于组合优化的问题，这类问题一般是NP-hard的（很难很难求解到精确解）。同样这类问题也是无梯度可求，基于梯度的方法不适用。所有多半是靠进化计算来做；

3 一部分结构和特性固定的组合优化问题：进化计算在一部分组合优化问题和整数规划问题上表现比较好，甚至能够比肩传统的数学优化算法或者击败传统的数学优化算法。例如针对传统的VRP问题（车辆路径规划问题），在精巧的设计变异，交叉算子的情况下，遗传算法能够取得不错的效果；

4 一部分机理模型难以建立的黑箱优化问题： 有一部分优化问题由于其本身机理难以描述清楚或者其机理并不是一个解析解表达式的情况下，数学优化算法往往不适用，此时就是进化计算比较适合的情况了例如我们这里所说的超参数优化问题就是这么一种黑箱优化的问题；

5 多目标优化问题

我们前面提到的贝叶斯优化的方法基于高斯的基本假设来进行复杂的求解，而进化算法基本没有什么前提假设，只需计算目标函数的值即可，对优化问题本身的性质要求是非常低的，不会像数学优化算法（例如梯度下降法）往往依赖于一大堆的条件，比如函数是否为凸优化，目标函数是否可微，但是很多时候面临的问题是非常复杂的，例如超参数优化，我们根本就不知道目标函数凸不凸，可导不可导，甚至可能都不知道目标函数的表达式是什么样的。这一点是进化算法相对数学优化算法来说最大的一个优势，实际上同时也是进化算法一个劣势，因为不依赖问题的性质对所有问题都好使往往意味着没有充分的利用不同问题的特性去进一步加速和优化算法。

下图表示了遗传算法的一个基本框架，

下面根据上图来介绍遗传算法的基本概念，首先

1、初始化种群，我们需要知道，种群包含的个体称为染色体，这个染色体上的每一个片段都被称为一个基因，一条染色体对应了目标问题的一个可行解，以超参数优化为例，一条染色体就是一组超参数，而超参数组合中的每一个超参数是一个基因；

2、适应度函数，用于衡量每一条染色体的优劣程度，对应于超参数优化问题，适应度函数实际上就是我们交叉验证的评价指标的值，这里根据用户所面临的问题由用户自己来定义；

3、选择，优胜劣汰，适者生存，很充分的体现了选择的核心，对应到超参数优化种就是我们每次迭代都会删除一部分表现最差的超参数组合，留下表现最好的部分超参数组合；

4、交叉，对应了自然界中的交配的概念，品质优良的染色体之间互相交换基因组，就像是孩子的基因是由父母决定的一样，对应到超参数优化中就是我们对选择之后剩下的最优秀的超参数组合进行多次选择，选择出的两个超参数组合进行交叉形成新的超参数组合进入下一个环节，需要注意的是，“父母”超参数组合并不是使用均匀的随机采样，而是基于轮盘赌的算法：

举个例子，假设通过选择我们剩下四组超参数，那么我们会根据超参数组合的适应度函数值（也就是交叉验证的评价指标）来进行采样，越大的超参数组合对应的被选择的概率越大，概率通过： 超参数组合i被选择的概率=超参数组合i的适应度（交叉验证的评价指标） / 所有超参数组合的适应度之和

5、变异，显然黑猫和白猫生下来的幼猫也可能是橘猫，我们的交叉得到的新的“孩子”超参数组合也需要发生变异，因为如果只有交叉，超参数组合中的超参数永远是那么几个，只不过交换了他们的组合顺序。这样我们的超参数搜索就很快会被局限在一个小范围里，为了解决这个问题，我们引入了变异，当我们通过交叉生成了一个新的超参数组合之后，需要在新超参数组合上随机选择若干个超参数，然后随机修改超参数的值，从而给现有的“孩子”超参数组合引入了新的超参数空间，突破了当前搜索的限制，更有利于算法寻找到更优的解。
可以看到 遗传算法的交叉和变异与贝叶斯优化的搜索策略中的 exploit（挖掘）和explore（探索）是非常类似的，一个是希望在当前最优值附近搜索，一个是希望在更大的空间进行搜索以追求更好的解；
可以看到遗传算法本身是非常直观且易于理解的。

目前来说，遗传算法的框架中deap是历史最悠久并且使用者最多文档也相对最丰富的，下面我们来看看示例代码就知道具体遗传算法应用到超参数优化中是如何实施的。

import sklearn.datasets
import numpy as np
import random

data=sklearn.datasets.load_digits()
X=data["data"]
y=data["target"]

from sklearn.svm import SVC
from sklearn.model_selection import StratifiedKFold

paramgrid={"kernel":["rbf"],
             "C"     : np.logspace(-9, 9, num=25, base=10),
             "gamma" : np.logspace(-9, 9, num=25, base=10)}

random.seed(1)

from evolutionary_search import EvolutionaryAlgorithmSearchCV
cv=EvolutionaryAlgorithmSearchCV(estimator=SVC(),
                                   params=paramgrid,
                                   scoring="accuracy",
                                   cv=StratifiedKFold(n_splits=4),
                                   verbose=1,
                                   population_size=50,
                                   gene_mutation_prob=0.10,
                                   gene_crossover_prob=0.5,
                                   tournament_size=3,
                                   generations_number=5,
                                   n_jobs=4)
cv.fit(X, y)

evolutionary_search 是大名鼎鼎的deap的sklearn api的形式。

这里我们要调参的算法estimator为svc，超参数params的搜索空间为paramgrid，超参数搜索空间界定了基因的所有可能的类型；

定义适应度函数为4折交叉验证的准确accuract指标，用于衡量每一条染色体（超参数组合）的适应度；

population_size=50 意味着我们始终保持整个种群的染色体数目为50个超参数组合；

tournament_size=3 意味着我们每次从上一代中选择出适应度最好的3个超参数组合直接进行 “复制”，不进行变异和交叉进入下一代的繁衍中，在50个超参数组合中我们进行交叉和变异生成47组新的超参数，这也意味着上一代排名靠后的47个超参数组合被淘汰；

gene_crossover_prob=0.5 表示我们会选择每一条“父母”染色体（超参数组合）中的50%的基因（超参数）进行相互交叉，具体的做法就是是否交换某个超参数设置为bool，然后随机取0，1即可；（我们所谓的轮盘赌算法是应用在父母的选择上，和这里的交叉概率无关）

gene_mutation_prob=0.10 意味着我们的“孩子”超参数组合中每次会大概选择出10%的超参数进行随机取值，这个随机取值不是乱取值而是根据我们之前定义的超参数搜索空间进行随机搜索；

（注意，变异具体的做法是取0~1之间均匀随机采样数然后和我们设定的概率进行比较，这里用的就是常规的采样而不是轮盘赌）

这样，遗传算法的最基本的算法思想流程就讲完了，非常简单直观，后续的很多变体也都是在相似的框架上做了一些局部的修改，比如不使用变异只使用交叉等等；