Evolutionary algorithms and analog electronic circuits
hforsten.com
hforsten.com
Evolution is _really_ good at gaming the system. Unless you are very careful at specifying all of the constraints that you care about you can end up with a solution that is very clever but not quite what you had in mind. Here power consumption is the issue. If you tried to evolve a sturdy chair you might end up with something that is 1mm tall. or maybe a fuel efficient car that exploits continental drift.
For circuit simulation there are a bunch of potential pitfalls beyond power consumption. I think you would probably need to do multiple runs with components of varying values within their specified precision. I can see evolution getting some sort of benefit by exploiting the fact that two identically specced components behave _exactly_ the same way. Something that would not happen in real life.
great way to illustrate your point, thanks for the laugh
That's called Monte Carlo analysis. It's important for standard simulation applications as well because most components are specified with certain tolerances. Your amplifier might look stable at the expected component values, but if all of your resistors are at the bottom or top of their tolerance range, it might become unstable!
Commercial SPICE simulators (like HSPICE, for example) come with the option to perform this built-in. You can do Monte Carlo analysis with NGSPICE, but you have to organize the input and output yourself.
> I can see evolution getting some sort of benefit by exploiting the fact that two identically specced components behave _exactly_ the same way. Something that would not happen in real life.
You get pretty close with matched transistors, especially when they're on the same die. But yeah, Monte Carlo.
Another advantage of using simulated annealing instead of evolutionary algorithms is that you can add this sort of noise in pretty much for free (instead of doing multiple runs, you basically just lower the cooling rate).
Really this is an effect of all optimization approaches, not just "evolutionary" ones. Even simple parameter hill climbers will do that.
A fun personal example, many years ago I was trying to optimize an antenna design. I used a simple blackbox optimizer to adapt a parametrization of the geometry and a simulator to characterize the performance. I started it off and it was slowly making progress. The next day I came back and was exited to see _very good results_ ... but it turned out that it had made the length of the antenna _negative_ and the simulation was spouting nonsense (like the peak gain was a complex number). :)
The fundamental unreality of negative lengths must have resulted in me not thinking to add that as a constraint or make sure the simulation handled them gracefully... much in the same way that input fuzzing can turn up nasty bugs in otherwise well tested and competently written software.
Similar tricks in the "output" work for your chair and car examples.
>The plucky chip was utilizing only thirty-seven of its one hundred logic gates, and most of them were arranged in a curious collection of feedback loops. Five individual logic cells were functionally disconnected from the rest-- with no pathways that would allow them to influence the output-- yet when the researcher disabled any one of them the chip lost its ability to discriminate the tones. Furthermore, the final program did not work reliably when it was loaded onto other FPGAs of the same type.
This reminds me of Physically Unclonable Functions (PUFs) that tries to utilize differences in manufactured devices as a method of distinquishing unique devices. This is used for identification and authentication. There are for example PUFs that use differences in delays between logic blocks in FPGAs to generate unique responses to applied patterns/challenges.
See for example: http://en.wikipedia.org/wiki/Physical_unclonable_function
Ideally, you want to take a bunch of FPGAs, pull out a random subsample of them only for acceptance testing, and stop evolving the circuit when the performance on the acceptance testing subset starts getting worse.
There is no way to stop overfitting because it's difficult if not impossible to test it in every possible environment we want it to work under.
In the other case, the evolutionary algorithm found a long trace on the board that was to be an output from the FPGA (and so was undriven), and used it as an antenna to pick up the room's mains power and use it as a clock! I can't seem to find a reference to that one anymore, but if anyone else remembers this, I'd love to read about it again.
One thing to notice is the emphasis on comparing the GA performance to other search methods (like hill climbing). It would be nice to see that more in blog posts like this.
[1]: http://creativemachines.cornell.edu/sites/default/files/GPEM...
In my degree programme I did computer systems, not RF - but even this involved designing/building microwave amplifiers, playing with network analyzers and learning transmission line theory. I wish I could say that this work ~10 years ago has properly prepared me for the task but it seems I have many months of weekend study ahead of me...
In any case, even back then the RF students were generating pretty funky antenna designs out of modeling tools that ran for days sweeping through physical dimensions, numbers & types & topologies of elements, etc. to optimize toward some goal.
My guess is that today's compact models and solvers are both good enough for us to contemplate a 'Turing test' for analog circuit design.
Anyway this post was more detailed than the introductory on scientific america. This kind idea did not expolode over the past ten years. Something in detail might be wrong.
To give you an idea, only recently have we discovered that totally different species can exchange genetic sequences through virus (it is called horizontal gene transfer) and we are not really sure why sexual reproduction is a good idea when you can already mutate, have horizontal transfers and clone yourself.
"Make random mutations, select the best" is really not how nature works.
The mutations indeed are far from random. More important regions which fundamentally affect the viability of the organism evolve incredibly slowly and conservatively. The less important bits are less restricted and mutate more readily.
Additionally it's interesting to consider an individual in the context of its lineage. Some branches are extremely rich in diversity but mightn't have the population numbers of more "boring" clades.
It's easy to mistake success at population size as the end-game, the winner if you will, of evolution. Population size helps but at the end of the day it might be the smaller population, more diverse clades that are more adaptable to environment changes and survivability into the future in general.
(this isn't to say that evolutionary approaches are all that useful, they're usually outclassed by other optimization approaches, and where they work it's either in trivial cases or with mind-boggling amounts of computation)
Did you check your experiment against a simulated annealing process?
It's simpler to implement, converges faster and gives better results. So far I am unaware of any optimizing problem that was solved better with an evolutionary/genetic algorithm than simulated annealing. That is, unless the evolution part (crossover, mainly) is inextricably connected to the problem at hand and therefore other algorithms are simply not suitable to even try.
And yes it is, thanks!
> One thing to watch out with these sorts of approaches is[:] (you are -> are you) actually improving …
http://nwavguy.blogspot.com/2011/07/o2-headphone-amp.html
Is there any way from genetic algorithms to learn from good human designs as starting points and breed the together?
What about genetic algorithms for battery and solar cell design?
Source: several years of arguing with SPICE in a professional capacity.
Having said that you could use VirtualBox to get a Linux environment up fairly painlessly from Windows, if that's what you're on now.