Abstract:

Finding the global minimum of complex functions has broad applications in engineering computations and artificial intelligence. The multi-start algorithm is a commonly used heuristic approach for this; however, it suffers from low computational efficiency. To address this issue, a new algorithm based on rejection sampling is proposed. This algorithm improves the initial point selection strategy to reduce computation time and the number of function evaluations while enhancing global convergence capabilities. Traditional multi-start algorithms obtain initial points via independent uniform sampling, which can lead to issues such as clustering of starting points, regions with no points, and low iterative efficiency. Inspired by the k-means++ algorithm′s approach to selecting the initial cluster centers, a rejection sampling method is proposed. This method restricts the distance threshold between a newly sampled point and the previously sampled points in each sampling round, ensuring a uniform spatial distribution of sampling points. A mathematical proof is provided to support this approach. The experimental results demonstrate that, compared to independent uniform sampling, rejection sampling significantly improves the optimization efficiency. For high-dimensional functions, this method can reduce the number of target function evaluations by up to 28%. In problems with multiple global minimums, the reduction in function evaluations can reach up to 41%. The chi-square test is employed to statistically verify that the proposed method can significantly enhance computational efficiency. Compared with currently prevalent optimization algorithms, the proposed algorithm exhibits significant advantages in terms of convergence and computation time. By leveraging parallel computing to accelerate this algorithm, its efficiency reaches 90% with 32-core parallelism, significantly reducing computation time and demonstrating good scalability.

Key words: rejection sampling, multi-start algorithm, global optimization, artificial intelligence, parallel acceleration

摘要：

求解复杂函数的全局最小值点在工程计算和人工智能领域都有广泛的应用，多起始点算法是一种常用的解决此问题的启发式算法，但该算法计算效率较低。为此，提出一种基于拒绝采样的新算法，改进初始点选择策略，以减少计算时间和函数调用次数，同时提高全局收敛能力。传统的多起始点算法采用独立均匀采样获得初始点，会出现起始点聚簇、部分区域无点、迭代效率低等问题。受到k-means++算法对初始聚类中心选择的启发，提出一种拒绝采样方法，通过在每轮采样中限制新采样点到已采样点之间的距离阈值，确保采样点在空间中分布更加匀称，并在数学理论上进行了证明。实验结果表明，相比独立均匀采样，拒绝采样在提高优化效率上具有显著优势，在高维函数的求解中，该方法的目标函数调用次数最多减少28%，在存在多个全局最小值点的问题中，函数调用次数最多减少41%。通过卡方检验在统计学上验证了所提方法可以显著提高计算效率。在与目前通用的优化算法进行比较时，所提算法在收敛性和计算时间上也有显著优势。使用并行计算加速该算法，在32核并行下其效率高达90%，可以显著降低计算时间，显示了良好的可扩展性。

关键词: 拒绝采样, 多起始点算法, 全局优化, 人工智能, 并行加速