Genetic algorithm with the help of functional operators¶
In this notebook, we demonstrate how one can design a genetic algorithm by combining operators implemented within the namespace evotorch.operators.functional.
Introduction¶
EvoTorch provides the namespace evotorch.operators.functional which contains genetic algorithm operators that can be called directly on PyTorch tensors. These operators are implemented in conformance with the functional programming paradigm, meaning that they do not mutate the tensors they receive as arguments (*).
A genetic algorithm can be designed by simply calling these genetic algorithm operators in an evolution loop. This way of implementing a genetic algorithm grants the user complete flexibility regarding how and when the operators are to be called, and what extra procedures are to be followed between these operator calls.
Use cases¶
Batched optimization. These operators are defined in such a way that, if they receive a population tensor with 3 or more dimensions (instead of 2 dimensions), the extra leftmost dimensions are interpreted as batch dimensions, and the steps of the operators are broadcast to those batch dimensions. This means that they can work not just on a population, but on a batch of populations, in a vectorized manner.
This feature could be helpful when one has multiple populations (each initialized around different values and/or using different initialization methods), and one wishes to run an evolutionary search on all these populations efficiently.
Nested optimization. It could be the case that the optimization problem at hand has an inner (nested) optimization problem that needs to be addressed within its fitness function. In such cases, one has to run an inner evolutionary search while evaluating each solution. This inner evolutionary search could be implemented with the help of these functional operators. Considering that each solution of the outer problem ends up with its own inner optimization problem, this way of tackling the inner problem could result in an efficient and vectorized implementation (vectorization would happen across multiple inner optimization problems induced by multiple solutions of the outer problem; see the use case "Batched optimization").
(*) It is to be noted, however, that they do mutate the global random state of PyTorch, because of how they use PyTorch functions such as torch.randn(...), etc.
Example¶
We now show how to use the functional operators to design a genetic algorithm to solve the Rastrigin problem. To keep the example simple, we do not consider the use cases of batched/nested optimization.
We begin with the necessary imports.
import torch
from evotorch.operators import functional as func_ops
from evotorch.decorators import rowwise
from datetime import datetime
Below, we have the implementations for the fitness functions rastrigin and sphere.
Notice how these fitness functions are decorated via evotorch.decorators.rowwise.
This decorator allows the user to implement the function with the assumption that its received argument is a single row (i.e. a 1-dimensional tensor). As an additional behavior, if a function decorated via @rowwise receives a tensor with 2 or more dimensions, the operations defined within the decorated function are broadcast across the extra leftmost dimensions. In other words, the extra leftmost dimensions are interpreted as batch dimensions.
@rowwise
def rastrigin(x: torch.Tensor) -> torch.Tensor:
from math import pi
A = 10
[n] = x.shape
return A * n + torch.sum((x ** 2.0) - (A * torch.cos(2 * pi * x)))
In this notebook, the variable f points to the fitness function whose value we want to minimize:
Various hyperparameters and problem settings:
popsize = 1000 # population size
solution_length = 1000 # length of a solution
# lower and upper bounds for the decision values of the initial population
lb = -5.12
ub = 5.12
tournament_size = 8 # tournament size
mutation_stdev = 0.01 # standard deviation for the Gaussian mutation
eta = 10.0 # eta value for the simulated binary cross-over
num_generations = 1000 # number of generations
# Initialize the decision values of the initial population
parents = (torch.rand(popsize, solution_length, dtype=torch.float32) * (ub - lb)) + lb
# Evaluate the initial population
parent_evals = f(parents)
last_reporting_time = None
reporting_interval = 1
# Main loop of the population
for generation in range(1, 1 + num_generations):
# Given the parent solutions and their evaluation results,
# run a tournament, pick pairs, and apply cross-over for each pair:
candidates = func_ops.simulated_binary_cross_over(
parents,
parent_evals,
eta=eta,
tournament_size=tournament_size,
objective_sense="min",
)
# Instead of simulated binary cross-over, you could use two-point
# cross-over:
# candidates = func_ops.two_point_cross_over(
# parents,
# parent_evals,
# tournament_size=tournament_size,
# objective_sense="min",
# )
# Apply Gaussian mutation on the newly made candidate solutions
candidates = candidates + (torch.randn_like(candidates) * mutation_stdev)
# On the newly mutated solutions, apply the permutation operator of the CoSyNE algorithm
permuted = func_ops.cosyne_permutation(parents, permute_all=True)
# Add the permutation results onto the new population of candidates
candidates = func_ops.combine(candidates, permuted)
# Evaluate all the candidate solutions
candidate_evals = f(candidates)
# Combine the parent population and the candidate population to form an
# extended population. This time, we combine together with the evaluation results.
extended_population, extended_evals = (
func_ops.combine((parents, parent_evals), (candidates, candidate_evals))
)
# From the extended population, take the best `popsize` number of solutions.
# These taken solutions will server as the parents of the next generation.
parents, parent_evals = (
func_ops.take_best(extended_population, extended_evals, popsize, objective_sense="min")
)
# Report how the evolution is progressing
now = datetime.now()
if (
(last_reporting_time is None)
or (generation == num_generations)
or ((now - last_reporting_time).total_seconds() > reporting_interval)
):
last_reporting_time = now
print("Generation:", generation, " Best eval of population:", parent_evals.min())
Decision values of the final population:
Best solution of the final population:
pop_best, pop_best_eval = func_ops.take_best(parents, parent_evals, objective_sense="min")
print("Best solution of the final population:", pop_best)
print("Best evaluation result of the final population:", pop_best_eval)