pattern — Pattern Search Algorithms

This module contains pattern search algorithms.

class dfoalgos.pattern.PatternSearch(problem, start_point, step_size, shrink_factor=0.5, pattern=None, opportunistic=True, max_iterations=inf, xtol=None, ftol=None, individual_factory=None, sort_key=None, verbosity=1, **kwargs)

A synchronous implementation of pattern search.

This implementation uses a double-ended queue (collections.deque) to store the pattern. In case of opportunistic behavior (accepting the first improvement), the elements in the deque are cycled so that the successful direction is at the front of the pattern, and thus is the first tried direction in the next iteration. The original order of directions is always retained.

__init__(problem, start_point, step_size, shrink_factor=0.5, pattern=None, opportunistic=True, max_iterations=inf, xtol=None, ftol=None, individual_factory=None, sort_key=None, verbosity=1, **kwargs)

Constructor.

Parameters:
  • problem (optproblems.Problem) – An optimization problem.
  • start_point (list) – The starting point for the optimization.
  • step_size (float) – The initial step size.
  • shrink_factor (float, optional) – This value must be larger than 0 and smaller than 1. It is multiplied with the step size in iterations where no improvement is found.
  • pattern (sequence, optional) – A sequence of direction vectors. To guarantee convergence to a stationary point, this must be a positive basis of the real coordinate space. By default, a maximal positive basis is generated. The provided sequence is not modified. Its elements are copied into another container.
  • opportunistic (bool, optional) – If True (default), the first improvement is accepted and the execution jumps to the next iteration. Additionally, the successful direction is cycled to the first position in the pattern. If False, the whole pattern is evaluated in every iteration (“best improvement”).
  • max_iterations (int, optional) – A potential budget restriction on the number of iterations. Default is unlimited.
  • xtol (float, optional) – The algorithm stops when the maximal absolute deviation in all dimensions of the search space between the best and the last len(pattern) evaluated solutions drops below this value. By default, this criterion is off.
  • ftol (float, optional) – The algorithm stops when the absolute difference of objective values between the best individual and the worst of the last len(pattern) evaluated solutions drops below this value. This criterion can only be used with scalar objective values. By default, this criterion is off.
  • individual_factory (callable, optional) – A callable taking a point as argument. It must return an object with two member attributes phenome and objective_values. The phenome contains the solution, while objective_values is set to None. By default, optproblems.base.Individual is used.
  • sort_key (callable, optional) – A sort key for ranking the individuals. By default, dfoalgos.base.lexicographic_sort_key() is used.
  • verbosity (int, optional) – A value of 0 means quiet, 1 means some information is printed to standard out on start and termination of this algorithm.
__str__()

Return the algorithm’s name.

classmethod minimize(fun, x0, args=(), bounds=None, callback=None, options=None, **kwargs)

Minimization of scalar function of one or more variables.

This function mimics the SciPy interface for optimizers.

Parameters:
  • fun (callable) – Objective function.
  • x0 (sequence) – Initial guess.
  • args (tuple, optional) – Extra arguments passed to the objective function.
  • bounds (sequence, optional) – Bounds for variables. (min, max) pairs for each element in x, defining the bounds on that parameter. Use None for one of min or max when there is no bound in that direction.
  • callback (callable, optional) – Called after each iteration, as callback(xk), where xk is the current parameter vector.
  • options (dict, optional) –

    A dictionary of solver options. The following generic options are accepted:

    maxiter : int
    Maximum number of iterations to perform.
    disp : bool
    Set to True to print convergence messages.
Returns:

result – The optimization result represented as a OptimizeResult object. Important attributes are: x the solution array, success a Boolean flag indicating if the optimizer exited successfully and message which describes the cause of the termination.
Return type:

OptimizeResult
run()

Run the algorithm.

The step function is called in a loop. The algorithm stops when a StopIteration exception is caught or when the stopping criterion evaluates to True.

Returns:best_individual – The best individual found so far, according to the sort key.
Return type:Individual
step()

Perform one optimization step.

Raises:Stalled – when none of the generated points differ from the current best or previous best solution
stopping_criterion()

Check if optimization should go on.

The algorithm halts when this method returns True or raises an exception.

Raises:
  • ResourcesExhausted – when number of iterations reaches maximum
  • Stalled – when the xtol or ftol criteria trigger
update_best_individual(new_best)

Set a new current best individual.

Before the current best is overwritten, it is saved in the attribute previous_best_individual. The success is also marked by setting improvement_found to True.

update_pattern_and_step_size()

Reduce the step size by multiplying with shrink_factor.