from typing import Callable
from .problem import Problem
from .tools.support import print_info, Logbook, FinalResult, set_progress_bar
[docs]
class HC(object):
"""
Hill Climbing (HC) is a local search optimization method. In contrast to evolutionary algorithms, HC starts from a
single initial solution and considers its neighborhood to identify a better solution. Thus, the search takes place
by iteratively trying to replace the current solution with a better neighbour. There are several variants of Hill
Climbing search depending on how to find the next solution.
In `evovaq`, stochastic variant of HC described in [1] is implemented due to its successful application in several
domains.
References:
[1] Giovanni Acampora, Angela Chiatto, and Autilia Vitiello, "Training circuit-based quantum classifiers through
memetic algorithms", Pattern Recognition Letters, Elsevier, 2023.
Args:
generate_neighbour: A way of generating a neighbour of a current solution. This function is defined as
``generate_neighbour(prob, ind, *args) -> neighbour``, where ``prob`` is :class:`~.Problem`
to be solved; ``ind`` is an array of real parameters with (`n_params`,); ``args`` is a tuple
of other fixed parameters needed to specify the function; and the output is the neighbour
with the same shape as ``ind`` and ``fitness``.
"""
def __init__(self, generate_neighbour: Callable):
self.generate_neighbour = generate_neighbour
[docs]
def stochastic_var(
self, problem: Problem, current_solution, current_fitness):
"""
Stochastic variant.
Args:
problem: :class:`~.Problem` to be solved.
current_solution: A possible solution as array of real parameters with (`n_params`, ) shape.
current_fitness: The corresponding fitness value.
Returns:
The improved current solution and fitness value, and the number of fitness evaluations completed during one
iter.
"""
neighbour = self.generate_neighbour(problem, current_solution)
if problem.vectorized:
neighbour_vec = neighbour[:, None]
fit_neighbour = problem.evaluate_fitness(neighbour_vec)[0]
else:
fit_neighbour = problem.evaluate_fitness(neighbour)
if fit_neighbour < current_fitness:
return neighbour, fit_neighbour, 1
else:
return current_solution, current_fitness, 1
[docs]
def optimize(self, problem: Problem, init_point=None,
max_nfev=None, max_iter=1000, num_run=1, seed=None, verbose=True) -> FinalResult:
"""
Optimize the parameters of the problem to be solved.
Args:
problem: :class:`~.Problem` to be solved.
init_point: Initial possible solution as array of real parameters with (`n_params`, ) shape. If None, the
initial point is randomly generated from `param_bounds`.
max_nfev: Maximum number of fitness evaluations. If not None, this is considered as stopping criterion.
max_iter: Maximum number of iterations. If `max_nfev` is None, this is considered as stopping criterion.
num_run: Independent execution number of the algorithm.
seed: Initialize the random number generator. If None, the current time is used.
verbose: If True, the statistics of fitness values is printed during the evolution.
Returns:
A :class:`~.FinalResult` containing the optimization result.
"""
xp = problem.xp
if seed is not None:
xp.random.seed(seed)
if init_point is None:
current_solution = problem.generate_individual()
else:
current_solution = xp.asarray(init_point)
if problem.vectorized:
current_fitness = problem.evaluate_fitness(current_solution)[0]
else:
current_fitness = problem.evaluate_fitness(current_solution)
tot_nfev = 1
it = 0
pbar = set_progress_bar(max_iter, max_nfev, 'Iterations', 'iter')
if max_nfev is not None:
pbar.update(tot_nfev)
lg = Logbook()
lg.record(iter=it, nfev=tot_nfev, fitness=current_fitness)
if verbose: print_info(n_run=num_run, iter=it, nfev=tot_nfev, fitness=current_fitness, header=True)
for it in range(1, max_iter + 1):
if max_nfev is not None and tot_nfev >= max_nfev:
break
new_solution, new_fitness, nfev = self.stochastic_var(problem, current_solution, current_fitness)
tot_nfev += nfev
current_solution[:] = new_solution
current_fitness[:] = new_fitness
lg.record(iter=it, nfev=nfev, fitness=current_fitness)
if verbose: print_info(n_run=num_run, iter=it, nfev=nfev, fitness=current_fitness)
pbar.update(nfev if max_nfev else 1)
pbar.close()
return FinalResult(x=current_solution, fun=current_fitness, nfev=tot_nfev, iter=it,
log=lg.get_log())