基于GEP的符号回归问题的实现与GPU加速

论文摘要

随着在科学定律发现、微积分方程求解等方面取得不断成功，符号回归成为计算机科学的重要研究课题，但是对于求解高维物理系统自然规律隐式挖掘这个多世纪难题，则有待符号回归的进一步研究。目前，GP算法是符号回归问题的主流解决方法，结合随机偏导对概念，已经在4维物理系统中试验成功，但在拟合公式的多样性、收敛速度、计算效率等方面存在诸多不足，很难向高维空间继续扩展。本文在GP符号回归基础上，采用基因表达式编程算法（GEP），在个体表达、偏微分计算、遗传算子、常数生成等方面进行了改进，并采用―CPU+GPU‖异构模式并行加速适应度值计算，最终GPU并行部分获得了18-20倍的加速比，GEP算法整体较之其CPU版本获得了3-5倍的加速，而GEP算法较之GP算法则获得了200倍的速度提升。本文先后尝试了CGP、GEP等线性表达取代GP有向无环图表达形式，采用自动微分代替符号微分，改进了遗传算子操作，引入随机选择、差分进化、最小二乘法等常数生成方法，最后提出GPU并行方案并讨论了不同层次与粒度并行带来的不同加速效果。实验结果证明，GEP算法有效提高了符号回归问题的解决效率，为高维系统的高效符号回归提供了更大的可能性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外现状研究
• 1.3 本文研究内容
• 1.4 本文组织结构
• 第二章 基因表达式编程与 GPU 通用计算技术
• 2.1 基因表达式编程（GEP）
• 2.1.1 GA、GP、GEP 异同
• 2.1.2 个体表达方式
• 2.1.3 适应度函数与选择算子
• 2.1.4 变异，换位插入，重组
• 2.1.5 GEP 算法描述
• 2.2 GPGPU 与 CUDA
• 2.2.1 GPU 并行计算
• 2.2.2 CUDA 计算模型
• 2.3 本章小结
• 第三章 GEP 算法改进与 GPU 并行加速方案
• 3.1. 算法描述与改进
• 3.1.1 GP 算法求解符号回归
• 3.1.2 GEP 算法求解符号回归
• 3.2. 个体表达方式
• 3.2.1 CGP（Cartesian Genetic Programming）
• 3.2.2 GEP（Gene Expression Programming）
• 3.3. 微分方程
• 3.4. 遗传算子
• 3.4.1 选择算子（selection）
• 3.4.2 变异算子（mutation）
• 3.4.3 换位插入算子（transposition）
• 3.4.4 重组算子（recombination）
• 3.5. 常数项的生成与改进
• 3.5.1 随机选择进化常数
• 3.5.2 差分进化进化常数
• 3.5.3 最小二乘进化常数
• 3.6. GPU 并行方案设计
• 3.6.1 CPU+GPU 异构模式并行
• 3.6.2 Thread GEP、Block GEP、Warp GEP
• 3.6.3 CUDA 程序优化
• 3.7. 本章小结
• 第四章 实验结果与分析
• 4.1 实验环境
• 4.2 实验选取
• 4.3 实验验证与结果分析
• 4.3.1 基础测试用例
• 4.3.2 常数测试用例
• 4.3.3 多变量测试用例
• 4.3.4 GPU 加速测试用例
• 4.4 本章小结
• 第五章 总结与进一步工作
• 5.1 本文工作总结
• 5.2 进一步研究方向
• 致谢
• 参考文献
• 作者在读研期间的研究成果