基于进化算法的自动神经架构搜索

阅读文献： A Survey on Evolutionary Neural Architecture Search

是由 Yuqiao Liu 、Yanan Sun 等人发表在 IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS （JCR-Q1）上的一篇综述

abstract

首先指出深度神经网络DNNs的应用广泛，其中DNNs的多层结构在提升性能方面很重要，

但是设计结构过程需要不断试错，这要求设计者有丰富的实践经验。

然后提出神经架构搜索NAS可以实现神经网络的结构的自动设计，

并且实现NAS功能的众多方法中进化计算EC获得大家的广泛关注。

GAP：目前还没有基于EC的NAS算法的全面总结

GOAL：本文采集200多篇最新的基于EC的NAS方法的文章，系统地讨论他们的设计原则和设计依据

 

introduction

DNNs应用广泛且前景不错，DNNs性能依赖本身结构和相关层次的权重，二者达到最合适状态，DNNs的性能才能达到最好。

后续指出DNN的普遍实现方法中，架构都是人为设计的。

所以NAS是一种很有前途的方法。

在数学上，NAS可以通过以下公式化的优化问题来建模：

花体A表示潜在神经架构的搜索空间，L函数测量架构A在训练数据集Dtrain上训练之后在适应度评估数据集 Dfitness上的性能，找到其中适应度的最小值，然而L函数通常是非凸不可微的。

这意味着评估神经网络性能的函数可能在参数空间中有很多局部最小值，且在某些点上没有导数，这使得传统的基于梯度的优化方法难以直接应用。

根据使用的优化器，现有的NAS算法大致可以分为三类:

神经架构搜索算法	特点
基于强化学习 (RL)	需要数千个GPU工作数天才能够完成预期的效果，例如CIFAR-10图像分类数据集，显示很难广泛应用。
基于梯度	相比于强化学习，更加有效率，但是由于优化器的选择可能会导致病态，并且需要专家知识
基于进化算法（EC）	广泛应用于解决非凸优化问题，甚至目标函数数学表达式未知的问题。

即使在目标函数的数学形式不可用的情况下，EC方法依然具有对局部极小值不敏感且不需要梯度信息的良好特性，所以EC也被广泛应用于解决复杂的非凸优化问题

 

之后开始讲解基于EC的NAS的历程，开端是谷歌于2017年3月在arXiv中发布的LargeEvo算法（采用遗传算法搜索CNN的最佳结构），从此之后三年内基于EC的NAS大量涌出。

对比其他综述，本文的gap：其他综述的大多数参考文献都是在2019年之前，不包括过去两年发表的论文的更新，而过去两年是大多数ENAS作品发表的时间。本文对大量ENAS论文进行了综述，以期为促进ENAS的发展提供一些新的思路。

Elsken等人[26]将NAS分为三个阶段：搜索空间、搜索策略和性能评估策略。

对应本文介绍了编码空间和编码策略、种群更新过程、加快进化的多种方法。

之后介绍本文的行文顺序。即第二节讨论了ENAS的背景。第三节记录了ENAS算法的不同编码空间、初始空间和搜索空间。在第四节中，介绍了编码策略和体系结构表示。第五节总结了种群更新的过程，包括进化算子和选择策略。第六节展示了加快进化的多种方法。第七节介绍了ENAS算法的应用。第八节讨论了挑战和前景，最后第九节提出了结论（本节为第一节）

background

ENAS的普遍流程图

首先群体初始化，确定编码策略。即从初始空间中构建个体（每个个体代表一个深度神经网络架构），然后评估个体适应度。

初始化完成后，进入群体进化阶段。从初始化群体中随机选择个体作为父代。根据搜索空间，进行交叉、变异等进化操作，对生成的个体评估其适应度。根据群体更新策略，选择保留的个体，加入到群体中，直到满足条件，返回最优的个体。

上面算法主要涉及搜索空间的设计，编码，群体更新策略，以及评估加速方法。

 

ENAS分类

按照使用的搜索策略分类

如下图1所示，ENAS使用的EC方法，根据采用的搜索策略，可以分为进化算法（evolution algorithm），群体智能（swarm intelligence）和其他方法。目前论文研究中进化算法占绝大多数，其中遗传算法（GA）又占一大部分，遗传编程（GP）和进化策略（ES）也属于进化算法。群体智能算法中又包括粒子群优化方法（PSO）和蚁群算法（ACO）。同时，在其他分类中也存在差分进化（DE），萤火虫算法（FA）等

按照用于的神经网络分类

按照用于的神经网络分类，ENAS的最终产品：卷积神经网络（CNN）、深度置信网络（DBN）、堆叠自编码器（SAE）、循环神经网络（RNN）、其他。

各网络结构的例子

CNN：

DBN:

SAE:

RNN:

 

ENAS在不同的DNNs下对常用参数的优化

	参数
CNN	全局参数	层数，层之间的连接
	卷积层	滤波器尺寸（宽和高）、步长尺寸（宽和高）、特征图尺寸、卷积类型、滤波器元素的标准差和均值
	池化层	滤波器尺寸（宽和高）、步长尺寸（宽和高）、池化类型
	全连接层	神经元数量，权重的标准差和均值
DBN, AE	隐藏层数量，每层神经元数量
RNN	隐藏层数量，每层神经元数量，时间槽数量

编码空间

下图为不同的编码空间及其限制

	固定深度	丰富的初始化	部分固定结构	相对较少的约束
基于层的编码空间	[34],[47]-[57]	[34],[58]-[62]	[20],[54],[63]-[73]	[21]-[23],[25],[39],[40],[42],[46],[74]-[106]
基于块的编码空间	[107]-[109]	[110]	[69],[110],[111]	[9],[24],[32],[76],[105],[112]-[122]
基于单元的编码空间			[123]-[125]	[36],[122],[126]-[132]
基于拓扑的编码空间		[133],[134]		[35],[135]-[140]

编码空间类型	定义	优点	缺点
基于层的编码空间	编码空间的基本单位是原始层，如卷积层和全连接层。	- 能够构建复杂的网络结构 - 灵活性高	- 搜索空间巨大，导致搜索过程耗时 - 难以找到优秀的网络架构
基于块的编码空间	编码空间的基本单位是组合了不同类型层的块，如ResBlock、DenseBlock。	- 减少了搜索空间 - 易于找到优秀的网络架构	- 块的设计和选择需要专业知识
基于单元的编码空间	编码空间的基本单位是重复的单元，通常所有块都相同。	- 大大减少了编码空间的大小 - 易于构建和搜索	- 可能限制了网络的多样性和创新性
基于拓扑的编码空间	不考虑每个单元的参数或结构，只关心单元之间的连接。	- 能够探索不同连接方式的网络架构 - 适用于超图表示的网络	- 对于复杂的网络结构可能不够灵活

同时，编码空间中的约束也是非常重要的，这表示人参与的程度。较多的约束可以得到较好的结构，但阻止了任何不在约束中的新结构。另外，不同大小的搜索空间也会影响搜索效率。

 

当前，编码空间主要关注三方面，固定深度，丰富的初始化以及部分固定结构。固定深度表明群体中的所有个体结构有着相同的深度。丰富的初始化表示结构具有良好的设计，通常是人工设计的。部分固定结构意味着网络结构中有部分是确定的。相对较少的约束表明没有前面三个方面要求的较强的约束。

 

下图为三个空间之间的联系

一般而言，初始化以及进化过程中的搜索空间是相同的，有时初始化时会加入一些人为约束，使得进化过程的搜索空间将大于初始化的搜索空间。

初始空间

一般分为三种形式：从普通的初始条件开始、在编码空间内随机初始化、从高性能结构开始

这三种形式被称为三种初始空间即：平凡空间（可以演化出新颖的结构）、随机空间、精心设计的空间（很难演化出好的结构），但实际上很多人使用精心设计的空间来提高性能

初始空间类型	描述	特点	应用
平凡空间（Trivial Space）	从非常简单的初始条件开始，通常只包含一些基本的原始层。	- 可以演化出新颖的结构 - 需要较少的先验知识 - 可能需要更多的进化步骤来达到高性能	- 适用于探索全新的解决方案 - 鼓励创新和多样性
随机空间（Random Space）	在编码空间内随机初始化个体，每个个体都是随机生成的。	- 初始种群具有较高的多样性 - 不依赖于先验知识 - 搜索过程可能更加随机和不可预测	- 适用于广泛的搜索空间 - 可以避免局部最优
精心设计的空间（Richly Initialized Space）	从已经表现良好的结构开始，这些结构通常是人工设计的。	- 很难演化出比初始结构更好的新结构 - 依赖于专业知识和先验知识 - 可能快速收敛到高性能解	- 适用于性能提升和微调 - 常用于在已知的优秀架构基础上进行改进

搜索空间

使用随机空间的话，搜索空间和初始空间一样大；使用另外两种空间的话，搜索空间会大于初始空间。有的人采用限制进化算子的方法限制搜索空间，而不是直接定义搜索空间

编码策略

每种ENAS方法在开始第一个阶段之前，需要确定如何将网络编码成个体。一般根据进化过程中个体长度是否变化，将编码策略分为固定长度编码以及可变长度编码。

使用固定长度编码，在进化过程中个体拥有相同的长度。但是，需要定义一个合适的最大长度，因为这关系到网络结构的最优深度，但这依赖一定的专业知识以及经验。可变长度编码包含结构的更多细节以及更自由的表示，当面临一个新问题时，可以随机设置编码长度。（具体参考论文第6、7页）。

 

编码策略类型	定义	优点	缺点
固定长编码策略	个体在进化过程中具有相同的长度	- 有利于直接利用原本为固长编码设计的标准进化操作 - 实现简单，易于处理。	- 需要预先定义个体的最大长度，这与深度神经网络的最佳深度有关。 - 最佳深度通常未知，因此依赖于构造者的专业知识和经验。
变长编码策略	个体在进化过程中具有不同的长度	- 不依赖于构造者的专业知识和经验。 - 可以更灵活地探索解空间。	- 需要重新设计进化算子以适应不同长度的个体。 - 可能导致过度复杂的个体，增加评估的计算成本。

 

此外，大多数的DNN结构都可以表示为由不同的基本单元和单元之间的连接组成的有向图，因此，对于架构的编码可以分为两个方面：基本单元的配置和连接。

基本单元的配置编码

不同的基本单元有不同的配置Table 1 可以看到

连接的编码

网络架构一般分为线性架构和非线性架构

群体更新

下图是ENAS根据EC方法的分类

EAs for ENAS

基于进化算法EA的群体更新，按照选择策略分类：

Elitism	精英主义方法会保留最高适应度的个体，但这种方法容易损失种群多样性，导致种群落入局部最优
Discard the worst or the oldest	丢弃最坏的个体与精英主义相似，从种群中移除最低适应度的个体。也有选择丢弃种群中最老的个体，这种方法可以更多的探索搜索空间不用过早的选择好模型
roulette wheel selection	轮转法会根据群体中个体的适应度分配一个概率，无论好坏，将决定个体是否存活（或被丢弃)
tournament selection	锦标赛选择法从等概率采样的个体中选择最好的一个
Others	在一些论文中，强调基因比存活个体更重要，基因可以表示结构中的任何成分。

基于进化算法EA的群体更新，按照进化操作分类：

操作类型	定义	特点
突变	在进化操作中，突变是指在单个个体上执行的操作，目的是在个体周围搜索全局最优解。	- 允许编码信息在给定范围内变化 - 可以是有方向的，通过预测可能的高性能架构来指导突变 - 可以保持种群多样性，通过使用可变的突变概率或强制突变和距离计算
交叉	在进化操作中，交叉是指需要两个个体参与，通过交换它们的部分基因来产生后代的操作。	- 通常用于长度相等的个体 - 可以是破坏性的，交换整个层序列 - 可以是非标准的，如模拟二进制交叉，产生与双亲不同的后代

多目标ENAS

单目标	搜索精度最高的架构
多目标	同时处理神经网络的性能和参数数量

解决多目标优化问题的方法

多目标ENAS方法	描述	优点	缺点
加权求和法	将多个目标函数通过加权因子转化为单目标优化问题。	- 简单易实现 - 可直接应用于现有的单目标优化算法	- 权重选择可能带有主观性 - 可能无法平衡各目标间的冲突
非线性惩罚项	使用非线性惩罚项代替加权求和法来处理多目标优化。	- 可以减少权重选择的主观性	- 设计合适的惩罚项较为复杂
NSGA-II	一种经典的多目标优化算法，用于寻找帕累托前沿。	- 能够找到一组帕累托最优解 - 适用于多目标问题	- 计算复杂度较高 - 对于非凸优化问题可能存在局限性
MOEA/D	基于分解的多目标进化算法。	- 有效处理多目标优化问题 - 灵活性高	- 参数设置较为复杂 - 对于特定问题可能需要调整
LEMONADE	将目标函数分为昂贵和便宜的评估目标，以节省计算资源。	- 减少对资源的消耗 - 提高评估效率	- 可能无法完全反映所有目标的重要性
改进的NSGA-III	对传统NSGA-III进行改进，以更好地处理特定多目标问题。	- 适应性更强 - 能够处理更复杂的多目标问题	- 需要针对具体问题进行调整 - 实现难度较高

SI for ENAS

基于群体智能SI的群体更新

粒子群优化 (PSO)	启发来自鱼群，利用群体中的个体对信息的共享 使整个群体的运动再问题求解空间中产生从无序 到有序的演化过程，从而获得最优解
蚁群算法 (ACO)	由自然界中蚂蚁觅食的行为而启发，每个蚂蚁根 据信息素的指导从一个节点到另一个节点构建出 一个结构，每代更新信息素，从而吸引下一代蚂 蚁进行探索，由于信息素是逐渐衰减的，这也鼓 励其他蚂蚁探索其他区域。最终得到一个最优结 构。

用于ENAS的其他EC技术

进化差分 (DE)	首先，产生足量的随机变量，作为初始的可能解。接着进行突变、交叉、选择计算，一轮后, 检查是否满足终止条件，若未满足，则重新突变、交叉、选择计算，最终输出最后一轮的最佳解。
萤火虫算法 (FA)	是一种模仿萤火虫之间信息交流，相互吸引集合，算法中，每个萤火虫的位置代表了一个待求问题的可行解，而萤火虫的亮度表示该萤火虫位置的适应度，亮度越高的萤火虫个体在解空间中的位置越好
爬山算法 (HCA)	是一种局部搜索算法，再增加高度的方向上连续移动，以找到山峰或最佳解决问题的方法。 再达到峰值时终止，其中没有邻居具有更高的值
Coronavirus optimization algorithm (CVOA)	通过模拟病毒传播以及感染健康个体从而发现最优结构

性能评估

评估策略选择（因为ENAS评估很消耗时间）

在进化NAS算法中，通常网络评估过程是最耗费时间的。几乎所有的方法评估个体，首先要进行训练，然后在验证集/测试集上评估效果。由于结构正变得越来越复杂，训练每一个结构要花费大量时间使其收敛。因此，有了各种不同的方法来缩短评估时间，减少计算资源消耗。常见的加速评估过程的方法有权重继承，早停，减小训练集，以及群体记忆

评估加速算法	简介
权重继承	因为进化操作不会完全打破个体结构，新生成的个体的一 些结构和它们父代相同。因而相同部分的权重可以很容易 的继承过来。由于权重继承，不需要再从头训练网络。
早停策略	早停策略已被广泛用于NAS方法中，最简单的方式是设置 一个固定且相对较小的训练epoch。但是，早停策略也导 致评估个体表现不准确，特别对于大型，复杂结构
减少训练集	使用与大数据集相似特性的数据集子集，可以有效的缩短 时间。一般与迁移学习结合将搜索出的模型迁移到大型数 据集上
群体记忆	重用群体中前面出现过的结构信息。在基于群体方法，特 别是基于遗传的算法中，会在后代中保留群体内表现良好 的个体。有时下一代个体直接继承它们父代所有的结构信 息，因此，不需要再重新评估该个体

如图可知选取观测点的不同，性能评估的结果不同

应用

基本上深度神经网络应用到哪里，ENAS就可以应用到哪

挑战和议题

效率、可扩展性、高效的评估方法和减少计算成本、可解释性

结论

缺少统一的评价标准以及挑战和议题中提到的问题

最后本文比较老2020，所以需要最新的文献

 

ref：

https://blog.csdn.net/qq_40367982/article/details/133147320?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522172467338016800227475444%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=172467338016800227475444&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-133147320-null-null.142^v100^control&utm_term=A%20Survey%20on%20Evolutionary%20Neural%20%20Architecture%20Search&spm=1018.2226.3001.4187

https://blog.csdn.net/weixin_56593260/article/details/122662661?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522172467564316800185845375%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=172467564316800185845375&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-6-122662661-null-null.142^v100^control&utm_term=A%20Survey%20on%20Evolutionary%20Neural%20%20Architecture%20Search&spm=1018.2226.3001.4187