Using Multiple Expressions to derive the Pythagorean Theorem

0: a 1: b 2: * 3: / 4: + 5: - 6: Q (square root)

The method for calculating the fitness is shown below:

Listing 1 - Calculating the Fitness of the Genes against several sample triangles

public float CalculatePythagoreanFitness()
{
int index = 0;
float calc = 0.0f;
float sum = 0.0f;
int count = measure.GetLength(0);
for (int i = 0; i < count; i++)
{
calc = PerformCalculation(measure[i, 0], measure[i, 1]);float error = 100 - Math.Abs(measure[i,2] -calc);
sum += error;
}
CurrentFitness = sum/(measure.GetLength(0)*100);
if (float.IsNaN(CurrentFitness))
CurrentFitness = 0.01f;
return CurrentFitness;
}

This is the same fitness function that we used in our previous GEP article except we now normalize the fitness value so it falls between 0 and 1. (We didnt have to normalize, it just looks nicer).

The PerformCalculation method takes the sample values and determines a calculation based on the steps carried out in the Genome. The simple way to implement this algorithm is by using an array. If you recall, for walking the GEP PostFix calculation, we used a stack collection, but since the order of calculation is very much index-specific, an ArrayList is the best bet for implementing our MEP calculation.

Listing 2 - Implementing the steps of the MEP chromosome with an array

public float PerformCalculation(float a, float b)
{
int count = 0;
foreach (Gene g in TheArray)
{
if (g.operation < NumSymbols)
{
// the gene is a variable,
// variable identity is contained in the
// operation field
// step contains a or b, assign value
if (g.operation == 0)
alculationArray[count] = a; else
CalculationArray[count] = b;
}
else
{
// gene is an operation
// use it to put the calculation into an
// array using the referenced line results
// indicated by instruction1 and instruction2
CalculationArray[count] = DoOperation(CalculationArray[g.instruction1], CalculationArray[g.instruction2], g.operation);
}
count++;
} // end for each Gene
// return last calculation
return CalculationArray[TheArray.Count - 1];
}

The DoOperation method in the listing above simply interprets the operation and performs the numerical binary or unary operation and returns the result. Note: We purposely check for some potentially bad situations such as divide by zero or the square root of a negative number and assign them numbers:

Listing 3 - Performing the operation of an individual gene

public float DoOperation(float a, float b, int operation)
{
float result = 0.0f;
switch(operation)
{
case 2: // *
result = a * b;
break;
case 3: // /
if (b == 0.0f)
{
// divide-by-0, just set b to a small number
b = .0001f;
}
result = a/b;
break;
case 4: // +
result = a + b;
break;
case 5: // -
result = a - b;
break;
case 6: // Q
if (a > 0) // make sure its greater than 0
result = (float)Math.Sqrt(a);
break;
default:
// +
break;
} // end switch
return result;
}

We used the following sample set of triangles to run against our MEP program. The first two numbers of each value group represents the sides of the triangle (a and b), and the third number is the hypotenuse in which we are measuring our MEP result against to determine the fitness of the Gene. Note that we picked negative values for the sides of one of the triangles. I found that the more diversity in your sample set, the better chance you have of converging on the correct solution.

Listing 4 - twelve sample triangles stored in a multidimensional rectangular array

float[,] measure = new float[12,3]{{ -1, -3, 3.162277f}, {30,40,50}, {40, 30, 50}, {1, 1, 1.4142f}, {1, 2, 2.23607f}, {3, 1, 3.162277f}, {6, 13, 14.31782f}, {4,3,5}, {1,3, 3.16228f}, {2, 1, 2.23607f}, {4, 5, 6.403f}, {5,4, 6.403f}};

Below is the solution set after 52 generations with an initial population of 2000 genomes. The mutation rate was about .33 and the chromosome length was 15.

Figure 6 Pythagorean Theorem derived by the MEP Algorithm

There is a ToString function in the EquationGenome shown below. If you uncomment the FormStepsString method, you can look at the steps that produce the Equation:

public override string ToString()
{
string strResult = "";
int index = 0;
strResult += " --> " + this.FormStepsString();
strResult += " --> " + this.FormEquationString();
strResult += " --> " + CurrentFitness.ToString();
return strResult;
}

Below are the MEP steps generated for one of the 15-Gene chromosomes that produces the Pythagorean equation. Note that its not as clean as our initial representation of this solution, nor is everything in the Genome utilized, but it gets the job done.

Figure 7 MEP Genome that produces the solution

Conclusion

MEP is another GA Technique that can be used for coming up with general models from empirical data. Because you can choose the complexity of the functions, you can use it to model anything from simple mathematical curves to complex physical systems. You can have fun experimenting with MEP by changing the empirical data supplied by the measure array and by varying the functions and symbols in the Genome. Also you'll want to vary population size, gene length and crossover and mutation frequencies to come up with different convergences. Most of the GA parameters are located in the population class. The data and symbols are located in the EquationGenome class. I suspect people will make some cool discoveries using this technique and the beauty is that you can just let the computer and .NET do all the work!

References

Multi Expression Programming, Mihai Oltean.
Gene Expression Programming, Candida Ferreira
Implementing a Genetic Algorithm in C# and .NET, Mike Gold
GEP Algorithm in C# and .NET, Mike Gold