rs.py

import numpy as np  # engine for numerical computing

# abstract class of all Black-Box Optimizers (BBO)
from pypop7.optimizers.core.optimizer import Optimizer


class RS(Optimizer):
    """Random (stochastic) Search (optimization) (RS).

    This is the **abstract** class for all `RS` classes. Please use any of
    its instantiated subclasses to optimize the black-box problem at hand.

    .. note:: `"Local search was reinvigorated in the early 1990s by
       surprisingly good results for large (combinatorial) problems ...
       and by the incorporation of randomness, multiple simultaneous
       searches, and other improvements."---[Russell&Norvig, 2022, AIMA]
       <http://aima.cs.berkeley.edu/global-index.html>`_

       **Randomized Local Search (RLS)** is often seen as one of `heuristic
       optimization algorithms, also called hill climbing, steepest ascent,
       or greedy search <>`_.

    Parameters
    ----------
    problem : dict
              problem arguments with the following common settings (`keys`):
                * 'fitness_function' - objective function to be **minimized** (`func`),
                * 'ndim_problem'     - number of dimensionality (`int`),
                * 'upper_boundary'   - upper boundary of search range (`array_like`),
                * 'lower_boundary'   - lower boundary of search range (`array_like`).
    options : dict
              optimizer options with the following common settings (`keys`):
                * 'max_function_evaluations' - maximum of function evaluations (`int`, default: `np.inf`),
                * 'max_runtime'              - maximal runtime to be allowed (`float`, default: `np.inf`),
                * 'seed_rng'                 - seed for random number generation needed to be *explicitly* set (`int`);
              and with the following particular setting (`key`):
                * 'x' - initial (starting) point (`array_like`).

    Attributes
    ----------
    x     : `array_like`
            initial (starting) point.

    Methods
    -------

    References
    ----------
    Nesterov, Y. and Spokoiny, V., 2017.
    Random gradient-free minimization of convex functions.
    Foundations of Computational Mathematics, 17(2), pp.527-566.
    https://link.springer.com/article/10.1007/s10208-015-9296-2

    Bergstra, J. and Bengio, Y., 2012.
    Random search for hyper-parameter optimization.
    Journal of Machine Learning Research, 13(2).
    https://www.jmlr.org/papers/v13/bergstra12a.html

    Appel, M.J., Labarre, R. and Radulovic, D., 2004.
    On accelerated random search.
    SIAM Journal on Optimization, 14(3), pp.708-731.
    https://epubs.siam.org/doi/abs/10.1137/S105262340240063X

    Schmidhuber, J., Hochreiter, S. and Bengio, Y., 2001.
    Evaluating benchmark problems by random guessing.
    A Field Guide to Dynamical Recurrent Networks, pp.231-235.
    https://ml.jku.at/publications/older/ch9.pdf

    Schmidhuber, J. and Hochreiter, S., 1996.
    Guessing can outperform many long time lag algorithms.
    Technical Report.
    https://www.bioinf.jku.at/publications/older/3204.pdf

    Rastrigin, L.A., 1986.
    Random search as a method for optimization and adaptation.
    In Stochastic Optimization.
    https://link.springer.com/chapter/10.1007/BFb0007129

    Solis, F.J. and Wets, R.J.B., 1981.
    Minimization by random search techniques.
    Mathematics of Operations Research, 6(1), pp.19-30.
    https://pubsonline.informs.org/doi/abs/10.1287/moor.6.1.19

    Schrack, G. and Choit, M., 1976.
    Optimized relative step size random searches.
    Mathematical Programming, 10(1), pp.230-244.
    https://link.springer.com/article/10.1007/BF01580669

    Schumer, M.A. and Steiglitz, K., 1968.
    Adaptive step size random search.
    IEEE Transactions on Automatic Control, 13(3), pp.270-276.
    https://ieeexplore.ieee.org/abstract/document/1098903

    Matyas, J., 1965.
    `Random optimization.
    <https://tinyurl.com/yj398bs5>`_
    Automation and Remote control, 26(2), pp.246-253.

    Karnopp, D.C., 1963.
    Random search techniques for optimization problems.
    Automatica, 1(2-3), pp.111-121.
    https://www.sciencedirect.com/science/article/abs/pii/0005109863900189

    Rastrigin, L.A., 1963.
    The convergence of the random search method in the extremal control of a many parameter system.
    Automaton & Remote Control, 24, pp.1337-1342.
    https://tinyurl.com/djfdnpx4

    Brooks, S.H., 1958.
    A discussion of random methods for seeking maxima.
    Operations Research, 6(2), pp.244-251.
    https://pubsonline.informs.org/doi/abs/10.1287/opre.6.2.244

    Ashby, W.R., 1952.
    `Design for a brain: The origin of adaptive behaviour.
    <https://link.springer.com/book/10.1007/978-94-015-1320-3>`_
    Springer.
    """
    def __init__(self, problem, options):
        Optimizer.__init__(self, problem, options)
        self.x = options.get('x')  # initial (starting) point
        # reset its default value from 10 to 1000, since typically more iterations can be run
        # for individual-based iterative search
        self.verbose = options.get('verbose', 1000)
        self._n_generations = 0  # number of generations

    def initialize(self):
        raise NotImplementedError

    def iterate(self):  # for each iteration (generation)
        raise NotImplementedError

    def _print_verbose_info(self, fitness, y):
        if self.saving_fitness:
            if not np.isscalar(y):
                fitness.extend(y)
            else:
                fitness.append(y)
        if self.verbose and ((not self._n_generations % self.verbose) or (self.termination_signal > 0)):
            info = '  * Generation {:d}: best_so_far_y {:7.5e}, min(y) {:7.5e} & Evaluations {:d}'
            print(info.format(self._n_generations, self.best_so_far_y, np.min(y), self.n_function_evaluations))

    def _collect(self, fitness, y=None):
        if y is not None:
            self._print_verbose_info(fitness, y)
        results = Optimizer._collect(self, fitness)
        results['_n_generations'] = self._n_generations
        return results

    def optimize(self, fitness_function=None, args=None):  # for all iterations (generations)
        fitness = Optimizer.optimize(self, fitness_function)
        x = self.initialize()  # starting point
        y = self._evaluate_fitness(x, args)  # fitness of starting point
        while not self._check_terminations():
            self._print_verbose_info(fitness, y)
            x = self.iterate()  # to sample a new point
            y = self._evaluate_fitness(x, args)  # to evaluate the new point
            self._n_generations += 1
        return self._collect(fitness, y)