Source code for tno.quantum.optimization.qubo.solvers._classical._neighborhood_solver

"""This module contains the ``NeighborhoodSolver`` class.

The ``NeighborhoodSolver`` addresses QUBOs through a local neighborhood search.
"""

from __future__ import annotations

import numpy as np
from numpy.random import RandomState

from tno.quantum.optimization.qubo.components import QUBO, Solver
from tno.quantum.optimization.qubo.solvers._classical._iterative_result import (
    IterativeResult,
)
from tno.quantum.utils import BitVector, BitVectorLike
from tno.quantum.utils.validation import (
    check_int,
    check_random_state,
    check_string,
)


[docs]class NeighborhoodSolver(Solver[IterativeResult]): r"""Neighborhood solver. The :py:class:`NeighborhoodSolver` addresses QUBOs through a local neighborhood search algorithm. By default, it employs the ``local2_descent`` method, which performs two bit-flips per iteration. This approach often yields more optimal solutions compared to the ``local_descent`` method, which is limited to flipping one bit at a time. The ``local_descent`` method can get stuck in local minima more quickly because it explores fewer neighboring states per iteration, making it less effective at escaping suboptimal solutions. However, the advantage of the ``local_descent`` method is that it requires fewer computations and hence quicker to perform. However, in the current implementation both have a complexity of $\mathcal{O}(N^2)$, where $N$ is the size of the QUBO. Example: >>> from tno.quantum.optimization.qubo.components import QUBO >>> from tno.quantum.optimization.qubo.solvers import NeighborhoodSolver >>> >>> qubo = QUBO([[1, 2, 3], [4, -50, 6], [7, 8, 9]]) >>> solver = NeighborhoodSolver() >>> result = solver.solve(qubo) >>> result.best_bitvector BitVector(010) """
[docs] def __init__( self, random_state: int | RandomState | None = None, initial_bitvector: BitVectorLike | None = None, solver_type: str = "local2_descent", max_iterations: int = 1000, ) -> None: """Init :py:class:`NeighborhoodSolver`. Args: random_state: Random state for reproducibility. Defaults to ``None``. initial_bitvector: Initial bitvector. Defaults to ``None``. solver_type: Type of solver to use ('local_descent' or 'local2_descent'). Defaults to 'local2_descent'. max_iterations: Maximum number of iterations during local descent. Raises: ValueError: If `random_state` has invalid value, or if `max_iterations` is less than 1, or if `solver_type` is not a valid option. TypeError: If `max_iterations` is not an integer or `solver_type` is not a string. """ self.random_state = check_random_state(random_state, "random_state") self.initial_bitvector = initial_bitvector solver_type = check_string(solver_type, "solver_type") if solver_type not in ["local_descent", "local2_descent"]: error_msg = f"Unknown solver type: {solver_type}" raise ValueError(error_msg) self.solver_type = solver_type self.max_iterations = check_int(max_iterations, "max_iterations", l_bound=1)
def _solve_via_local_descent( self, qubo: QUBO, initial_bitvector: BitVector, max_iterations: int, ) -> IterativeResult: """Solve QUBO using local descent. Args: qubo: QUBO instance. initial_bitvector: Initial bitvector. max_iterations: Maximum number of iterations. Returns: Result of the optimization as a IterativeResult. """ x = initial_bitvector for _iteration in range(max_iterations): delta_x = qubo.delta_x(x) idx_minimal_change_in_energy = int(np.argmin(delta_x)) if delta_x[idx_minimal_change_in_energy] >= 0: break x.flip_indices(idx_minimal_change_in_energy, inplace=True) return IterativeResult.from_result(x, qubo.evaluate(x), _iteration) def _solve_via_local2_descent( self, qubo: QUBO, initial_bitvector: BitVector, max_iterations: int, ) -> IterativeResult: """Solve QUBO using local2 descent. Args: qubo: QUBO instance. initial_bitvector: Initial bitvector. max_iterations: Maximum number of iterations. Returns: Result of the optimization as a IterativeResult. """ x = initial_bitvector for _iteration in range(max_iterations): delta_x2 = qubo.delta_x2(x) i, j = map(int, np.unravel_index(np.argmin(delta_x2), delta_x2.shape)) if delta_x2[i, j] >= 0: break x.flip_indices(i, j, inplace=True) return IterativeResult.from_result(x, qubo.evaluate(x), _iteration) def _solve(self, qubo: QUBO) -> IterativeResult: """Use the neighborhood solver to solve the QUBO.""" if self.initial_bitvector is None: cutoff = 0.5 initial_bitvector = BitVector( (self.random_state.random(qubo.size) < cutoff).astype(int) ) else: initial_bitvector = BitVector(self.initial_bitvector) if self.solver_type == "local_descent": return self._solve_via_local_descent( qubo, initial_bitvector, self.max_iterations ) return self._solve_via_local2_descent( qubo, initial_bitvector, self.max_iterations )