Genetic Algorithm Classifier in Java: Rule-Based System

Question

I've coded from scratch a genetic algorithm with all features (tournament selection, crossover, mutation, elitism etc.) which successfully evolves a solution to the "counting ones" problem - i.e. it manipulates a randomly generated population of binary chromosomes comprised of 1s & 0s until a perfect one filled with 1s is reached.

Now I need to apply that algorithm and create a classifier. The system should classify binary data into either class "0" or class "1". I have a few sets of training data but here is the most basic:

32 rows x 5 variables (+ class, space separated, CR EOL) 00000 0 00001 0 00010 0 00011 1 00100 0 00101 1 00110 1 00111 0 01000 0 01001 1 01010 1 01011 0 01100 1 01101 0 01110 0 01111 1 10000 0 10001 1 10010 1 10011 0 10100 1 10101 0 10110 0 10111 1 11000 1 11001 0 11010 0 11011 1 11100 0 11101 1 11110 1 11111 0

How would I go about applying the genetic algorithm I've already built to such a problem with a rule-based context in the form IF x (AND y) THEN z ? I'm not sure where to begin, I think I may have to do some rule extraction but I don't know how to go about doing that in this context.

EDIT: Further code

public class Controller {

public static void main(String[] args) {
    final int P = 50;                   // population size
    final int N = 32;                   // chromosome length
    final double C = 0.95;              // crossover rate
    final double M = (double) 1 / P;    // mutation rate
    final int G = 50;                   // # of generations

    GA ga = new GA(P, N, C, M);

    // Initialise population of random individuals
    Individual[] population = ga.initPop();

    // "Counting ones" fitness evaluation
    System.out.println("GEN0");
    ga.evaluatePop(population);
    ga.printFitness(population);

    int generation = 1;
    for (int i = 0; i < G; i++) {

        System.out.println("\nGeneration: " + generation);

        // Tournament selection
        population = ga.tournament(population);

        // Tournament winners fitness evaluation
        ga.evaluatePop(population);

        // Single-point crossover
        population = ga.crossover(population);

        // Crossover children fitness evaluation
        ga.evaluatePop(population);

        // Bit-wise mutation
        population = ga.mutate(population);

        // Post-mutation population fitness evaluation
        ga.evaluatePop(population);

        // Elitism replacement (remove the worst gene and replace with a copy of the best)
        population = ga.elitism(population);

        // Post-elitism population fitness evaluation
        ga.evaluatePop(population);
        ga.printFitness(population);

        generation++;

        if (ga.bestFitness(population) == N) {
            break;
        }
    }
}

`

public class GA {

int populationSize;
int chromosomeSize;
double crossoverRate;
double mutationRate;
Random random = new Random();

public GA(int populationSize, int chromosomeSize, double crossoverRate, double mutationRate) {
    this.populationSize = populationSize;
    this.chromosomeSize = chromosomeSize;
    this.crossoverRate = crossoverRate;
    this.mutationRate = mutationRate;
}

public Individual[] initPop() {
    Individual[] population = new Individual[populationSize];
    for (int i = 0; i < populationSize; i++) {
        population[i] = new Individual(chromosomeSize);
    }
    return population;
}

public void evaluatePop(Individual[] population) {                          
    for (int i = 0; i < population.length; i++) {
        population[i].evaluate();
    }
}

public Individual[] tournament(Individual[] population) {
    Individual[] selectionTemp = new Individual[populationSize];
    for (int i = 0; i < population.length; i++) {

        Individual parent1 = population[random.nextInt(population.length)];
        Individual parent2 = population[random.nextInt(population.length)];

        if (parent1.getFitness() >= parent2.getFitness()) {
            selectionTemp[i] = parent1;
        } else {
            selectionTemp[i] = parent2;
        }
    }
    population = selectionTemp;
    return population;
}

public Individual[] crossover(Individual[] population) {
    for (int i = 0; i < population.length - 1; i += 2) {
        Individual offspring1 = new Individual(population[0].getChromosome().length);
        Individual offspring2 = new Individual(population[0].getChromosome().length);

        int xpoint = 1 + random.nextInt(chromosomeSize - 1);

        if (random.nextDouble() < crossoverRate) {
            for (int j = 0; j < xpoint; j++) {
                offspring1.setGene(j, population[i].getGene(j));
                offspring2.setGene(j, population[i+1].getGene(j));
            }
            for (int j = xpoint; j < population[0].getChromosome().length; j++) {
                offspring1.setGene(j, population[i+1].getGene(j));
                offspring2.setGene(j, population[i].getGene(j));
            }
        }
        population[i] = offspring1;
        population[i+1] = offspring2;
    }
    return population;
}

public Individual[] mutate(Individual[] population) {
    for (int i = 0; i < population.length; i++) {
        for (int j = 0; j < population[i].getChromosome().length; j++) {
            if (random.nextDouble() < mutationRate) {
                population[i].mutate(j);
            }
        }
    }
    return population;
}

public Individual[] elitism(Individual[] population) {
    Individual min = population[0];
    int minOffset = 0;
    for (int i = 0; i < population.length; i++) {
        if (population[i].getFitness() <= min.getFitness()) {
            min = population[i];
            minOffset = i;
        }
    }
    Individual max = population[0];
    int maxOffset = 0;
    for (int i = 0; i < population.length; i++) {
        if (population[i].getFitness() >= max.getFitness()) {
            max = population[i];
            maxOffset = i;
        }
    }
    population[minOffset] = population[maxOffset];
    return population;
}

// <editor-fold defaultstate="collapsed" desc="Debug logic...">
public int totalFitness(Individual[] population) {
    int population_fitness = 0;
    for (int i = 0; i < population.length; i++) {
        population_fitness += population[i].getFitness();
    }
    return population_fitness;
}

public double avgFitness(Individual[] population) {
    return (double) totalFitness(population) / population.length;
}

public int bestFitness(Individual[] population) {
    int max = population[0].getFitness();
    for (int i = 0; i < population.length; i++) {
        if (population[i].getFitness() > max) {
            max = population[i].getFitness();
        }
    }
    return max;
}

    public Individual bestIndividual(Individual[] population) {
    Individual max = population[0];
    for (int i = 0; i < population.length; i++) {
        if (population[i].getFitness() >= max.getFitness()) {
            max = population[i];
        }
    }
    return max;
}

public void printFitness(Individual[] population) {
    System.out.println("Total fitness: " + totalFitness(population));
    System.out.println("Average fitness: " + avgFitness(population));
    //System.out.println("Best fitness: " + bestFitness(population));
    System.out.println("Best individual: " + bestIndividual(population));
}

public void printPop(Individual[] population) {
    for (int i = 0; i < population.length; i++) {
        System.out.println(Arrays.toString(population));
    }
}
// </editor-fold>

``

public class Individual {

public int[] chromosome;
public int fitness = 0;
Random random = new Random();

public Individual(int chromosomeSize) {
    this.chromosome = new int[chromosomeSize];
    for (int i = 0; i < chromosomeSize; i++) {
        this.setGene(i, random.nextInt(2));
    }
}

// Initializes individual with a blank chromosome (all genes 0)
public Individual(int chromosomeSize, boolean isBlank) {
    this.chromosome = new int[chromosomeSize];
    Arrays.fill(chromosome, 0);
}

public void mutate(int offset) {
    if (this.getGene(offset) == 1) {
        this.setGene(offset, 0);
    } else {
        this.setGene(offset, 1);
    }
}

public void evaluate() {
    int count = 0;
    for (int offset = 0; offset < this.chromosome.length; offset++) {
        if (this.getGene(offset) == 1) {
            count++;
        }
    }
    this.setFitness(count);
}

public int getGene(int offset) {
    return this.chromosome[offset];
}

public void setGene(int offset, int gene) {
    this.chromosome[offset] = gene;
}

public int[] getChromosome() {
    return chromosome;
}

public int getFitness() {
    return fitness;
}

public void setFitness(int fitness) {
    this.fitness = fitness;
}

@Override
public String toString() {
    String output = "Binary gene representation: ";
    for (int i = 0; i < this.chromosome.length; i++) {
        output += this.getGene(i);
    }
    System.out.println(output);
    System.out.println("Fitness: " + this.getFitness());
    return output;
}

Answer 1

A genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection. A metaheuristic is defined as a higher-level procedure or heuristic designed to find, generate, or select a sub-heuristic, or a combination or permutation of sub-heuristics. Using a GA in itself tells you nothing about how or what the sub-heuristics should look like. So you could reformulate your current realization as:

I've developed a GA metaheursitic framework, but now I need to determine and design the sub-heuristic(s) that might allow me to solve this particular problem. I guess I'm only halfway done.

That's correct. And now for the second important understanding about GAs: They are best applied in problems where a partial success (a sub-solution or a non-optimal solution) may be further refined to obtain even better results.

GAs work well to solve mathematical optimizations, for example, where there is often continuity and locality. Or to solve a maze, for example, where a good partial solution is definitely a decent starting point to attempt the full solution.

Unfortunately, in your particular case, the parity-bit problem (even or odd problem) is not an optimization problem or a clearly iterative problem. It's an all-or-nothing sort of problem and the GA is not a natural fit with a 0 or 1 binary chromosome.

This doesn't mean you couldn't force a GA solution—you could create various lookup rules that use modulus or XOR (for example) and very quickly evolve a solution that works. But it almost feels like cheating since you hardcoded the essential "insight" (modulo operation or XOR) that you would have preferred to evolve. Another way to pigeonhole the GA into a solution here would be to develop "genes" that code for "programmatic" syntax and actually evolve a small program function bool result = f(x) that would output a true or false value (your binary classification). But this adds a lot of complexity like syntax, etc., and you would likely end up in STGP (strongly-typed genetic programming) territory and you should be aware that the natives who live there will exact a heavy temporal tax on you for passing through their land unprepared.

My advice for the parity problem: Lower yourself to using just a neural net. They are not quite as sexy or as universal, but they will get the job done without requiring you to either cheat or do a whole lot more work (STGP). It is well known that neural nets with a sufficient number of nodes can learn XOR and thus parity.

Edit:

To pigeonhole this as a GA school assignment, I recommend taking a digital-gate styled approach. You'll need to move from a binary chromosome scheme to a ternary chromosome scheme (which should require no extra coding since you already use an int[] chromosome declaration). Each trit (trinary digit) could then code for the following lookup rules:

1: prior State AND B[next]
2: prior State OR B[next]
3: NOT

For a given input bit pattern B[], the ternary chromosome could be evaluated from left to right on a per-bit basis, with an initial State variable of 0 (where State is an internal variable inside the evaluation function) and an implicit AND operation happening between each consecutive trit (except for the NOT type). So, for example, imagine you evolved the ternary solution 2, 3, 3, 1, which would represent the following sequence of operations in your evaluation function (applied once for each input bit):

((!(!(prior State | B[next]))) & (prior State & B[next]))

where State and B[next] are obviously bit (bool) variables. Note that the AND operation near the middle comes from the implicit AND operation we defined to occur between any trits that are not of the NOT-type. So for example, the input bit string 100 when run through the evaluation function against our example chromosome of 2, 3, 3, 1 would look like follows:

1. State = 0
2. B[next] = 1, State = ((!(!(0 | 1))) & (0 & 1)) = 0
3. B[next] = 0, State = ((!(!(0 | 0))) & (0 & 0)) = 0
4. B[next] = 0, State = ((!(!(0 | 0))) & (0 & 0)) = 0
5. Return final State value (0 here) from evaluation function.

You could arbitrarily define a result of 0 to mean even and a result of 1 to mean odd if you liked. The choice doesn't matter since the GA could easily learn to invert the result with an additional NOT trit at the end of the chromosome.

The nice thing about this evaluation function is that it will handle arbitrarily long input bit strings since it is applied only per-bit in a rolling fashion and does not care about the overall bit string length. And we know that it can theoretically evolve a correct solution since A XOR B = (A OR B) AND (NOT (A AND B)) and XOR is all that is needed for parity.

In order for this to work, you will have to allow variable-length solutions (variable-length evolved trit sequences), but cap the chromosomes at a reasonable upper limit (say 15 trits or so) to prevent the GA from going crazy with ever-longer solutions. And one other thing you will need to do in order for this to work: scoring based on batch evaluation of many input bit strings. Because the output of the evaluation function for any input bit string is just 0 or 1, the result will either be 100% correct or 0% correct. This in itself doesn't allow useful fitness scoring because you have no good way to rank different trit sequences (solutions) comparatively, since about half will be 100% correct and the other half will be 0%. But the solution is simple: just score each trit sequence on the % of all input strings that it correctly labels. So if you have 100 input bit strings in your dataset, and solution 1 labels 57% of the input bit strings correctly, while solution 2 labels only 49% of the inputs correctly, now you have a good way to rank your solution population and select for genetic crossover, mutation, elitism survival, etc.