"""Hooke and Jeeves pattern search local search algorithm."""
import numpy as np
from pymoo.algorithms.base.local import LocalSearch
from pymoo.core.individual import Individual
from pymoo.core.population import Population
from pymoo.core.replacement import is_better
from pymoo.docs import parse_doc_string
from pymoo.operators.repair.to_bound import set_to_bounds_if_outside_by_problem
from pymoo.util.display.single import SingleObjectiveOutput
from pymoo.util.optimum import filter_optimum
from pymoo.util import default_random_state
# =========================================================================================================
# Implementation
# =========================================================================================================
[docs]
class PatternSearch(LocalSearch):
def __init__(
self,
init_delta=0.25,
init_rho=0.5,
step_size=1.0,
output=SingleObjectiveOutput(),
**kwargs,
):
"""Hooke and Jeeves Pattern Search local optimizer.
Args:
init_delta: Initial step size for exploration. Scaled relative to bounds.
init_rho: Contraction factor for step size reduction on unsuccessful moves.
step_size: Scaling factor for pattern moves along promising directions.
output: Output handler for convergence information.
**kwargs: Additional arguments passed to parent class.
"""
super().__init__(output=output, **kwargs)
self.init_rho = init_rho
self.init_delta = init_delta
self.step_size = step_size
self.n_not_improved = 0
self._rho = init_rho
self._delta = None
self._center = None
self._current = None
self._trial = None
self._direction = None
self._sign = None
def _initialize_advance(self, infills=None, **kwargs):
super()._initialize_advance(infills=infills, **kwargs)
self._center, self._explr = self.x0, self.x0
self._sign = np.ones(self.problem.n_var)
if self.problem.has_bounds():
xl, xu = self.problem.bounds()
self._delta = self.init_delta * (xu - xl)
else:
self._delta = np.abs(self.x0.X) / 2.0
self._delta[self._delta <= 1.0] = 1.0
def _next(self):
# whether the last iteration has resulted in a new optimum or not
has_improved = is_better(self._explr, self._center)
# that means that the exploration did not find any new point and was thus unsuccessful
if not has_improved:
# increase the counter (by default this will be initialized to 0 and directly increased to 1)
self.n_not_improved += 1
# keep track of the rho values in the normalized space
self._rho = self.init_rho**self.n_not_improved
# explore around the current center - try finding a suitable direction
self._explr = yield from exploration_move(
self.problem, self._center, self._sign, self._delta, self._rho
)
# if we have found a direction in the last iteration to be worth following
else:
# get the direction which was successful in the last move
self._direction = self._explr.X - self._center.X
# declare the exploration point the new center (it has led to an improvement in the last iteration!)
self._center = self._explr
# use the pattern move to get a new trial vector along that given direction
self._trial = yield pattern_move(
self.problem, self._center, self._direction, self.step_size
)
# get the delta sign adjusted for the exploration
self._sign = calc_sign(self._direction)
# explore around the current center to try finding a suitable direction
self._explr = yield from exploration_move(
self.problem, self._trial, self._sign, self._delta, self._rho
)
self.pop = Population.create(self._center, self._explr)
def _set_optimum(self):
pop = self.pop if self.opt is None else Population.merge(self.opt, self.pop)
self.opt = filter_optimum(pop, least_infeasible=True)
@default_random_state
def exploration_move(
problem, center, sign, delta, rho, randomize=True, random_state=None
):
n_var = problem.n_var
# the order for the variable iteration
if randomize:
K = random_state.permutation(n_var)
else:
K = np.arange(n_var)
# iterate over each variable
for k in K:
# the value to be tried first is given by the amount times the sign
_delta = sign[k] * rho * delta
# make a step of delta on the k-th variable
_explr = yield step_along_axis(problem, center.X, _delta, k)
if is_better(_explr, center, eps=0.0):
center = _explr
# if not successful try the other direction
else:
# now try the negative value of delta and see if we can improve
_explr = yield step_along_axis(problem, center.X, -1 * _delta, k)
if is_better(_explr, center, eps=0.0):
center = _explr
return center
def pattern_move(problem, current, direction, step_size):
# calculate the new X and repair out of bounds if necessary
X = current.X + step_size * direction
set_to_bounds_if_outside_by_problem(problem, X)
# create the new center individual
return Individual(X=X)
def calc_sign(direction):
sign = np.sign(direction)
sign[sign == 0] = -1
return sign
def step_along_axis(problem, x, delta, axis):
# copy and add delta to the new point
X = np.copy(x)
# now add to the current solution
X[axis] = X[axis] + delta[axis]
# repair if out of bounds if necessary
X = set_to_bounds_if_outside_by_problem(problem, X)
return Individual(X=X)
parse_doc_string(PatternSearch.__init__)
