关键词:
文法演化
符号回归
新解码方式
并行计算
多进程
多线程
摘要:
文法演化(Grammatical Evolution,GE)最早是由爱尔兰学者O’Neill和Ryan提出的一种基于遗传算法和Backus–Naur form(BNF)基础上,基因型和表现型分离的新型进化算法。该算法不仅拥有遗传算法的解码特性且自身拥有很强的描述力,同时它也是遗传程序设计(Genetic Programming,GP)的一个变种。与GP不同的是,GE采用可变长度的二进制字符串来进化出任意语言的程序,而其个体表现型的解码过程主要由BNF产生式的规则之间的替换而成。然而,传统的GE算法在个体生成过程中会产生大量不能被完整映射的个体,而这种不完整映射的个体通常会被赋予最低适应值,这种做法在一定程度上影响了算法的收敛速度和算法精确度。为提高GE算法的演化效率与性能,本文主要对GE算法的编码进行了改进以及高性能并行方面做出了研究,并做出了如下具体改进,详细如下:1)提出一种基于新的解码方式的GE算法(New Decode Grammatical Evolution,NDGE),首先对BNF文法系统中的产生式进行分类,分为递归产生式和非递归产生式,其次利用产生式序列集合替代了传统GE算法的二进制序列作为个体的基因型,并通过设置递归产生式出现的次数从而实现个体基因型的完整映射,最后提出了新的遗传算子以及基因型分组概念和补全机制,有效地解决了传统GE算法中个体不能完整映射的问题,从而使得GE算法在在收敛速度和求解的精度方面有所改善。其中实验结果表明,在平均用时上,NDGE相较于CGE缩短了40%左右,而平均迭代次数上NDGE相较于CGE降低了57%左右。2)基于现有主从模型并没有依据算法本身的结构有选择性地选择多进程还是多线程问题,本文深入分析了GE算法本身框架中设计的可并行结构,以及多进程和多线程的不同应用场景,将算法中可并行的结构与不同并行方式相结合,其中针对评估流程选择使用于计算密集型的多进程方式,而其他种群生成,遗传操作则是选择CPU利用率高的多线程方式。基于此,本文提出一种基于主从模型改进的并行GE算法(Improved parallel GE algorithm based on master-slave model,IPGE),从而通过并行缩短其中的评估时间以及个体生成过程,达到加快算法的迭代和收敛,实验结果表明改进的并行文法演化算法(IPGE)相较于CGE缩短了50%-70%。而基于新解码方式的并行的文法演化算法(IP-NDGE)相较于NDGE时间缩短了40%-70%。3)在1)和2)的基础上,本文提出基于主从模型改进的并行的新解码的文法演化(Improved parallel GE algorithm for new decoding based on master-slave model,IP-NDGE),该方法结合两种改进措施的优点。实验比较了NDGE,IPGE,IP-NDGE,传统GE(CGE)和整数型编码的GE(Integer-Number Grammatical Evlolution,NGE)的算法性能。这五种算法基于相同函数的符号回归的演化性能,本文主要比较进化辈数、平均适应度、平均运行时间和平均迭代次数等标准。实验结果表明改进后的GE算法有更强的自动函数发现能力,都优于CGE和NGE。