pygsti.algorithms.grasp.run_grasp_iteration

pygsti.algorithms.grasp.run_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, rng=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 various 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.

  • rng (random.Random) – Optional random number generator to allow for determinism.

  • 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.