论文标题
GBEAM-ACO：Beam-Aco的贪婪和更快的变体
gBeam-ACO: a greedy and faster variant of Beam-ACO
论文作者
论文摘要
Beam-Aco是包含改良光束搜索的传统蚂蚁菌落优化（ACO）算法的修改，是解决旅行推销员问题（TSP）的最有效的ACO算法之一。尽管将光束搜索添加到ACO启发式搜索过程中是有效的，但它也增加了每个步骤算法所做的工作量（就部分路径而言）。在这项工作中，我们引入了一种贪婪的Beam-Aco变体，该变体使用贪婪的路径选择启发式。贪婪路径选择的开发被维护路径束所需的探索所抵消。这种方法具有避免对随机数生成器的昂贵调用并减少算法内部状态的额外好处，从而使并行化更简单。我们的实验表明，在某些情况下，不仅比传统的beam-aco速度更快，我们的贪婪的束 - 阿科（Gbeam-Aco）的速度不仅是较大的，而且不是牺牲发现的解决方案的质量，尤其是在大型TSP实例上。我们还发现，我们称为gbeam-aco的贪婪算法较少依赖超参数设置。
Beam-ACO, a modification of the traditional Ant Colony Optimization (ACO) algorithms that incorporates a modified beam search, is one of the most effective ACO algorithms for solving the Traveling Salesman Problem (TSP). Although adding beam search to the ACO heuristic search process is effective, it also increases the amount of work (in terms of partial paths) done by the algorithm at each step. In this work, we introduce a greedy variant of Beam-ACO that uses a greedy path selection heuristic. The exploitation of the greedy path selection is offset by the exploration required in maintaining the beam of paths. This approach has the added benefit of avoiding costly calls to a random number generator and reduces the algorithms internal state, making it simpler to parallelize. Our experiments demonstrate that not only is our greedy Beam-ACO (gBeam-ACO) faster than traditional Beam-ACO, in some cases by an order of magnitude, but it does not sacrifice quality of the found solution, especially on large TSP instances. We also found that our greedy algorithm, which we refer to as gBeam-ACO, was less dependent on hyperparameter settings.
