Skip to content

Pattern Search

Introduction

The pattern search works by initializing a cross-shaped collection of positions in the search space. Those positions expplore the search-space by moving the collection of positions as a whole towards optima or shrinking the cross.

Example

from gradient_free_optimizers import PatternSearch

...

opt = PatternSearch(search_space, n_positions=2)
opt.search(objective_function, n_iter=100)

About the implementation

Similar to the downhill simplex algorithm the pattern search has a list of positions and their scores to form the pattern. As the pattern moves through the search space this information gets updated.

At first all positions that form the cross are evaluated. After that the center of the cross moves to the best position. This leads to new positions inside the cross that have not been evaluated, yet. So the algorithm restarts evaluating all of the positions in the cross. If non of the positions have a better score than the center position the cross shrinks by the reduction-factor creating new positions inside the cross.

The pattern-search can be seen as a special case of the hill-climbing algorithm. The pattern-search will also try to move locally through the search-space by evaluating positions within its neighbourhood (the cross-shape), but it does so by choosing positions that each extend into different dimensions and equal distance to the center. The hill-climbing algorithm chooses the neighbour positions more randomly.

Parameters

n_positions

Number of positions that the pattern consists of. If the value of n_positions is large the algorithm will take a lot of time to choose the next position to move to, but the choice will probably be a good one. It might be a prudent approach to increase n_positions of the search-space has a lot of dimensions, because there are more possible directions to move to.

  • type: int
  • default: 4
  • typical range: 2 ... 8

pattern_size

The initial size of the patterns in percentage of the size of the search space in the corresponding dimension.

  • type: float
  • default: 0.25
  • typical range: 0.1 ... 0.5

reduction

The factor that reduces the size of the pattern if no better position is found.

  • type: float
  • default: 0.9
  • typical range: 0.75 ... 0.99