evolution 0.1.8

An Evolutionary Algorithm library for Dart featuring Differential Evolution for projects on any platform.

Evolution

A simple to use optimization library based on evolutionary algorithms.

It can be used in both dart and flutter projects.

Getting started

Add the dependency to your pubspec.yaml file:

dependencies:
  evolution: #latest version

Add this import statement to your source files:

import 'package:evolutionSimple/evolution.dart';

To give it a try, simply run the example.

dart ./example/main.dart 

• Sphere100 is version of the sphere function with a global minimum at (100.0, ..., 100.0).
• Sphere100 (restricted) is the same problem to be solved within a restricted search space.
• Ackley10 is a version of the ackley function with a global minimum at (10.0, ..., 100.0).
• Ackley100 is a version of the ackley function with a global minimum at (100.0, ..., 100.0).
• Ackley100 (restricted) is the same problem to be solved within a restricted search space.

Differential Evolution

Differential Evolution is defined as:

/// A version of Differential Evolution with unrestricted search space.
Agent diff(
  int positions, // dimensionality of the problem
  int sizeN, // number of solution candidates to be entered in each new generation 
  int bestN, // number of best solutions selected within on generation 
  int randN, // number of random solutions selected within on generation with arbitrary fitness
  int diffN, //  number of solution candidates generated by differential process in  each generation 
  int seed, // initializing the pseudo-random number generator 
  int steps, // number of generations 
  double w, // spread of mutation 
  double Function(List<double>) fitness, //
) {
  Random r = Random(seed);

  int z = 0;
  Population p0 = gp(sizeN, positions, r, fitness);

  while (z < steps) {
    double wz = w / ((z == 0 ? 1 : z)).toDouble();
  
    // selecting survivors randomly gives less fit 
    // solution a chance to improve the result in case
    // the search is trapped in a local minimum. 
    
    /*
    Population p01 = p0.copy();
    p01.shuffle(r.r);
    Population rand = p01.select(randN);
    */

    // best survivors
    Population p02 = p0.copy();
    Population p021 = p02.sorted();
    Population best = p021.select(bestN);

    // mutation
    Population p03 = p0.copy();
    Population mutated = p03.mutation(wz / 10.0);

    Population differential = mutated.differential(diffN, wz * 10.0);

    // combine candidate solutions
    Population all = Population(
        /*rand + */ best + differential,
        r,
        fitness);
    Population p8 = all.copy();
    Population p9 = p8.sorted();
    Population p10 = p9.select(sizeN);

    p0 = p10;
    z++;
  }
  Population res = p0.sorted().select(1);
  return res.first;
}

To improve performace, use a restricted search space and the corresponding version of the algorithm:

/// Version of [diff] for opitimizing with an restricted search space.
Agent diff2(
  int positions, //dimensionality of the problem
  int sizeN, // number of solution candidates to be entered in each new generation 
  int bestN, // number of best solutions selected within on generation 
  int randN, // number of random solutions selected within on generation with arbitrary fitness
  int diffN, //  number of solution candidates generated by differential process in  each generation 
  int seed, // initializing the pseudo-random number generator 
  int steps, // number of generations 
  double w, // spread of mutation 
  double Function(List<double>) fitness, // evaluation function for solution candidates
  double lower, // lower bound of the search space
  double upper, // upper bound of the search space
) {
  //int seed = DateTime.now().millisecond;
  Random r = Random(seed);

  //Agent l(int i) => Agent(List<double>.generate(10, (int i) => 0.0), r);

  int z = 0;
  Population p0 = gp(sizeN, positions, r, fitness);

  if (p0.isEmpty) throw Exception("zu kurz, aber sizeN ${sizeN}");
  while (z < steps) {
    double wz = w / ((z == 0 ? 1 : z)).toDouble();

    // selecting survivors randomly gives less fit 
    // solution a chance to improve the result in case
    // the search is trapped in a local minimum. 

    /*
    Population p01 = p0.copy();
    p01.shuffle(r.r);
    Population rand = p01.select(randN);
    */

    // best survivors
    Population p02 = p0.copy();
    Population p021 = p02.sorted();
    Population best = p021.select(bestN);

    // mutation
    Population p03 = p0.copy();
    Population mutated = p03.mutation(wz / 10.0).confined(lower, upper);

    Population differential = mutated.differential(diffN, wz * 10.0);

    // combine
    Population all = Population(
        /*rand + */ best + differential,
        r,
        fitness);
    Population p8 = all.copy();
    Population p9 = p8.sorted();
    Population p10 = p9.select(sizeN);

    p0 = p10;
    z++;
  }
  Population res = p0.sorted().select(1);
  return res.first;
}

Evolutionary Algorithms

Evolutionary algorithms [EA] optimize a problem iteratively by trying to improve a candidate solution stochastically with regard to a given measure of quality. An EA maintains a population of candidate solutions and creates new candidate solutions by mutation and recombination from existing ones keeping whichever candidate solution has the best score or fitness on the optimization problem. EAs make few assumptions about the problem being optimized except for restricting the search space of candidate solutions. In this way the optimization problem is treated as a black box that merely provides a measure of quality given a candidate solution in terms of its fitness and the gradient of the problem function is therefore not needed.

EAs can be used for multidimensional real-valued functions but does not use the gradient of the problem being optimized, which means they do not require the optimization problem to be differentiable, as is required by classic optimization methods such as gradient descent and quasi-newton methods. They can therefore also be used on optimization problems that are not even continuous, are noisy, change over time, etc. EAs do not guarantee an optimal solution is ever found.