Optimise component values in circuits with Genetic Algorithms

[ai_maker]

Hi,

I'm delving into the details of Genetic Algorithms and I thought of a nice way to exemplify their deployment on electronics by automatically optimising the values of components in a circuit. I explain it in this post:

http://ai-maker.com/%EF%BB%BFproblem-state-encoding-in-genetic-algorithms-through-electronics/

I thought it might be of your interest. Regards,

Alex

[rs20]

Interesting. It would have been more compelling if,
a) The solution space wasn't so small that just brute-forcing it would be instantaneous (what language are you using that evaluating 4096 equations takes a whole second btw??), and
b) As a prep for running your GA, you hadn't solved the equations to the extent that solving by hand was trivial.

Side question, why do GAs need to be binary? It must be tough for a GA to transition from 011111 to 100000... Or is Gray code often used?

[JacquesBBB]

There is something I do not understand in your study.

Is there any more equation to solve than the one you mention relating the output voltage to the input voltage ?
If this is so,  the solution  depends only on the ratio Rf/Rg and is linear in this ratio, so can be easily solved.

Moreover, on your plot, the maximum are clearly aligned, probably  with this constant best ratio r=Rf/Rg.

Now I see a problem, as your maximum may well be only due to your discretisation.  Assume your best  solution
will be given for r=r0, a real number.

When you sample your resistors, Rf = n * x   and Rg=m*x,  where x is the discretisation step
you will  compute   r' = n*x/(m*x) = n/m , a rational number

Then, you may just reflect how  r0 is approximated by rationals, and the local maximum you find are just  that.

[alexanderbrevig]

Side question, why do GAs need to be binary? It must be tough for a GA to transition from 011111 to 100000... Or is Gray code often used?

They don't need to be binary, but you need to be able to do inheritance, crossover and mutation. If you do not use simple (very fast) operators for this, then the run time of your search will quickly end up being usable.

These 'genetic operations' happens a lot in a GA, and if they're slow it will quickly add up.

I'm on a machine with a Titan Z with 5760 cuda cores. This has a much easier time with floating point arithmetic. For serious deployment of genetic algorithms (and other machine learning techniques such as Neural Networks) doing the calculation on a heavily paralleled pipeline (i.e a graphics card with compute support) yields much better results. 

As a student I got tempted to make an OOP class library for GA and NN, although the code was easily read, the computer was not happy when trying to solve with it. I ended up reverting to a slightly more obfuscated bits in- bits out solver and I never looked back.

@JacquesBBB I presume this is just a sample problem. GAs shine when classifying the problem as *solved* close to impossible - which this particular one clearly is not.

Also, very nice work @ai_maker!

[nctnico]

Hi,

I'm delving into the details of Genetic Algorithms and I thought of a nice way to exemplify their deployment on electronics by automatically optimising the values of components in a circuit. I explain it in this post:

http://ai-maker.com/%EF%BB%BFproblem-state-encoding-in-genetic-algorithms-through-electronics/

I thought it might be of your interest. Regards,

Alex

A long time ago I did some research into the fitness of genetic algorithms. It turned out that GA are only suitable for problems with multiple equally acceptable outcomes. If a problem only has one solution a GA won't work. The way a GA works is that it finds extremes in a function. If a function only has one extreme then the GA will not converge.

[JacquesBBB]

@JacquesBBB I presume this is just a sample problem. GAs shine when classifying the problem as *solved* close to impossible - which this particular one clearly is not.

But his example, as demonstrated is not very conclusive.  Rf and Rg are totally correlated.  So  either one reduces the problem by using Rf/Rg as the new variables, or one leaves the two correlated variables. In this case, a
parameter determination method needs to find the full line as a family of equally possible solutions,
 and not a few points that will vary if the sampling is changed.

I suggest that ai_maker double the sampling a does the  same experiment again. Most probably the  "solution"
found by the algorithm will change.

[helius]

A long time ago I did some research into the fitness of genetic algorithms. It turned out that GA are only suitable for problems with multiple equally acceptable outcomes. If a problem only has one solution a GA won't work. The way a GA works is that it finds extremes in a function. If a function only has one extreme then the GA will not converge.

Well, this objection is true for any optimization strategy that works in a continuous field. It would be a problem for linear optimization as well, if there is no differentiable surface that describes optimality of the solution.
The reason that genetic algorithms (not to be confused with genetic programming which is something else) fell out of favor is that it is no better than, and usually much slower than sequential type algorithms.
See Mitchell, et al., "When will a genetic algorithm outperform hill climbing?" 1994.

[hamster_nz]

Sounds familiar...

http://hackaday.com/2012/07/09/on-not-designing-circuits-with-evolutionary-algorithms/

I also remember hearing something similar with FPGAs...

http://www.damninteresting.com/on-the-origin-of-circuits/

"It seems that evolution had not merely selected the best code for the task, it had also advocated those programs which took advantage of the electromagnetic quirks of that specific microchip environment. The five separate logic cells were clearly crucial to the chip's operation, but they were interacting with the main circuitry through some unorthodox method-- most likely via the subtle magnetic fields that are created when electrons flow through circuitry, an effect known as magnetic flux."

[helius]

http://www.damninteresting.com/on-the-origin-of-circuits/

4000 generations * 50 candidates in pool = 200,000 programming cycles. I hope it wasn't an Actel.
The size of the genome is 100 gates, which must have been a very small portion of the chip, unless it was a PALCE or something. Let's suppose that each gate has a 4-to-2 LUT and some muxes, about 40 configuration bits (after all, it is a simple device). So the bitstream is ~4000 bits, or about 1 generation (50 trials) required per bit. Somehow it seems less and less interesting as a viable technique.

[eneuro]

If a problem only has one solution a GA won't work. The way a GA works is that it finds extremes in a function. If a function only has one extreme then the GA will not converge.

I've played with GA more than 15 years ago and GAs was the only way to find best solution.
GAs do nothing usefull without good fitness function, so they are as smart as you are 

BTW: Finding values of only two resistors in OPs example is overkill, but there are many other difficult problems to solve by brute force even using latest fast CPUs.
Simply OPs problem is bad choice for demo of GAs power 

[ai_maker]

Thank you for your comments. Indeed, the example problem is a piece of cake. There's no need to apply GA for solving it, but I thought it would be a nice hack doing so. Btw, coming up with a suitable encoding and fitness function required some trial-and-error testing, it's not direct nor trivial why one method works and another doesn't. And putting degrees of freedom in the problem easily makes it intractable: for a 4 resistor transistor-based amp with degeneration, it took like 10 secs to solve (code written in Lua: https://github.com/ai-maker/aima/blob/master/src/genetic_algorithm.lua ), one or two resistors (or caps) more and you can go have a stroll around your village 'cos it's going to take a while. And wrt performance issues, Lua with the just-in-time compiler runs (almost) as fast as natively compiled C.

And regarding the resistor discretisation, I agree that sticking to the 10% resistor range available in the store is a somewhat artificial complication, but as said, solving this with GA was just for kicks.

Again, thanks a lot for your feedback!

[alexanderbrevig]

If you can describe the solution perfectly then GAs are usually not the best approach for searching for the solution.
If you can describe a good enough solution, then for some problem spaces (NP *) GA may be the only viable approach to get a satisfying answer.

I do not completely agree with the statement that GAs can not converge to one solution. For small problem spaces this entirely depends on the chosen heuristic. If the heuristic describe the perfect solution, then given a large enough population and generations - it will find the answer.
If you expand population and generations toward infinity then a GA can find an answer to any problem because it effectively would try ever answer. The one thing that restricts GAs in the real life is memory and run-time. Because of this, a good heuristic is a must - and good application. OPs example is not really a good application, but interesting none the less.

This is the first time I've come across using AI for EE. I'm a computer science AI major, so I will need to read more about what's been tried and what challenges there are in this field.

[ai_maker]

I support that the success of GA's is driven by the quality of the heuristic, and if this is clever enough to deal with one single extremum, the GA will succeed. I had posted another piece with a toy problem with GA using a chunk of the sinc function:

http://ai-maker.com/the-%EF%BB%BFgenetic-algorithms/

you can see how GA succeeds there as well.

@alexanderbrevig, I am unaware of the intersection of AI and EE, but I also find it interesting nonetheless. As far as I've been able to ask (it's been a modest polling, though), such applications (eg, filter synthesis) run by exhaustive linear search, no intelligence at all. Since I don't quite believe it, here I am :-)

[eneuro]

And wrt performance issues, Lua with the just-in-time compiler runs (almost) as fast as natively compiled C.

Had no idea what Lua is , while written GAs framework in C with inline assembly statements to use MMX, SSEx for crossovers, mutations, etc as well as optimized custom pseudo random generator which speeds up computations as well.
There are many ways to implement GAs, so talking about 10s, 5s doesn't makes sense, while someone else can run the same code on 10 computers in parallel and do it 10x faster than on one multicore CPU 

BTW: More real usage of GA in EE could be design of PCB to auto route and place SMD electronic components, so if find more time will try go back and write some code to design SMD PCB based on elements net lists and components footprints, but probably it has been already done 
Anyway it could be fun add some constrains on given elemns position on PCB and let route and place another to achieve different optimisation goals based on PCB requirements, track tolerances, etc....

[rs20]

BTW: More real usage of GA in EE could be design of PCB to auto route and place SMD electronic components, so if find more time will try go back and write some code to design SMD PCB based on elements net lists and components footprints, but probably it has been already done 
Anyway it could be fun add some constrains on given elemns position on PCB and let route and place another to achieve different optimisation goals based on PCB requirements, track tolerances, etc....

Maybe I've got a terrible imagination, but what does the "breeding" step of a GA autorouter look like? I mean, imagine two completely different layouts for the same circuit -- completely different, but both near-optimal solutions. How do you "breed" those two things together, without ending up with a circuit that's neither like original A, original B, nor a complete disastrous mess?

[hamster_nz]

Maybe I've got a terrible imagination, but what does the "breeding" step of a GA autorouter look like? I mean, imagine two completely different layouts for the same circuit -- completely different, but both near-optimal solutions. How do you "breed" those two things together, without ending up with a circuit that's neither like original A, original B, nor a complete disastrous mess?

My guess is that during the routing process you have points where the constraints and heuristics you have give you no strong preference as to which is the optimal choice to make - e.g. which of these signals do I route first? Which layer to put this signal on?  The 'gene' would be guide the choice to be made at such points of indecision....

[eneuro]

How do you "breed" those two things together, without ending up with a circuit that's neither like original A, original B, nor a complete disastrous mess?

This is quite interesting task for GAs 
Lets take example simple linear 4.1VDC psu I used to successfully power up crappy cell phone with its internal Li-on thrown away-I do not want charge phone to use it-just connect to car battery or solar panel and make call when I do want 

Components net list looks like this (UPS: duplicated R3 before update script run, so missed this when taking image, but principle doesn't change-we know all possible connectins needed)

Footprints are defined in schematics and this is text file so we can read it and import to our GA fitness evaulation function if needed.
Now lets code GA gene with elements, its position and orientation and assigned layer.
Our goal is to connect everything together using as low number of viases as possible.
We can represent PCB track as a vector with given length, thickness and assigned layer AND component pin/pad/vias/connector points so we are starting draw small track fragments coded as small discrete lengths lets say 1mm long with angle relative to previous segment coded in gene as well.
So yes, if our fitness function will be bad we end with complete mess and random curves starting from pins/pads, BUT smart fitness function can evaluate to solution where ONLY curves strting from given pins are connected at some points and in a way to avoid crossing with another net.

Basicly like humans tries to do design PCB, but.... evaluating it so many times per second and just watch how your schematics evaluates to something usable.

There can be a few possible correct solutions but but by adding another constrains we can dismiss unwanted ones and end up -hopefully-with nice designed PCB 
 

[ai_maker]

Although the post is focused on component value optimisation, indeed, other applications in EE are effectively solvable with AI, namely the PCB routing layout like you say, or VLSI layout problems (that was early 80's), as mentioned in the Russell and Norvig's book "AI: A Moden Approach".

[metacollin]

Any problem that doesn't need to be solved exactly, but where one of many solutions that are 'good enough' are acceptable, or, more generally put, anything humans have been doing manually, is fair game for neural networks or even evolutionary algorithms (genetic included, of course).  Neither humans nor the best autorouters 'solve' a board, but humans at least always manage to produce a solution that is 'good enough', and in certain situations autorouters can as well. 

Neither we nor computers can ever find the perfect way to route a board, and for any given board, there IS a perfect layout, and perfect way to route it (for all the different ways you would define 'perfect', which could vary board to board of course).  However, to find that perfect layout (and beyond that, know that it actually is the perfect layout) is whats called an NP Hard problem.  NP Hard problems are problems where computers are just totally fucked.  Any problem called NP Hard is basically a problem computers will never be able to solve algorithmically, regardless of how many more orders of magnitude CPU power continues to increase. 

However, as CPU power increases, neural network/neural turing machine based AIs will quickly be able to come up with the same, fuzzy, "non-perfect but still pretty good" solutions humans can and have been doing for ages.  This is by tackling the problem just like our brains do, and rather than finding 'the answer', it finds something that is not the answer, but is still good enough to be practical.

Cool post, ai_maker.  I have experience in genetic algorithms to train neural networks, but in the context of game AIs (I made little worms that run/wriggle around and eat food and avoid poison - hardly anything that will revolutionize an industry any time soon hehe). The take away here is not the immediate practicality so much as that ai_maker is taking some first steps in thoroughly documenting proof-of-concept like posts in the context of electrical engineering and optimization, and in a few years time, I think stuff like that may become much more relevant to your standard board jockey, not just intel VSLI wizards. 

[penfold]

I am aware of the use of genetic algorithms used to determine components for high order resonant power converters.  In these applications the problem is difficult to describe in terms of non-linearity, straight frequency response, component tolerance etc in analytical terms. GA's do a good job in getting through the massive search space and redesign and characterize inductors etc on the fly. In these cases the models are relatively simple, there are few components and spice style simulations can be performed to get a solution.

If you take a discrete circuit then there is not a great deal you can do with components, you are tied to a fixed number of resistor power ratings, each with their own quirks which have to be individually characterized and the search space becomes quite discontinuous, think what would happen if you mutated a 10k 1/4 Watt resistor into a 1 ohm 10 W wire wound resistor, that would introduce a huge discontinuity not only in value but in parasitics, however, if you could define resistances in say a 'field' of carbon ink which can grow and change shape continuously then youd be on to something. I'm not saying its impossible, but its a bit daft. Good solutions for discrete circuits are rarely realizable.

[eneuro]

However, as CPU power increases, neural network/neural turing machine based AIs will quickly be able to come up with the same, fuzzy, "non-perfect but still pretty good" solutions humans can and have been doing for ages.

Did you tried use Nvidia TESLA supercomputing for GAs frameworks? 
http://www.nvidia.com/object/tesla-supercomputing-solutions.htm

Take a free test drive and experience a significant speed up in your application. You can run your own code or try one of the preloaded applications like AMBER, NAMD, GROMACS and LAMMPS.

http://www.nvidia.com/object/gpu-test-drive.html

I've now real optimization problem that probably can be solved without GAs, but it can take some time to create *.DXF file to cut 2.1m x 2.8m wood plate to pieces 2cm wide and around maximum half meter long to let CNC manufacture as many as possible things like this proof of concept (*.STL file from my CAE written in C++ and imported to Blender to see if everything fits together).

Quick estimation based on total length of wood needed for one such thing is 11m, so around 26-27 can be made, but without close to optimum cut probably less and some amount of  garbage-fitness function simple minimalize useless wood garbage.
One such thing is made of 49 wood parts so I have to solve puzzle with about ~1300 parts 
Probably it will be warm up before more chalenging EE PCB design using GAs and with a litle effort my old GAs framework converted to support at least Nvidia CUDA should do the trick.
http://docs.nvidia.com/cuda/cuda-getting-started-guide-for-linux/

BTW: Do you use multiple point crosovers in your GAs frameworks?
I do with concept of probability masks, so I need to create as many random numbers as possible and I wonder if latest Nvidia CUDA or TESLA has some kind of hardware support for fast pseudorandom numbers genarators-I need set bits in mask with given probability and it could be nice to have hardware accelartion for this 

I was able qualify using this GAs framework (many times ago on quite slow CPUs but parallel MOSIX Linux OS) to championschips where humans had to solve many very difficult NP class problems, but of course do not participated since I do not think support of GAs in cluster of few computers  was allowed during final competitions 

[alexanderbrevig]

de facto lib for RNG with CUDA https://developer.nvidia.com/cuRAND

Inreresting project @eneuro!

[penfold]

A more appropriate application of GA solvers to EE is what is known as genetic programming, it basically uses a GA to manipulate the structure of a network. GP can be used to develop optimal  controller structures (which frequently come out as PID!) and filter structures.
If the filter can be implemented digitally then the system can be tested 'hardware in the loop' and hence can take into account things that would be almost impossible to model

[eneuro]

de facto lib for RNG with CUDA https://developer.nvidia.com/cuRAND

Thx for this hint   
At least found quite nice site with NVidia driver repos for Fedora 21 and was able compile cuRAND  host API demo and this thing can be really powerfull  to speed up my GAs framework

Unfortunatelly, was not able get acces so far to this NVIDIA® Tesla® K80 GPU Accelerators, to compare with quite cheap NVIDIA cuda GPU video card 
http://www.nvidia.com/object/gpu-test-drive.html
They promissed send instructions after registration but I do not know, maybe spam filter catched it 
Anyway, after looking latest @Dave http://www.eevblog.com/2015/04/02/dave-is-the-human-in-the-machine/  quite interesting intro to deap learning it is worth to upgrade GAs framework to run on modern GPUs 
http://en.wikipedia.org/wiki/May_the_Force_be_with_you

[alexanderbrevig]

Cool!
I've tried many of these https://developer.nvidia.com/gpu-accelerated-libraries and I tend to prefer Thrust for general purpose stuff. Then use a specialized lib that fit any particular need I may have. cuDNN, cuFFT and OpenCV are also frequent.
Try them out, in my opinion they are all awesome!