pygsti.algorithms.grasp

Functions to facilitate using GRASP.

Module Contents

Functions

neighboring_weight_vectors(weights[, forced_weights, ...])	Return the list of weights in the neighborhood of a given weight vector.
run_grasp_iteration(elements, greedy_score_fn, rcl_fn, ...)	Perform one iteration of GRASP (greedy construction and local search).
run_grasp(elements, greedy_score_fn, rcl_fn, ...[, ...])	Perform GRASP to come up with an optimal feasible set of elements.

pygsti.algorithms.grasp.neighboring_weight_vectors(weights, forced_weights=None, shuffle=False)

Return the list of weights in the neighborhood of a given weight vector.

A weight vector is in the neighborhood of a given weight vector if it is only a single swap away from the given weight vector. There is an option to use forced_weights to indicate elements you don’t want to swap out.

Parameters

weightsnumpy.array

Binary vector to find the neighborhood of.

forced_weightsnumpy.array, optional

Binary vector indicating elements that must be included in all neighboring vectors (these elements are assumed to already be present in weights.

shufflebool, optional

Whether the neighborhood should be presented to the optimizer in a random order (important if the local optimizer updates the solution to the first better solution it finds in the neighborhood instead of exhaustively searching the neighborhood for the best solution).

Returns

list of numpy.array

List of binary vectors corresponding to all the neighbors of weights.

pygsti.algorithms.grasp.run_grasp_iteration(elements, greedy_score_fn, rcl_fn, local_score_fn, get_neighbors_fn, feasible_threshold=None, feasible_fn=None, initial_elements=None, rng=None, verbosity=0)

Perform one iteration of GRASP (greedy construction and local search).

Parameters

elementslist

A list containing some representation of the elements that can be used by the verious score functions.

greedy_score_fncallable

Function that takes a sublist of elements and returns a score to minimize that is comparable with other scores. Used by the greedy construction to construct the initial feasible subset.

rcl_fncallable

Function that takes a list of sublists of elements (that is, a list of candidate partial solutions) and returns the indices within that list of partial solutions to be included in the restricted candidate list.

local_score_fncallable

Function that takes a sublist of elements and returns a score to minimize that is comparable with other scores. Used by the local search to find a locally optimal feasible subset.

get_neighbors_fncallable

Function that takes a binary vector indicating which members of elements are included in the current solution and returns a list of binary vectors indicating which potential solutions are in the neighborhood of the current solution for the purposes of local optimization.

feasible_thresholdscore

A value comparable with the return value of the various score functions against which a score may be compared to test if the solution is feasible (the solution is feasible iff solnScore < feasible_threshold). Overrides feasible_fn if set to a value other than None.

feasible_fncallable

Function that takes a sublist of elements defining a potential solution and returns True if that solution is feasible (otherwise should return False). Not used if feasible_threshold is not None.

initial_elementsnumpy.array

Binary vector indicating whether the corresponding elements in elements should be automatically included by the greedy construction routine at the start of its construction.

rngrandom.Random

Optional random number generator to allow for determinism.

verbosityint

Sets the level of logging messages the printer will display.

Returns

initialSolnlist

The sublist of elements given by the greedy construction.

localSolnlist

The sublist of elements given by the local search.

pygsti.algorithms.grasp.run_grasp(elements, greedy_score_fn, rcl_fn, local_score_fn, get_neighbors_fn, final_score_fn, iterations, feasible_threshold=None, feasible_fn=None, initial_elements=None, seed=None, verbosity=0)

Perform GRASP to come up with an optimal feasible set of elements.

Parameters

elementslist

A list containing some representation of the elements that can be used by the verious score functions.

greedy_score_fncallable

Function that takes a sublist of elements and returns a score to minimize that is comparable with other scores. Used by the greedy construction to construct the initial feasible subset.

rcl_fncallable

Function that takes a list of sublists of elements (that is, a list of candidate partial solutions) and returns the indices within that list of partial solutions to be included in the restricted candidate list.

local_score_fncallable

Function that takes a sublist of elements and returns a score to minimize that is comparable with other scores. Used by the local search to find a locally optimal feasible subset.

get_neighbors_fncallable

Function that takes a binary vector indicating which members of elements are included in the current solution and returns a list of binary vectors indicating which potential solutions are in the neighborhood of the current solution for the purposes of local optimization.

final_score_fncallable

Function that takes a sublist of elements and returns a score to minimize that is comparable with other scores. Used to compare the solutions from various iterations in order to choose an optimum.

iterationsint

How many iterations of greedy construction followed by local search to perform.

feasible_thresholdscore

A value comparable with the return value of the various score functions against which a score may be compared to test if the solution is feasible (the solution is feasible iff solnScore < feasible_threshold). Overrides feasible_fn if set to a value other than None.

feasible_fncallable

Function that takes a sublist of elements defining a potential solution and returns True if that solution is feasible (otherwise should return False). Not used if feasible_threshold is not None.

initial_elementsnumpy.array

Binary vector with 1s at indices corresponding to elements in elements that the greedy construction routine will include at the start of its construction.

seedint

Seed for the random number generator.

verbosityint

Sets the level of logging messages the printer will display.

Returns

list of Circuits

The best germ set from all locally-optimal germ sets constructed.