GSGP-C 2.0：几何语义遗传编程框架

软件X 10（2019）100313原始软件出版物GSGP-C++2.0：一个几何语义遗传编程框架Mauro Castellia，Luca ManzonibaNOVA Information Management School（NOVA IMS），Universidade Nova de Lisboa，Campus de Campolide，1070-312，Lisboa，PortugalbDipartimento di Matematica e Geoscienze，的里雅斯特大学，34127 Trieste，意大利ar t i cl e i nf o文章历史记录：收到2019年收到修订版，2019年7月2日接受，2019年保留字：遗传程序设计语义机器学习a b st ra ct近年来，遗传编程的几何语义算子（GSO）得到了广泛的研究GSO的使用得到了C++框架的促进，该框架以非常有效的方式实现了这些运算符。这项工作提出了一个系统的描述，并专注于最近实施的功能，允许用户存储的信息相关的最佳个人和评估新的数据在一个时间是线性的代数用于找到最佳的个人。本文介绍了该系统的主要特点，并为感兴趣的用户或开发人员提供了一步一步的指导©2019作者由爱思唯尔公司出版这是CC BY-NC-ND下的开放获取文章许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。代码元数据当前代码版本2.0用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2019_170代码海洋计算胶囊https://doi.org/10.24433/CO.5881521.v1GNU通用公共许可证（GPL）使用的代码版本控制系统无使用C++的软件代码语言、工具和服务编译要求，操作环境依赖性源代码可以在Linux，Windows和Cygwin下编译。 如 果 可用，链接到开发人员文档/手册http://gsgp.sourceforge.net/?页面ID=51问题支持电子邮件mcastelli@novaims.unl.pt1. 动机和意义近年来，人们对遗传编程（GP）中语义方法的定义越来越感兴趣[1]。虽然语义的定义不是唯一的，但它通常指的是GP个体对一组训练案例进行评估所产生的输出向量。在GP中包含语义概念的最初尝试集中在间接方法（即，其中使用标准的基于语法的遗传算子，并且考虑语义标准以接受或拒绝新创建的个体）。虽然这些方法提供了一些有益的影响，对GP的每一个，他们需要一个不可忽视的计算工作量，由于*通讯作者。电子邮件地址：mcastelli@novaims.unl.pt（M. Castelli），lmanzoni@units.it（L.Manzoni）。https://doi.org/10.1016/j.softx.2019.100313对大量无用个体（基于语义标准不被接受的个体）的评估。这个问题已经通过直接方法的定义得到了解决，直接方法能够通过定义特定的遗传算子来将语义的概念包括在GP中，这些遗传算子与标准遗传算子不同，对个体的语义有直接的影响[2]。虽然这些算子具有重要的性质[2]，使它们在回归和分类问题中特别有用，但它们存在重要的缺点：首先，由几何语义算子（GSO）生成的独立性的特征在于较大的大小（即，（1）父母的数量，父母的数量。个体随代数呈指数增长（当应用交叉时）是一个重要的限制，在使用语义运算符解决复杂问题时必须考虑到这一点，其中需要数百代才能生成良好的质量2352-7110/©2019作者。由爱思唯尔公司出版。这是一篇开放获取的文章，使用CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx=·+ −·：→−−−−=+·−[客户端]→·：[]n2M. Castelli和L. Manzoni / SoftwareX 10（2019）100313溶液事实上，对这些人的评估使得GP过程慢得令人难以忍受。由于本文中提出的软件，GSO近年来越来越受欢迎，并且可以使用它们来解决复杂的现实问题，这意味着处理大量数据[3]。该软件被称为GSGP-C++（C++中的几何语义遗传编程），现在是GP社区的参考使用新版本的软件，现在可以在生产场景中使用它保存进化结束时返回的最佳模型。本文介绍了新版本的软件，该软件可以保存重建最佳个体所需的信息，并将该个体应用于测试数据，即，以前没有用于进化GP群体的数据。虽然重建完整的个体是一项耗时的任务，但可以以这样一种方式存储最佳解决方案的所有组件，即评估新实例将需要与用于进化最终解决方案的代数2. 软件说明GSGP-C++框架实现了[2]中概述的符号回归的GSO，定义如下：几何语义交叉。给定两个父函数T1，T2RnR，几何语义交叉返回实函数TXO（T1（TR） （（1 （TR）T2），其中TR是一个随机数， 输出值范围在区间内的dom实函数0，1。几何语义突变。给定一个父函数TR R，返回实函数T M不ms（T R1TR2），其中TR1和TR2是随机实函数，其输出值范围在区间0， 1内。实现这些运算符的主要思想是，给定要使用的父树和随机树，只有一种可能的方法来应用几何语义运算符。因此，没有理由存储子代的整个树结构。例如，对于交叉，给定父树T1和T2以及随机树TR，我们可以简单地存储元组（交叉，T1，T2，TR），其中，对于每个个体π，π是到π的存储器引用（或指针）。类似地，没有理由根据后代的树结构来计算后代的适应度。适应度只是语义向量和目标向量之间的距离。因此，我们所需要计算的适应度是语义向量，它可以很容易地从语义向量的T1，T2和TR应用几何语义交叉的定义。对于几何语义突变，可以进行完全类比推理能够简单地通过计算数字向量之间的距离来计算适应度，而不是必须评估树结构，这是所提出的实现效率的主要原因。在时间和空间方面，进化一个n个个体的种群g代的成本是O（ng）（读者可以参考[4]了解详细信息）。2.1. 重建最佳解决方案为了使用GP运行返回的模型，系统存储以下信息：名为“individuals.txt”的文件存储了在GP运行的数学表达式。 文件的第一部分包含形成初始种群的个体，而文件的其余部分存储随机个体。这些参数可以在系统的配置文件中指定（读者可以参考到www.example.com上提供的文档http://gsgp.sourceforge。net/.）所有个体都以中缀表示法存储，运算符写在它们的操作数之间（即，我们通常的表达方式）。方括号用于明确运算符之间的优先级。一个例子，文件 “individuals.txt” 的 第 一 行 ，报告在图。 1. 一 、 文 件“trace.txt”包含重建最佳个体所需的信息。详细地，文件的每一行将与每个交叉、再现和突变事件相关的数据存储为包含以下信息的6元组：– 如果发生了交叉事件，则6元组包含第一父的索引、第二父的索引、随机树的索引、指示交叉事件的0、后代的索引以及最后的哑值（哑值允许系统对变异、交叉和再现事件使用相同的数据结构）。– 如果发生了突变事件，则6元组包含第一随机树的索引、第二随机树的索引、父树的索引（即，突变的个体），1表示突变事件，后代的索引，最后是突变步骤。– 如果发生了再现事件，则6元组包含父的索引、三个伪值、子的索引以及最后的伪值。这些信息用于评估最佳模型的看不见的数据后，图中所示的程序。 二、例如，6-tuple260−&278 −&186 −&1 −&83 −&0。695687表示通过对当前群体的个体186进行突变而获得新群体的个体83。该语义突变必须使用具有0.695687的突变步长的随机树260和278为了优化系统的性能，文件“trace.txt”只包含为构建最佳个体而 这是通过在图1开始描述的标记程序获得的。 二、该过程执行从表示最佳个体的节点开始的有向非循环图的探索上一代）。这种实现方式需要的时间是线性的，相对于图的节点的数量，这是，最多，n g，其中n是人口规模和g的代数。考虑到评估过程具有O（ng）的复杂度，全局过程（即，将所有节点标记为可从最佳个体到达并评估所得到的图）保持相同的复杂性。3. 使用系统本节简要说明如何使用该系统。使用库的第一步需要定义适应度函数，函数和终端符号，以及一组参数。默认的适应度函数是目标值和预测值之间的均方根误差。此外，该软件已经提供了数学运算符的实现，并使用所有因变量作为终端符号。可以指定用作端子符号的常数值范围。在库的文档中，用户可以找到应该修改哪些功能，以便使库适应特定问题。配置文件（名为configuration.ini，包含在可下载的软件包中）允许··M. Castelli和L. Manzoni/SoftwareX 10（2019）1003133图1.一、解 决 方案以中缀表示法 存 储 在文件“individuals.txt”中。图二. 评价最佳个体。图的顶部描述了标记程序，而图的底部部分显示了评估程序。每个区块代表一个个体，每行代表一个总体。箭头表示地球静止轨道的应用。白色块是不被考虑的块。标记程序，因此他们不参与构建最佳解决方案的过程。另一方面，橙色块是由标记过程，并且是必须被评估以提取最佳个体的语义的那些用户指定文档中描述的适当参数。文件1. random_tree：该参数指定系统使用的随机树池2. expression_file：该参数的值为1，指示系统使用文件“individuals.txt”中包含的个体。不同于1的值意味着系统将通过使用可以通过使用参数"init_type“指定的初始化方法之一来创建个体3. USE_TEST_SET：值为1表示系统用于将最佳解决方案应用于一组未见过的实例。如果值不等于1，则表示系统执行标准的进化过程。使用该系统解决用户定义问题的典型方法包括以下步骤：4米 Castelli和L. Manzoni / SoftwareX 10（2019）100313在学习模式下使用系统（即，通过执行标准进化过程）。在此阶段，将参数USE_TEST_SET设置为0，expression_file设置为1（如果要使用文件“individuals.txt”中包含的个体运行系统）或0（如果要随机初始化GP种群）;将上一步中获得的最佳模型应用于未看到的数据。 在此阶段，将参数USE_TEST_SET和expression_file都设置为1。模型的输出存储在文件"evaluation_on_unseen_data.txt“中要编译包含使用建议库的GP算法的文件GP.cc，只需执行以下命令：g++-Wall-O0-g GP.cc-o GP运行程序以执行标准学习过程需要执行以下命令：./ GP-train_file train.txt -test_file test.txt而要将解决方案应用于一组看不见的实例，用户必须运行以下命令：./ GP-test_file test.txt在本例中，train.txt和test.txt是包含训练和测试实例的文件。当系统在USE_TEST_SET的值等于1的情况下执行时，包含测试实例的文件不需要以包含目标值。这在系统的文档中有详细说明。此外，与学习模式中指定的训练和测试文件不同，测试文件的第二行不能包含它存储的实例数C++源代码可以在Linux或Windows下使用Cygwin编译该项目是独立的，只依赖于标准库。提供了文件，包括用户4. 影响本文中描述的系统将允许GP从业者在生产环境中使用最终模型，这代表了GP领域的基本贡献，特别是基于语义的方法。该系统是目前运行速度最快的GP系统，其加速比至少是基于语法的GP系统的20倍我们相信，这种新的实现将使基于语义的方法和遗传编程的使用更加流行：特别是，该系统是可扩展的，允许解决以大量数据为特征的问题。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢这 项 工 作 得 到 了 葡 萄 牙 FCT （ Fun-dação para a Ciência e aTecnologia）项目DSAIPA/DS/0022/2018（GADgET）的国家基金的支持。Mauro Castelli感谢斯洛文尼亚研究机构Slove- nia的财政支持（研究核心资金No.P5-0410）。引用[1]放大图片Vanneschi L，Castelli M，Silva S.遗传程序设计中的语义方法综述。Genetic Program Evolvable Mach2014;15（2）：195-214.[2]Moraglio A，Krawiec K，Johnson CG.几何语义遗传程序。In：Coello CAC，Cutello V，Deb K，Forrest S，Nicosia G，Pavone M，editors.从自然中解决并行问题- PPSN XII：第12届国际会议，意大利陶尔米纳，2012年9月1日至5日，会议记录，第一部分。Berlin，Heidelberg：Springer Berlin Heidelberg;2012，p. 21比31[3]杨伟，王伟，王伟.几何语义遗传编程在现实生活中的应用。遗传编程理论与实践Xi. Springer; 2014，p.191-209.[4]作 者 ： Castelli M ， Silva S， Vanneschi L.几 何 语 义遗 传 编 程 的 C++ 框 架。Genetic Program Evolvable Mach2015;16（1）：73-81.··