Over the last three decades, many attempts have been made to improve the DIRECT (DIviding RECTangles) algorithm's efficiency. Various novel ideas and extensions have been suggested. The main two steps of DIRECT-type algorithms are selecting and partitioning potentially optimal rectangles. However, the most efficient combination of these two steps is an area that has not been investigated so far. This paper presents a study covering an extensive examination of various candidate selection and partitioning techniques within the same DIRECT algorithmic framework. Twelve DIRECT-type algorithmic variations are compared on 800 randomly generated GKLS-type test problems and 96 box-constrained global optimization problems from DIRECTGOLib v1.1 with varying complexity. Based on these studies, we have identified the most efficient selection and partitioning combinations leading to new, more efficient, DIRECT-type algorithms. All these algorithms are included in the latest version of DIRECTGO v1.1.0 and are publicly available.
翻译:在过去三十年中,为了提高直接(DIviding RECTangles)算法的效率,已经做出了许多尝试。提出了各种新的想法和扩展建议。直接型算法的主要两步是选择和分割潜在最佳矩形。然而,这两个步骤最有效的结合是迄今尚未调查的一个领域。本文件介绍了一项研究,涉及对同一直接算法框架内的各种候选人选择和分区技术进行的广泛审查。12个直接型算法变异比较了800个随机产生的GKLS型测试问题和96个组合式限制的、复杂程度不同的GLib v1.1全球优化问题。根据这些研究,我们查明了导致新的、更有效的、更高效的、直接型算法组合。所有这些算法都包含在最新版本的PLGGO v1.1.0中,并可供公众查阅。