论文部分内容阅读
遗传规划（Genetic programming,GP）是进化算法的代表之一,其采用树形结构来表示个体,并模拟达尔文进化论中优胜劣汰的思想,完成优化任务。GP能够在没有明确编程的情况下,自动生成用于解决问题的程序或者结构。笛卡尔遗传规划（Cartesian Genetic Programming,CGP）是针对GP存在的膨胀问题而提出的重要改进。在标准CGP中,个体使用二维有向图表示,能够灵活编码许多计算结构,每个CGP个体具有定长基因型,仅使用点突变算子生成子代,可以很好地避免膨胀问题。然而,在标准CGP中,存在着种群多样性低易陷入局部最优、定长基因无法适应未知规模问题等缺陷。针对这些问题,本文受生物学中DNA突变方式启发,将移码突变作为一种新的操作算子加入CGP算法,提出移码突变CGP（Frameshift Mutation Cartesian Genetic Programming,FMCGP）。围绕FMCGP,本文展开以下三点研究:（1）将DNA中的移码突变方式引入标准CGP中,针对具有一维拓扑的CGP个体,设计移码突变在演化过程中的具体算法。本文提出的移码突变,包括插入式移码突变和删除式移码突变。在FMCGP中,点突变与移码突变并存,在产生子代的过程中,子代有一定的概率使用移码突变。被选定进行移码突变的个体,根据随机概率进行插入式移码突变或者删除式移码突变。FMCGP个体通过插入或者删除节点的方式而具有变长基因。在符号回归和奇偶校验两组常用的基准实验中,通过分析比较标准CGP、对照组算法高级表现型突变（Towards Advanced Phenotypic Mutations in Cartesian Genetic Programming,TAPMCGP）与所提出的FMCGP在一维拓扑个体上的演化性能。实验表明,FMCGP比标准CGP具有更高的演化效率,比对照组算法TAPMCGP具有时间优势。此外,比较了传统GP、标准CGP、FMCGP在Koza-3问题和Even-8-Parity问题上的基因型与表现型程度,结果表明FMCGP仍然保持了CGP的非膨胀特性。（2）为提高算法可用性,将针对一维拓扑的移码突变引入二维拓扑,提出二维移码突变移码笛卡尔遗传规划（Two-dimensional Frameshift Mutation Cartesian Genetic Programming,2-dim-FMCGP）。在2-dim-FMCGP的个体网络中,节点基因中新增了节点所在列号基因（Colunm ID）、最小可连接节点地址基因（Minimum connectable ID）、最大可连接节点地址基因（Maximum connectable ID）三个基因位点,以适应移码突变。在2-dim-FMCGP演化策略中,点突变个体的优先级高于点突变个体,并为个体基因型长度设置上限比例和下限比例,适当缩小了搜索范围。符号回归和奇偶校验两组基准实验的实验结果表明,2-dim-FMCGP能够在确定二维拓扑的情况下,获得比同样拓扑的标准CGP更高的演化效率。为了量化分析图式个体的种群多样性,引入GP中的一种个体编辑距离的计算方式,计算并比较一维、二维的CGP和FMCGP在不同问题上的种群多样性变化,分析结果表明移码突变的加入,提高了种群多样性,增强了群搜索能力。（3）在明确了移码突变在具有二维拓扑图式个体上的操作算法之后,移码突变被进一步引入神经结构搜索（Neural Architecture Search,NAS）问题中,研究了基于FMCGP的自动构建卷积神经网络（Convolutional Neural Network,CNN）的方法。在CGP-CNN的基础上,提出FMCGP-CNN,并在CIFAR-10、CIFAR-100数据集上,通过两组函数集Convset和Res Set验证效果。FMCGP-CNN中,个体网络采用与2-dim-FMCGP中个体相同的编码方式,后代个体由父代个体随机选用点突变或者移码突变生成。根据构建CNN的经验,在FMCGP-CNN中设定了特殊的等位基因约束。在初始化时,个体网络中第一个连接度（level-back）长度内,只选用Conv Block或者Res Block作为函数基因。演化过程中,输出节点基因只能指向最末列网络节点。实验中,使用小部分CIFAR-10或CIFAR-100的训练集评估个体适应度,实验结果表明,在分别使用Conv Set和Res Set两组函数集时,FMCGP-CNN均能获得比CGP-CNN更优的结果。本文围绕移码突变,设计了适用于一维拓扑、二维拓扑图式个体的移码突变算法,在基准函数上分别验证了性能。将FMCGP其引入至NAS问题中,完成了搜寻CNN结构的应用。移码突变的引入,提高了标准CGP种群的演化效率,缓解了标准CGP易陷入局部最优解的问题,并使得个体基因型具有变长基因,能够更好地适应不同规模的问题。此外,FMCGP在NAS问题中的应用,也表明该算法有一定的实用价值。