Skip to content

ericmedvet/jgea

BranchesTags

Repository files navigation

JGEA

Java General Evolutionary Algorithm (jgea) is a modular Java framework for experimenting with Evolutionary Computation.

JGEA aims at providing a general interface to potentially all evolutionary algorithms (EA). To do so, it provides an interface to problems that can be solved with an EA and components of an EA (e.g., genetic operators, selection criteria, ...).

Moreover, a few EAs are actually implemented in JGEA: Map-Elites, NSGA-II, OpenAI-ES, CMA-ES, Differential Evolution, Graphea, GA, GP, and some variants of Grammar-guided GP.

Several research papers have been published in which the experimental evaluation is based on JGEA or its previous version evolved-ge. See a partial list below.

If you use JGEA please cite our paper:

@inproceedings{medvet2022jgea,
  title={JGEA: a Modular Java Framework for Experimenting with Evolutionary Computation},
  author={Medvet, Eric and Nadizar, Giorgia and Manzoni, Luca},
  booktitle={Proceedings of the genetic and evolutionary computation conference companion},
  year={2022}
}

Usage

JGEA inside your Java project

Add (at least) this to your pom.xml:

<dependency>
    <groupId>io.github.ericmedvet</groupId>
    <artifactId>jgea.core</artifactId>
    <version>2.7.0</version>
</dependency>

Standalone (through the Experimenter)

First, get the code:

git clone https://github.com/ericmedvet/jgea.git
cd jgea
mvn clean package

Then run an example experiment

java -jar io.github.ericmedvet.jgea.experimenter/target/jgea.experimenter-2.7.0-jar-with-dependencies.jar -e sr-comparison

Main components

Typical usage of JGEA consists in trying to solve a problem using an EA.

Problem

The problem is described by a class implementing the Problem interface. A problem simply defines the solution space, by using a generics S, and a way to compare two solutions, by extending the PartialComparator<S> interface.

public interface Problem<S> extends PartialComparator<S> {}

Most problems actually define also a space for the quality of the solutions and a way to compute the quality given a solution, on the assumption that solutions are compared by comparing the fitness. This kind of problems is described by classes implementing the QualityBasedProblem interface.

public interface QualityBasedProblem<S, Q> extends Problem<S> {
  PartialComparator<Q> qualityComparator();

  Function<S, Q> qualityFunction();
}

Here, Q represents the quality space (or fitness space).

JGEA includes many realization of this abstract definition, i.e., other interfaces that extend QualityBasedProblem and implementations (possibly abstract) of these interfaces.

For example, there is a class representing the OneMax problem:

public class OneMax implements ComparableQualityBasedProblem<BitString, Double> {
  /* ... */
}

where the solution space is the one of BitStrings and the quality space is the one of Doubles.

There are other interfaces extending QualityBasedProblem that model more specific classes of problems. For example, there is a class representing, in general, a classification problem:

public class ClassificationProblem<O, L extends Enum<L>> implements ProblemWithValidation<Classifier<O, L>,
    List<Double>> {
  /* ... */
}

where O is the space of observations (or instances, or data points, in supervised learning jargon), L is the space of labels (or responses, or outputs), and Classifier<O, L> is the space of solutions. Here, the quality space is given by List<Double> because we model the quality of a classifier with potentially more than one indexes (i.e., not necessarily only the accuracy).

Solver

A problem can be solved by a Solver:

public interface Solver<P extends Problem<S>, S> {
  Collection<S> solve(
      P problem, RandomGenerator random, ExecutorService executor
  ) throws SolverException;
}

The unique ability of a Solver is to solve a problem P. The return value of solve() is a collection of solutions: depending on the solver and on the problem, this collection might be composed of a single solution, i.e., the best solution, or of multiple solutions.

In general, an implementation of a solver might be able to solve only a subset of the possible problems, i.e., only problems of a given type, here representated by P, e.g., QualityBasedProblem<S, Double>.

The solve() method takes, besides the problem, a RandomGenerator and an ExecutorService, because a solver can be, in general, non-deterministic and capable of exploiting concurrency.

  • The RandomGenerator instance is used for all the random choices, hence allowing for repeatability of the experimentation. Note: reproducibility, i.e., obtaining the same results in the same conditions, is not a direct consequence of repeatability if some conditions are not satisfied. JGEA attempts to meet all of these conditions: however, executing an evolutionary run with some parallelism leads in general to not meeting one condition.
  • The ExecutorService instance is used for distributing computation (usually, of the fitness of candidate solutions) across different workers of the executor.

Most of the solvers are iterative, i.e., the build solutions based on an iterative process.

public interface IterativeSolver<T extends Copyable, P extends Problem<S>, S> extends Solver<P, S> {
  /* ... */
  default Collection<S> solve(
      P problem, RandomGenerator random, ExecutorService executor, Listener<? super T> listener
  ) throws SolverException {
    /* ... */
  }
}

Intuitively, an IterativeSolver evolves a state T across iterations starting from an initial value. In the practical case of evolutionary algorithms (EAs) the state usually contains also the population of individuals. The trajectory of the state during the solution of problems can be monitored by a Listener, that has to be passed to solve().

Listeners

Listeners are a key component of JGEA. Their main use is to monitor the evolution by extracting some information and printing it somewhere. Typical information of interest is, at each iteration of the EA:

  • the size of the population
  • the diversity in the population
  • the quality (a Q) of the best individual
  • the best individual (a S)
  • some function of the best individual

In the example below, it is shown how to use listener to print on the standard output how this kind of information changes during the evolution. JGEA contains classes for printing on stdout as well as on files, with proper formats.

Implemented EAs

JGEA contains a few significative EAs, i.e., classes implementing IterativeSolver.

One, that is at the same time pretty standard and a template that can be realized in many ways depending on the parameters, is StanderdEvolver, that corresponds to a μ + λ (or μ, λ, depending on the parameter overlapping) generational model (see [1]). StandardEvolver parameters are set using the only class constructor: names of the parameters indicate the corresponding meaning.

public class StandardEvolver<G, S, Q>
    extends AbstractStandardEvolver<
    POCPopulationState<Individual<G, S, Q>, G, S, Q>,
    QualityBasedProblem<S, Q>,
    Individual<G, S, Q>,
    G,
    S,
    Q> {
  public StandardEvolver(
      Function<? super G, ? extends S> solutionMapper,
      Factory<? extends G> genotypeFactory,
      int populationSize,
      Predicate<? super POCPopulationState<Individual<G, S, Q>, G, S, Q>> stopCondition,
      Map<GeneticOperator<G>, Double> operators,
      Selector<? super Individual<G, S, Q>> parentSelector,
      Selector<? super Individual<G, S, Q>> unsurvivalSelector,
      int offspringSize,
      boolean overlapping,
      boolean remap) {
    /* ... */
  }
}

StandardEvolver automatically exploits parallelism using the ExecutorService parameter of solve().

POCPopulationState is a state that includes the population, in the form of a partially ordered set (poset).

public interface POCPopulationState<I extends Individual<G, S, Q>, G, S, Q> extends State {
  long nOfBirths();
  long nOfFitnessEvaluations();
  PartiallyOrderedCollection<I> pocPopulation();
}

Selector represents a selection criterion: it is a functional interface with a method select() that takes a poset and returns, possibly stochastically, an element.

public interface Selector<T> {
  <K extends T> K select(POCPopulationState<K> ks, RandomGenerator random);
}

JGEA uses PartialComparator and PartiallyOrderedCollection instead of the standard JDK interfaces Comparator and Collection because the latter represent a total ordering, whereas there are many cases where the EA does not assume a total ordering among candidate solutions.

Example

In this example, JGEA is used for solving the parity problem with the standard EA and solution encoded as derivation trees of a provided grammar, that is, with a form of G3P. Here a solution is a List<Tree<Element>>, because the general form of a bits-to-bits set function is list of trees, each tree encoding a bits-to-bit function.

public class Example {
  public static void main(String[] args) {
    ExecutorService executor =
        Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors() - 1);
    @SuppressWarnings({"unchecked", "rawtypes"})
    ListenerFactory<POCPopulationState<?, ?, NamedUnivariateRealFunction, Double>, Void>
        listenerFactory = new TabularPrinter<>(
        (List) List.of(
            nOfIterations(),
            elapsedSeconds(),
            nOfBirths(),
            all().then(size()),
            firsts().then(size()),
            lasts().then(size()),
            all().then(each(genotype())).then(uniqueness()),
            all().then(each(solution())).then(uniqueness()),
            all().then(each(quality())).then(uniqueness()),
            best().then(genotype()).then(size()),
            best().then(solution()).then(size()),
            best().then(fitnessMappingIteration()),
            NamedFunctions.<Individual<Object, Object, Double>, Object, Object, Double>best()
                .then(quality())
                .reformat("%5.3f"),
            NamedFunctions.<Individual<Object, Object, Double>, Object, Object, Double>all()
                .then(each(quality()))
                .then(hist(8)),
            best().then(solution()).reformat("%20.20s")
        ),
        List.of()
    );
    Random r = new Random(1);
    SyntheticUnivariateRegressionProblem p = new Nguyen7(UnivariateRegressionFitness.Metric.MSE, 1);
    List<Element.Variable> variables = p.qualityFunction()
        .getDataset()
        .xVarNames()
        .stream()
        .map(Element.Variable::new)
        .toList();
    List<Element.Constant> constantElements = Stream.of(0.1, 1d, 10d).map(Element.Constant::new).toList();
    IndependentFactory<Element> terminalFactory = IndependentFactory.oneOf(
        IndependentFactory.picker(variables), IndependentFactory.picker(constantElements));
    IndependentFactory<Element> nonTerminalFactory = IndependentFactory.picker(List.of(
        Element.Operator.ADDITION,
        Element.Operator.SUBTRACTION,
        Element.Operator.MULTIPLICATION,
        Element.Operator.PROT_DIVISION
    ));
    TreeBuilder<Element> treeBuilder = new GrowTreeBuilder<>(x -> 2, nonTerminalFactory, terminalFactory);
    // operators
    Map<GeneticOperator<Tree<Element>>, Double> geneticOperators = Map.ofEntries(
        Map.entry(new SubtreeCrossover<>(10), 0.80),
        Map.entry(new SubtreeMutation<>(10, treeBuilder), 0.20)
    );
    StandardEvolver<Tree<Element>, NamedUnivariateRealFunction, Double> solver = new StandardEvolver<>(
        t -> new TreeBasedUnivariateRealFunction(
            t,
            p.qualityFunction().getDataset().xVarNames(),
            p.qualityFunction().getDataset().yVarNames().get(0)
        ),
        new RampedHalfAndHalf<>(4, 10, x -> 2, nonTerminalFactory, terminalFactory),
        100,
        StopConditions.nOfFitnessEvaluations(10000),
        geneticOperators,
        new Tournament(5),
        new Last(),
        100,
        true,
        false
    );
    Collection<NamedUnivariateRealFunction> solutions = solver.solve(p, r, executor, listenerFactory.build(null));
    System.out.printf("Found %d solutions%n", solutions.size());
  }
}

Methods inside the constructor of TabularPrinter are static methods of the class NamedFunctions that return functions that take an evolution State and return an object that will be printed as a table cell.

Research papers based on JGEA

The list includes paper published from 2018 on.

References

  1. De Jong, Kenneth. "Evolutionary computation: a unified approach." Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. 2016.

About

No description, website, or topics provided.

Resources

Readme

License

Apache-2.0 license
Activity

Stars

19 stars

Watchers

0 watching

Forks

11 forks
Report repository

Releases 13

v2.7.0 Latest
Sep 15, 2024
+ 12 releases

Packages

 
 
 

Contributors 10

Languages