4 ms·

Sample Efficient Evolutionary Algorithm for Analog Circuit Design

114 points by headalgorithm 7y ago

vessenes 7y ago
I'd love to see some sample circuits evolved -- I feel like humans might get stuck in known patterns, and I'm curious to see more 'random' circuits that still work.
- jandrese 7y ago
  Unfortunately genetic algorithms are notoriously bad about getting hung up on local minima/maxima. They'll probably produce a lot of really interesting patterns, but none that are notably better than what we do today.
  - DuskStar 7y ago
    Equivalent results but with lower engineering effort is still a gain, of course.
- the8472 7y ago
  There's Tompson's famous work with evolving circuit design on physical FPGAs[0] where the algorithms exploited analog properties of the discrete circuit elements, something no human would have done. [0] https://static.aminer.org/pdf/PDF/000/308/779/an_evolved_circuit_intrinsic_in_silicon_entwined_with_physics.pdf https://static.aminer.org/pdf/PDF/000/308/779/an_evolved_cir...
  - EvanAnderson 7y ago
    Discover Magazine had a very approachable article on this work: http://discovermagazine.com/1998/jun/evolvingaconscio1453 http://discovermagazine.com/1998/jun/evolvingaconscio1453
    - the8472 7y ago
      He asked to see some evolved circuits. The linked slides do (well, FPGA schematics), the magazine article does not.
      - djmips 7y ago
        No one asked for your comment. I hope it gets punished.
      - EvanAnderson 7y ago
        What motivates somebody to make a comment like this, out of curiosity? Was my link to an article that some people might find interesting hurting the discussion?
  - tehsauce 7y ago
    Super cool! Thanks for sharing
- gwern 7y ago
  They give a sorta example on https://arxiv.org/pdf/1907.10515.pdf#page=8 https://arxiv.org/pdf/1907.10515.pdf#page=8
deepnotderp 7y ago
Fascinating. We've been working on an internal project for layout of digital circuits using stochastic search and ML and have been having good results. ML and AI in general will likely have a pretty big impact on circuit design in the near future, excited to see other work in this area ^_^
- ultrasounder 7y ago
  Board level EE here of about 15 years here. Right now the most advanced PCB layout tool is Allegro which can route up to 20 positive layers. BUT, the autorouter is unusable. Wonder why Apple/Google/LAB126/MSFT maintain an army of "eCAD" engineers. If you can point me in the direction of any publication that your "internal project" has contributed to that would be great. IMHO, PCB layout is the most underappreciated engineering task in product development right now. At the speeds of PCI-E Gen4 the traditional lumped elements theory no longer hold good. So, interested to see whats coming my way so that i can be ready to pivot when "computers can actually make computers themselves".
  - ChuckNorris89 7y ago
    >BUT, the autorouter is unusable. Wonder why Apple/Google/LAB126/MSFT maintain an army of "eCAD" engineers. Because: 1. They're working on the cutting edge of miniaturization and autoroute functionality just doesn't cut it at that level. You need a human understanding of the end product as in consumer electronics you have to plan in advance several (often for lower cost) revisions of the same product for the future. 2. All the ML/AI experts are expensive and they have much lucrative fish to fry such as getting you to buy or click on things rather than optimize PCB aoutoroute for some eCAD company that can't justify their expense as most of their customers will still route by hand since the hardware business is very resilient to change. 3. PCB layout is done(in Western Europe at least) mostly by technicians, not engineers, and their labor costs are cheap as technical high-schools churn hundreds every year. You don't need a university degree and sometimes the company will pay your training for the eCAD tool they're using. In my area, a city with lots of hardware industry, it's basically a blue collar job. Source: FW dev in the consumer electronics business
amelius 7y ago
Bad news for Qualcomm? This makes me wonder, what if the algorithm finds a patented circuit, would it be allowed? Another thing I wonder is if instead of starting with a fixed topology, you start with a complete graph, would the algorithm automatically find the correct topology (where e.g. resistors that are dropped simply become very large). Or would it get stuck in a local minimum?
gumby 7y ago
This looks just like the simulated annealing work AI researchers were using on chip design and verification in the 1980s.
- B1FF_PSUVM 7y ago
  I think the trick is here: "In our proposed method, we devised a model to predict the performance before simulation and only simulate those samples which have better predicted performance." In other words, build a model for the system, use that for (cheap) sample point evaluation, occasionally check (doing an expensive circuit simulation) and adjust. P.S. back in 80s the guys doing simulated annealing were not claiming to be AI researchers, and the actual AI researchers were doing other stuff (neural networks and knowledge-based systems, among others).
  - peterwoerner 7y ago
    Surrogate modeling techniques have been around for a while. They come standard in many optimization software e.g. DAKOTA. https://dakota.sandia.gov/ https://dakota.sandia.gov/
  - gumby 7y ago
    There were some folks doing it at the mit AI lab where I also was at the time, hence my unfortunate conflation. I know there were folks elsewhere working on it too, sorry. (Not so much NN in the 80s except for a few holdouts like Rumelhart and Hinton).
- peterwoerner 7y ago
  That's because genetic algorithms and simulated annealing algorithms are really similar. You could imagine a GA as being a multiple simulated annealing algorithm in which you occasionally cross pollinated your solutions. Technically, in GA you keep the top solutions and SA you will move to a less optimal solution with some probability. But the mechanics of them are quite similar.
proc0 7y ago
So circuit design can be similar to certain software patterns. I wonder if this can be adapted to produce AST's and/or logic gates such that it can be run in some language. Interesting, will need to read through.
ycui1986 7y ago
Assuming the AI work perfectly, it will only be as good as the circuit simulation it can do. Unfortunately, there are some many things the start-of-art circuit simulation software cannot do. I really doubt the claim the author made here. Back in time around year 2000, Scientific American had published an article about using genetic evolution algorithm to create circuits. 20 years later, the same idea keeps pop up again and again, but no commercial product has really claimed they were generate by algorithm.
- rusticpenn 7y ago
  Because all such projects are purchased by cadence and other biggies and killed. The workflow is also completely different that it takes time for engineers to trust the new workflow. The difference between 20 years and now is the computing power. ( I have worked on such an automation tool )

114 points by headalgorithm 7y ago

I'd love to see some sample circuits evolved -- I feel like humans might get stuck in known patterns, and I'm curious to see more 'random' circuits that still work.

jandrese 7y ago
Unfortunately genetic algorithms are notoriously bad about getting hung up on local minima/maxima. They'll probably produce a lot of really interesting patterns, but none that are notably better than what we do today.
- DuskStar 7y ago
  Equivalent results but with lower engineering effort is still a gain, of course.
the8472 7y ago
There's Tompson's famous work with evolving circuit design on physical FPGAs[0] where the algorithms exploited analog properties of the discrete circuit elements, something no human would have done. [0] https://static.aminer.org/pdf/PDF/000/308/779/an_evolved_circuit_intrinsic_in_silicon_entwined_with_physics.pdf https://static.aminer.org/pdf/PDF/000/308/779/an_evolved_cir...
- EvanAnderson 7y ago
  Discover Magazine had a very approachable article on this work: http://discovermagazine.com/1998/jun/evolvingaconscio1453 http://discovermagazine.com/1998/jun/evolvingaconscio1453
  - the8472 7y ago
    He asked to see some evolved circuits. The linked slides do (well, FPGA schematics), the magazine article does not.
    - djmips 7y ago
      No one asked for your comment. I hope it gets punished.
    - EvanAnderson 7y ago
      What motivates somebody to make a comment like this, out of curiosity? Was my link to an article that some people might find interesting hurting the discussion?
- tehsauce 7y ago
  Super cool! Thanks for sharing
gwern 7y ago
They give a sorta example on https://arxiv.org/pdf/1907.10515.pdf#page=8 https://arxiv.org/pdf/1907.10515.pdf#page=8

deepnotderp 7y ago

Fascinating. We've been working on an internal project for layout of digital circuits using stochastic search and ML and have been having good results. ML and AI in general will likely have a pretty big impact on circuit design in the near future, excited to see other work in this area ^_^

ultrasounder 7y ago
Board level EE here of about 15 years here. Right now the most advanced PCB layout tool is Allegro which can route up to 20 positive layers. BUT, the autorouter is unusable. Wonder why Apple/Google/LAB126/MSFT maintain an army of "eCAD" engineers. If you can point me in the direction of any publication that your "internal project" has contributed to that would be great. IMHO, PCB layout is the most underappreciated engineering task in product development right now. At the speeds of PCI-E Gen4 the traditional lumped elements theory no longer hold good. So, interested to see whats coming my way so that i can be ready to pivot when "computers can actually make computers themselves".
- ChuckNorris89 7y ago
  >BUT, the autorouter is unusable. Wonder why Apple/Google/LAB126/MSFT maintain an army of "eCAD" engineers. Because: 1. They're working on the cutting edge of miniaturization and autoroute functionality just doesn't cut it at that level. You need a human understanding of the end product as in consumer electronics you have to plan in advance several (often for lower cost) revisions of the same product for the future. 2. All the ML/AI experts are expensive and they have much lucrative fish to fry such as getting you to buy or click on things rather than optimize PCB aoutoroute for some eCAD company that can't justify their expense as most of their customers will still route by hand since the hardware business is very resilient to change. 3. PCB layout is done(in Western Europe at least) mostly by technicians, not engineers, and their labor costs are cheap as technical high-schools churn hundreds every year. You don't need a university degree and sometimes the company will pay your training for the eCAD tool they're using. In my area, a city with lots of hardware industry, it's basically a blue collar job. Source: FW dev in the consumer electronics business

amelius 7y ago

Bad news for Qualcomm? This makes me wonder, what if the algorithm finds a patented circuit, would it be allowed? Another thing I wonder is if instead of starting with a fixed topology, you start with a complete graph, would the algorithm automatically find the correct topology (where e.g. resistors that are dropped simply become very large). Or would it get stuck in a local minimum?

gumby 7y ago

This looks just like the simulated annealing work AI researchers were using on chip design and verification in the 1980s.

B1FF_PSUVM 7y ago
I think the trick is here: "In our proposed method, we devised a model to predict the performance before simulation and only simulate those samples which have better predicted performance." In other words, build a model for the system, use that for (cheap) sample point evaluation, occasionally check (doing an expensive circuit simulation) and adjust. P.S. back in 80s the guys doing simulated annealing were not claiming to be AI researchers, and the actual AI researchers were doing other stuff (neural networks and knowledge-based systems, among others).
- peterwoerner 7y ago
  Surrogate modeling techniques have been around for a while. They come standard in many optimization software e.g. DAKOTA. https://dakota.sandia.gov/ https://dakota.sandia.gov/
- gumby 7y ago
  There were some folks doing it at the mit AI lab where I also was at the time, hence my unfortunate conflation. I know there were folks elsewhere working on it too, sorry. (Not so much NN in the 80s except for a few holdouts like Rumelhart and Hinton).
peterwoerner 7y ago
That's because genetic algorithms and simulated annealing algorithms are really similar. You could imagine a GA as being a multiple simulated annealing algorithm in which you occasionally cross pollinated your solutions. Technically, in GA you keep the top solutions and SA you will move to a less optimal solution with some probability. But the mechanics of them are quite similar.

proc0 7y ago

So circuit design can be similar to certain software patterns. I wonder if this can be adapted to produce AST's and/or logic gates such that it can be run in some language. Interesting, will need to read through.

ycui1986 7y ago

Assuming the AI work perfectly, it will only be as good as the circuit simulation it can do. Unfortunately, there are some many things the start-of-art circuit simulation software cannot do. I really doubt the claim the author made here. Back in time around year 2000, Scientific American had published an article about using genetic evolution algorithm to create circuits. 20 years later, the same idea keeps pop up again and again, but no commercial product has really claimed they were generate by algorithm.

rusticpenn 7y ago
Because all such projects are purchased by cadence and other biggies and killed. The workflow is also completely different that it takes time for engineers to trust the new workflow. The difference between 20 years and now is the computing power. ( I have worked on such an automation tool )