SR2JLIB - Java 的符号回归库

引言

SR2JLIB 是一个 Netbeans 项目，它提供了一个用于语法引导的符号回归 (SR) [Koza93] 的 Java 库，该库由遗传编程 (GP) [Koz94, WHM+97] 提供支持，更具体地说，是语法引导遗传编程 (GGGP) [GCA+08]。

本库中实现的这种方法与标准的 GP 不同，它将种群放置在二维网格上。后者定义了可以并行繁殖的个体的栖息地，因此没有阶段的概念。繁殖过程由多个并行线程确保，这些线程随机选择当前种群中的个体，并允许它们繁殖，尝试将后代安置在其祖先的预定义邻域中。每次创建新个体时，都会尝试根据锦标赛选择或概率锦标赛选择将其放置在相邻单元格中。

需要注意的是，用户也可以限制个体的生命周期。这是通过定义最小和最大繁殖次数来完成的。实际繁殖次数将根据个体的适应度，但在预定范围内进行选择。

实现的 GP 程序允许将（多维）向量函数拟合到数据。SR 可以同时或并行地完成向量函数子组件的拟合。库允许的函数是任意的 Java 数值表达式，并允许使用以下形式的条件表达式：

<boolean expression> ? <numeric expression> : <numeric expression>

此外，数值表达式允许使用 java.lang.Math 类中的任何函数原语。我们坚信，交叉操作在繁殖函数时通常意义不大。因此，唯一支持的遗传操作是突变，突变可以分为以下两种类型：

1. 将现有表达式突变为同一类型的一个全新的表达式
2. 将给定函数突变为具有相同元数和相同参数的另一个函数

该库的另一特性是允许对个体进行即时编译 (JIT)，将其编译成 Java 类并动态加载到 JVM 中。后者对库用户来说是无缝进行的，它允许用户通过 Java 代码或使用Java 本地接口 (JNI) 来计算个体的适应度，从而例如从 C 或 C++ 代码计算适应度。

最后但同样重要的是，用于构建表达式的语法是概率性的，每个语法表达式都可以被赋予一个权重，该权重定义了在同类型表达式之间进行选择时，该表达式被选中的可能性。

使用的软件

使用该软件需要 Netbeans IDE 8.2 或更高版本，以及 JDK v1.8 或更高版本。提供了使用该库的示例项目：

1. https://github.com/ivan-zapreev/SR2JLIB_EX
2. https://github.com/ivan-zapreev/SCOTS2SR

前者是一个纯 Java 项目，给出了如何使用该库的基本示例，其中包含多个注释且不言自明。后者是一个更复杂的、基于 JNI 的项目，用于符号拟合 SCOTSv2.0 https://gitlab.lrz.de/matthias/SCOTSv0.2 BDD 控制器 [Run16]。我们还建议仔细查看存储在项目./api/ 文件夹中的库的 Java 文档。

Java 8 JIT 编译器的一个已知问题是其缓存可能已满，从而阻止进一步的个体编译，并可能阻止库正常运行。因此，如果需要使用 JIT 编译，请参阅文本后面的库接口部分，我们建议向 Java 提供以下命令行参数：

-XX:InitialCodeCacheSize=1024m
-XX:ReservedCodeCacheSize=2048m 
-XX:+UseCodeCacheFlushing

这些参数应作为使用 SR2JLIB 的应用程序的 Java 命令行参数提供。如果需要，缓存大小可以进一步增加。

主要概念

本节解释了如何通过指定以下内容来使用该库：

1. 语法的指定方式
2. 要使用的库接口
3. 要实现的观察者和监听器

语法

grammar 用于定义用于向量函数组件的有效数值和布尔表达式。它定义为一组换行符分隔的语法条目：

<grammar> := <entry> | <grammar> \n <entry>

每个语法 `entry` 定义了一个表达式 `type`，并由类型名称和一个或多个分号分隔的该类型的表达式组成：

<entry> := (<type> := <expression>) | <entry> ; <expression>

每个 `type` 是一个 `string`，并且默认提供了一些预定义的（因此是保留的）类型：

R - real expression
B - boolean expression
L - logical constant
V - variable
D - double constant

请注意，`L`、`V` 和 `D` 是内置的，而 `R` 和 `B` 需要由用户指定。布尔表达式 (B) 仅在隐式或显式用于定义 R 时需要指定。指定 R 是强制性的，因为任何经过遗传繁殖的函数都将是 R 类型。

每个 `expression` 定义如下：

1. 一个函数（某个数值/布尔表达式）；
2. 其参数类型；
3. 可选的 `weight` - 一个正双精度数，用于定义同一类型表达式的概率分布（如果省略，则默认值为 1.0）。

<expression> := [<function>](<types>) |
                [<function>](<types>)@<weight>

在这里，`function` 是一个有效的 Java 表达式（根据上下文是布尔值或数值），它使用名为 `x` 的参数，后跟从 `1` 开始的索引（即 x1、x2、x3）。函数参数定义了函数参数，其类型由上面的定义中的 `types` 条目给出。后者是一个逗号分隔的列表：

<types> := <type> | <types>, <type>

列表中元素的数量必须与不同 `function` 参数的数量相对应。此外，参数索引与列表中的相应 `type` 位置匹配。

任何 `function` 都可以通过使用 `$` 符号引用 `java.lang.Math` 类。例如，`$sin(x1)` 将被解释为 `Math.sin(x1)`。考虑以下有效表达式示例：

[x1 - $floor(x1)](D)
[$sin(x1)*x2](V,D)
[$sin(x2)*x1](D,V)

请注意，这里的 `[$sin(x1)*x2](V,D)` 和 `[$sin(x2)*x1](D,V)` 是等效的，并且都表示一个变量参数的正弦乘以一个实常数。

最后一点是，文本语法描述允许使用注释，注释应以 `//` 开头，直到当前行的末尾。

为完整起见，下面提供一个示例语法，该语法假设所有表达式的概率分布均匀，除了 `[$abs(x1)](R)@0.1` 和 `x1](L) @0.01`，它们被赋予较小的使用概率（通过将权重分别设置为 0.1 和 0.01）。

R := [x1](D); [x1](V); [$abs(x1)](R)@0.1; [$sin(x1)](R); [$cos(x1)](R); 
[$sinh(x1)](R); [$cosh(x1)](R); [$tan(x1)](tR); [$tanh(x1)](R); [$acos(x1)](aR); 
[$asin(x1)](aR); [$sqrt(x1)](npR); [$cbrt(x1)](R); [$ceil(x1)](R); [$floor(x1)](R); 
[$log(x1)](lR); [$log10(x1)](lR); [$max(x1,x2)](R,R) ; [$min(x1,x2)](R, R) ; 
[$pow(x1,x2)](R,pI); [$signum(x1)](R); [-x1](R); [x1/x2](R,nR); [x1*x2](R,R); 
[x1+x2](R,R); [x1-x2](R,R) ; [x1 ? x2 : x3](B,R,R)
B := [x1](L) @0.01; [x1!=x2](R,R); [x1==x2](R,R); [x1<x2](R,R); [x1<=x2](R,R); 
[x1>x2](R,R); [x1>=x2](R,R); [!x1](B) ; [x1&&x2](B,B); [x1||x2](B,B)

//User defined by demand:
aR :=  [x1 - $floor(x1)](R) //domain for acos/asin
lR := [(x1<1.0e-4)?1.0e-4:x1](pR) //domain for log/log10
nR := [(x1==0.0)?1.0e-10:x1](R)  //non-zero real
pR := [$abs(x1)](nR)  //positive real
npR := [$abs(x1)](R)  //non-negative real
pI := [$floor(1.0/x1)](nR) //positive integer
tR := [x1 - $floor(x1/$PI)*$PI](R) //domain for tangent

//Form: [function](arguments)@weight
//"$" - is replaced with "Math."
//Arguments are comma separated
//The variable arguments for the java code
//are "args[idx]" where idx begins with 0
//Standard argument types:
//R - real expression
//B - boolean expression
//L - logical constant
//V - variable
//D - double constant

主要接口

SR2JLIB 允许在单独的网格上并行运行多个 SR 进程。每个这样的进程都封装在 `nl.tudelft.dcsc.sr2jlib.ProcessManager` 类的实例中。单个进程管理器可以繁殖多维向量函数。每个向量函数维度函数由某个语法定义。这样的语法可以是个体专用的，也可以与同一实例中或不同 `ProcessManager` 实例中的其他维度共享。语法由 `nl.tudelft.dcsc.sr2jlib.grammar.Grammar` 类的实例定义。每个实例都必须提供一个 `nl.tudelft.dcsc.sr2jlib.grammar.GrammarConfig` 类型的配置对象。通过下面的示例，以示例形式给出了实例化和设置语法的通用模式：

//Clear any previously registered grammars
Grammar.clear_grammars();

//Register dof 0 grammar for process manager index 0
final GrammarConfig g_cfg00 = new GrammarConfig(...);
final Grammar grammar00 = Grammar.create_grammar(g_cfg00);
Grammar.register_grammar(0, 0, grammar00);

//Register dof 1 grammar for process manager index 0
final GrammarConfig g_cfg01 = new GrammarConfig(...);
final Grammar grammar01 = Grammar.create_grammar(g_cfg01);
Grammar.register_grammar(0, 1, grammar01);

//Register dof 0 grammar for process manager index 1
//It has the same grammar as dof 1 of process manager 0
Grammar.register_grammar(1, 0, grammar01);

//Post-process the registered grammars preparing for work
Grammar.prepare_grammars();

这里，`grammar00` 和 `grammar01` 用于在标识符为 0 的 `ProcessManager` 实例中繁殖二维向量函数。此外，`grammar01` 用于在标识符为 1 的 `ProcessManager` 实例中繁殖单维向量函数。

一旦语法被实例化并注册，就需要实例化进程管理器。这些管理器需要使用 `nl.tudelft.dcsc.sr2jlib.ProcessManagerConfig` 类的实例进行配置。此外，每个进程管理器都可以单独启动——开始其符号回归；并停止——停止遗传繁殖过程。

//Create the configuration object
final ProcessManagerConfig config = new ProcessManagerConfig(...)
//Instantiate the process manager with the given configuration
final ProcessManager manager = new ProcessManager(config);
//Start the Symbolic regression
manager.start();
//Stop the manager softly, waiting for all worker threads to finish
manager.stop(true);

如您所见，所有 `Grammar` 和 `ProcessManager` 类的参数都封装在相应的配置对象中。后者，包括建议值和默认值，将在下一节中讨论。另请注意，停止进程管理器通常是在找到足够好的个体后完成的。这样做将在下一节关于监听器、观察者和计算器的部分进行讨论。

配置对象

让我们考虑两个配置对象 `GrammarConfig` 和 `ProcessManagerConfig`。

GrammarConfig 用于语法配置，其构造函数如下：

    /**
     * The basic constructor
     *
     * @param grammar the grammar's textual description
     * @param max_ts the maximum allowed generated expression tree size
     * @param ch_vs_rep the change versus replace ratio from the range [0,1]
     * @param num_vars the number of variables to be used in this grammar
     * @param min_node_grow the minimum node grow coefficient, a positive double
     * @param max_node_grow the maximum node grow coefficient, a positive double
     * @param is_prop_pnodes true if placement nodes are to be propagated
     * @param max_gd the maximum grammar depth for fixed point iteration
     * @param tm_vs_ntm terminal versus non terminal mutation ratio from the
     * range [0,1]
     */
    public GrammarConfig(final String grammar,
            final int max_ts, final double ch_vs_rep,
            final int num_vars, final double min_node_grow,
            final double max_node_grow, final boolean is_prop_pnodes,
            final int max_gd, final double tm_vs_ntm) {...}

这里，我们建议以下默认值：

ch_vs_rep = 0.5;
min_node_grow = 0.8;
max_node_grow = 1.2;
is_prop_pnodes = false;
tm_vs_ntm = 0.5;

选择 `max_ts` 的值取决于具体的 `grammar`，从某种意义上说，使用许多 `Math` 类方法的语法将导致难以计算的函数，这可能会对适应度计算的性能产生负面影响。在这种情况下，树的大小可以选择得比定义多项式的语法等情况小。总的来说，树的大小定义了树中的节点数。每个表达式节点会增加树的大小。

类似地，`max_gd` - *最大语法深度* (MGD) 也与 `grammar` 相关。它应该被设置为 MGD 的上限，MGD 定义为（所有函数上的）最小值（所有函数实例上的）表达式大小的最大值。为简单起见，可以简单地将 `max_gd` 设置为一个相当大的值，例如 `1000`，然后尝试设置语法。如果实际 MGD 大于此值（这种情况非常罕见），则会报告相应的错误。将 `max_gd` 的值设置得高于实际 MGD 不会产生任何性能开销。然而，也可能创建具有无界 MGD 的语法，这类语法是不支持的，因为它们不可行，例如：

R := [x1+x2](R,R)

显然，`R` 是递归定义的，但没有显式或隐式使用任何终端表达式。要修复此语法并使其有界，只需添加一个终端表达式，例如：

R := [x1](D); [x1+x2](R,R)

在这种情况下，最大语法深度将是 3，根据经验法则：“如果每个语法表达式都可以实例化为有限的表达式树，则该语法将具有有界的 MGD。”

ProcessManagerConfig 用于配置进程管理器，其构造函数如下：

    /**
     * The basic constructor
     *
     * @param mgr_id the id of the population manager
     * @param init_pop_mult the initial population coefficient relative to the
     * number of grid cells, from (0.0,1.0]
     * @param num_workers the number of worker threads for this manager, each
     * thread works on reproducing individuals
     * @param max_num_reps the maximum number of reproductions, defined the
     * run-time of the symbolic regression on the grid
     * @param num_dofs the number of dimensions for the individual's vector
     * function
     * @param size_x the number of the population grid cells in x
     * @param size_y the number of the population grid cells in y
     * @param ch_sp_x the number of positions from the parent in x the children
     * will be spread
     * @param ch_sp_y the number of positions from the parent in y the children
     * will be spread
     * @param sel_type the individual's selection type
     * @param is_allow_dying if true then individuals are dying after they had a
     * certain number of children
     * @param min_chld_cnt the minimum number of children before dying
     * @param max_chld_cnt the maximum number of children before dying
     * @param observer the fitness observer instance to monitor the population
     * @param done_cb the call back to be called once this manager has finished
     */
    public ProcessManagerConfig(
            final int mgr_id,
            final double init_pop_mult,
            final int num_workers,
            final long max_num_reps,
            final int num_dofs,
            final int size_x, final int size_y,
            final int ch_sp_x, final int ch_sp_y,
            final SelectionType sel_type,
            final boolean is_allow_dying,
            final int min_chld_cnt,
            final int max_chld_cnt,
            final GridObserver observer, 
            final FinishedCallback done_cb){...}

此类配置的默认建议值为：

init_pop_mult = 0.1;
num_workers = 20;
max_num_reps = Long.MAX_VALUE;
size_x = 30;
size_y = 30;
ch_sp_x = 1;
ch_sp_y = 1;
is_allow_dying = false;
min_chld_cnt = 0;
max_chld_cnt = 0;
sel_type = SelectionType.VALUE;

`mgr_id` 的值取决于管理器的数量，我们建议使用从 `0` 开始的连续（非负整数域）管理器 ID。`num_dofs` 的值是特定于问题的。

最后但同样重要的是，`done_cb` 和 `observer` 提供了回调对象。前者只是一个实现函数式接口的对象，在进程管理器完成 SR 程序后会被调用。后者是一个网格观察对象，允许监控所有种群变化。我们将在下一节中讨论这些接口和其他接口。

监听器、观察者和计算器

有几个主要的接口需要由使用 SR2JLIB 的应用程序来实现，其中前三个是：

1. nl.tudelft.dcsc.sr2jlib.FinishedCallback - 一个函数式接口，供 ProcessManager 使用，以通知用户 SR 已完成
2. nl.tudelft.dcsc.sr2jlib.grid.GridObserver - 一个允许监控符号回归过程的接口，即其开始、停止以及在网格上添加/删除新个体/旧个体
3. nl.tudelft.dcsc.sr2jlib.ErrorListener - 一个可选的错误监听器，用于监控 SR 过程中发生的异常和错误。例如，损坏的语法可能导致无法编译的个体类，这些异常将通过此接口的实例报告。

实现 FinishedCallback 和 GridObserver 的对象作为 ProcessManagerConfig 类构造函数的参数提供。实现 ErrorListener 的对象需要通过调用以下方法从代码中显式设置：

    /**
     * Allows to set a new instance of the error listener
     *
     * @param new_el the new error listener
     * @return an old error listener
     */
    public ErrorListener set_listener(final ErrorListener new_el){...}

nl.tudelft.dcsc.sr2jlib.err.ErrorManager 类的 `addErrorListener` 方法。

需要注意的是，由于 GridObserver 提供了一个接口来监控种群管理器中的个体，因此通常会在此接口的实现中检查个体的适应度，以从内部停止相应的进程管理器。

其他接口（至少需要实现一个）用于个体适应度计算。这些接口由 nl.tudelft.dcsc.sr2jlib.fitness 包中的 `abstract` 类提供，需要实现其重载的

    public abstract Fitness compute_fitness(final int mgr_id, ...);

`compute_fitness` 方法。需要继承的具体 `abstract` 类，以及需要实现的 `compute_fitness` 方法，取决于用户的偏好。我们根据传递给 `compute_fitness` 方法的参数对其进行分类：

1. FitnessComputerExpression - 个体的向量函数表达式树
2. FitnessComputerString - 个体的向量函数序列化为 Java 表达式字符串
3. FitnessComputerClass - 个体的向量函数编译成 Java 类
4. FitnessComputerInstance - 个体的向量函数编译并实例化为一个 Java 对象

为了将适应度计算器类设置为要使用的类，需要使用

    /**
     * Allows to set the instance of the fitness computer.
     *
     * @param inst the instance to be set
     */
    public static void set_inst(final FitnessComputerExpression inst) {...}

nl.tudelft.dcsc.sr2jlib.fitness.FitnessManager 类的 `setFitnessComputer` 方法。

表达式树

每个个体的向量函数维度都以 Java 数值表达式的形式表示。后者最初以树的形式存储，其中非终端节点对应于函数（数值或布尔表达式），终端节点对应于数值或布尔常量，或自由变量。用于构成表达式树的类存储在 nl.tudelft.dcsc.sr2jlib.grammar.expr 包中。每个树节点都是 `Expression` 类的实例。非终端节点是 `FunctExpr` 类的实例，终端节点是 `TermExpr` 类的实例。后者有三个子类：

1. BConstExpr - 布尔常量表达式
2. NConstExpr - 数值常量表达式
3. VarExpr - 双精度自由变量表达式

所有这些都有接口函数，用于遍历表达式树并获取每个节点的有关信息。有关更多详细信息，请参阅 Java 文档。

许可

这是自由软件：您可以在 GNU 通用公共许可证（由自由软件基金会发布）的条款下分发和/或修改它，版本 3 或（根据您的选择）任何更高版本。

本软件的发布是希望它能有所帮助，但**不附带任何担保**；甚至不附带**适销性或特定用途适用性**的默示担保。有关更多详细信息，请参阅GNU 通用公共许可证版本 3 (GPL3)。

您应该已经收到了本程序随附的 GNU 通用公共许可证副本。如果没有，请参阅 https://gnu.ac.cn/licenses/。

文学

1. [Koza93] John R. Koza; Martin A. Keane; James P. Rice (1993). "Performance improvement of machine learning via automatic discovery of facilitating functions as applied to a problem of symbolic system identification" (PDF). IEEE International Conference on Neural Networks. San Francisco: IEEE. pp. 191–198.
2. [Koz94] John R. Koza. Genetic programming as a means for programming computers by natural selection. Statistics and Computing, 4(2):87–112, 1994.
3. [WHM+97] M. J. Willis, H. G. Hiden, P. Marenbach, B. McKay, and G. A. Montague. Genetic programming: an introduction and survey of applications. In Second International Conference On Genetic Algorithms In Engineering Systems: Innovations And Applications, pages 314–319, Sep 1997.
4. [GCA+08] Manrique Gamo, Daniel and Ríos Carrión, Juan and Rodríguez-Patón Aradas, Alfonso (2008). Grammar-Guided Genetic Programming. In: "Encyclopedia of Artificial Intelligence". Information Science Reference, EEUU, pp. 767-773.
5. [Run16] Rungger, M. and Zamani, M. (2016). SCOTS: A tool for the synthesis of symbolic controllers. In Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control, HSCC, 99–104.