#6 Abstraction power in genetic algorithms

In this post I will explain the implementation of GA for buying motorocycle from the previous post as well as I will show a good practice – creating abstraction layers.

Code – GA part

In the code, which is available here you can see package ‘ag’ containing 2 classes and one interface:

  • Phenotype:
public class Phenotype implements Comparable<Phenotype> {
  int gene;
  int value;

  // TODO - should be configurable
  static MapableToGene geneToIndividualMapper = new Moto();
...
  public void crossover(Phenotype p, int k) {
    int geneA = gene;
    int geneB = p.gene;
    int maskA = ~(~0 << k); // i.e. if k = 2 then maskA = 000011, but on 32 bits
    int maskB = (~0 << k); //                then maskB = 111100, but on 32 bits
    gene = (geneA & maskA) + (geneB & maskB);
    p.gene = (geneB & maskA) + (geneA & maskB);

    calculateValue();
    p.calculateValue();
  }

  private void calculateValue() {
    geneToIndividualMapper.mapFromGene(gene);
    value = geneToIndividualMapper.value();
  }
}
  • Population:
public class Population { // should be generic
  List<Phenotype> population;
  List<Phenotype> nextGeneration;
  MapableToGene mapableToGene;

  // Temporary constants TODO: Should be configurable
  final int populationSize = 20; // == 7*6 / 2
  final int counterMax = 5;
...
}
  • MapableToGene:
public interface MapableToGene {
  int mapToGene();
  void mapFromGene(int gene);
  int value();
}

My intention was to write as simple as possible code – there are still some TODO marks there. Once I improve the code I will update the post as well.

As you may already see – MapableToGene interface is our bridge between concrete Moto class and abstract Phenotype (or individual in GA terminology). Phenotype doesn’t know about the problem it is used for, except the moment when we try to value concrete set of genes.

Code – concrete optimization problem

When we create a class implementing MapbleToGene interface it is really easy to use this GA implementation. We need to define 3 methods, in Moto class they look like this:


public class Moto implements MapableToGene{
  int power;
  int ccm;
  int price;
  int weight;
  int gasUsage;
  int equipmentQuality;
  boolean canMyWifeUseIt;
  boolean doesMyWifeLikeItsDesign;
...

  @Override
  public int mapToGene() {
    // 8 fields, so every information is normalized into 4 bits
    int gene = power > 100 ? 15 : 15 * power / 100; //max is 100

    gene += (ccm > 1000 ? 15 : 15 * ccm / 1000) << 4; //max is 1000
    gene += (price > 40000 ? 15 : 15 * price / 40000) << 8; //max is 40000
    gene += (weight > 220 ? 15 : 15 * weight / 220) << 12; //max is 220
    gene += (gasUsage > 10 ? 15 : 15 * gasUsage / 10) << 16; //max is 10
    gene += (equipmentQuality > 15 ? 15 : equipmentQuality) << 20; //max is 15

    gene += (canMyWifeUseIt ? 15 : 0)<<24;
    gene += (doesMyWifeLikeItsDesign ? 15 : 0)<<28;

    return gene;
}

  @Override
  public void mapFromGene(int gene) {
    int mask = 15; // 0000....01111 but we use 32bits
    power = (gene & mask) * 100/15;
    ccm = ((gene & mask<<4) >> 4) * 1000/15;
    price = ((gene & mask<<8) >> 8) * 40000/15;
    weight = ((gene & mask<<12) >> 12) * 220/15;
    gasUsage = ((gene & mask<<16) >> 16) * 10/15;
    equipmentQuality = ((gene & mask<<20) >> 20);
    canMyWifeUseIt = ((gene & mask<<24) >> 24) != 0;
    doesMyWifeLikeItsDesign = ((gene & mask<<28) >> 28) != 0;
}
  @Override
  public int value() {
    return power/4 + ccm/10 - price/1000 - weight/10 - gasUsage + equipmentQuality/2 + (canMyWifeUseIt?5:0) + (canMyWifeUseIt?3:0);
  }
}

The idea behind mapToGene() implementation is simple. We try to put all relevant information about motorocycle into 32bit int. As you see, I chose to give every information the same space – 4 bits, which is probably not the best choice (I will show better example shortly). By this mapping we lose some information, but it doesn’t have to be like that. Firstly we can use 64 bit long or array of ints for example. Secondly I didn’t use this space wisely. Boolean fields could be mapped to single bit, and then price, weight and ccm could have more space for themselves.

Implementation of mapFromGene() is reverse process to mapToGene(), and value() is really important function, but in this case really simple.

Code – Another example. Benefits of separation of layers

Let’s create small class PerfectHusband:

public class PerfectHusband implements MapableToGene{

  List<HusbandAttribute> attributes;

  public PerfectHusband(){
    attributes = new ArrayList<>();
    attributes.add(new HusbandAttribute("earnings", 0, 14));
    attributes.add(new HusbandAttribute("iq", 0, 7));
    attributes.add(new HusbandAttribute("emotional intelligence", 0, 7));
    attributes.add(new HusbandAttribute("addictons", 0, 2));
    attributes.add(new HusbandAttribute("attractive", 0, 1));
    attributes.add(new HusbandAttribute("having a motorocycle", 0, 1));
  }

  @Override
  public int mapToGene() {
    int gene = 0;
    int bitsShift = 0;
    for(HusbandAttribute attr : attributes){
      int maxValue = (int)Math.pow(2.0, attr.getnOfBits())-1;
      gene += (attr.getValue() > maxValue ? maxValue : attr.getValue()) << bitsShift;
      bitsShift = attr.getnOfBits();
    }
    return gene;
  }

  @Override
  public void mapFromGene(int gene) {
    int bitsShift = 0;
    for(HusbandAttribute attr : attributes){
      int mask = ((int)Math.pow(2.0, attr.getnOfBits())-1) << bitsShift;       attr.setValue(Math.abs((mask&gene) >> bitsShift));
      bitsShift += attr.getnOfBits();

    }
  }

  @Override
  public int value() {
    int value = 0;

    int earnings = getValueByAttributeName("earnings");
    value += earnings < 1000 ? - 100 : (int)Math.sqrt(earnings);
    value += getValueByAttributeName("iq") - 95;
    value += getValueByAttributeName("emotional intelligence") - 95;
    value -= Math.pow(getValueByAttributeName("addictons") * 2.0, 3);
    value += getValueByAttributeName("attractive") * 30;
    value += getValueByAttributeName("having a motorocycle")*50;
    return value;
}   
  private int getValueByAttributeName(String name){
    return attributes.stream().filter( a -> a.getName().equals(name)).findFirst().get().getValue();
  }
}

As you can see it is different class, different problem we want to solve, but using this separation of concerns between GA layer and concrete layer gives us a solution here as well:

Phenotype [ gene=11001111100111101111000101100101, value=249]

PerfectHusband [attributes=[HA [earnings, 12645], HA [iq, 123],
HA [emotional intelligence, 124], HA [addictons, 0], HA [attractive, 1],
HA [having a motorocycle, 1]]]

You can try this by yourself it should be very easy. You can create PerfectBicycle class, or Event TSP path class, the only thing your class need to do is to map itself from gene (32 bit int), map it to gene, and value itself based on criteria you choose. Good luck!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s