Improve MAPElites performance

[JakeForsey]

https://github.com/nnaisense/evotorch/issues/93

Is a second implementation appropriate? The only drawback I can see is that the feature grid has to be regular.

mapelites_profiling.py

import time

import torch
from evotorch import Problem
from evotorch.algorithms import MAPElites, RegularMAPElites
from evotorch.operators import GaussianMutation, SimulatedBinaryCrossOver

def kursawe(x: torch.Tensor) -> torch.Tensor:
    f1 = torch.sum(
        -10 * torch.exp(
            -0.2 * torch.sqrt(x[:, 0:2] ** 2.0 + x[:, 1:3] ** 2.0)
        ),
        dim=-1,
    )
    f2 = torch.sum(
        (torch.abs(x) ** 0.8) + (5 * torch.sin(x ** 3)),
        dim=-1,
    )
    fitnesses = torch.stack([f1 + f2, f1, f2], dim=-1)
    return fitnesses

def main():
    lower_bounds = [-20, -14]
    upper_bounds = [-10, 4]
    num_bins = 50

    for clazz, feature_grid in [
        (RegularMAPElites, RegularMAPElites.make_feature_grid(lower_bounds, upper_bounds, [num_bins, num_bins])),
        (MAPElites, MAPElites.make_feature_grid(lower_bounds, upper_bounds, num_bins, dtype="float32")),
    ]:
        problem = Problem(
            "min",
            kursawe,
            solution_length=3,
            eval_data_length=2,
            bounds=(-5.0, 5.0),
            vectorized=True,
        )
        searcher = clazz(
            problem,
            feature_grid=feature_grid,
            operators=[
                SimulatedBinaryCrossOver(problem, tournament_size=4, cross_over_rate=1.0, eta=8),
                GaussianMutation(problem, stdev=0.03),
            ],
        )
        start = time.time()
        searcher.run(100)
        print("Final status:\n", searcher.status)
        print("Impl: ", clazz)
        print("Time spent (secs): ", time.time() - start)
        print("Filled hypervolumes: ", searcher.filled.sum())

if __name__ == "__main__":
    main()

out:

python examples/scripts/mapelites_profiling.py
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4430191008) -- The `dtype` for the problem's decision variables is set as torch.float32
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4430191008) -- `eval_dtype` (the dtype of the fitnesses and evaluation data) is set as torch.float32
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4430191008) -- The `device` of the problem is set as cpu
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4430191008) -- The number of actors that will be allocated for parallelized evaluation is 0
Final status:
 <LazyStatusDict
    mean_eval = <not yet computed>
    pop_best_eval = <not yet computed>
    pop_best = <not yet computed>
    median_eval = <not yet computed>
    iter = 100
    best = <Solution values=tensor([-1.1418, -1.1287, -1.1360]), evals=tensor([-26.1036, -14.5129, -11.5906])>
    worst = <Solution values=tensor([-4.9854,  3.2066, -3.7966]), evals=tensor([17.0567, -6.7572, 23.8138])>
    best_eval = -26.10356903076172
    worst_eval = 17.056659698486328
>
Impl:  <class 'evotorch.algorithms.mapelites.RegularMAPElites'>
Time spent (secs):  0.46088290214538574
Filled hypervolumes:  ReadOnlyTensor(1564)
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4839976912) -- The `dtype` for the problem's decision variables is set as torch.float32
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4839976912) -- `eval_dtype` (the dtype of the fitnesses and evaluation data) is set as torch.float32
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4839976912) -- The `device` of the problem is set as cpu
[2024-02-09 15:26:24] INFO     <28574> evotorch.core: Instance of `Problem` (id:4839976912) -- The number of actors that will be allocated for parallelized evaluation is 0
Final status:
 <LazyStatusDict
    mean_eval = <not yet computed>
    pop_best_eval = <not yet computed>
    pop_best = <not yet computed>
    median_eval = <not yet computed>
    iter = 100
    best = <Solution values=tensor([-1.1362, -1.1318, -1.1396]), evals=tensor([-26.1026, -14.5087, -11.5939])>
    worst = <Solution values=tensor([-3.4925,  3.5591, -4.8970]), evals=tensor([16.4008, -6.6685, 23.0693])>
    best_eval = -26.102632522583008
    worst_eval = 16.400814056396484
>
Impl:  <class 'evotorch.algorithms.mapelites.MAPElites'>
Time spent (secs):  38.28567409515381
Filled hypervolumes:  ReadOnlyTensor(1523)

Summary:

Impl: <class 'evotorch.algorithms.mapelites.RegularMAPElites'> Time spent (secs): 0.46088290214538574 Filled hypervolumes: ReadOnlyTensor(1564)

Impl: <class 'evotorch.algorithms.mapelites.MAPElites'> Time spent (secs): 38.28567409515381 Filled hypervolumes: ReadOnlyTensor(1523)