Page 63 - 《软件学报》2025年第8期

3486 软件学报 2025 年第 36 卷第 8 期

5 实 验

为了评估提出的 MIL 框架剪枝算法的性能, 我们比较了使用和不使用剪枝算法的系统. 实验在 4 个不同的任
务上进行: 青蛙与荷叶问题、机器人服务员、国际象棋策略和删除列表尾部. 所有实验都在 Intel Core i9-9900K
CPU 和 64 GB 内存的设备上进行.
在评估我们提出的剪枝算法时, 我们的分析重点是比较其与原方法的内存消耗. 为了获得全面且准确的评估,
我们使用了 Prolog 内置谓词 statistics 提供的几个关键性能指标. 这些指标列在表 3 中, 包括推理 (inferences), 即系
统的总逻辑推理尝试次数, 原子 (atoms) 表示符号数据的内存消耗, 全局堆栈 (global_stack) 反映了在执行期间的
数据结构和调用帧的内存消耗. 我们还监控了 CGC (子句垃圾收集) 来评估程序生命周期内的内存回收效率. 需要
注意的是, 在所有进行的实验中, global_stack 都保持在 256 MB, 这符合 SWI-Prolog 的默认堆栈限制.

表 3 评估 Prolog 程序内存消耗的关键指标

指标 定义
Inferences 自Prolog启动以来, 通过调用和重做端口的总次数. 包括子线程中的推理次数
Atoms 内存使用的原子数目
Global_stack 全局使用量, 全局空闲量
CGC 执行的子句垃圾回收次数

5.1 青蛙与荷叶问题
表 4 显示了在有 2 只绿色青蛙和 2 只黄色青蛙时, Metagol 为青蛙与荷叶问题学习到的程序. 生成的程序 (跳
跃策略) 包括 5 条子句和 3 个发明谓词 (即 f3 f2 f1).
,
,

表 4 青蛙与荷叶问题中 Metagol 学到的程序, 其中 n=2

序号 程序步骤
1 f (A,B) : − f3(A,C), f3(C,B)
2 f3(A,B) : −f2(A,C), f2(C,B)
3 f2(A,B) : − f1(A,C),right_two(C,B)
4 f1(A,B) : −left_two(A,C),righ_one(C,B)
5 f2(A,B) : −right_one(A,C),left_two(C,B)

我们首先通过设置不同数量的青蛙来扩展任务青蛙与荷叶问题 (见表 5). 尽管任务的程序空间巨大, 但程序
本身很简单. 因此, 该解决方案不需要高阶的 MIL 系统. 仅使用一阶的 MIL 系统 Metagol 和 Metagol F 来学习策略.
找到策略的学习时间如表 5 所示. 第 2 列表示实例 (作为 MIL 的实例集输入), 第 3 和第 4 列分别代表 Metagol 和
Metagol F 的学习时间 (以 s 为单位). 显然, 改进后的系统 Metagol F 能显著缩短该任务的学习时间. 此外, 实验结果
表明 Metagol F 始终会学习到和 Metagol 相同的策略.

表 5 青蛙与荷叶问题中 Metagol 和 Metagol F 的学习时间 (s)

No. 实例集 Metagol Metagol F
1 f ([1, 0, −1], [−1, 0, 1]) 0.033 0.006
2 f ([1, 1, 0, −1, −1], [−1, −1, 0, 1, 1]) 0.128 0.056
3 f ([1, 1, 1, 0, −1, −1, −1], [−1, −1, −1, 0, 1, 1, 1]) 19.488 5.368
4 f ([1, 1, 1, 1, 0, −1, −1, −1, −1], [−1, −1, −1, −1, 0, 1, 1, 1, 1]) 9 761.168 1 526.604

表 6 展示了 Metagol 及其优化版 Metagol F 的效率, 这里使用了与表 5 相同的 4 个实例, 重点关注推理、原子、
全局堆栈和子句垃圾收集. 当只有一个实例时, 两个模型的表现相似, 表明它们的基本效率相当. 然而, 随着示例数
量的增加, Metagol F 表现出更好的性能, 推理次数更少、原子消耗更低, 表明其计算效率有所提高. 此外, 在 Prolog