Evolving Register Network using Genetic Algorithms in C#

Genetic Algorithms are powerful AI tools because they can evolve through trial and error and converge into a solution. Electronics is one place where genetic algorithms are useful because you can run ga's on evolving circuits and have them approach values that meet the specs you desire for the output of your circuit. In the past we explored one use of these genetic algorithms for converging on desired digital outputs. In this article we will use genetic algorithms to come up with an analog solution.

Figure 1 - Resistor network for D/A Conversion

Before demonstrating the power of genetic algorithms to create analog circuits, first let me pose the problem. I have a box of resistors with the following common values (100 , 1k , 2.2k, 10K , 100k , 1 Meg , 10M) and multiple values of each. Using some combination these resistors, I want to come up with a total resistance of 314.159 ohms (a factor of pi). How the heck do I do this? Well, using ohms law we know that two resistors in series is the sum of their resistance (R1 + R2). We also know from ohms law that two resistors in parallel are equal to the reciprocal sum of their reciprocals (1/ (1/R1 + 1/R2) ) . Even armed with this knowledge, I could be stringing resistors together all day and never figure out the combination that will get me a nice factor of pi. I'll probably create a colorful resistor mobile that could hang in the Guggenheim Museum in New York, though.

So how can I solve this problem? One sure way is to run the whole thing through a genetic algorithm. I chose MEP (Multiple Expression Programming) for its effective ability of evolving equations. The two operations in my algorithm are simply parallel and series. These operations are numerically represented as 2 possible integers in our genome(7 and 8). The other values the genome can take are the values of the resistors in our box of resistors (100, 1000, 2200, etc.), each one represented by an integer number. The possible values for our genome are shown below:

0: 100 ohm
1: 1000 ohm
2: 2200 ohm
3. 10K ohm
4. 100K ohm
5. 1 Megaohm
6. 10 MegaOhm
7. parallel (operation (1/ (1/R1) + (1/R2)) symbol = ||
8. series (operation R1 + R2) symbol = --

The Perfect Fitness

It turns out that coming up with a fitness function for the resistor network is not that complicated since we are only evolving towards a single resistor value of 314.59. We just need to compare the results of the total calculated resistor network resistance in a genome against the desired value. I like to use the natural number exponential function for finding the error, because it only gives a perfect fitness value if the difference between the calculated and desired resistance is zero. All other fitnesses fall off exponentially. So the formula for fitness is:

fitness = e^-^{|desired - calculated|}

The crux of the genome fitness calculation is performed in the PerformCalculation method of the EquationGenome shown below in listing 1 used to calculate the genome resistor network

Listing 1 - Calculating the resistance of the genome resistor network

float[] ResistorValues = new float[] {100, 1000, 2200, 10000, 100000, 1000000, 10000000};
public float PerformCalculation()
{
int count = 0;
foreach (Gene g in TheArray)
{
if (g.operation < NumSymbols)
{
CalculationArray[count] = ResistorValues[g.operation]; // if gene is a resistor value, get value from resistor array
}
else
{
// operation (either parallel or series), use it to fill calculation in array
CalculationArray[count] = DoOperation(CalculationArray[g.instruction1], CalculationArray[g.instruction2], g.operation);
}
count++;
}
return CalculationArray[TheArray.Count - 1]; // return last calculation
}

The exponential fitness method of the EquationGenome compares the calculation from listing 1 to the desired value. From this comparison we get our final fitness as seen in listing 2.

Listing 2 - Calculating the fitness of the genome using the exponential formula

public double CalculateResistorCircuitOutputFitness()
{
double calc = 0.0f;
calc = PerformCalculation(); // calculate the fitness of the genome
CurrentFitness = Math.Exp(-Math.Abs(measure-calc)); // calculate the error value from the exponential formula
return CurrentFitness;
}

Running the Evolving Resistor Networks

Below are the factors we chose to use to run our population. The mutation rate is fairly high (.33), but this is recommended for MEP. Our genomes are 15 genes long allowing for a 15 line long MEP genome program. We limit the population to 100 and choose the 100 fittest genes each generation.

Listing 3 - Initial parameters for our MEP Genetic Algorithm

public const int kLength = 15; // length of MEP program (length of genome)
const int kInitialPopulation = 100;
const int kPopulationLimit = 100;
const int kMin = 0; // minimum gene value
const int kMax = 9; // maximum gene value + 1
const double kMutationFrequency = 0.33f; //mutation frequency

After we run for 30000 generations, we find the resistor network converging to a very close value to our desired fitness. Even after the first 2500 generations, we come fairly close with a fitness of .982, but many generations later, we have a fitness of .9999. (Note that 1E+07 is our 10 Meg resistor).

Generation 2

--> (100--100) --> 2.63861629666332E-50

Generation 2502

--> ((((1000--10000)||1000)||(((1000--10000)||1000)||(1000000||1E+07)))||1000) --> 0.98206919884047

Generation 30002

--> (1000||(((1000--10000)||1000)||((1E+07||((1000--10000)||1000))||((1000--10000)--(1E+07||(1000000||1E+07)))))) --> 0.999905033806458

Conclusion

Once again, genetic algorithms have solved a fairly difficult, but practical problem. Note that you should keep in mind that resistors have tolerances, and for the value of the resistor to be fairly precise, you should use resistors with very high precision values. Perhaps you can even use our calculated circuit with a divider and an opamp as an analog computer that can calculate the circumference of a circle. Either way, it's hard to resist the power of genetic algorithms in the world of .NET.