Optimizers

Evolutionary Algorithms

class fevovaq.GeneticAlgorithm.GA(selection: Callable, crossover: Callable, mutation: Callable, elitism: bool = True, cxpb: float = 0.8, mutpb: float = 1.0, **kwargs)

Bases: object

Genetic Algorithm (GA) is the simplest evolutionary algorithm inspired by Darwinian evolution principles: the evolution of a population of possible solutions to a given problem is linked to the concepts of randomness and survival of the fittest [1]. In detail, during an evolutionary cycle, the processes of selection, crossover and mutation, known as stochastic genetic operators, take place in order to produce the next generation of solutions. The evolution process stops when a maximum number of generations or fitness evaluations is reached. Typically, during the evolution process, the best individual of the current generation can be inserted into the next one in order to prevent its possible disappearance [2].

References

[1] Giovanni Acampora, Angela Chiatto, and Autilia Vitiello, “Training variational quantum circuits through genetic algorithms”, Proceedings of 2022 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8, 2022.

[2] Giovanni Acampora, Angela Chiatto, and Autilia Vitiello, “Genetic algorithms as classical optimizer for the quantum approximate optimization algorithm”, Applied Soft Computing, pp. 110296, Elsevier, 2023.

Parameters:

• selection – Selection operator used to select individuals to create the mating pool.

• crossover – Crossover operator used to mate parents.

• mutation – Mutation operator used to mutate individuals.

• elitism – If True, the best solution of current population is transferred directly into the next generation.

• cxpb – The probability of mating two individuals.

• mutpb – The probability of mutating an individual.

• kwargs – Additional keyword arguments used to set hyperparameter values of genetic operators.

evolve_population(problem: Problem, population, fitness, gen)

Evolve the population by means of genetic operators.

Parameters:

• problem – Problem to be solved.

• population – A population of individuals as array of real parameters with (pop_size, n_params) shape.

• fitness – A set of fitness values associated to the population as array of real values with (pop_size, ) shape.

• gen – Current generation number.

Returns:

The offspring and fitness values obtained after evolution, and number of fitness evaluations completed during the evolution.

optimize(problem: Problem, pop_size: int, initial_pop=None, max_nfev=None, max_gen=1000, num_run=1, seed=None, verbose=True) → FinalResult

Optimize the parameters of the problem to be solved.

Parameters:

• problem – Problem to be solved.

• pop_size – Population size.

• initial_pop – Initial population of possible solutions as array of real parameters with (pop_size, n_params) shape. If None, the initial population is randomly generated from init_range in Problem.

• max_nfev – Maximum number of fitness evaluations. If not None, this is considered as stopping criterion.

• max_gen – Maximum number of generations. 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 default method is used.

• verbose – If True, the statistics of fitness values is printed during the evolution.

Returns:

A FinalResult containing the optimization result.

class fevovaq.DifferentialEvolution.DE(variant: str = 'best/1/bin', differential_weight: float | tuple = 0.8, CR: float = 0.9)

Bases: object

Differential Evolution (DE) is a parallel direct search method designed for minimizing possibly nonlinear and non-differentiable continuous space functions [1]. Starting from an initial random population, the evolutionary cycle that creates a new population for the next generation consists of an appropriate perturbation of each individual. In detail, for each target individual, a mutant individual is generated by adding a weighted difference between two or four randomly chosen individuals to a third individual selected as best or randomly. At this point, a uniform crossover is applied between the target and the mutant to obtain the trial individual. Lastly, the trial individual is compared to the target individual to determine the best member of the next generation [2].

References

[1] R. Storn and K. Price, “Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces,” Journal of global optimization, vol. 11, no. 4, pp. 341–359, 1997.

[2] Giovanni Acampora, Angela Chiatto, and Autilia Vitiello, “A comparison of evolutionary algorithms for training variational quantum classifiers”, Proceedings of 2023 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8, 2023.

Parameters:

• variant – The variants are denoted as <selection>/<n_diffs>/<crossover>, where <selection> is best or rand, <n_diffs> is 1 or 2, and <crossover> is bin.

• differential_weight – Differential weight is a hyperparameter that controls the amplification of the individuals difference used to create the mutant. It must be in the range (0, 2). If (min, max) tuple, dithering is employed. Dithering randomly changes the differential weight in each generation so that it can help speed convergence significantly.

• CR – The probability that a parameter of the trial individual is replaced with the corresponding one of the mutant individual.

evolve_population(problem: Problem, population, fitness, gen)

Evolve the population by means of genetic operators.

Parameters:

• problem – Problem to be solved.

• population – A population of individuals as array of real parameters with (pop_size, n_params) shape.

• fitness – A set of fitness values associated to the population as array of real values with (pop_size, ) shape.

• gen – Current generation number.

Returns:

The offspring and fitness values obtained after evolution, and number of fitness evaluations completed during the evolution.

optimize(problem: Problem, pop_size: int, initial_pop=None, max_nfev=None, max_gen=1000, num_run=1, seed=None, verbose=True) → FinalResult

Optimize the parameters of the problem to be solved.

Parameters:

• problem – Problem to be solved.

• pop_size – Population size.

• initial_pop – Initial population of possible solutions as array of real parameters with (pop_size, n_params) shape. If None, the initial population is randomly generated from param_bounds.

• max_nfev – Maximum number of fitness evaluations used. If not None, this is considered as stopping criterion.

• max_gen – Maximum number of generations. 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 FinalResult containing the optimization result.

class fevovaq.MemeticAlgorithm.MA(global_search: Callable, local_search: Callable, sel_for_refinement: Callable, frequency: float, intensity: int, elitism: bool = True)

Bases: object

Memetic Algorithm (MA) [1] is an evolutionary approach that merge population- and local-based methods to improve exploration and exploitation capabilities in visiting the problem search space. In evovaq, MA workflow described in [2] is implemented.

References

[1] P. Moscato, et al., “On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms”, Caltech concurrent computation program, C3P Report, vol. 826, pp. 37, 1989.

[2] Giovanni Acampora, Angela Chiatto, and Autilia Vitiello, “Training circuit-based quantum classifiers through memetic algorithms”, Pattern Recognition Letters, Elsevier, 2023.

Parameters:

• global_search – Population-based method used to evolve the population of individuals. The global search function is defined as global_search(prob, pop, fitness, gen, *args) -> (offspring, fit_offspring, nfev), where prob is Problem to be solved; pop and fitness are two arrays of real parameters with (pop_size,`n_params`) and (n_params, ) shape, respectively; gen is the current generation number; args is a tuple of other fixed parameters needed to specify the function; and the output is the resulting offspring and fitness values with the same shape as pop and fitness, and number of fitness evaluations completed during the evolution. Here, it is possible to use GA or DE as a population-based method via evolve_population() method.

• local_search – Local search method used to improve a subset of individuals. The local search function is defined as local_search(prob, ind, fitness, *args) -> (ind, fitness, nfev), where prob is Problem to be solved; ind is an array of real parameters with (n_params,); fitness is a float value; args is a tuple of other fixed parameters needed to specify the function; and the output is the improved individual and fitness value with the same shape as ind and fitness, and number of fitness evaluations completed during the local research. Here, it is possible to use HC as a local search method via stochastic_var() method.

• sel_for_refinement – Selection operator used to choose the individuals undergoing local refinement.

• frequency – Individual learning frequency defined in the range (0 , 1) influencing the number of individuals that is undergone to local refinement.

• intensity – Individual learning intensity representing the maximum computational budget allowable for individual learning to expend on improving a single solution. Here, it corresponds to the maximum number of iterations to be performed during the local search.

• elitism – If True, the best solution of current population is transferred directly into the next generation.

optimize(problem: Problem, pop_size: int, initial_pop=None, max_nfev=None, max_gen=1000, num_run=1, seed=None, verbose=True) → FinalResult

Optimize the parameters of the problem to be solved.

Parameters:

• problem – Problem to be solved.

• pop_size – Population size.

• initial_pop –

  Initial population of possible solutions as array of real parameters with (pop_size, n_params)

  shape. If None, the initial population is randomly generated from param_bounds.

  max_nfev: Maximum number of fitness evaluations. If not None, this is considered as stopping criterion.

• max_gen – Maximum number of generations. 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 FinalResult containing the optimization result.

class fevovaq.BigBangBigCrunch.BBBC(elitism: bool = True, alpha: float = 10.0, beta: float = 0.25)

Bases: object

The Big Bang - Big Crunch (BBBC) method as developed by Erol and Eks in 2006 [1] consists of two alternating steps: 1) a Big Bang phase, where the candidate solutions are randomly distributed over the search space; 2) a Big Crunch phase, where a contraction operation estimates a weighted average, denoted as Centre of Mass, of the randomly distributed candidate solutions. During the Big Bang phases, new candidate solutions are generated considering the Center of Mass and the best global solution, as introduced in [2].

References

[1] O. K. Erol and I. Eksin, “A new optimization method: big bang–big crunch”, Advances in Engineering Software, vol. 37, no. 2, pp. 106– 111, 2006.

[2] C. V. Camp, “Design of space trusses using big bang–big crunch optimization,” Journal of Structural Engineering, vol. 133, no. 7, pp. 999–1008, 2007.

Parameters:

• elitism – If True, the best solution of current population is transferred directly into the next generation.

• alpha – Hyperparameter limiting the size of the search space.

• beta – Hyperparameter defined in range (0,1) controlling the influence of the best individual on the location of new candidate solutions.

evolve_population(problem, population, fitness, gen)

Evolve the population by means of genetic operators.

Parameters:

• problem – Problem to be solved.

• population – A population of individuals as array of real parameters with (pop_size, n_params) shape.

• fitness – A set of fitness values associated to the population as array of real values with (pop_size, ) shape.

• gen – Current generation number.

Returns:

The offspring and fitness values obtained after evolution, and number of fitness evaluations completed during the evolution.

optimize(problem: Problem, pop_size: int, initial_pop=None, max_nfev=None, max_gen=1000, num_run=1, seed=None, verbose=True) → FinalResult

Optimize the parameters of the problem to be solved.

Parameters:

• problem – Problem to be solved.

• pop_size – Population size.

• initial_pop – Initial population of possible solutions as array of real parameters with (pop_size, n_params) shape. If None, the initial population is randomly generated from param_bounds.

• max_nfev – Maximum number of fitness evaluations. If not None, the maximum number this is considered as stopping criterion.

• max_gen – Maximum number of generations. 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 FinalResult containing the optimization result.

class fevovaq.ParticleSwarmOptimization.PSO(vmin: float | None = None, vmax: float | None = None, inertia_weight: float = 0.7298, phi1: float = 1.49618, phi2: float = 1.49618)

Bases: object

Particle Swarm Optimization (PSO) is an optimization method based on a swarm of candidate solutions, named particles, moving in the search space according to appropriate position and velocity equation [1]. Starting from a swarm of particles with random positions and velocities, each particle’s velocity is updated by combining its own best position (pbest) and the global best position (gbest) ever found in the search space with some random perturbations influenced by two hyperparameters, denoted as phi1 and phi2. At this point, each particle’s position is updated by adding its resulting velocity to the current position. The final goal is to move the whole swarm close to an optimal position in the search space. In fevovaq, PSO with inertia weight (inertia_weight) described in [2] is implemented.

References

[1] Giovanni Acampora, Angela Chiatto, and Autilia Vitiello, “A comparison of evolutionary algorithms for training variational quantum classifiers”, Proceedings of 2023 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8, 2023.

[2] Poli R., Kennedy J., & Blackwell T., “Particle swarm optimization: An overview”, Swarm intelligence, vol. 1, pp. 33-57, 2007.

Parameters:

• vmin – Lower value(s) of the velocity. If None, no limits are considered.

• vmax – Upper value(s) of the velocity. If None, no limits are considered.

• inertia_weight – Inertia weight.

• phi1 – Acceleration coefficient determining the magnitude of the random force in the direction of personal best solution.

• phi2 – Acceleration coefficient determining the magnitude of the random force in the direction of global best solution.

evolve_population(problem, population, fitness, gen)

Evolve the population by means of genetic operators.

Parameters:

• problem – Problem to be solved.

• population – A population of individuals as array of real parameters with (pop_size, n_params) shape.

• fitness – A set of fitness values associated to the population as array of real values with (pop_size, ) shape.

• gen – Current generation number.

Returns:

The offspring and fitness values obtained after evolution, and number of fitness evaluations completed during the evolution.

optimize(problem: Problem, pop_size: int, initial_pop=None, max_nfev=None, max_gen=1000, num_run=1, seed=None, verbose=True) → FinalResult

Optimize the parameters of the problem to be solved.

Parameters:

• problem – Problem to be solved.

• pop_size – Population size.

• initial_pop – Initial population of possible solutions as array of real parameters with (pop_size, n_params) shape. If None, the initial population is randomly generated from init_range in Problem.

• max_nfev – Maximum number of fitness evaluations. If not None, this is considered as stopping criterion.

• max_gen – Maximum number of generations. 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 FinalResult containing the optimization result.

class fevovaq.CHCAlgorithm.CHC(crossover: Callable, distance: Callable, multiplier: float = 1, dec_percentage: float = 0.1, **kwargs)

Bases: object

Cross generational elitist selection, Heterogeneous recombination, and Cataclysmic mutation (CHC) algorithm is a nontraditional genetic algorithm which combines a conservative selection strategy that always preserves the best individuals found so far with a radical (highly disruptive) crossover operator that produces offspring that are maximally different from both parents [1]. In detail, it is based on four main components: a elitist selection, a highly disruptive crossover, an incest prevention check to avoid the recombination of similar solutions, and a population reinitialization method when the population has converged. In evovaq, a real-coded CHC version based on [2-3] is implemented. However, the similarity is measured between fitness values and not between individuals, since different solutions can lead to equal or close cost values when training variational quantum circuits.

References

[1] Larry J. Eshelman, “The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination”, Foundations of Genetic Algorithms, Elsevier, vol. 1, pp. 265-283, 1991.

[2] O. Cordón, S. Damas, J. Santamaría, “Feature-based image registration by means of the CHC evolutionary algorithm”, Image and Vision Computing, vol. 24, Issue 5, pp. 525-533, 2006.

[3] Cuéllar, M. P., Gómez-Torrecillas, J., Lobillo, F. J., & Navarro, G., “Genetic algorithms with permutation-based representation for computing the distance of linear codes”, Swarm and Evolutionary Computation, vol. 60, pp. 100797, 2021.

Parameters:

• crossover – Crossover operator used to mate parents.

• distance – Distance metric used to evaluate the similarity between parents. Select a distance function from

• input (`~.tools.distances`or customize your distance function by considering as function) –

• multiplier – Factor influencing the initial crossover threshold.

• dec_percentage – Crossover threshold update rate.

• kwargs – Additional keyword arguments used to set hyperparameter values of crossover operator.

evolve_population(problem: Problem, population, fitness, gen)

Evolve the population by means of genetic operators.

Parameters:

• problem – Problem to be solved.

• population – A population of individuals as array of real parameters with (pop_size, n_params) shape.

• fitness – A set of fitness values associated to the population as array of real values with (pop_size, ) shape.

• gen – Current generation number.

Returns:

The offspring and fitness values obtained after evolution, and number of fitness evaluations completed during the evolution.

incest_prevention_mask(population, fitness, xp)

Incest prevention check. Before mating, the similarity between the potential parents is calculated, and if this distance does not exceed the threshold thr, they are not mated.

initialize_cx_threshold(population, fitness, xp)

Initialize the crossover threshold and compute the decrement value.

optimize(problem: Problem, pop_size: int, initial_pop=None, max_nfev=None, max_gen=1000, num_run=1, seed=None, verbose=True) → FinalResult

Optimize the parameters of the problem to be solved.

Parameters:

• problem – Problem to be solved.

• pop_size – Population size.

• initial_pop – Initial population of possible solutions as array of real parameters with (pop_size, n_params) shape. If None, the initial population is randomly generated from param_bounds.

• max_nfev – Maximum number of fitness evaluations used as stopping criterion. If None, the maximum number of generations max_gen is considered as stopping criterion.

• max_gen – Maximum number of generations used as stopping criterion. If max_nfev is not 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 FinalResult containing the optimization result.

Local Search Algorithms

class fevovaq.HillClimbing.HC(generate_neighbour: Callable)

Bases: 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.

Parameters:

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

optimize(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.

Parameters:

• problem – 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 FinalResult containing the optimization result.

stochastic_var(problem: Problem, current_solution, current_fitness)

Stochastic variant.

Parameters:

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