I recently read an article by Alan Bellows about an FPGA being "evolved" to distinguish a 1kHz tone from a 10kHz tone using less than 100 logic gates and no system clock. Many engineers at the time thought this task would be impossible -- and using traditional methods to do it most likely would have been. But using genetic algorithms, a type of algorithm that mimics nature's process of improving a population of organisms over many generations, produced a solution that defied what engineers thought possible. I began wondering where these powerful tools could fit in the world of microcontrollers.
Genetic algorithms have been employed in all kinds of applications (searching "genetic algorithm" on IEEE Xplore yields 24,598 results). They are great at finding optimized solutions to problems in nontraditional ways, using a combination of crossovers between and random variations within potential solution sets and evaluating how well the new candidates perform. To explore their potential for MCU designs, I decided to try making my own genetic algorithm to optimize a simple control loop that a microcontroller might use.
The example involves a reflow oven that can activate its heating element or open a vent to let heat escape quickly. (Heat will also dissipate slowly through its walls.) An onboard microcontroller can read the temperature inside and make decisions every five seconds as to whether the heating element should be on or the vent should be open. This microcontroller must use a proportional-integral-derivative (PID) loop to control these two peripherals. The goal in this example is to keep the oven temperatures as close as possible to the desired temperature profile.
Table 1:
| Minute 1: |
100 degrees |
| Minutes 2-3: |
Linear slope from 100 to 400 degrees |
| Minutes 4-5: |
400 degrees |
| Minutes 6-7: |
Linear slope from 400 to 70 degrees |
| Minutes 8-10: |
70 degrees |
For this problem, we need to solve five variables: the three variables for the PID loop (Kp, Ki, Kd) and two thresholds that control whether the heater or vent should be activated. The idea with these thresholds is that, if the PID function returns a value outside the thresholds, the oven will either vent heat or produce more heat. If the function returns some value in between, the oven will just sit idly and lose heat slowly through its walls.
It turns out in practice that these five values are interrelated to one another and the PID function. Fixing one of the thresholds to a specific value will leave only four variables to optimize, saving many clock cycles when running the genetic algorithm.
The simplest, most obvious way to optimize these variables is by brute force. You could write a program that goes through every combination of values for these variables and returns the combination that produced the best outcome. For this example, I wrote a program in Java that simulates the reflow oven and calculates the total amount of error between the desired temperature at a given time and the actual temperature. (Perhaps a few gross assumptions were made about thermodynamics, but these are irrelevant, since the programs should still optimize the variables around whatever conditions are given.) I ran this program for 40 different values each for Kp, Ki, and Kd and 100 different values for the open-vent threshold -- a total of 6.4 million simulations. This took roughly 4.5 seconds to run, and it yielded the following temperature profile with an accumulated error of 3,854 degree-seconds.
I made a second program using a Java library genetic algorithm called WatchMaker that evolved a population of 100 oven controllers (each with a different set of values) over 5,000 generations, meaning the simulation had to be run only 500,000 times. Between each generation, each oven controller had a 3 percent chance of mutating one of its variables, a 3 percent chance of completely rerolling all its variables, and a 20 percent chance of "mating" with another controller to produce offspring, with each variable coming from one or the other parent. The top two controllers from each generation were guaranteed to survive.
After running the simulation many times, I found that most of the time, the simulation would converge on the same temperature profile in the first thousand generations with an accumulated error of 3,716 degree-seconds, as shown below.
The average run time varied but was generally less than half that of the brute force method.
The interesting thing is that the program returned different values for variables but produced essentially the same profile every time it was run. The fact that the answer was unique every time highlighted the major draw of genetic algorithms: Their randomness ensures they do not get stuck in any local maxima of an equation, and it ensures an increasing precision based on how many evolutions the population has made.
I also tinkered with the fitness function, making it optimize based on saving electricity (using the heating element as little as possible while maintaining an acceptable error). The genetic algorithm was able to produce a new solution that saved 15 seconds of the heating element being on. If you wish to try this program out yourself, I have put the code on my GitHub, along with an Excel sheet that lets you see the outcome visually based on the five variables.
Even in this simple example, genetic algorithms produced a better set of optimized variables than brute force -- and much faster. We have already seen genetic algorithms being using in many electrical engineering applications, but where else do you think they can be used? Do you think one-day compilers will use genetic algorithms to optimize code? Will silicon manufacturers use them to find new ways to produce their circuits cheaper or using less material? Leave a comment with an interesting application for genetic algorithms.
Tweet This
