Arithmetic Experiment (XEvolution Example)
The Arithmetic experiment is an example of the usage of the XEvolution framework. The problem is to find a fixed length arithmetic expression that is equal to a specific target value. For example, if the target value is 0, then "2 + 1 - 2 + 0 - 3 + 2" is a correct solution.
Each genome carries a binary string which encodes the expression. As evolution progresses, the fitness of genomes increase as the value of their expressions approaches the target value.
Arithmetic expressions are encoded in strings of 0's and 1's. Numbers and operators have a specific bit length, denoted by NUMBER_BIT_LENGTH and OP_BIT_LENGTH respectively. In this example, numbers have a bit length of 4 (values 0-15) and operators have a bit length of 1 (ops + and -).
A binary string is a sequence of encoded numbers and operators. The following string (with spaces added for readability) would be resolved:
1010 0 0100 0 1011 0 1001 1 0010
10 + 4 + 11 + 9 - 2
32
All genomes are given a binary string of a uniform length. In this example, all expressions have 10 numbers and 9 operators, so they'd have length 10 * 4 + 9 * 1 = 49. The initial population of genomes are initialized with uniformly random binary strings.
Both the mutate and crossover operators are what is typically found in GA's of this type. The mutate operator goes through each bit the data string and, with a given probability, flips the bit of the string. The crossover operator selects a point and splits both parents' strings at that point. The child is given a string that's the first part of one split concatenated with the second part of the other split.
Once a genome's bit string is decoded, it's straight-forward to calculate its value. The genome's fitness is calculated using the following equation:
double fitness = 1.0 / (1 + Math.abs(target - num));
The default target for this example is 64. So the fitness for the above genome is 1.0 / (1 + 64 - 32) = 1.0 / 33 = 0.0303.
Creating and running a simple run configuration for com.xtructure.xnet.demos.arith.ArithmeticExperiment.java makes an evolution experiment for the Arithmetic problem. ArithmenticExperiment.java accepts as a program argument a number to use as the target value for evolution.
As the evolution experiment runs, it alternately outputs statistics for the population
0 [main] INFO com.xtructure.xevolution.evolution.impl.EvolutionStrategyImpl - com.xtructure.xevolution.genetics.impl.PopulationImpl@1bca5f1[
id=Population:[0]
size=100
attributes={"genomeIdNum:[java.lang.Integer]":100,"ageLastImproved:[java.lang.Long]":0,"age:[java.lang.Long]":0}
highGenomes={age:[java.lang.Long]=Genome:[9], complexity:[java.lang.Double]=Genome:[9], evaluationCount:[java.lang.Long]=Genome:[9], fitness:[java.lang.Double]=Genome:[66]}
lowGenomes={age:[java.lang.Long]=Genome:[0], complexity:[java.lang.Double]=Genome:[0], evaluationCount:[java.lang.Long]=Genome:[0], fitness:[java.lang.Double]=Genome:[39]}
averageMeasures={age:[java.lang.Long]=0.0, complexity:[java.lang.Double]=49.0, evaluationCount:[java.lang.Long]=0.0, fitness:[java.lang.Double]=0.023125809334746564}
]
1 [main] INFO com.xtructure.xevolution.evolution.impl.EvolutionStrategyImpl - fittest : Genome:[66]
1 [main] INFO com.xtructure.xevolution.evolution.impl.EvolutionStrategyImpl - fitness : 0.25
and indicates how the genomes of the next generation are produced.
6 [main] INFO com.xtructure.xevolution.evolution.impl.ReproductionStrategyImpl - Genome:[96] : Genome:[44] : Genome:[100] : com.xtructure.xevolution.demo.arith.ArithmeticCrossoverOperator@e5855a
7 [main] INFO com.xtructure.xevolution.evolution.impl.ReproductionStrategyImpl - Genome:[12] : Genome:[101] : com.xtructure.xevolution.demo.arith.ArithmeticMutateOperator@12558d6
...
When a solution is found the bit string and the decoded expression is output.
0010000000100001011011010101101111111100011101011
2 +0 +8 +11 +13 +11 +15 -14 +7 +11