pyscat

PyScat Package

class pyscat.ESSExitFlag(*values)

Bases: int, Enum

Scatter search exit flags.

Exit flags used by ESSOptimizer and SacessOptimizer.

DID_NOT_RUN = 0

ESS did not run/finish yet

ERROR = -99

Termination because of other reasons than exit criteria

MAX_EVAL = -2

Exited after exhausting function evaluation budget

MAX_ITER = -1

Exited after reaching the maximum number of iterations

MAX_TIME = -3

Exited after exhausting wall-time budget

TOO_MANY_FAILURES = -4

class pyscat.ESSOptimizer(*, max_iter=None, dim_refset=None, local_n1=1, local_n2=10, balance=0.5, local_optimizer=None, max_eval=None, n_diverse=None, n_procs=None, n_threads=None, max_walltime_s=None, result_includes_refset=False, result_includes_local_solutions=True)

Bases: object

Enhanced Scatter Search (eSS) global optimization.

Scatter search is a meta-heuristic for global optimization. A set of points (the reference set, RefSet) is iteratively adapted to explore the parameter space and to follow promising directions.

This implementation is based on [1][2], but does not implement any constraint handling beyond box constraints.

The basic steps of ESS are:

• Initialization: Generate a diverse set of points (RefSet) in the parameter space.

• Recombination: Generate new points by recombining the RefSet points.

• Improvement: Improve the RefSet by replacing points with better ones.

The steps are repeated until a stopping criterion is met.

ESS is gradient-free, unless a gradient-based local optimizer is used (local_optimizer).

Variables:

history – History of the best values/parameters found so far. (Monotonically decreasing objective values.)

Parameters:

• max_iter (int)

• dim_refset (int)

• local_n1 (int)

• local_n2 (int)

• balance (float)

• local_optimizer (pypesto.optimize.Optimizer | OptimizerFactory | None)

• n_diverse (int)

• result_includes_refset (bool)

• result_includes_local_solutions (bool)

Hyperparameters

Various hyperparameters control the behavior of eSS. Initialization is controlled by dim_refset and n_diverse. Local optimizations are controlled by local_optimizer, local_n1, local_n2, and balance.

Exit criteria

The optimization stops if any of the following criteria are met:

• The maximum number of iterations is reached (max_iter).

• The maximum number of objective function evaluations is reached (max_eval).

• The maximum wall-time is reached (max_walltime_s).

One of these criteria needs to be provided. Note that the wall-time and function evaluation criteria are not checked after every single function evaluation, and thus, the actual number of function evaluations may slightly exceed the given value.

Parallelization

Objective function evaluations inside ESSOptimizer can be parallelized using multiprocessing or multithreading by passing a value >1 for n_procs or n_threads, respectively.

See also

SacessOptimizer

[1]

Jose A. Egea, Eva Balsa-Canto, María-Sonia G. García, and Julio R. Banga. Dynamic optimization of nonlinear processes with an enhanced scatter search method. Industrial & Engineering Chemistry Research, 48(9):4388–4401, April 2009. doi:10.1021/ie801717t.

[2]

Jose A. Egea, Rafael Martí, and Julio R. Banga. An evolutionary method for complex-process optimization. Computers & Operations Research, 37(2):315–324, 2010. URL: https://www.sciencedirect.com/science/article/pii/S0305054809001440, doi:10.1016/j.cor.2009.05.003.

__init__(*, max_iter=None, dim_refset=None, local_n1=1, local_n2=10, balance=0.5, local_optimizer=None, max_eval=None, n_diverse=None, n_procs=None, n_threads=None, max_walltime_s=None, result_includes_refset=False, result_includes_local_solutions=True)

Initialize.

For plausible values of hyperparameters, see Villaverde et al.[3].

Parameters:

• dim_refset (int) – Size of the RefSet. Note that in every iteration at least dim_refset**2 - dim_refset function evaluations will occur.

• max_iter (int) – Maximum number of eSS iterations.

• local_n1 (int) – Minimum number of iterations before first local search. Ignored if local_optimizer=None.

• local_n2 (int) – Minimum number of iterations between consecutive local searches. Maximally one local search per performed in each iteration. Ignored if local_optimizer=None.

• local_optimizer (Optimizer | OptimizerFactory | None) – Local optimizer for refinement, or a callable that creates an pypesto.optimize.Optimizer or None to skip local searches. In case of a callable, it will be called with the keyword arguments max_walltime_s and max_eval, which should be passed to the optimizer (if supported) to honor the overall budget. See SacessFidesFactory for an example.

• n_diverse (int) – Number of samples to choose from to construct the initial RefSet

• max_eval – Maximum number of objective functions allowed. This criterion is only checked once per iteration, not after every objective evaluation, so the actual number of function evaluations may exceed this value.

• max_walltime_s – Maximum walltime in seconds. Will only be checked between local optimizations and other simulations, and thus, may be exceeded by the duration of a local search.

• balance (float) – Quality vs. diversity balancing factor with \(0 \leq balance \leq 1\); 0 = only quality, 1 = only diversity. Affects the choice of starting points for local searches. I.e., whether local optimization should focus on improving the best solutions found so far (quality), or on exploring new regions of the parameter space (diversity). Ignored if local_optimizer=None.

• n_procs – Number of parallel processes to use for parallel function evaluation. Mutually exclusive with n_threads.

• n_threads – Number of parallel threads to use for parallel function evaluation. Mutually exclusive with n_procs.

• result_includes_refset (bool) – Whether the minimize() result should include the final RefSet.

• result_includes_local_solutions (bool) – Whether the minimize() result should include the local search results (if any).

balance: float

dim_refset: int

history: HistoryBase | None

local_n1: int

local_n2: int

local_only_best_sol: bool

max_eval: int

max_iter: int

minimize(problem=None, refset=None, history=None)

Minimize the given objective.

Parameters:

• problem (Problem) – Problem to run ESS on.

• refset (RefSet | None) – The initial RefSet or None to auto-generate.

• history (HistoryBase | None) – History object to track the best values found so far.

Return type:

Result

Returns:

The optimization result. Contains the overall best value found and, depending on the settings, the final RefSet and local search results.

Note that the number of gradient and Hessian evaluations is not tracked and thus set to 0 in the result, even if a local optimizer is used that performs gradient/Hessian evaluations.

n_change: int

n_diverse: int

n_procs: int | None

n_threads: int | None

static prioritize_local_search_candidates(x_best_children, fx_best_children, local_solutions, balance)

Compute an index order for local-search start points that balances solution quality and diversity.

The priority combines a quality ranking (better objective values are preferred) and a diversity ranking (candidates further from known local optima are preferred). The final priority is a weighted combination of the two ranks.

See [PenasGon2017] Algorithm 2 L12-L18.

Parameters:

• x_best_children (ndarray) – Array of candidate parameter vectors with shape (n_candidates, problem_dim).

• fx_best_children (ndarray) – Array of objective values for the candidates with shape (n_candidates,).

• local_solutions (Sequence[OptimizerResult]) – Sequence of existing local ``OptimizerResult``s used to compute distances for diversity. May be empty.

• balance (float) – Balancing factor in [0, 1]. 0 -> prioritize quality only, 1 -> prioritize diversity only.

Return type:

ndarray

Returns:

Array of indices into the candidate arrays ordered by decreasing priority (i.e., first index = highest priority).

class pyscat.EvalLogger(selector=None, _shared_evals=None, _shared_lock=None)

Bases: object

Log function evaluations.

This is experimental and is likely to change in future releases.

Parameters:

• selector (EvalSelectorBase)

• _shared_evals (ListProxy)

• _shared_lock (threading.Lock)

__init__(selector=None, _shared_evals=None, _shared_lock=None)

Initialize.

Parameters:

• selector (EvalSelectorBase) – Optional selector / handler for evaluations. See TopKSelector and ThresholdSelector. If not provided, all objective evaluations will be kept in memory.

• _shared_evals (ListProxy)

• _shared_lock (lock)

attach(problem)

Context manager to attach the EvalLogger to an Objective.

Parameters:

problem (Problem) – The problem that contains the objective whose evaluations are to be logged.

property evals: list

log(x, fx)

Log an evaluation.

Parameters:

• x (ndarray) – Parameter vector

• fx (float) – Function value

Return type:

None

class pyscat.SacessCmaFactory(options=None)

Bases: object

Factory for CmaOptimizer instances for use with SacessOptimizer.

__call__() will forward the walltime limit and function evaluation limit imposed on SacessOptimizer to CmaOptimizer. Besides that, default options are used.

Parameters:

options (dict[str, Any] | None) – Options as passed to CmaOptimizer.__init__(). See cma.CMAOptions() for available options.

__init__(options=None)

Parameters:

options (dict[str, Any] | None)

class pyscat.SacessFidesFactory(fides_options=None, fides_kwargs=None)

Bases: object

Factory for FidesOptimizer instances for use with SacessOptimizer.

__call__() will forward the walltime limit and function evaluation limit imposed on SacessOptimizer to FidesOptimizer. Besides that, default options are used.

Parameters:

• fides_options (dict[str, Any] | None) – Options for the FidesOptimizer. See fides.constants.Options.

• fides_kwargs (dict[str, Any] | None) – Keyword arguments for the FidesOptimizer. See FidesOptimizer.__init__(). Must not include options.

__init__(fides_options=None, fides_kwargs=None)

Parameters:

• fides_options (dict[str, Any] | None)

• fides_kwargs (dict[str, Any] | None)

class pyscat.SacessIpoptFactory(ipopt_options=None)

Bases: object

Factory for IpoptOptimizer instances for use with SacessOptimizer.

__call__() will forward the walltime limit and function evaluation limit imposed on SacessOptimizer to IpoptOptimizer. Besides that, default options are used.

Parameters:

ipopt_options (dict[str, Any] | None) – Options for the IpoptOptimizer. See https://coin-or.github.io/Ipopt/OPTIONS.html.

__init__(ipopt_options=None)

Parameters:

ipopt_options (dict[str, Any] | None)

class pyscat.SacessOptimizer(problem, num_workers=None, ess_init_args=None, max_walltime_s=inf, sacess_loglevel=20, ess_loglevel=30, mp_start_method='spawn', options=None, autosave_dir=None)

Bases: object

SACESS optimizer.

A shared-memory-based implementation of the Self-Adaptive Cooperative Enhanced Scatter Search (SaCeSS) algorithm presented in Penas et al.[4]. This is a meta-heuristic for global optimization. Multiple processes (workers) run enhanced scatter searches (eSSs) in parallel. After each ESS iteration, depending on the outcome, there is a chance of exchanging good parameters, and changing eSS hyperparameters to those of the most promising worker. See Penas et al.[4] for details.

SacessOptimizer can be used with or without a local optimizer, but it is highly recommended to use one.

Variables:

histories – List of the histories of the best values/parameters found by each worker. (Monotonically decreasing objective values.) See pyscat.plot.plot_sacess_history() for visualization.

Parameters:

• problem (Problem)

• num_workers (int | None)

• ess_init_args (list[dict[str, Any]] | None)

• max_walltime_s (float)

• sacess_loglevel (int)

• ess_loglevel (int)

• mp_start_method (str)

• options (SacessOptions)

• autosave_dir (Path | str)

A basic example using SacessOptimizer to minimize the Rosenbrock function:

>>> from pyscat import SacessOptimizer
>>> from pypesto import Problem, Objective
>>> import scipy as sp
>>> import numpy as np
>>> import logging
>>> # Define some test Problem
>>> objective = Objective(
...     fun=sp.optimize.rosen,
...     grad=sp.optimize.rosen_der,
...     hess=sp.optimize.rosen_hess,
... )
>>> dim = 6
>>> problem = Problem(
...     objective=objective,
...     lb=-5 * np.ones((dim, 1)),
...     ub=5 * np.ones((dim, 1)),
... )
>>> # Create and run the optimizer
>>> sacess = SacessOptimizer(
...     problem=problem,
...     num_workers=2,
...     max_walltime_s=5,
...     sacess_loglevel=logging.WARNING
... )
>>> result = sacess.minimize()

See also

ESSOptimizer

References

[3]

Alejandro F Villaverde, Jose A Egea, and Julio R Banga. A cooperative strategy for parameter estimation in large scale systems biology models. BMC Systems Biology, June 2012. doi:10.1186/1752-0509-6-75.

[4] (1,2)

David R. Penas, Patricia González, Jose A. Egea, Ramón Doallo, and Julio R. Banga. Parameter estimation in large-scale systems biology models: a parallel and self-adaptive cooperative strategy. BMC Bioinformatics, January 2017. doi:10.1186/s12859-016-1452-4.

__init__(problem, num_workers=None, ess_init_args=None, max_walltime_s=inf, sacess_loglevel=20, ess_loglevel=30, mp_start_method='spawn', options=None, autosave_dir=None)

Construct.

Parameters:

• problem (Problem) – The minimization problem. Problem.startpoint_method() will be used to sample random points. SacessOptimizer will deal with non-evaluable points. Therefore, using pypesto.startpoint.CheckedStartpoints with check_fval=True or check_grad=True is not recommended since it would create significant overhead.

• num_workers (int | None) – Number of workers to be used. A minimum of 2 workers is required. If this argument is given, (different) default eSS settings will be used for each worker. Mutually exclusive with ess_init_args. See get_default_ess_options() for details on the default settings. Currently, if problem.objective supports gradients, the default local optimizer is FidesOptimizer. Otherwise, no local optimizer is used by default. This may be changed in future releases.

• ess_init_args (list[dict[str, Any]] | None) –

  List of argument dictionaries passed to ESSOptimizer.__init__(). Each entry corresponds to one worker process. I.e., the length of this list is the number of eSSs. Mutually exclusive with num_workers. If not provided, default settings will be used, see get_default_ess_options().

  Ideally, this list contains some more conservative and some more aggressive configurations. Resource limits such as max_eval apply to a single eSS iteration, not to the full search. Mutually exclusive with num_workers.

• max_walltime_s (float) – Maximum walltime in seconds. It will only be checked between local optimizations and other simulations, and thus, may be exceeded by the duration of a local search. Defaults to no limit. Note that in order to impose the wall time limit also on the local optimizer, the user has to provide a wrapper function similar to SacessFidesFactory.__call__().

• ess_loglevel (int) – Loglevel for ESS runs.

• sacess_loglevel (int) – Loglevel for SACESS runs.

• autosave_dir (Path | str) – Directory for storing intermediate results. If not None, HDF5 files with intermediate results will be saved in this directory during the optimization. This can be used to monitor the optimization while it is running, or to recover results if the optimization was interrupted. When setting this option, make sure any optimizers running in parallel have a unique tmpdir. The directory is expected to be empty.

• mp_start_method (str) – The start method for the multiprocessing context. See multiprocessing for details. Running SacessOptimizer under Jupyter may require mp_start_method="fork".

• options (SacessOptions) – Further optimizer hyperparameters, see SacessOptions.

static get_autosave_path(base_dir, worker_idx)

Get the path of the autosave file for the given worker.

Return type:

Path | None

Parameters:

• base_dir (Path)

• worker_idx (int)

minimize()

Minimize the given problem.

Note that if this function is called from a multithreaded program (multiple threads running at the time of calling this function) and the multiprocessing start method is set to fork, there is a good chance for deadlocks. Postpone spawning threads until after minimize or change the start method to spawn.

Return type:

Result

Returns:

Result object with optimized parameters in pypesto.Result.optimize_result.

Only the best solution found is returned. To get the per-worker histories of the best values/parameters found, use the histories attribute.

Note that the number of gradient and Hessian evaluations is not tracked and thus set to 0 in the result, even if a local optimizer is used that performs gradient/Hessian evaluations.

property n_eval_total: int

Get the total number of objective evaluations.

Only available after minimize() has been called and finished.

set_local_optimizer(local_optimizer)

Set a local solver for all workers.

Parameters:

local_optimizer (None | Optimizer | Callable[..., Optimizer]) –

The local optimizer to use (see same argument in ESSOptimizer): a Optimizer instance, a Callable returning an optimizer instance, or None to disable local searches.

The callable can be used to propagate walltime limits to the local optimizers. See SacessFidesFactory.__call__() for an example.

class pyscat.SacessOptions(manager_initial_rejection_threshold=0.001, manager_minimum_rejection_threshold=0.001, worker_acceptance_threshold=0.0001, adaptation_min_evals=5000, adaptation_sent_offset=20, adaptation_sent_coeff=10)

Bases: object

Container for SacessOptimizer hyperparameters.

Parameters:

• manager_initial_rejection_threshold (float)

• manager_minimum_rejection_threshold (float) – Initial and minimum threshold for relative objective improvements that incoming solutions have to pass to be accepted. If the number of rejected solutions exceeds the number of workers, the threshold is halved until it reaches manager_minimum_rejection_threshold.

• worker_acceptance_threshold (float) – Minimum relative improvement of the objective compared to the best known value to be eligible for submission to the Manager.

• adaptation_min_evals (int)

• adaptation_sent_offset (int)

• adaptation_sent_coeff (int) –

  Hyperparameters that control when the workers will adapt their settings based on the performance of the other workers.

  The adaptation step is performed if all the following conditions are met:

  • The number of function evaluations since the last solution was sent to the manager times the number of optimization parameters is greater than adaptation_min_evals.

  • The number of solutions received by the worker since the last solution it sent to the manager is greater than adaptation_sent_coeff * n_sent_solutions + adaptation_sent_offset, where n_sent_solutions is the number of solutions sent to the manager by the given worker.

__init__(manager_initial_rejection_threshold=0.001, manager_minimum_rejection_threshold=0.001, worker_acceptance_threshold=0.0001, adaptation_min_evals=5000, adaptation_sent_offset=20, adaptation_sent_coeff=10)

Parameters:

• manager_initial_rejection_threshold (float)

• manager_minimum_rejection_threshold (float)

• worker_acceptance_threshold (float)

• adaptation_min_evals (int)

• adaptation_sent_offset (int)

• adaptation_sent_coeff (int)

Return type:

None

adaptation_min_evals: int = 5000

adaptation_sent_coeff: int = 10

adaptation_sent_offset: int = 20

manager_initial_rejection_threshold: float = 0.001

manager_minimum_rejection_threshold: float = 0.001

worker_acceptance_threshold: float = 0.0001

class pyscat.ThresholdSelector(*, dim, mode, threshold, path=None, dtype=<class 'float'>, _k=100, _chunk_size=64)

Bases: EvalSelectorBase

Maintain all unique parameter vectors below a certain threshold based on the best function value seen so far.

Parameters:

• dim (int)

• mode (str)

• threshold (float)

• path (Path | str | None)

• _k (int)

• _chunk_size (int)

__init__(*, dim, mode, threshold, path=None, dtype=<class 'float'>, _k=100, _chunk_size=64)

Initialize.

Parameters:

• dim (int) – Problem dimension (length of parameter vector).

• path (Path | str | None) – Optional filesystem path for snapshots.

• threshold (float) – Threshold for accepting new entries. Interpreted according to mode.

• mode (str) – ‘abs’ or ‘rel’ mode for thresholding. If ‘abs’, new entries are accepted if fx - best_fx <= threshold. If ‘rel’, new entries are accepted if |(fx - best_fx) / best_fx | <= threshold.

• dtype – Numpy dtype used for internal numeric storage.

• _k (int) – Initial capacity.

• _chunk_size (int) – Minimum grow chunk size.

process(x, fx)

Process an objective evaluation.

Add (x, fx) if it meets the threshold and is not a duplicate.

Return type:

None

Parameters:

• x (Sequence[float])

• fx (float)

save()

Save the stored entries as numpy .npz file.

snapshot()

Create a snapshot of the stored entries.

to_ensemble()

Create a pypesto.Ensemble from the stored entries.

Return type:

Ensemble

class pyscat.TopKSelector(*, k, dim, path=None, dtype=<class 'float'>)

Bases: EvalSelectorBase

Maintain the K-best unique parameter vectors seen so far.

Parameters:

• k (int)

• dim (int)

• path (Path | str | None)

__init__(*, k, dim, path=None, dtype=<class 'float'>)

Initialize.

Parameters:

• k (int) – The number of best entries to keep. (Best means lowest function value.)

• dim (int) – Problem dimension (length of parameter vector).

• path (Path | str | None) – Optional filesystem path used by subclasses.

• dtype – Numpy dtype used for internal numeric storage.

process(x, fx)

Process an objective evaluation.

Add (x, fx) to top-K if x is not already stored.

Return type:

None

Parameters:

• x (Sequence[float])

• fx (float)

save()

Save the stored entries as numpy .npz file.

snapshot()

Create a snapshot of the stored entries.

Return type:

dict[str, ndarray]

to_ensemble()

Create a pypesto.Ensemble from the stored entries.

Return type:

Ensemble

pyscat.get_default_ess_options(num_workers, dim, local_optimizer=True)

Get default ESS settings for (SA)CESS.

Returns settings for num_workers parallel scatter searches, combining more aggressive and more conservative configurations. Mainly intended for use with SacessOptimizer. For details on the different options, see keyword arguments of ESSOptimizer.__init__().

Setting appropriate values for n_threads and local_optimizer is left to the user. Defaults to single-threaded and no local optimizer.

Based on https://bitbucket.org/DavidPenas/sacess-library/src/508e7ac15579104731cf1f8c3969960c6e72b872/src/method_module_fortran/eSS/parallelscattersearchfunctions.f90#lines-929

Parameters:

• num_workers (int) – Number of configurations to return.

• dim (int) – Problem dimension (number of optimized parameters).

• local_optimizer (bool | Optimizer | Callable[..., Optimizer]) – The local optimizer to use (see same argument in ESSOptimizer), a boolean indicating whether to set the default local optimizer (currently FidesOptimizer), a Optimizer instance, or a Callable returning an optimizer instance. The latter can be used to propagate walltime limits to the local optimizers. See SacessFidesFactory.__call__() for an example. The current default optimizer assumes that the optimized objective function can provide its gradient. If this is not the case, the user should provide a different local optimizer or consider using pypesto.objective.finite_difference.FD to approximate the gradient using finite differences.

Return type:

list[dict]

Examples

To get default ESS settings for running SacessOptimizer without a local optimizer, use:

>>> from pypesto.optimize.ess import get_default_ess_options
>>> ess_init_args = get_default_ess_options(
...     num_workers=12,
...     dim=10, # usually problem.dim
...     local_optimizer=False,
... )
>>> ess_init_args
[{'dim_refset': 5, 'balance': 0.0, 'local_n1': 1, 'local_n2': 1},
...
 {'dim_refset': 7, 'balance': 1.0, 'local_n1': 4, 'local_n2': 4}]