坐标搜索 (CS)

class pypop7.optimizers.ds.cs.CS(problem, options)[源代码]

坐标搜索 (Coordinate Search, CS)。

注意

CS 是最早的直接（模式）搜索方法，至少可以追溯到费米 (1938 年诺贝尔物理学奖) 和梅特罗波利斯 (1984 年 IEEE 计算机学会计算机先驱奖)。鉴于它现在很少用于优化黑盒问题，强烈建议首先尝试其他更先进的方法来解决大规模黑盒优化 (LSBBO) 问题。

其原始版本在最坏情况下每次迭代需要 3**n - 1 次采样，其中 n 是问题的维度。这种最坏情况下的复杂度严重限制了其在大规模黑盒优化 (LSBBO) 中的适用性。因此，为简单起见，我们在此使用机会主义策略。更多详情，请参见 Torczon, 1997, SIOPT 中的算法 3。

又称：交替方向法 (alternating directions)、交替变量搜索 (alternating variable search)、轴向松弛 (axial relaxation)、局部变分 (local variation)、罗盘搜索 (compass search)。

参数:

  • problem (dict) –

    问题参数，包含以下通用设置 (键)

    • 'fitness_function' - 需要被最小化的目标函数 (func),

    • 'ndim_problem' - 维度数量 (int),

    • 'upper_boundary' - 搜索范围的上边界 (array_like),

    • 'lower_boundary' - 搜索范围的下边界 (array_like).

  • options (dict) –

    优化器选项，包含以下通用设置 (键)

    • 'max_function_evaluations' - 函数评估的最大次数 (int, 默认: np.inf),

    • 'max_runtime' - 允许的最大运行时间 (float, 默认: np.inf),

    • 'seed_rng' - 随机数生成器的种子，需要明确设置 (int);

    以及以下特定设置 (键)

    • 'sigma' - 初始全局步长（浮点数，默认值：1.0），

    • “x”- 初始（起始）点 (array_like)，

      • 如果未给出，它将从一个均匀分布中随机抽样，该分布的搜索范围由 problem[‘lower_boundary’] 和 problem[‘upper_boundary’] 界定。

    • ‘gamma’ - 全局步长的缩减因子 (float，默认值：0.5)。

示例

使用优化器最小化著名的测试函数 Rosenbrock

 1>>> import numpy
 2>>> from pypop7.benchmarks.base_functions import rosenbrock  # function to be minimized
 3>>> from pypop7.optimizers.ds.cs import CS
 4>>> problem = {'fitness_function': rosenbrock,  # define problem arguments
 5...            'ndim_problem': 2,
 6...            'lower_boundary': -5*numpy.ones((2,)),
 7...            'upper_boundary': 5*numpy.ones((2,))}
 8>>> options = {'max_function_evaluations': 5000,  # set optimizer options
 9...            'seed_rng': 2022,
10...            'x': 3*numpy.ones((2,)),
11...            'sigma': 1.0,
12...            'verbose_frequency': 500}
13>>> cs = CS(problem, options)  # initialize the optimizer class
14>>> results = cs.optimize()  # run the optimization process
15>>> # return the number of function evaluations and best-so-far fitness
16>>> print(f"CS: {results['n_function_evaluations']}, {results['best_so_far_y']}")
17CS: 5000, 0.1491367032979898
gamma

全局步长的缩减因子。

类型:

float

sigma

最终的全局步长（在优化过程中会改变）。

类型:

float

x

初始（起始）点。

类型:

array_like

参考文献

Larson, J., Menickelly, M. and Wild, S.M., 2019. Derivative-free optimization methods. Acta Numerica, 28, pp.287-404. https://tinyurl.com/4sr2t63j

Audet, C. and Hare, W., 2017. Derivative-free and blackbox optimization. Berlin: Springer International Publishing. https://link.springer.com/book/10.1007/978-3-319-68913-5

Conn, A.R., Scheinberg, K. and Vicente, L.N., 2009. Introduction to derivative-free optimization. SIAM. (请参考第七章“方向直接搜索方法”中的算法 7.1（坐标搜索方法）。)

Torczon, V., 1997. On the convergence of pattern search algorithms. SIAM Journal on Optimization, 7(1), pp.1-25. https://epubs.siam.org/doi/abs/10.1137/S1052623493250780

Fermi, E. and Metropolis N., 1952. Numerical solution of a minimum problem. Los Alamos Scientific Lab.