Add Caching to Avoid Re-evaluating Solutions

[yhamadi75]

Dear Antonio,

I am using jMetalPy for multi-objective optimization with NSGAII, SPEA2, and HYPE. My app requires calling an external simulator for evaluation. Today, I am filtering out already seen solutions and returning their previously computed evaluation at the app level. However, with several workers, it requires shared memory for the cache, which impacts performances.

Ideally, such a caching mechanism to filter out already seen solutions from solution_list could be implemented at the library level, i.e., before calling any specific evaluator (sequential, multiprocess, dask, spark). Doing that would save from distributed caching problems.

Where is the best place to implement this filtering so it works across different modes (sequential, multiprocess, dask, spark)?

How can we do this without hacking the existing library code? Ideally doing an extension through inheritance?

Not sure evaluator.py is the place to start, I guess that a higher up level in the code, where solution_list is computed would be better. Should be independent from the number of objectives, by design.

Would love to hear your thoughts and happy to help out!

Thanks!

[ajnebro]

Hi.
I would implement the cache into an evaluator. When the evaluate(solution_list) method is called, the solutions in the list that are already in the cache should be filtered, and the cache would be updated with the resulting evaluated solutions.

Antonio

[yhamadi75]

Thanks for the reply. A last question: I am new to Python (coming for C++), is there a way to do the previous without hacking the jmetalpy code? Like doing this through some inheritance mechanism?

Thanks!

[ajnebro]

I would explore the idea of using a generic evaluator with a cache storing only solution variables, including any existing evaluator as a parameter in the constructor method.

The code would look something like this:

class EvaluatorWithCache(Evaluator[S]):
    def __init__(self, base_evaluator:Evaluator[S]):
        self.cache = set()
        self.base_evaluator = base_evaluator

    def evaluate(self, solution_list: List[S], problem: Problem) -> List[S]:
        filtered_solutions = [solution for solution in solution_list if solution.variables not in self.cache]
        filtered_solutions = self.base_evaluator.evaluate(filtered_solutions, problem)
        for solution in filtered_solutions:
            self.cache.add(solution.variables)

        return filtered_solutions

[yhamadi75]

Hi Antonio,
The snippet you provided filters out duplicates entirely, which is not ideal since it might discard valuable genetic material. I have extended it to keep all duplicate solutions evaluations. Could it be more efficient? What do you think?

def evaluate(self, solution_list: List[S], problem: Problem) -> List[S]:
        new_solutions = []
        cached_solutions = []

        for solution in solution_list:
            variables_tuple = tuple(solution.variables)
            if variables_tuple in self.cache:
                solution.objectives = self.cache[variables_tuple]                 # Reuse cached objective values
                cached_solutions.append(solution)
            else:
                new_solutions.append(solution)                # Add to the list of new solutions to evaluate

        # Evaluate new solutions using the base evaluator
        if new_solutions:
            evaluated_solutions = self.base_evaluator.evaluate(new_solutions, problem)
            for solution in evaluated_solutions:
                variables_tuple = tuple(solution.variables)                # Cache the objective values of newly evaluated solutions
                self.cache[variables_tuple] = solution.objectives

            return cached_solutions + evaluated_solutions
        else:
            return cached_solutions            # All solutions were cached

Thanks!

[ajnebro]

I certainly did not pay attention to storing the objective values in the first code fragment. We have to consider also that a solution may have constraints that must be stored in the cache, which leads me to think that maybe, instead of using a set, it might be more convenient to use a dictionary where the keys are the variables and the values is a list with the objectives and constraints.

Another issue that we have to take into account is that the algorithms using evaluators(e.g., evolutionary algorithms) assume that all the solutions are evaluated to update of the evaluation counter. We can observe this in the update_progress() method of class EvolutionaryAlgorithm:

    def update_progress(self) -> None:
        self.evaluations += self.offspring_population_size

Here, it is assumed that all the solutions of the offspring population size have been evaluated.

If you are using jMetalPy to solve a problem of your interest, I don't see a problem here, but if you intend to compare the performance of different algorithms using a stopping condition based on the number of evaluations, then using cached evaluators may lead to wrong conclusions.

[yhamadi75]

Hi Antonio,
Talking about stopping condition. It would make sense to auto stop when the ratio of cached vs total becomes bad.

How would you do that? Maybe computing ratio over several generations, like a mobile average? How to cleanly implement the stop of the search?

Something like:

# Calculate cache ratio for this evaluation
    total_solutions = len(solution_list)
    cache_ratio = len(cached_solutions) / total_solutions if total_solutions > 0 else 0.0
if cache_ration > ...: 
   terminate search


Thanks for your help