pygsti.algorithms.grasp

Functions to facilitate using GRASP.

Module Contents

Functions

neighboring_weight_vectors(weights, forced_weights=None, shuffle=False)

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

_grasp_construct_feasible_solution(elements, score_fn, rcl_fn, feasible_threshold=None, feasible_fn=None, initial_elements=None)

Constructs a subset of elements that represents a feasible solution.

_grasp_local_search(initial_solution, score_fn, elements, get_neighbors_fn, feasible_threshold=None, feasible_fn=None)

Perfom the local-search part of a grasp iteration.

run_grasp_iteration(elements, greedy_score_fn, rcl_fn, local_score_fn, get_neighbors_fn, feasible_threshold=None, feasible_fn=None, initial_elements=None, seed=None, verbosity=0)

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

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.

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
  • weights (numpy.array) – Binary vector to find the neighborhood of.

  • forced_weights (numpy.array, optional) – Binary vector indicating elements that must be included in all neighboring vectors (these elements are assumed to already be present in weights.

  • shuffle (bool, 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._grasp_construct_feasible_solution(elements, score_fn, rcl_fn, feasible_threshold=None, feasible_fn=None, initial_elements=None)

Constructs a subset of elements that represents a feasible solution.

This function performs the “greedy-construction” part of a grasp iteration (see run_grasp_iteration()). The returned solution subset is built up by repeating the following step until a feasible solution (using feasible_threshold OR feasible_fn):

  1. Build a candidate list from elements that haven’t been chosen.

  2. Based on the scores of the candidates (using score_fn), construct a “reduced candidate list” (using rcl_fn) that need not (but could) be just the single best-scoring element.

  3. Choose a random element from the reduced candidate list and add it to the solution subset.

Parameters
  • elements (list) – A list containing some representation of the elements that can be used by the verious score functions.

  • score_fn (callable) – Function that takes a sublist of elements and returns a score to minimize that is comparable with other scores.

  • rcl_fn (callable) – 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.

  • feasible_threshold (score) – 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_fn (callable) – 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_elements (numpy.array) – Binary vector indicating whether the corresponding elements in elements should be automatically included at the start of this construction.

Returns

list – A sub-list of elements.

Perfom the local-search part of a grasp iteration.

Attempts to find a better (lower-scoring) solution based on successive “local” (as determined by get_neighbors_fn) steps from initialSolution.

Parameters
  • initial_solution (list) – A list of some (or all) of the items in elements, representing an initial solution. This solution must be “feasbile” as determined by feasible_threshold or feasible_fn.

  • score_fn (callable) – 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.

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

  • get_neighbors_fn (callable) – 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_threshold (score) – 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_fn (callable) – 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.

Returns

list – A sub-list of elements, representing the locally-improved solution.

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, seed=None, verbosity=0)

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

Parameters
  • elements (list) – A list containing some representation of the elements that can be used by the verious score functions.

  • greedy_score_fn (callable) – 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_fn (callable) – 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_fn (callable) – 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_fn (callable) – 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_threshold (score) – 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_fn (callable) – 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_elements (numpy.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.

  • seed (int) – Seed for the random number generator.

  • verbosity (int) – Sets the level of logging messages the printer will display.

Returns

  • initialSoln (list) – The sublist of elements given by the greedy construction.

  • localSoln (list) – 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
  • elements (list) – A list containing some representation of the elements that can be used by the verious score functions.

  • greedy_score_fn (callable) – 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_fn (callable) – 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_fn (callable) – 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_fn (callable) – 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_fn (callable) – 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.

  • iterations (int) – How many iterations of greedy construction followed by local search to perform.

  • feasible_threshold (score) – 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_fn (callable) – 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_elements (numpy.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.

  • seed (int) – Seed for the random number generator.

  • verbosity (int) – 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.