Tutorial

This tutorial describes basic principles of EvoJ usage. For more complex details please refer to the technical guide.

Note for Maven users

In order to add EvoJ to your project you need to add following sections to your pom.xml file.

A repository:

And the dependency:

Minimum of a function

For the beginning we will find a minimum of a function: Z(x, y)=12 * x2 + 8 * x + 9 * y2. The basic approach of using EvoJ consists of two steps:

  1. Declare Java Interface describing solution to your problem.
  2. Define the way to distinguish between good and bad solutions

The solution to the problem in question is simply two floating point numbers, therefore we will declare our solution-interface as:

public interface Solution {

    @Range(min = "-10", max = "10")
    double getX();

    @Range(min = "-10", max = "10")
    double getY();
}

Here we simply declare interface describing two double typed properties - x and y. Note the @Range annotations which influence range of initial values of properties. Please also note that values of annotation attributes min and max are strings, this allows to specify property names instead of concrete values, and change property values at runtime. There are other annotations influencing various aspects of evolutionary algorithm, these annotations are described in the technical guide.

Next we need to define a mechanism to distinguish between bad and good solutions. The most frequently used technique is to define a fitness function - in terms of EvoJ to implement SolutionRating interface. This interface is declared as:

public interface SolutionRating<T> {

    Comparable calcRating(T solution);

}

The contract of the only method of this interface is to return rating of the given solution as a Comparable value: the better solution - the bigger the returned Comparable should be.

For our problem the natural rating of the solution is the value of the function itself - with the only exclusion - we search for the minimum, hence the rating will be calculated as -Z(x, y).

It is recommended to implement the SolutionRating interface not directly but by extending the helper class AbstractSimpleRating which deals with common corner cases of evolutionary algorithm (please refer to technical guide for details).

public class Rating extends AbstractSimpleRating<Solution, Double> {

    public static double calcFunction(Solution solution) {
        double x = solution.getX();
        double y = solution.getY();
        return 12 * x * x + 8 * x + 9 * y * y;
    }

    @Override
    public Double doCalcRating(Solution solution) {
        double fn = calcFunction(solution);
        if (Double.isNaN(fn)) {
            return null;
        } else {
            return -fn;
        }
    }
}

The code here is self explanatory, the only thing to notice here is that null is a valid value for rating. The solutions having null-rating will be placed at the end of the list for replication.

Now as we have all preparations in place we can write following code:

DefaultPoolFactory pf = new DefaultPoolFactory();
GenePool<Solution> pool = pf.createPool(200, Solution.class, null);
DefaultHandler handler = new DefaultHandler(new Rating(), null, null, null);

handler.iterate(pool, 200);
Solution solution = pool.getBestSolution();

Let's go through this code line by line.

Since there is no implementation for our solution interface we cannot instantiate an array of solutions directly - we need a special factory class for that purpose. And first of all we create that factory:

DefaultPoolFactory pf = new DefaultPoolFactory();

Then we use just created factory to create a GenePool object which is merely a list of solutions with various values of variables.

GenePool<Solution> pool = pf.createPool(200, Solution.class, null);

This line creates a GenePool containing 200 instances of Solution interface filled with random values placed within range specified by annotations. The last parameter in this invocation is a Map describing context properties, which we do not touch in this tutorial.

Next we need to create an object which will perform iterations of evolutionary algorithm over our GenePool.

DefaultHandler handler = new DefaultHandler(new Rating(), null, null, null);

Constructor of DefaultHandler accepts parameters representing strategies influencing various stages of evolutionary iterations: selection, replication and mutation. All these have default implementations that's why the only not null parameter here is our implementation of rating calculation strategy.

Next we instruct the DefaultHandler to perform 200 iterations of evolutionary algorithm over our GenePool.

handler.iterate(pool, 200);

Since our problem is quite simple 200 iterations is most likely enough to get close the right solution. Which we obtain in the last line.

Solution solution = pool.getBestSolution();

The harder problems may need hundreds of thousands or even millions of iterations.

Image approximation

Let's move to more complex example demonstrating the power of EvoJ. For this time we are going to write program which would approximate raster images with set of polygons.

As in previous example, first we need to declare a solution interface, or in our case it will be a set of interfaces describing polygons, points and colors.

public interface PolyPicture {

    @ListParams(length = "50")
    List<Polygon> getPolygons();
}

public interface Polygon {

    Colour getColor();

    @ListParams(length = "8")
    List<Point> getPoints();
}

public interface Point {

    @Range(min = "-5", max = "325", strict = "true")
    float getX();

    @Range(min = "-5", max = "245", strict = "true")
    float getY();

    void setX(float x);

    void setY(float y);
}

public interface Colour {

    @MutationRange("0.2")
    @Range(min = "0", max = "1", strict = "true")
    float getRed();

    @MutationRange("0.2")
    @Range(min = "0", max = "1", strict = "true")
    float getGreen();

    @MutationRange("0.2")
    @Range(min = "0", max = "1", strict = "true")
    float getBlue();

    void setRed(float red);

    void setGreen(float green);

    void setBlue(float blue);

}

As you might have noticed, the solution can be described as set of nested interfaces. There other things to learn from the example above.

First of all it's the strict option of the @Range annotation. This option ensures that the annotated property will not exceed the prescribed range, neither during mutation, nor due to direct setter method invocation.

Next new thing here is the @MutationRange annotation which is meant to limit the area in which the corresponding property can change within single act of mutation.

One more important annotation is @ListParams which is intended to describe List properties. Length of List properties must be specified, otherwise EvoJ will be unable to calculate amount of memory it would need to reserve for corresponding property.

Next we need to decide how we will calculate the rating of the solution. The obvious criterion is the sum of squares of pixel component differences between original image and the image drawn using polygons from the solution. The ideal rating therefore would be 0. Since we need to maintain contract of SolutionRating interface, where higher values correspond to better solutions, we will negate sum of errors.

public class DemoRating extends AbstractSimpleRating<PolyPicture, Long> {

    private BufferedImage originalImage;

    public DemoRating(BufferedImage pImg) {
        this.originalImage = new BufferedImage(320, 240, BufferedImage.TYPE_3BYTE_BGR);
        originalImage.getGraphics().drawImage(pImg, 0, 0, 320, 240, null);
    }

    @Override
    protected Long doCalcRating(PolyPicture picture) {
        BufferedImage img = drawPicture(picture);
        int[] originalPix = getPixels(originalImage);
        int[] testPix = getPixels(img);
        return -calcError(originalPix, testPix);
    }

    private BufferedImage drawPicture(PolyPicture picture) {
        BufferedImage result = new BufferedImage(320, 240, BufferedImage.TYPE_3BYTE_BGR);
        Graphics2D graphics = result.createGraphics();
        drawPolygons(graphics, picture.getPolygons());
        graphics.dispose();
        return result;
    }

    private void drawPolygons(Graphics2D graphics, List<Polygon> polygons) {
        for (Polygon poly : polygons) {
            List<Point> points = poly.getPoints();
            int x[] = new int[points.size()];
            int y[] = new int[points.size()];
            for (int i = 0; i < points.size(); i++) {
                final Point point = points.get(i);
                x[i] = (int) point.getX();
                y[i] = (int) point.getY();
            }
            Colour clr = poly.getColor();
            graphics.setColor(new Color(clr.getRed(), clr.getGreen(), clr.getBlue(), 0.5f));
            graphics.fillPolygon(x, y, x.length);
        }
    }

    private int[] getPixels(BufferedImage img) {
        return img.getRaster().getPixels(0, 0, img.getWidth(), img.getHeight(), (int[]) null);
    }

    private Long calcError(int[] originalPix, int[] testPix) {
        long result = 0;
        for (int i = 0; i < originalPix.length; i++) {
            int diff = originalPix[i] - testPix[i];
            result += diff * diff;
        }
        return result;
    }
}

The class above draws all the polygons from the solution with 50% opacity, then takes pixels from both original and new image and calculates the sum of squared component differences.

Let's use above mentioned classes.

DefaultPoolFactory factory = new DefaultPoolFactory();
GenePool<PolyPicture> pool = factory.createPool(40, PolyPicture.class, null);
DemoRating rating = new DemoRating(PICTURE_TO_APPROX);
MultithreadedHandler handler = new MultithreadedHandler(2, rating, null, null, null);

handler.iterate(pool, 1000);

handler.shutdown();

The code you can see above resembles the code from the first example, but with one important difference - we used MultithreadedHandler instead of DefaultHandler. The MultithreadedHandler class does the same things as DefaultHandler, but as it results from it's name it does evolutionary calculations in parallel threads for better performance. In our example 2 threads are used, however you can specify any reasonable number of thread (usually equal to number of threads your system can execute in parallel).

In fact this example is just a draft, because image approximation problem is not that simple as finding a minimum of a functions. There are many optimizations to be done in order to increase the speed of image drawing, and to improve the effectiveness of evolutionary computations. These optimizations deserve writing of a dedicated article and for simplicity of explanations are omitted here.

However, even this simple code will approximate given image after several hundreds of thousands of iterations (this might take several hours or days depending on performance of your system).

Events

05 May 2015
Java 8 compatibility fix 3.0.1 released
16 February 2013
Major EvoJ 3.0 released!!! Please review the Release notes .
29 October 2012
EvoJ 2.4 released! The release contains massive change set. Please read the Release notes .
16 June 2012
EvoJ 2.3 released! Please read the Release notes .