Skip to content

jrharbin-york/jgea

BranchesTags
 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

346 Commits
grammars
grammars
 
 
src/main
src/main
 
 
.gitignore
.gitignore
 
 
LICENCE.txt
LICENCE.txt
 
 
README.md
README.md
 
 
pom.xml
pom.xml
 
 

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 EA are actually implemented in JGEA, most of them being related to Genetic Programming (GP) and its Grammar-guided variants (G3P).

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

Main components

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

Problem

The problem is described by a class implementing the Problem interface. Problem is parametrized with two types that conceptually represent the solution space and the fitness space, i.e., the space of the quality of the solutions:

public interface Problem<S, F> {
  Function<S, F> getFitnessFunction();
}

A Problem is hence defined by the solution space S, the fitness space F and a fitness function from S to F.

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

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

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

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

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

public abstract class AbstractClassificationProblem<C, O, E extends Enum<E>> implements ProblemWithValidation<C, List<Double>>, BiFunction<C, O, E> { /* ... */ }

where C is the space of classifiers, O is the space of observations (or instances, or data points, in supervised learning jargon), E is the space of labels (or responses, or outputs).

Evolutionary Algorithm (EA)

The EA is described by a class implementing the Evolver interface. Evolver is parametrized with three types that potentially represent the genotype (G), solution (S), and fitness (F) spaces:

public interface Evolver<G, S, F> {
  Collection<S> solve(
      Function<S, F> fitnessFunction,
      Predicate<? super Event<G, S, F>> stopCondition,
      Random random,
      ExecutorService executor,
      Listener<? super Event<G, S, F>> listener) throws InterruptedException, ExecutionException;
}

In general, any Evolver can be used to solve any Problem with suitable S, F by invoking solve() on the problem fitness function. The genotype space G is the one in which the search is actually performed by applying the genetic operators: items in G are mapped to items in S, i.e., to solutions, with a mapper, that, when required, is one of the parameters of the EA, that are fields of the class implementing Evolver in JGEA. Note that some EAs might support only the case in which G = S; other my constraint G or S or both to be a given type (e.g., List<Double>).

An Evolver solves a problem when the solve() method is invoked; that is, invoking solve() corresponds to performing an evolutionary run (also called evolutionary search or simply evolution).

Besides the Problem parameter, whose role is obvious, this methods takes as input also a Predicate, a Random, an ExecutorService, and a Listener.

  • The Predicate instance represents a termination criterion (possibly the conjuction or disjunction of other predicates). Many EAs are iterative and support, in general, various termination conditions. However, some EAs might not use, or need, a termination criterion.
  • The Random 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.
  • The Listener instance is used for notifying about important events during the evolution.

The return value of solve() is a collection of solutions: depending on the EA and on the problem, this collection might be composed of a single solution, i.e., the best solution found by the EA, or a more than one solutions.

Listeners

Listeners are a key component of JGEA. They 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 fitness (a F) 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 significatives EAs, i.e., classes implementing Evolver.

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 mu + lamda (or mu, lambda, 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, F> extends AbstractIterativeEvolver<G, S, F> {
  public StandardEvolver(
      Function<? super G, ? extends S> solutionMapper,
      Factory<? extends G> genotypeFactory,
      PartialComparator<? super Individual<G, S, F>> individualComparator,
      int populationSize,
      Map<GeneticOperator<G>, Double> operators,
      Selector<? super Individual<? super G, ? super S, ? super F>> parentSelector,
      Selector<? super Individual<? super G, ? super S, ? super F>> unsurvivalSelector,
      int offspringSize,
      boolean overlapping,
      boolean remap) { /* ... */}
}

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

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

public interface Selector<T> {  
  <K extends T> K select(PartiallyOrderedCollection<K> ks, Random 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. Note that the PartialComparator is a parameter of an EA, rather than part of the definition of a Problem because different ranking criteria can be used on individuals rather than just quality. For example, one may want to solve a symbolic regression problem by ranking solutions according to Pareto dominance based on mean absolute error and complexity of the expression, both to be minimized.

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 executorService = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
    Random r = new Random(1);
    GrammarBasedProblem<String, List<Tree<Element>>, Double> p = new EvenParity(8);
    Evolver<Tree<String>, List<Tree<Element>>, Double> evolver = new StandardEvolver<>(
        new FormulaMapper(),
        new RampedHalfAndHalf<>(3, 12, p.getGrammar()),
        PartialComparator.from(Double.class).on(Individual::getFitness),
        100,
        Map.of(
            new StandardTreeCrossover<>(12), 0.8d,
            new StandardTreeMutation<>(12, p.getGrammar()), 0.2d
        ),
        new Tournament(3),
        new Worst(),
        100,
        true,
        false
    );
    Listener.Factory<Event<?, ?, ? extends Double>> listenerFactory = new TabularPrinter<>(List.of(
        iterations(),
        births(),
        elapsedSeconds(),
        uniqueness().of(each(genotype())).of(all()),
        size().of(solution()).of(best()),
        birthIteration().of(best()),
        fitness().reformat("%5.3f").of(best()),
        hist(8).of(each(fitness())).of(all())
    ));
    Collection<List<Tree<Element>>> solutions = evolver.solve(
        Misc.cached(p.getFitnessFunction(), 10000),
        new Iterations(100),
        r,
        executorService,
        listenerFactory.build().deferred(executorService)
    );
    System.out.printf("Found %d solutions with %s.%n", solutions.size(), evolver.getClass().getSimpleName());
    listenerFactory.shutdown();
  }
}

Methods inside the constructor of TabularPrinter are static methods of the class NamedFunctions that returns functions that take an evolution Event and returns 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

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

35 tags

Packages

No packages published

Languages

  • Java 100.0%