Results of Bet-and-Run Strategies with Different Decision Makers on the Traveling Salesman Problem and the Minimum Vertex Cover Problem

Results of Bet-and-Run Strategies with Different Decision Makers on the Traveling Salesman Problem and the Minimum Vertex Cover Problem 1. Introduction In this repository, we provide the implementation and results of an improved generic Bet-and-Run strategy for black-box optimization. The goal our new Bet-and-Run method is to obtain the best possible results within a given time budget T using a given black-box optimization algorithm. If no prior knowledge about problem features and algorithm behavior is available, the question about how to use the time budget most efficiently arises. We propose to first start n>=1 independent runs of the algorithm during an initialization budget T1<T, pausing these runs, then apply a decision maker D to choose 1<=m<n runs from them (consuming T2>=0 time units in doing so), and then continuing these runs for the remaining T3=T-T1-T2 time units. In previous bet-and-run strategies, the decision maker currentBest would simply select the run with the best-so-far results at negligible time. We propose using more advanced methods and test several different approaches, including neural networks trained or polynomials fitted on the current trace of the algorithm to predict which run may yield the best results if granted the remaining budget. Applying this implementation to run "virtual experiments," one can find that this approach can yield better results than the previous methods, but also find that the `currentBest` method is a very reliable and robust baseline approach. Here you can find the results of such experiments on the Traveling Salesman Problem and the Minimum Vertex Cover Problem. Both betAndRun_tsp.tar.xz and betAndRun_vertex_cover.tar.xz are extracted in the scale of 30 GiB of size. 2. Copyright The source code in this repository is under MIT License and is published in the most recent version at http://github.com/thomasWeise/betAndRun, while the results are under the Creative Commons Attribution 4.0 License. The code on bet-and-run (mainly under cn.edu.hfuu.iao.betAndRun) is jointly developed by Dr. Thomas Weise (http://iao.hfuu.edu.cn), [e-mail], [e-mail]) and Dr. Markus Wagner (http://cs.adelaide.edu.au/~markus/, [e-mail]). The jpack (http://github.com/marmakoide/jpack) code for Artificial Neural Networks, Linear Algebra, and Evolution Strategies (e.g., CMA-ES) has originally been developed by Dr. Alexandre Devert (http://www.marmakoide.org, [e-mail], and http://github.com/marmakoide), who kindly granted us the permission to include it in our repository. The code published here is a slightly modified version of his code, but the copyright and authorship remains entirely with Dr. Devert, who provides it under the MIT license at GitHub under http://github.com/marmakoide/jpack. Please contact Dr. Devert for any questions, in particular regarding licensing and (re-)distribution.

# 面向旅行商问题（Traveling Salesman Problem）与最小顶点覆盖问题（Minimum Vertex Cover Problem）的不同决策者下注并继续（Bet-and-Run）策略实验结果

1. 引言
本仓库提供了面向黑盒优化（black-box optimization）的改进型通用下注并继续（Bet-and-Run）策略的实现与实验结果。我们提出的新型下注并继续方法的目标，是在给定的时间预算T内，通过指定的黑盒优化算法获取最优可能的结果。若不存在关于问题特性与算法行为的先验知识，则会出现如何最高效地利用时间预算的问题。我们提出的流程为：首先在初始化预算T1（T1<T）内启动算法的n≥1次独立运行并暂停这些进程；随后通过决策者D从这n次运行中选取1≤m<n次运行（此过程耗时T2≥0）；最后针对剩余时长T3=T-T1-T2继续执行选中的运行。
在过往的下注并继续策略中，currentBest型决策者仅需极短耗时即可选出当前已获得最优结果的运行进程。我们提出采用更先进的方法，并测试了多种不同的实现路径，包括基于算法当前运行轨迹训练的神经网络或拟合的多项式，以预测在获得剩余预算后哪次运行能够取得最优结果。
将本实现用于开展"虚拟实验"后可发现，该方法能够取得优于过往策略的结果，但同时也证实currentBest方法是一种极为可靠且鲁棒的基准方法。本仓库可获取针对旅行商问题与最小顶点覆盖问题的此类实验结果。betAndRun_tsp.tar.xz与betAndRun_vertex_cover.tar.xz两个压缩包解压后体积约为30 GiB。

2. 版权声明
本仓库内的源代码采用MIT许可证（MIT License）开源，最新版本发布于http://github.com/thomasWeise/betAndRun；而实验结果采用知识共享署名4.0国际许可协议（Creative Commons Attribution 4.0 License）发布。
下注并继续模块的代码（主要位于cn.edu.hfuu.iao.betAndRun路径下）由托马斯·魏斯博士（Dr. Thomas Weise，http://iao.hfuu.edu.cn，[e-mail]、[e-mail]）与马库斯·瓦格纳博士（Dr. Markus Wagner，http://cs.adelaide.edu.au/~markus/，[e-mail]）联合开发。
用于人工神经网络、线性代数与进化策略（Evolution Strategies，如CMA-ES）的jpack代码（http://github.com/marmakoide/jpack）最初由亚历山大·德韦尔博士（Dr. Alexandre Devert，http://www.marmakoide.org，[e-mail]，http://github.com/marmakoide）开发，其已慷慨授权我们将该代码纳入本仓库。本仓库发布的代码为其原始代码的小幅修改版本，但版权与著作权仍完全归属德韦尔博士，其在GitHub的http://github.com/marmakoide/jpack以MIT许可证发布该原始代码。若有任何相关问题，尤其是涉及许可证及（再）分发的问题，请联系德韦尔博士。