第一部分

第一部分"/>

第一部分

最近读了一篇关于进化神经网络搜索出最好的图像分类网络的论文，本人英文不是很好，翻译错误的地方请多指正。原文链接：Evolving Deep Convolutional Neural Networks for Image Classification

1.摘要：

1.翻译
进化算法在20年前就已经被应用于神经网络，但是由于它的权值和结构十分复杂，所以当时的电脑性能跟不上，无法用于深度学习，但是现在可以了。在本文中，我们提出使用遗传算法的思想来“进化”出图像分类模型所需要的各种权值和结构。我们在这个算法中用一种可变长的基因编码来代表多种多样的神经网络块和神经网络的深度（每一段基因都代表了神经网络块，而基因的长度则代表了神经网络的深度）。此外，我们提出一种全新且高效的初始化神经网络的连接权值的方式，这个方式还可以避免网络进入局部最优点。此外，我们还提出了一种新的适应度策略（适应度就是网络自我调整的方法），它可以用更少的资源更快地实现自我优化。实验结果表明，无论是从分类的错误率还是从分类的参数的数量而言（参数越少，识别越快），这个算法比当前所有最先进的分类算法都要好。

2.解读：
从摘要中我们知道他使用的是遗传算法，遗传算法就是模拟自然界自然的基因变化，父母基因杂交，杂交以后变异，然后适者生存不适者淘汰。那关键的就是基因是如何编码的，杂交的方法是什么，如何变异，适者生存不适者淘汰的准则是什么这几个点，分别对应了上面黄体字标记的部分。这个论文里面我们需要找到答案，并且实现它。

2.简介和算法介绍

1.大概
总结一下就是传统的CNN存在结构难以确定，所耗费的资源很大，时间很长，但是用遗传算法可以自己找模型的结构，即便你不是专家，你也可以找到很好的结构。
2.目标
同时列出了本文的目标，即开发一种有效且高效的遗传算法搜索框架，它可以自动地找到一个cnn架构实现权值的最优化，包括初始函数和激活函数的最优化。一共有以下几点：
（1）它是灵活的，并没有规定目标卷积网络的最大层数是多少，因为在对不同的目标进行分类时，所需的神经网络层数往往也是不同的，这样就可以突破以往的限制。
（2）研究一种编码方法来表示连接的权值（其实就是卷积核和全连接层的参数），要求可以代表尽可能多的权值并且消耗的资源很少。
（3）设计一种很好的自然选择策略，可以实现权值的自改变和网络架构的自适应。
（4）判断新的方法是在精度和参数数量方面是不是优于现有方法。

3.关键知识点：
（1）在一个卷积操作中涉及的参数是卷积核的尺寸、特征映射的数量、步幅宽度、步幅高度、卷积类型和卷积核中的参数。
（2）图像分类的大进化算法（ Large Evolution for Image Classification,LEIC）：这个算法是谷歌在2017年发布的，首次证明了进化算法可以用于卷积网络的图像分类，取得了很好的成功。这个是一个论文重点介绍的算法：
首先，该算法是从零开始用遗传算法来进化cnn框架的，它的基因编码策略也是可变长的，这和本文要用到的编码策略很相似。在进化阶段，不同的层（比如卷积层池化层和全连接层）都可以通过变异的方式融合到一起，也就是任意组合。希望可以通过变异来产生好的cnn架构。但是，有一点，LEIC算法没有着重研究，那就是父母之间的基因是如何交叉配对的。如果你不交叉配对，仅仅通过变异就想要得到很好的框架的话，那你需要的基因要足够长，数量要足够多才行。所以LEIC还真的搞了很大的基因群（不少于1000）和很长的基因序列（不少于100）。此外，LEIC的适应度原则也很耗费资源，因此谷歌一共用了250台高端电脑来运行这个算法。LEIC的适应度原则就是看最后的图片识别精度够不够，但是它判断精度的方法用的是传统的误差反向传播的方法，很耗费时间。说白了，其实这个算法的思想就是，先用传统的梯度下降，把误差减到最小值，然后保留它，然后随机变异一个副本，这个副本的层数和参数是任意的，然后梯度下降到最优，和前面一个比较，好的一个留下，然后继续变异，当然有250台电脑，也可能不淘汰，继续变异，装不下了才淘汰。之后，谷歌又进行了一次实验，这次实验使用到了交叉配对，但是只是对全连接层进行交叉配对，之后用随机梯度下降算法来更新网络。那为什么LEIC算法不用交叉配对呢？别忘记了我们的基因长度是可以变的，那不同长度的基因之间如何交叉配对，这是一件很困难的事情（虽然x和y染色体长度不一样也配对了，但是要注意的是cnn又卷积层，池化层和全连接层三种层，而染色体的基因本质上都同一个物质），谷歌一直没有找到好的交叉配对算法，所以干脆没有交叉配对。所以LEIC的缺点就是太费资源了，这个缺点的解决办法就是找一个好的交叉配对算法（谷歌都没有实现，确实是有点棘手的）。
（3）连接权值的初始化方法，常用的一共有三种：

1 ◯ \textcircled{1} 1◯第一种是用一个常数来初始化全部的权值，比如一开始把权值全部设置为0，1或者其他任何合适的数字。

2 ◯ \textcircled{2} 2◯第二种是用一个特定的分布中的数字来初始化权值，比如用高斯分布，或者是均匀分布来初始化。

3 ◯ \textcircled{3} 3◯第三种是用经验来初始化（前人一个个数字的尝试出来的），比如Xavier初始化。

（4）卷积神经网络如何初始化权值：因为卷积神经网络的权值很多，比如卷积核的值，连接层的值等，所以全部设置成同一个数字（也就是第一个方法），那肯定是行不通的，你想要是卷积核初始化是全1，那不是等于对图片求平均值，并没有提取到任何特征吗。使用第二种的话，选什么分布函数来初始化，以及选择分布函数以后它的参数（比如均匀分布的范围，高斯分布的高斯标准）要怎么选择，其实也是一个完全懵逼的状态，选不出来的。既然前两种都不合适，那么作者的意思大家肯定也明白了，作者用了第三种，并且用的就是上面提到的Xavier初始化。

（5）Xavier初始化：Xavier把每层的神经元的数值都输入到Sigmoid激活函数中计算，将计算结果作为均匀分布的范围，比如：我们假设相邻两层之间有两个相连的神经元经过Sigmoid激活函数计算以后，他们分别是 n 1 n_1 n1​和 n 2 n_2 n2​，那么均为分布的范围就是 ( − 6 ( n 1 + n 2 ) , 6 ( n 1 + n 2 ) ) (-\sqrt{\frac{6}{(n_1+n_2)}},\sqrt{\frac{6}{(n_1+n_2)}}) (−(n1​+n2​)6​ ​,(n1​+n2​)6​ ​)。但是，作者也指出，虽然这个初始化方法比其他的方法都要好，它也有它自己的缺点，那就是它高度依赖卷积神经网络的结构，比如如果输入很多，那么它的值也会跟着变，具有不确定性。如果一开始的结构就很差，那么按照这个初始化去变异，只会越来越差。同时，在卷积神经网络中，我们常用ReLU激活函数而不是用Sigmoid函数。

（6）所以，其实现在根本就没有适用于进化算法的初始化神经网络的权值的算法。原因很简单，cnn的权值实在是太多了还一直在变，很难用基因来对其进行编码，也很难优化它。层数虽然也多，但是不会到几千几万。

4.作者提出的算法
综合上面的考虑，作者提出了超进化卷积神经网络（Evolving deep Convolutional Neural Networks，EvoCNN)。算法的伪代码如下（里面的很多具体细节将在下面描述）：

1.用一个特定的方法来初始化一个种群，记为P_0
2.t=0	# t是第几代，和P是相对应的，所以后面称为 P_t
3.while 误差没有达到我们要求的标准:（这里也不一定是误差，可以设置成运行100代）4.把P_t里面的个体两两配对，放入一个数组S中:S = [(p_t_0, p_t_1), (p_t_1,p_t_2)...]5.把S中的一对对的父亲和母亲进行交叉配对和变异生下一个新的子女数组Q_t,Q_t=[Q_t_0, Q_t_1...]6.在P_t和Q_t里面进行自然选择的竞争，选出的前n个，作为我们的新一代P_(t+1)7.t = t+1 # 表示又生了一代
8.从最终符合要求的P数组里面，再进行适者生存，不适者淘汰，最后活下来的就是我们的模型

它的基因编码大概是这样的（论文里面搬出来的）：

C是卷积层，P是池化层，F是全连接层。每一层的编码细节如下（我翻译的有可能有点误差，但是不会太大）

5.具体的基因编码策略
首先，我们要编码的基因有三种，分别是卷积层，池化层和全连接层，这三种基因组成一条染色体。因为用卷积神经网络来处理一张图片的时候，卷积网络的深度影响很大，所以我们让染色体的长度不固定，这样就有可能找到最好的卷积网络框架来处理我们的图片。用前面的图和表已经可以说明编码是怎么编的了。但是，每个全连接层里面的权值或者是卷积层里面的卷积核的值可能有许多个，他们的表示方法并不能通过上图来说明。这么多的数据要进行编码是很困难的，所以作者想到了一个办法，只写两个实数，这两个实数分别代表了卷积核或者全连接层的全部权值，最后再根据高斯采样获得每一个权值的具体值。

6.初始化种群的方法
前面EvoCNN算法里面一开始说的初始化种群的特定方法如下，用伪代码来表示：

Input: 初始染色体的最小长度N，在该染色体中：卷积层和池化层和的最小数目N_cp和全连接层的最少数目N_f
Output:一个初始化种群P_0
1.P_0 = {}	# P_0一开始是空的染色体
2.while len(P_0)<=N:	# 如果染色体的长度不达标# 先生成一个卷积和池化的组合层part13.生成一个空的集合part1={}4.从[1,N_cp]中随机挑选一个整数n_cp5.while part1的长度没有到n_cp(len(part1<=n_cp)):6.生成一个[0,1]之间的随机浮点数r:7.if r<=0.5:8.用随机的参数初始化卷积核，并且生成一个卷积层作为L9.else:生成一个内核尺寸随机，种类也随机的池化层作为L10.最后把L加入到part1中# 再生成对应的全连接层part2	11.生成一个空的part2={}11.从[1,N_f]中随机的选择一个数字n_f12.while part2的长度没有到n_f:13.生成一个具有随机参数的全连接层L14.把L加入到part2中15.最后把part1和part2都加入到P_0中
16.最后生成的P_0就是我们的最初染色体

7.染色体筛选准则（也就是我们的适者生存，不适者淘汰的算法）：
这里的s也是一个字典，分为{net:[]和fit:[]}

Input:对于P_t中的每一个染色体，因为都是一个网络结构，所以我们设置一个最大的训练次数k,一个训练集D_train和一个验证集，我们这里称之为适应集D_fitness,同时还有训练批次大小num_of_batch
Output:这个P_t中每个染色体的适应度1.for s in P_t: # 用一个循环来检测种群中的每一个染色体2.i = 1	# i就是一个计数器3.while i<=k :4.用常规的方法训练这个网络s，怎么训练都行5.if i == k:	# 也就是训练到第最后一轮以后6.eval_steps = |Df itness|/num of batch	# 把验证集也分成多份7.创建一个空的集合来装验证结果accy_list={}8.j = 1 # j也是一个计数器9.while j <= len(eval_steps):10.运用常规的误差检测方法求eval_steps[j]的误差accy_j11.把误差accy_j装入accy_list中11. j = j+112. 求accy_list所有误差值的平均值和标准差作为一个适应度评判标准，放入s的fit里面去13. i = i+1

其实每一个染色体s的fit里面有三个值除了误差的平均值和标准差，还有一个就是染色体的网络长度len(net)，这三个共同来衡量这个染色体的适应能力。这里说一下，不能用常规的训练神经网络的办法去训练这里的每一个染色体，除非你也有350台高性能电脑。不然每一次训练都是100轮以上，有10个染色体就行训练1000轮，然后重复100代就是10万轮，显卡是3080都扛不住的。所以怎么办呢，我们就每一个染色体训练上10轮就行，这样最多1W轮。这样还可以找到经过最少的训练就有最好效果的网络。虽然说，有的网络可能训练少的时候性能差，训练多了比谁都好，但是我们只是学习，别为难电脑了，等有了超算再搞（而且，据研究表明，多数的神经网络，如果一开始就很好，那多训练以后只会更好）。

比较的原则是：误差的平均值越小越好，如果平均值差不多（小于0.01），那就比较标准差，标注差越小越好，标准差也只差个0.01左右，那就比较网络层数，网络层数越少越好，如果层数都一样，那看看参数情况如何，选参数最少的。

8.注意
（1）我们训练个10轮，比较其趋势就行，多数的神经网络，如果一开始就很好，那多训练以后只会更好。
（2）最终这个最好的网络的误差我们要用常规方法来算，不是仅仅计算其误差的平均值和标准差。

9.父母的选择标准：
因为父母是一对一对的，所以选择的过程就是一个二进制选取的过程，每次选两个作为父母来交叉配对。这里其实说的就是第一个算法中第四行的操作。具体是这样做的：
和前面的比较原则一样，区别就在于这里设置一个平均值的差异标准 α \alpha α和一个层数的差异标准 β \beta β：
（1）我们先把全部的染色体根据其平均值从小到大进行一个排序，然后依次两两取出。比如现在我们取出来了μ1和μ2,因为μ1的平均值要比μ2的大，所以可以用μ2的平均值减去μ1的平均值，如果大于 α \alpha α，那就可以说明μ2的误差平均值远大于μ1，先把μ1取出来。
（2）如果不大于 α \alpha α，那就说明两者其实误差的平均值是差不多的，那么就用它们两个层数c1和c2作差求绝对值即|c1-c2|，如果这个值大于 β \beta β的那就说明两个的层数相差很大，那么层数少的那一个可以被取出来。
（3）当两个网络层数差不多时，那就比较它们的标准差，标准差小的优先。
（4）如果标准差一模一样，那就是随便选一个。
（5）最后选出来的这个放到一个数组中，称之为繁殖池。选n个以后停止。剩下的没有生育的资格，因为繁殖也需要成本，所以不能全部都繁殖。

下面是具体的算法伪代码：

Input:两个染色体s1和s2，以及设置好的误差平均值和层数的阈值α和β
Output:被选出来的，有优先择偶权的那个1.if μ2-μ1 > α：2.return s13.else:4.c = |c1-c2|5.if c > β:6.	if c1 > c2:7.		return s28.	else:9.		return s110.else:	11.if std1>std2:13.return s214.else:15.return s1	# 如果标准差也是一样的，那还是返回s1，反正是随便返回一个

10.繁殖的具体步骤：
（1）从刚刚选好的繁殖池里面随机的选取两对出来，作为父母。
（2）把父母的基因进行交叉配对，生下两个新的后代，生完以后把父母从繁殖池删除。
（3）把这两个新生的染色体进行变异，之后保存到一个新的集合Q_t中。
（4）重复上面的操作，直到把繁殖池中的元素删空或者只剩一个。
交叉配对如下：

上图演示了交叉配对的过程： 交叉配对和我们自然界中X和Y染色体的配对过程是一样的，具体过程分为三个部分:
(1)单元拆分(UC)阶段：该阶段把两个神经网络中的三种层分别单独取出，按照它们在染色体的顺序排列好（其实只需要依次取出来就行）。
(2)单元交叉(UAC)阶段：该阶段把两个染色体的三种层都放到一个容器里面进行交叉，如果没有可以与之对应的，就保留。
(3)复原阶段(UR):该阶段把交叉以后的值给放回去，组成和原本一样的新染色体。

**变异：**对应交叉配对之后的新染色体，会发生变异，在这个染色体上的任意一个位置，可能会发生：改变（比如层的参数全部从0变成1）、增加（突然加一个池化层）和删除（删除原本的卷积层）三种变化，概率都是1/3。对于不同的基因层（也就是基因），改变的方式必定也不同，但是我们可以看前面的表格知道这层的主要参数全是数字，对于数字，我们可以采用模拟交叉算法（ Simulated Crossover，SBX）和多项式裂变算法，因为研究表明，它们在模拟自然界中的实数基因时，效果极好。
模拟变异算法的参考论文：
Simulated Crossover (SBX)
多项式裂变算法
赶时间可以参考这两篇博客：
模拟二进制交叉算子详解
遗传算法交叉算子详解

11.自然选择的过程
主要思路就是先把精英保留下来，然后再留一部分幸存者，我们假设有 γ \gamma γ的人能成为精英( γ \gamma γ是一个分数)，所以 γ \gamma γ也被称之为精英分数。如果有n个染色体，那么就有a = n γ \gamma γ的染色体可以称为精英。筛选方法也很简单，就用前面提到的适者生存，不适者淘汰的算法，搞前a个出来。之后再从剩下的几个里面随机选几个。伪代码如下：

Input:一个精英分数γ，Pt和刚刚交叉配对变异生成的Qt
Output: 下一代P(t+1)
1.先计算一下精英的个数a = Nγ(N是初始化时就定义的最大种群数)
2.用上面的适者生存不适者淘汰的算法，从Qt和Pt组成的集合里面，计算出前a个最好的，放入空集P(t+1)中
3.从Pt∪Qt的集合中去掉P(t+1)中的部分
4.while len(P(t+1))小于N：5.从Pt∪Qt里面随机的选择2个染色体s1和s26.用上面说的，挑选父母的算法从中选一个出来加入到P(t+1)
7.最后输出P(t+1)

12.选择最后的染色体：
选择最后的染色体的方法很简单，我们可以根据需要，在最后的一群染色体中选出准确率最好的，也可以选择层数最少的，然后进行更多的训练即可。

3.实验：

种群规模N和设置为100。SBX和多项式裂变的分布指数均设为20，它们的相关概率分别指定为0.9和0.1，池化层卷积层和全连接层的最大值都设置为5，所以神经网络最初最深是15层。根据帕雷托原则，精英比例为20%。卷积层的步幅宽度和高度设置为1，池化层的宽度和高度与核的值相同，卷积类型固定为“相同”。运行环境为搭载了GTX1080的两台电脑。，每个人都由批处理规范强制进行加速和重量衰减，以防止过拟合。由于所提出的EvoCNN方法的启发式性，在每个基准数据集上执行了30次独立的运行，除非另有说明，否则将估计比较的平均结果。此外，实验在我们的硬件基准上需要4天，在其他基准上需要2-3天。注意，要看数据集可能要开科技。
数据集
实验代码

4.总结

最后就是一些和常用的图像识别网络比如VGGnet的比较，发现虽然精度比VGGnet差了一点点，但是参数比VGGnet少了很多。