MiniZinc:如何实现自定义搜索启发式?(对)



对于完整的上下文,我的目标是实现一个"代理";它试图以在线方式从给定的池中学习最佳启发式(意味着学习和解决过程同时完成)。从本质上讲,搜索策略将基于重新启动:求解器应该能够在每次重新启动时根据搜索期间积累的观察结果在搜索启发式之间切换。以下是之前关于这个主题的一些作品:

https://www.ijcai.org/proceedings/2022/258

https://drops.dagstuhl.de/opus/volltexte/2022/16661/

我认为这不能直接在MiniZinc中完成,必须直接在求解器(例如Gecode)中实现。我对FlatZinc、求解器以及两者之间的接口了解甚少。事实上,我有数学背景,并没有太多的编程经验。我可以看到MiniZinc和Gecode参考手册都非常详细,但由于我似乎无法掌握基本知识,它们实际上让我比以前更困惑。

到目前为止,我已经下载了Gecode源代码,但即使我设法实现了我的自定义启发式(这是一个很大的如果),我也不确定下一步会是什么。我如何在MiniZinc中使用它?我真的很感激一些一般的指示(记住我没有太多的编程经验)!

MiniZinc中的搜索启发式通常通过搜索注释进行管理。

当求解器实现自定义搜索启发式时,它通常会添加求解器特定的注释。可以在gecode.mzn文件中找到Gecode的示例。然后,例如,使用"放松和重建";(随机LNS)搜索启发式,您可以包含Gecode声明并将其作为常规搜索启发式使用:

include "gecode.mzn";
array[1..4] of var int: x;
solve ::relax_and_reconstruct(x, 90) maximize sum(x);

就像你描述的搜索启发式一样,relax_and_reconstruct依赖于重启。因此,它需要您使用重启标志来指示求解器如何(以及何时)重启:--restart-base,--restart,--restart-scale,--restart-limit

在Gecode中实现自定义搜索启发式可能很棘手,但MPG应该提供一个全面的指南。创建了新的搜索启发式后,可以将其添加到FlatZinc处理中,以便将其添加到创建的实例中。(并将其添加到前面提到的gecode.mzn文件中,使其在MiniZinc中可用。

最新更新