evolution 0.1.11

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

Evolution

An optimization library based on evolutionary algorithms for use in dart and flutter projects.

Getting started

Add the dependency to your pubspec.yaml file:

dependencies:
  evolution: #latest version

Add the import statement to your source files:

import 'package:evolution/evolution.dart' ;

Or, give it a try and run the example:

dart ./example/main.dart 

The example consists of some simple optimization tasks:

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

It will run 10 trials of the same problem, printing the number of the trial , the fitness value [f] (small is better) and the solution [ag] represented by an Agent.

Build a simple algorithm

1. Generate an initial population of candidate solutions (Agents), each of which will have property values of 0.0:

Population start = generatePopulation(
    sizeN, // number of [Agent]s in the population
    positions, // number of variables, i.e dimensionality of the problem
    Random(seed), // pass a random number generator object to the Population
    fitness, // gibe each Agents an evaluation function
  );

2. Mutate the population. You can specify a weight factor to control the impact of mutation.

Population mutated = start.mutation();

Instead, you can use the imperative version:

Population mutated = start.mutationI();

3. Generate a differential population of size [diffN].

Population differential = mutated.differential(diffN);

4. Select a portion of the population of [sizeN] as survivors.

Population selected = differential.sorted().select(sizeN);

Instead, you can use the imperative version:

Population selected = differential.sortedI().selectI(sizeN);

5. Loop!

Try the Differential Evolution algorithm

A more specific algorithm is Differential Evolution. It is defined as:

/// A version of Differential Evolution with unrestricted search space.
Agent diff(
  int positions, // number of variables, i.e dimensionality of the problem
  int sizeN, // number of [Agent]s in the population
  int bestN, // number of [Agent]s selected by fitness
  int randN, // number of [Agent]s randomly selected
  int diffN, // number of [Agent]s generated by differential evolution
  int seed, // seeding the random number generator
  int steps, // number of generations
  double w, // weighting factor used in differential evolution
  double Function(List<double>) fitness, // evaluation function
) {
  Random r = Random(seed);

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

  while (z < steps) {
    double wz = w / ((z == 0 ? 1 : z)).toDouble();
    
    // best survivors
    Population best = p0.sorted().select(bestN);

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

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

    // combine subpopulations
    Population all = Population(
        best + differential,
        r,
        fitness);

    // best survivors of combined population
    Population result = all.sorted().select(sizeN);

    p0 = result;
    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:

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
) {
  Random r = Random(seed);

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

  while (z < steps) {
    double wz = w / ((z == 0 ? 1 : z)).toDouble();

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

    // mutation
    Population mutatedConfined = p0.mutation(wz / 10.0).confined(lower, upper);

    // differential operation
    Population differential = mutatedConfined.differential(diffN, wz * 10.0);

    // combine subpopulations
    Population all = Population(
        best + differential,
        r,
        fitness);

    // best survivors of combined population
    Population result = all.sorted().select(sizeN);

    p0 = result;
    z++;
  }

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