Multi-Objective Evolutionary Algorithms in Spark

spark-opt-moea

https://github.com/chen0040/spark-opt-moea

Spark implementation of Multi-Objective Evolutionary Computation Framework for Distributed Computing Numerical Optimization

Features

The distributed optimization is performed so that computationally intensive optimization cost evaluation can be distributed in a computing cluster via Spark.

The following Multi-Objective EA are supported:

• NSGA-II
• GDE-3

Install

Add the follow dependency to your POM file:

<dependency>
  <groupId>com.github.chen0040</groupId>
  <artifactId>spark-opt-moea</artifactId>
  <version>1.0.1</version>
</dependency>

Usage

NSGA-II for solving NDND 2-Objective Problem

The following sample code shows how to use NSGA-II to solve the NDND 2-objective optimization problem:

SparkNSGAII algorithm = new SparkNSGAII();
algorithm.setCostFunction((CostFunction) (x, objective_index, lowerBounds, upperBounds) -> {
 double f1 = 1 - Math.exp((-4) * x.get(0)) * Math.pow(Math.sin(5 * Math.PI * x.get(0)), 4);
 if (objective_index == 0)
 {
    // objective 0
    return f1;
 }
 else
 {
    // objective 1
    double f2, g, h;
    if (x.get(1) > 0 && x.get(1) < 0.4)
       g = 4 - 3 * Math.exp(-2500 * (x.get(1) - 0.2) * (x.get(1) - 0.2));
    else
       g = 4 - 3 * Math.exp(-25 * (x.get(1) - 0.7) * (x.get(1) - 0.7));
    double a = 4;
    if (f1 < g)
       h = 1 - Math.pow(f1 / g, a);
    else
       h = 0;
    f2 = g * h;
    return f2;
 }
});
algorithm.setDimension(2);
algorithm.setObjectiveCount(2);
algorithm.setLowerBounds(Arrays.asList(0.0, 0.0));
algorithm.setUpperBounds(Arrays.asList(1.0, 1.0));

algorithm.setPopulationSize(1000);
algorithm.setMaxGenerations(100);
algorithm.setDisplayEvery(10);

JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");
NondominatedPopulation pareto_front = algorithm.solve(context);

'pareto_front' is a set of solutions that represents that best solutions found by the algorithm (i.e. the pareto front).

To access individual solution in the pareto front:

for(int i=0; i < pareto_front.size(); ++i) {
   Solution solution = pareto_front.get(i);
}

To visualize the pareto front:

List<TupleTwo<Double, Double>> pareto_front_data = pareto_front.front2D();
ParetoFront chart = new ParetoFront(pareto_front_data, "Pareto Front");
chart.showIt(true);

GDE-3 for solving NDND 2-Objective Problem

The following sample code shows how to use GDE-3 to solve the NDND 2-objective optimization problem:

SparkGDE3 algorithm = new SparkGDE3();
algorithm.setCostFunction((CostFunction) (x, objective_index, lowerBounds, upperBounds) -> {
 double f1 = 1 - Math.exp((-4) * x.get(0)) * Math.pow(Math.sin(5 * Math.PI * x.get(0)), 4);
 if (objective_index == 0)
 {
    // objective 0
    return f1;
 }
 else
 {
    // objective 1
    double f2, g, h;
    if (x.get(1) > 0 && x.get(1) < 0.4)
       g = 4 - 3 * Math.exp(-2500 * (x.get(1) - 0.2) * (x.get(1) - 0.2));
    else
       g = 4 - 3 * Math.exp(-25 * (x.get(1) - 0.7) * (x.get(1) - 0.7));
    double a = 4;
    if (f1 < g)
       h = 1 - Math.pow(f1 / g, a);
    else
       h = 0;
    f2 = g * h;
    return f2;
 }
});
algorithm.setDimension(2);
algorithm.setObjectiveCount(2);
algorithm.setLowerBounds(Arrays.asList(0.0, 0.0));
algorithm.setUpperBounds(Arrays.asList(1.0, 1.0));

algorithm.setPopulationSize(100);
algorithm.setMaxGenerations(50);
algorithm.setDisplayEvery(10);

JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");
NondominatedPopulation pareto_front = algorithm.solve(context);

List<TupleTwo<Double, Double>> pareto_front_data = pareto_front.front2D();

ParetoFront chart = new ParetoFront(pareto_front_data, "Pareto Front for NDND");
chart.showIt(true);

Regex Generator in Spark

spark-ml-regex-generator

https://github.com/chen0040/spark-ml-regex-generator

Spark implementation that takes a set of texts and use genetic programming which discover regex for grok that will match other similar texts

Install

Add the following dependency to your POM file:

<dependency>
  <groupId>com.github.chen0040</groupId>
  <artifactId>spark-ml-regex-generator</artifactId>
  <version>1.0.1</version>
</dependency>

Usage

The sample code below shows how the gp regex cultivator discover the regex for the message "":

GpCultivator generator = new GpCultivator();
      generator.setDisplayEvery(2);
      generator.setPopulationSize(1000);
      generator.setMaxGenerations(50);

List<String> trainingData = new ArrayList<>();
trainingData.add("user root login at 127.0.0.1");

JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");
Grok generated_grok = generator.fit(context.parallelize(trainingData));

System.out.println("user root login at 127.0.0.1");
System.out.println(generator.getRegex()); // this is the regex generated


Match matched = generated_grok.match("user root login at 127.0.0.1");
matched.captures();
System.out.println(matched.toJson());

Below is the print out from the sample code above:

...
Generation: 4 (Pop: 1000), elapsed: 3 seconds
Global Cost: 0.2 Current Cost: 0.2
...
Global Cost: 0.14285714285714285 Current Cost: 0.16666666666666666
user root login at 127.0.0.1
%{LOGLEVEL} %{USER} %{URIPROTO} %{URIHOST} %{IPV4}
{"IPORHOST":"at","IPV4":"127.0.0.1","LOGLEVEL":"er","URIHOST":"at","URIPROTO":"login","USER":"root"}

Genetic Programming in Spark

spark-ml-genetic-programming

https://github.com/chen0040/spark-ml-genetic-programming

Package provides java implementation of big-data genetic programming for Apache Spark

Install

Add the following dependency to your POM file:

<dependency>
  <groupId>com.github.chen0040</groupId>
  <artifactId>spark-ml-genetic-programming</artifactId>
  <version>1.0.5</version>
</dependency>

Features

• Linear Genetic Programming
  • Initialization
    • Full Register Array
    • Fixed-length Register Array
  • Crossover
    • Linear
    • One-Point
    • One-Segment
  • Mutation
    • Micro-Mutation
    • Effective-Macro-Mutation
    • Macro-Mutation
  • Replacement
    • Tournament
    • Direct-Compete
  • Default-Operators
    • Most of the math operators
    • if-less, if-greater
    • Support operator extension
• Tree Genetic Programming
  • Initialization
    • Full
    • Grow
    • PTC 1
    • Random Branch
    • Ramped Full
    • Ramped Grow
    • Ramped Half-Half
  • Crossover
    • Subtree Bias
    • Subtree No Bias
  • Mutation
    • Subtree
    • Subtree Kinnear
    • Hoist
    • Shrink
  • Evolution Strategy
    • (mu + lambda)
    • TinyGP

Future Works

• Grammar-based Genetic Programming
• Gene Expression Programming

Usage of Linear Genetic Programming

Create training data

The sample code below shows how to generate data from the "Mexican Hat" regression problem. We can split the data generated into training and testing data:

import com.github.chen0040.gp.utils.CollectionUtils;

List<BasicObservation> data = Tutorials.mexican_hat().stream().map(s -> (BasicObservation)s).collect(Collectors.toList());
CollectionUtils.shuffle(data);
TupleTwo<List<BasicObservation>, List<BasicObservation>> split_data = CollectionUtils.split(data, 0.9);
List<BasicObservation> trainingData = split_data._1();
List<BasicObservation> testingData = split_data._2();

Create and train the LGP

The sample code below shows how the SparkLGP can be created and trained:

import com.github.chen0040.gp.lgp.LGP;
import com.github.chen0040.gp.commons.BasicObservation;
import com.github.chen0040.gp.commons.Observation;
import com.github.chen0040.gp.lgp.gp.Population;
import com.github.chen0040.gp.lgp.program.operators.*;

SparkLGP lgp = new SparkLGP();
lgp.getOperatorSet().addAll(new Plus(), new Minus(), new Divide(), new Multiply(), new Power());
lgp.getOperatorSet().addIfLessThanOperator();
lgp.addConstants(1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0);
lgp.setRegisterCount(6); // the number of register here is the number of input dimension of the training data times 3
lgp.setPerObservationCostEvaluator((Function<Tuple2<Program, BasicObservation>, Double>) tuple2 -> {
 Program program = tuple2._1();
 BasicObservation observation = tuple2._2();
 program.execute(observation);
 return Math.pow(observation.getOutput(0) - observation.getPredictedOutput(0), 2.0);
});
lgp.setDisplayEvery(2); // display iteration result every 2 iterations


JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");
Program program = lgp.fit(context.parallelize(trainingData)); 
System.out.println(program);

The number of registers of a linea program is set by calling LGP.setRegisterCount(...), the number of registers is usually the a multiple of the input dimension of a training data instance. For example if the training data has input (x, y) which is 2 dimension, then the number of registers may be set to 6 = 2 * 3.

The cost per observation evaluator computes the training cost of a 'program' on a particular 'observation' (which is an instance of trainingData).

The last line prints the linear program found by the LGP evolution, a sample of which is shown below:

instruction[1]: <If< r[4] c[0] r[4]>
instruction[2]: <If< r[3] c[3] r[0]>
instruction[3]: <- r[2] r[3] r[2]>
instruction[4]: <* c[7] r[2] r[2]>
instruction[5]: <If< c[2] r[3] r[1]>
instruction[6]: </ r[1] c[4] r[2]>
instruction[7]: <If< r[3] c[7] r[1]>
instruction[8]: <- c[0] r[0] r[0]>
instruction[9]: <If< c[7] r[3] r[4]>
...

Test the program obtained from the LGP evolution

The best program in the LGP population obtained from the training in the above step can then be used for prediction, as shown by the sample code below:

for(Observation observation : testingData) {
 program.execute(observation);
 double predicted = observation.getPredictedOutput(0);
 double actual = observation.getOutput(0);

 logger.info("predicted: {}\tactual: {}", predicted, actual);
}

Usage of Tree Genetic Programming

Here we will use the "Mexican Hat" symbolic regression introduced earlier.

Create and train the TreeGP

The sample code below shows how the TreeGP can be created and trained:

import com.github.chen0040.gp.treegp.TreeGP;
import com.github.chen0040.gp.commons.BasicObservation;
import com.github.chen0040.gp.commons.Observation;
import com.github.chen0040.gp.treegp.gp.Population;
import com.github.chen0040.gp.treegp.program.operators.*;

SparkTreeGP tgp = new SparkTreeGP();
tgp.getOperatorSet().addAll(new Plus(), new Minus(), new Divide(), new Multiply(), new Power());
tgp.getOperatorSet().addIfLessThanOperator();
tgp.addConstants(1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0);
tgp.setVariableCount(2); //equal to the number of input dimension of the training data
tgp.setPerObservationCostEvaluator(tuple2 -> {
 Solution program = tuple2._1();
 BasicObservation observation = tuple2._2();
 program.execute(observation);
 return Math.pow(observation.getOutput(0) - observation.getPredictedOutput(0), 2.0);
});
tgp.setDisplayEvery(2); // display iteration result every 2 iterations

JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");
Solution program = tgp.fit(context.parallelize(trainingData));  

The cost per observation evaluator computes the training cost of a 'program' on a particular 'observation' (which is an instance of trainingData).

The program.mathExpress() call prints the TreeGP program found by the TreeGP evolution, a sample of which is shown below:

Trees[0]: 1.0 - (if(1.0 < if(1.0 < 1.0, if(1.0 < v0, 1.0, 1.0), if(1.0 < (v1 * v0) + (1.0 / 1.0), 1.0 + 1.0, 1.0)), 1.0, v0 ^ 1.0))

Test the program obtained from the TreeGP evolution

The best program in the TreeGP population obtained from the training in the above step can then be used for prediction, as shown by the sample code below:

for(Observation observation : testingData) {
 program.execute(observation);
 double predicted = observation.getPredictedOutput(0);
 double actual = observation.getOutput(0);

 logger.info("predicted: {}\tactual: {}", predicted, actual);
}