How to apply test functions to genetic algorithm

Question

I have written following code for population evolution (Genetic Algorithm Implementation):

Individual.java

import java.util.Random;

public class Individual {

    public static int SIZE = 500;
    private int[] genes = new int[SIZE];
    private double fitnessValue = 0.0;


    // Getters and Setters
    public void setGene(int index,int gene){
        this.genes[index] = gene;
    }

    public int getGene(int index){
        return this.genes[index];
    }

    public void setFitnessValue(double fitness){
        this.fitnessValue = fitness;
    }

    public double getFitnessValue(){
        return this.fitnessValue;
    }

    //Function to generate a new individual with random set of genes
    public void generateIndividual(){
        Random rand = new Random();
        for(int i=0;i<SIZE;i++){
            this.setGene(i, rand.nextInt(2));
        }
    }

    //Mutation Function
    public void mutate(){
        Random rand = new Random();
        int index = rand.nextInt(SIZE);
        this.setGene(index, 1-this.getGene(index)); // Flipping value of gene 
    }

    //Function to set Fitness value of an individual
    public int evaluate(){

        int fitness = 0;
        for(int i=0; i<SIZE; ++i) {
            fitness += this.getGene(i);
        }
        this.setFitnessValue(fitness);
        return fitness;
    }

}

Population.java

import java.util.Random;

public class Population {

    final static int ELITISM = 5;
    final static int POP_SIZE = 200+ELITISM; //Population size + Elitism (1)
    final static int MAX_ITER = 10000;
    final static double MUTATION_RATE = 0.05;
    final static double CROSSOVER_RATE = 0.7;
    public static int generation = 2;

    private static Random rand = new Random(); 
    private double totalFitness;
    private  Individual[] pop;

    //Constructor
    public Population(){
        pop = new Individual[POP_SIZE];
        //Initialising population
        for(int i=0;i<POP_SIZE;i++){
            pop[i] = new Individual();
            pop[i].generateIndividual();

        }
        //Evaluating current population
        this.evaluate();
    }

    //Storing new generation in population
    public void setPopulation(Individual[] newPop) {
        System.arraycopy(newPop, 0, this.pop, 0, POP_SIZE);
    }


    //Method to find total fitness of population
    public double evaluate(){
        this.totalFitness = 0.0;
        for (int i = 0; i < POP_SIZE; i++) {
            this.totalFitness +=  pop[i].evaluate();
        }


       return this.totalFitness;
    }


    //Getters
    public Individual getIndividual(int index) {
        return pop[index];
    }


    //Function to find fittest individual for elitism
    public Individual getFittest() {
        Individual fittest = pop[0];
        for (int i = 0; i < POP_SIZE; i++) {
            if (fittest.getFitnessValue() <= getIndividual(i).getFitnessValue()) {
                fittest = getIndividual(i);
            }
        }
        return fittest;
    }

    //CROSSOVER Function : Takes 2 individuals and returns 2 new individuals
    public static Individual[] crossover(Individual indiv1,Individual indiv2) {
        Individual[] newIndiv = new Individual[2];
        newIndiv[0] = new Individual();
        newIndiv[1] = new Individual();
        int randPoint = rand.nextInt(Individual.SIZE);
        int i;
        for (i=0; i<randPoint; ++i) {
            newIndiv[0].setGene(i, indiv1.getGene(i));
            newIndiv[1].setGene(i, indiv2.getGene(i));
        }
        for (; i<Individual.SIZE; ++i) {
            newIndiv[0].setGene(i, indiv2.getGene(i));
            newIndiv[1].setGene(i, indiv1.getGene(i));
        }

        return newIndiv;
    }

    //Roulette Wheel Selection Function
    public Individual rouletteWheelSelection() {

        double randNum = rand.nextDouble() * this.totalFitness;
        int idx;

        for (idx=0; idx<POP_SIZE && randNum>0; idx++) {
            randNum -= pop[idx].getFitnessValue();
        }
        return pop[idx-1];
    }

    //Main method

    public static void main(String[] args) {
        Population pop = new Population();
        Individual[] newPop = new Individual[POP_SIZE];
        Individual[] indiv = new Individual[2];
        //Current Population Stats
        System.out.print("Generation #1");
        System.out.println("Total Fitness = "+pop.totalFitness);
        System.out.println("Best  Fitness = "+pop.getFittest().getFitnessValue());

        int count;
        for(int iter=0;iter<MAX_ITER;iter++){
            count =0;

                //Elitism
                newPop[count] = pop.getFittest();
                count++;

           //Creating new population
            while(count < POP_SIZE){
                //Selecting parents
                indiv[0] = pop.rouletteWheelSelection();
                indiv[1] = pop.rouletteWheelSelection();

                // Crossover
                if (rand.nextDouble() < CROSSOVER_RATE ) {
                    indiv = crossover(indiv[0], indiv[1]);
                }

                // Mutation
                if ( rand.nextDouble() < MUTATION_RATE ) {
                    indiv[0].mutate();
                }
                if ( rand.nextDouble() < MUTATION_RATE ) {
                    indiv[1].mutate();
                }

                // add to new population
                newPop[count] = indiv[0];
                newPop[count+1] = indiv[1];
                count += 2;
            }
            // Saving new population in pop
            pop.setPopulation(newPop);
            //Evaluating new population
            pop.evaluate();
            System.out.println("Generation #"+ generation++);
            System.out.print("Total Fitness = " + pop.totalFitness);
            System.out.println(" ; Best Fitness = " +pop.getFittest().getFitnessValue()); 

            }


        Individual bestIndiv = pop.getFittest();
    }

}

I have been asked to test my algorithm using following functions: https://en.wikipedia.org/wiki/Test_functions_for_optimization Test functions for single objective optimisation

Can anyone explain how it is to be done? Explanation for any one function from the list would be helpful.

Answer 1

What the genes should represent

I'll assume the implementation of your genetic algorithm is correct, as that is beyond the scope of this question.

Right now your fitness function is defined to be the sum of all of the genes:

double fitness = 0;
for(int i=0; i<SIZE; ++i) {
  fitness += this.getGene(i);
}
this.setFitnessValue(fitness);

This is a strange thing to do: let's think about an Individual witch will have a high fitness. I hope you see that there is no real optimum, Individuals will simply tend to increase each of their genes because that will archive a higher fitness.

A second problem is that the genes should represent something: what do the doubles in the gene array actually mean? Why do we care? A possible example would be to have them represent the behavior of Individuals in a simulation. That's of course a whole other topic, so we need them to mean something simple so it's easy to calculate their fitness.

Let's let the array have size 1 and let's say x = genes[0]. The Individuals will only have one gene: the x-coordinate. Now we need to define our fitness function, we'll pick Easom with y = 0. This is how I would define the new fitness function:

double fitness = -cos(x)*cos(0)*exp(-(pow(x-PI,2)+pow(0-PI,2)));

With of course the appropriate imports at the top of the class:

import static java.lang.Math.*;

If your program does indeed optimize for fitness it should converge to x = PI. I quickly wrote my own (admittedly very ugly) implementation and it does indeed converge correctly.

One more thing: the genes should be a double[] instead of an int[], because incrementally optimizing a function doesn't really work when x can only be an int.

Why a gene array?

I think your assignment wants you to use an double array as the genes so you end up with a program that can optimize any function with any amount of variables. In programming it is always a good idea to write code that can be reused for multiple different things.

Feel free to ask any questions!

I tried to explain everything as clear as possible, but if you don't understand something feel free to ask!