SAGA¶
The SAGA algorithm uses the paradigm of Genetic Algorithms: We keep track of a population of possible solutions to an optimization/decision problem in the QUBO formulation, and iteratively create new solutions from these using mutations and recombinations. A selection ensures we only keep track of the most promising solutions in the population for the next iteration, where these again are used to create new solutions. This process is run until a predefined stopping criterion is reached, which might be a desired solution quality (i.e., an energy level) or a boundary on the time / iterations the algorithm is allowed to run. At the end, the best found solution vector and its corresponding solution value is returned. For SAGA, Simulated Annealing is used during the mutation phase.
Note
This solver is only available for commercial and academic licenses.
Compatible Backends¶
The SAGA algorithm supports the following backends:
By default, SAGA uses the DWave backend.
Initialization¶
The following section outlines the default configurations of SAGA. You can also specify other compatible backends for the algorithm. When backend=None is specified, the default backend will be initialized automatically. In this case, if the backend requires a token, it will be taken from the environment variables.
from luna_quantum.solve.parameters.algorithms import SAGA
algorithm = SAGA(
backend=None,
p_size=20,
p_inc_num=5,
p_max=160,
pct_random_states=0.25,
mut_rate=0.5,
rec_rate=1,
rec_method='random_crossover',
select_method='simple',
target=None,
atol=1e-08,
rtol=1e-05,
timeout=60.0,
max_iter=100,
num_sweeps=10,
num_sweeps_inc_factor=1.2,
num_sweeps_inc_max=7000,
beta_range_type='default',
beta_range=None
)
Parameter Details
For a complete overview of available parameters and their usage, see the SAGA API Reference.
Usage¶
from luna_quantum import LunaSolve
LunaSolve.authenticate("<YOUR_LUNA_API_KEY>")
# Define your model and algorithm
model = ...
algorithm = ...
solve_job = algorithm.run(model, name="my-solve-job")
API Reference¶
Bases: LunaAlgorithm[DWave]
Simulated Annealing Genetic Algorithm (SAGA).
SAGA combines genetic algorithms with simulated annealing to enhance optimization. While QAGA uses quantum annealing, SAGA uses classical simulated annealing for the mutation and recombination operations, making it more accessible while still providing benefits over standard genetic algorithms.
The algorithm maintains a population of solutions that evolve through selection, annealing-enhanced recombination, and mutation operations across generations.
Attributes:
| Name | Type | Description |
|---|---|---|
p_size |
int
|
Initial population size (number of candidate solutions). Default is 20. |
p_inc_num |
int
|
Number of new individuals added to the population after each generation. Default is 5. |
p_max |
int | None
|
Maximum population size. Once reached, no more growth occurs. Default is 160. |
pct_random_states |
float
|
Percentage of random states added to the population after each iteration. Default is 0.25 (25%). |
mut_rate |
float
|
Mutation rate - probability to mutate an individual after each iteration. Default is 0.5. Must be between 0.0 and 1.0. |
rec_rate |
int
|
Recombination rate - number of mates each individual is recombined with per generation. Default is 1. |
rec_method |
Literal['cluster_moves', 'one_point_crossover', 'random_crossover']
|
Method used for recombining individuals. Default is "random_crossover". |
select_method |
Literal['simple', 'shared_energy']
|
Selection strategy for the next generation. Default is "simple". |
target |
Union[float, None]
|
Target energy level to stop the algorithm. Default is None. |
atol |
float
|
Absolute tolerance when comparing energies to target. Default is DEFAULT_ATOL. |
rtol |
float
|
Relative tolerance when comparing energies to target. Default is DEFAULT_RTOL. |
timeout |
float
|
Maximum runtime in seconds. Default is 60.0 seconds. |
max_iter |
int | None
|
Maximum number of generations before stopping. Default is 100. |
num_sweeps |
int
|
Initial number of sweeps for simulated annealing in the first iteration. Default is 10. |
num_sweeps_inc_factor |
float
|
Factor by which to increase num_sweeps after each iteration. Default is 1.2 (20% increase per iteration). |
num_sweeps_inc_max |
Optional[int]
|
Maximum number of sweeps that may be reached when increasing the num_sweeps. Default is 7,000. |
beta_range_type |
Literal['default', 'percent', 'fixed', 'inc']
|
Method used to compute the temperature range (beta range) for annealing. Default is "default". |
beta_range |
Optional[Tuple[float, float]]
|
Explicit beta range (inverse temperature) used with beta_range_type "fixed" or "percent". Default is None. |
backend
class-attribute
instance-attribute
¶
beta_range_type
class-attribute
instance-attribute
¶
model_config
class-attribute
instance-attribute
¶
rec_method
class-attribute
instance-attribute
¶
rec_method: Literal[
"cluster_moves", "one_point_crossover", "random_crossover"
] = "random_crossover"
select_method
class-attribute
instance-attribute
¶
get_compatible_backends
classmethod
¶
get_compatible_backends() -> tuple[type[DWave], ...]
Check at runtime if the used backend is compatible with the solver.
Returns:
| Type | Description |
|---|---|
tuple[type[IBackend], ...]
|
True if the backend is compatible with the solver, False otherwise. |
get_default_backend
classmethod
¶
get_default_backend() -> DWave
Return the default backend implementation.
This property must be implemented by subclasses to provide the default backend instance to use when no specific backend is specified.
Returns:
| Type | Description |
|---|---|
IBackend
|
An instance of a class implementing the IBackend interface that serves as the default backend. |
run ¶
run(
model: Model | str,
name: str | None = None,
backend: BACKEND_TYPE | None = None,
client: LunaSolve | str | None = None,
*args: Any,
**kwargs: Any,
) -> SolveJob
Run the configured solver.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
model
|
Model or str
|
The model to be optimized or solved. It could be an Model instance or a string identifier representing the model id. |
required |
name
|
str | None
|
If provided, the name of the job. Defaults to None. |
None
|
backend
|
BACKEND_TYPE | None
|
Backend to use for the solver. If not provided, the default backend is used. |
None
|
client
|
LunaSolve or str
|
The client interface used to interact with the backend services. If not provided, a default client will be used. |
None
|
*args
|
Any
|
Additional arguments that will be passed to the solver or client. |
()
|
**kwargs
|
Any
|
Additional keyword parameters for configuration or customization. |
{}
|
Returns:
| Type | Description |
|---|---|
SolveJob
|
The job object containing the information about the solve process. |