In jakobbossek/ecr3: Evolutionary Computation in R - Version 3

ecr3: Evolutionary Computation in R - Version 3

NOTE: Under heavy development

Introduction

Evolutionary Algorithms (EAs) are general purpose problem solvers that show astonishing performance when applied to complex real-world black-box problems or hard (combinatorial) optimization problems. The key idea is to mimick the widely successful processes of natural evolution like genetic recombination, mutation and the famous survival of the fittest principle. These principles are transfered to the algorithmic domain. Basically and EA maintains a multi-set of candidate solutions, termed the population, and iteratively generates new candidate solutions by applying stochastic operators to a subset of the population. Each solution is assigned a fitness value which inidcates its quality in he respective domain. The current population and the generated offspring solutions are than ranked by fitness values with better ranked solutions having a higher probability to survive and form the populaion of he next generation.

ecr3 (short for evolutionary computation in R - version 3) is a framework/toolkit for rapid prototyping of evolutionary algorithms int the statistical programming language R. In contrast to many other existing solutions (see section on related software below) the toolkit has a strong focus on a so-called white-box approach where the user is asked to write the evolutionary loop by hand adopting the many provided light-weight helpers functions of ecr3 rather than calling a single bloated function with tons of parameters. The reason behind that is that -- despite the intrinsic simplicity of EAs on a first glance -- there exists a plethora of adaptable, adjustable setting screws within the generic evolutionary algorithm framework that can never be coded into a single function.

The ecr package is heavily inspired by the amazing python package DEAP and borrows a lot of ideas from the latter.

Features

ecr3 is designed as a generic framework for rapid prototyping of evolutionary algorithms in the statistical programming language R. Rather than offering a single, highly parameterizable function which is limited to special problem cases and also stronlgy limited in flexibility and extensibility, ecr3 instead provides a significant number of light-weight domain-specific helper functions, evolutionary opertators and R6 classes. Users are encouraged to use these utilities to implement their problem-specific evolutionary algorithms, i.e., to "write the evolutionary loop by hand". Even though this seems like a major drawback, in fact is is the other way around since it offers a flexibility which is not achievable by any black-box approach.

The key features of ecr3 are: Arbitrary representations genotypes (individuals are stored in lists and hence can be realized as arbitrary R objects, e.g., numeric vectors, bit strings, matrizes or lists of objects). Not limited to single-objective optimization scenarios. The scope is on single- and multi-objective optimization (2 or 3 objectives), but many-objective optimization (> 3 objectives) can be realized too. Rich set of common evolutionary variation operators for standard representations (binary strings, real-valued vectors and permutations). Multiple selection operators (single- and multi-objective), e.g., fitness-proportinal selection, random selection, NSGA-II selection, indicator-based selection, ... Possibility to easily write custom operators and representations. Powerful logging functionality (logging statistics, logging populations, ...) Parallelization with the future package. Rich set of performance assessment methods (graphical, quantitative) for the comparisson of the results of multi-objective (stochastic) optimization algorithms. Extensive documentation in terms of vignettes for different tasks. For standard tasks: easy plug-n-play style function ecr3::ecr(...) which expects a fitness function, a bunch of EA parameters (population size etc.), a set of operators and returns a nicely wrapped results. * Benchmark function for quick assessment of multiple algorithms on multiple test functions.

Simple Quickstart Example

In the following we demonstrate how to build a simple mutation-based EA to optimize the Pseudo-boolean function ONEMAX which counts the number of ones in a bistring of length n, i.e., the optimum is obviously the all-ones bit-string. We first define the fitness function that guides the evolutionary search.

library(ecr3)
library(ggplot2)

fitness.fn = function() sum(x)

Next, we create an instance of the R6 class EAControl which stores most of the information which is relevant for the optimization and offers a large set of methods to apply those utilities. Here, we decide for a simple (10+1)-EA with simple bitflip mutation with mutation probability 1/n, k-tournament mating selection with k = 3 and greedy survival selection, i.e., the 10 best out of 11 individuals go over to the next generation.

mu = 10 # population size
lambda = 1 # number of offspring generated in each generation
n = 50 # dimension of the problem (ONEMAX on n bits)
max.iter = floor(10 * n * log(n)) # number of iterations (stopping condition)

# control object
control = EAControl$new(fitness.fn, n.objectives = 1L,
  minimize = TRUE, genotype = "binary")$
  register("generate", EAGeneratorBinary(n = mu, d = n))$
  register("mutate", EAMutatorBitflip(p = 1/n))$
  register("selectForMating", EASelectorTournament(k = 3))$
  register("selectForSurvival", EASelectorGreedy())

Next, we define statistics to be logged. We want to log the iteration-wise minimum, maximum and standard deviation of the populations fitness values.

stats = EAStatistics$new()$
  register("fitness", group = "y", funs = list("min", "max", "sd"))

Finally we instantiate our evolutionary algorithm:

myEA = EA$new(control, pm = 1, mu = mu, lambda = lambda, stats = stats, algo.name = "myEA", strategy = "plus",
  terminators = list(EATerminatorIterations(max.iter)))

Next, we run the algorithm 10 times independently and plot the optimization trajectories (minimal fitness-values per iteration).

res = myEA$run(10)
lb  = res$getLogbook()
print(plotLogbook(lb, y = "y.min"))

This example just scratches the surface of things ecr3 is capable of. See the inst/examples folder or the various package vignettes for more and in particular more sophisticated / in-depth examples.

Related Software

ecr3 is the official successor of ecr, which offers similar functionality. Within the R environment, the following packages have a similar aim as ecr3 has:

• [GA] Nice, flexible and R-like general-purpose toolbox for genetic algorithms. Limited to the single-objective setting and standard representations (binary, real-valued and permutation) though.
• [mco] Some multi-objective test functions and a collection of functions to work with results of multi-objective optimization algorithms. The package also features a very fast implementation of the NSGA-II algorithm.
• [emoa] Toolkit for the design and analysis of evolutionary multi-objective algorithms.
• [MOEADr] Modular, component-wise implementation of multi-objective decomposition-based evolutionary multi-objective algorithms (MOEA/D).

The following R packages implementat specific evolutionary algorithms, but do aim to provide a generic toolkit:

• [cmaes, cmaesr] Pure R implementation(s) of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES).
• [DEoptim] Differential evolution algorithm for global optimization of a real-valued function of a real-valued parameter vector.
• [MaOEA] A set of evolutionary algorithms to solve many-objective optimization.

Evolutionary algorithm toolkits exists in many programming languages. Some prominent examples are listed below:

• [DEAP] Distributed Evolutionary Algorithms in Python is a EC framework for rapid prototyping and testing of ideas. DEAP is the blueprint for ecr. In fact the latter borrows many ideas from DEAP.
• [ParadisEO-MOEO] C++ framework for modular multi-objective evolutionary algorithms.

Development Team

The package is a one-man project by Jakob Bossek at the moment of writing. However, the package interfaces some neat implementations of various other people (see DESCRIPTION file for details).

How to contribute?

You can contribute by identifing annoying bugs in the issue tracker. This is also the preferred place to ask questions and raise feature requests. Moreover, users can contribute even more by forking the ecr3 repository, implementing feautures or bugfixes and raising a pull request.

Installation Instructions

The package will be available at CRAN when it is done. If you are interested in trying out and playing around with the current github developer version use the devtools package and type the following command in R:

remotes::install_github("jakobbossek/ecr3")

Getting help

Please address questions and missing features about the ecr3 as weell as annoying bug reports in the issue tracker. Pay attention to explain your problem as good as possible. At its best you provide an example, so I can reproduce your problem quickly. Please avoid sending e-mails.

jakobbossek/ecr3 documentation built on Nov. 14, 2019, 7:47 p.m.