core.post_process.local_search#
qamomile/core/post_process.py
This module provides functionality for Local Search Algorithm. Local Search Algorithm is one of the simplest heuristic algorithms for the optimization problem. You can apply the local search to the following Ising Hamiltonian.
\[\begin{split}\sum_{ij} J_{ij} z_i z_j + \sum_i h_i z_i, \\ \text{s.t.}~z_i \in \{-1, 1\}\end{split}\]
Key Features:
Implementation of first- and best-improvement local search algorithms
Construction of cost Hamiltonians for the Ising model
Conversion of Ising interactions from dictionary format to matrix form
Classes#
A class to represent the Ising model in matrix form. |
|
A class to perform local search algorithms on Ising models. |
Module Contents#
- class IsingMatrix(quad: numpy.ndarray | None = None, linear: numpy.ndarray | None = None)#
A class to represent the Ising model in matrix form.
- quad#
The interaction terms between spin variables in the Ising model.
- Type:
np.ndarray
- linear#
The external magnetic fields or self-interaction applied to each spin in the Ising model
- Type:
np.ndarray
- to_ising_matrix()#
Converts an Ising model into its corresponding matrix form.
- calc_E_diff()#
Calculates the change in energy if a specific bit is flipped.
Initializes an IsingMatrix instance.
- Parameters:
quad (Optional[np.ndarray]) – Quadratic term matrix representing the interaction term.
linear (Optional[np.ndarray]) – Linear term vector representing the self-interaction term.
- to_ising_matrix(ising: qamomile.core.ising_qubo.IsingModel) IsingMatrix#
Converts an IsingModel into matrix form with quadratic and linear components.
- Parameters:
ising (IsingModel) – The Ising model to be converted.
- Returns:
The converted Ising model in matrix form.
- Return type:
- calc_E_diff(state: numpy.ndarray, l: int) float#
Calculates the energy difference when flipping a bit in the Ising state.
- Parameters:
state (np.ndarray) – The current state of the Ising model.
l (int) – Index of the bit to be flipped.
- Returns:
The difference in energy due to flipping the specified bit.
- Return type:
float
- class LocalSearch(converter: qamomile.core.converters.converter.QuantumConverter)#
A class to perform local search algorithms on Ising models.
- converter#
The converter should be an implementation of the QuantumConverter abstract class, allowing the optimization problem to be encoded as an Ising model.
- Type:
- ising#
The encoded Ising model to be optimized.
- Type:
- decode()#
Decodes the final solution from Ising spin state to jijmodeling SampleSet.
- first_improvement()#
Performs first-improvement local search.
- best_improvement()#
Performs best-improvement local search.
- run()#
Runs the local search algorithm with a specified method.
Initializes a LocalSearch instance with a quantum converter.
- Parameters:
converter (QuantumConverter) – A converter used to encode optimization problems to Ising form.
- converter#
- ising#
- decode(result) jijmodeling.experimental.SampleSet#
Decodes the result obtained from a local search into a jijmodeling SampleSet.
- Parameters:
result (np.ndarray) – The final state of the Ising model after local search.
- Returns:
The decoded results.
- Return type:
jm.experimental.SampleSet
- first_improvement(ising_matrix: IsingMatrix, current_state: numpy.ndarray, N: int) numpy.ndarray#
Performs first-improvement local search on the Ising model.
The first-improvement local search method iteratively examines each bit in the current state of the Ising model to determine if flipping that bit will reduce the system’s energy. If a bit flip results in an energy decrease, the flip is accepted immediately, and the algorithm moves to the next bit. This process continues until all bits have been evaluated once.
- Parameters:
ising_matrix (IsingMatrix) – The Ising matrix representation of the problem.
current_state (np.ndarray) – The current state of the Ising model.
N (int) – Number of bits in the state.
- Returns:
The updated state after attempting to find an improving move.
- Return type:
np.ndarray
- best_improvement(ising_matrix: IsingMatrix, current_state: numpy.ndarray, N: int) numpy.ndarray#
Performs best-improvement local search on the Ising model.
The best-improvement local search method examines all possible bit flips in the current state of the Ising model to determine which single bit flip would result in the greatest decrease in energy. It then flips the bit that leads to the most significant energy reduction, provided there is at least one such improvement. If no flip results in a reduction in energy, the state remains unchanged.
- Parameters:
ising_matrix (IsingMatrix) – The Ising matrix representation of the problem.
current_state (np.ndarray) – The current state of the Ising model.
N (int) – Number of bits in the state.
- Returns:
The updated state after attempting to find the best improving move.
- Return type:
np.ndarray
- run(initial_state: numpy.ndarray, max_iter: int = -1, local_search_method: str = 'best_improvement') jijmodeling.experimental.SampleSet#
Runs the local search algorithm until convergence or until a maximum number of iterations.
- Parameters:
initial_state (np.ndarray) – The initial state to start the local search from.
max_iter (int) – Maximum number of iterations to run the local search. Defaults to -1 (no limit).
local_search_method (str) – Method of local search (“best_improvement” or “first_improvement”). Defaults to “best_improvement”.
- Returns:
The decoded solution after the local search.
- Return type:
jm.experimental.SampleSet