Evolutionary algorithms and analog electronic circuits

  • That is really cool. I have been dreaming about creating something like that for a long time. Seems like circuit design should be about defining inputs, outputs, and some set of constraints, like available components, and board size, power, and heat requirements, and then optimize for a fitness function which is a weighted formula of price and performance.

    I have used an evolutionary algorithm to do real work, saving real money for a company. Basically we had an extremely expensive tool that made vias one at a time. Since this tool was so expensive, it was always a bottleneck in the manufacturing process. I created a genetic algorithm that optimized the path of the tool, which significantly increased its throughput. I've stripped out all the proprietary stuff, and left behind a simple genetic algorithm to solve the Traveling Salesman Problem in Java and put it on github. Its got a GUI and its sort of mesmerizing to watch it evolve a solution. Works well, even with over 1000 different locations, which is unbelievable, considering that means a solution space of over 1000 factorial!

    https://github.com/YesSql/TspGA/wiki

  • There is a bunch of past work in this area. Circuits have been evolved in simulation (John Koza did a ton of papers on this) and directly on FPGAs (the seminal paper here was Adrian Thompson). There is a field concerning doing this, called "evolvable Hardware". GECCO is going on right now in Philly and should have some new papers on the topic.

  • Rudolf Kalman, the guy who invented the Kalman Filter, seems to be interested in this kind of stuff, too.

    He gave a talk at TUM a few years ago where he tried to motivate students to work on the problem of inverting transfer functions. The talk was for mathematicians, so I didn't understand a lot and might be completely mistaken. To make things worse I know little about circuits. So if I say something wrong here, plz correct me. The way I remember it was something along the lines:

    For a given circuit, made out of resistors (R), capacitors (C) and inductors (I), it is straight forward to compute the transfer function (input/output relationship) F. Given such a transfer function F, what would be a corresponding combination of R's, C's and I's? In other words, can you invert F?

  • I did my final project in undergrad on this type of stuff in 2006. It was a lot of fun:

    https://dl.dropbox.com/u/28315319/final_project.pdf

  • There was a very good general overview of this in Scientific American in Feb. 2003 by Koza, Keane and Streeter:

    http://www.eecs.harvard.edu/~rad/courses/cs266/papers/koza-s...

    The table listing patented inventions that had been recreated by the process was affecting.

  • This was one of the areas I wrote about wanting to do research in in my college application essay, but never did. I'll keep my eyes open for an opportunity to apply genetic algorithms; it should be fun.

    I'd like to hear if anyone's evolved significantly improved neural networks (instead of designing them). I don't know enough to say whether neural networks are good targets for genetic-algorithmic evolution, but it would be pretty fantastic to be able to easily evolve networks that are good at a simple specified objective (e.g. classification).

  • This kind of work is OK for some simple block level circuit designs. In the real world designs, as circuits grow complicated, and parasitics add in, the SPICE convergence issue kicks in and automation becomes difficult.

  • I love seeing work using evolutionary algorithms.

    This is a cool project of evolving a simple, yet efficient antenna:

    http://scienceblogs.com/goodmath/2008/11/11/evolution-produc...