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 Java

java-regex-cultivator

https://github.com/chen0040/java-regex-cultivator

Regex generator which use genetic programming to evolve grok and automatically discover regex given a set of texts having similar structure.

Install

Add the following dependency to your POM file:

<dependency>
  <groupId>com.github.chen0040</groupId>
  <artifactId>java-regex-cultivator</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");
Grok generated_grok = generator.fit(trainingData); // this is the grok interpreter generated

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"}

Multi-Objective Genetic Programming in Java

java-mogp

https://github.com/chen0040/java-mogp

Genetic Programming Framework that supports Multi-Objective Optimization

Install

Add the following dependency to your POM file:

<dependency>
  <groupId>com.github.chen0040</groupId>
  <artifactId>java-mogp</artifactId>
  <version>1.0.3</version>
</dependency>

Usage

The sample code belows show tree-gp based multi-objective optimization which minimizes the following two objectives:

1. the mean square errors in predicting the "Mexican Hat" symbolic regression problem
2. the average tree depth of the tree-gp program generated.

List<Observation> data = Tutorials.mexican_hat();
CollectionUtils.shuffle(data);
TupleTwo<List<Observation>, List<Observation>> split_data = CollectionUtils.split(data, 0.9);
List<Observation> trainingData = split_data._1();
List<Observation> testingData = split_data._2();

NSGPII tgp = NSGPII.defaultConfig();
tgp.setVariableCount(2); // the number of variables is equal to the input dimension of an observation in the "data" list
tgp.setCostFunction((CostFunction) (solution, mogpgpConfig) -> {
 List<Observation> observations = gpConfig.getObservations();
 double error = 0;
 for(Observation observation : observations){
    solution.execute(observation);
    error += Math.pow(observation.getOutput(0) - observation.getPredictedOutput(0), 2.0);
 }

 double cost1 = error;
 double cost2 = solution.averageTreeDepth();

 return Arrays.asList(cost1, cost2);
});
tgp.setMaxGenerations(50);
tgp.setPopulationSize(500);

tgp.setDisplayEvery(2); // diplay the iteration result for every 2 iterations
NondominatedPopulation pareto_front = tgp.fit(trainingData);
System.out.println("pareto_front: " + pareto_front.size());

The number of variable of a tree-gp program is set by calling NSGPII.setVariableCount(...), the number of variables is equal to the input dimension of the problem to be solved. In the case of "Mexican Hat" symbolic regression, the input is (x, y), therefore,the number of variables is 2.

The cost evaluator computes two objectives. The first objective is the training cost of a tree-gp 'program' on the 'observations' (which is the symbolic regression trainingData), the second objective is the average depth of the tree-gp 'program'.

Test the programs in the pareto front obtained from the TreeGP evolution

Once the pareto front for the MOGP is obtained, we can access each solution in the pareto front, just like the code below:

MOOGPSolution solution = (MOOGPSolution)pareto_front.get(0);
Solution program = solution.getGp();

These two line returns the tree-gp program associated with the first solution on the pareto-front obtained.

Calling program.mathExpression() will returns the math expression representing the gp program, 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))

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);
}

Display the Pareto Front

The following code shows how to display the pareto front generated from MOGP:

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

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

Multi-Objective Evolutionary Algorithms in Java

java-moea

https://github.com/chen0040/java-moea

An optimization framework for multi-objective evolutionary algorithms

 

Features

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>java-moea</artifactId>
  <version>1.0.5</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:

NSGAII algorithm = new NSGAII();
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);

NondominatedPopulation pareto_front = algorithm.solve();

'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:

GDE3 algorithm = new GDE3();
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);

NondominatedPopulation pareto_front = algorithm.solve();

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

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