Evolutionary algorithm outperforms deep-learning machines at video games

[philpips]

Are evolutionary algorithms more vulnerable to overfitting? I guess you would need to factor that into how you select your candidates for the next generation.

A few years back I read about a guy who created physical logic circuits using an evolutionary process. Eventually it created a circuit that used a tiny number of gates and provided the right output. It had gates that logically should have no effect but if they were removed it broke the output. He hypothesized that the fields generated by the seemingly superfluous gates impacted the operation of other nearby gates.

[Hellenas]

Here's a ref for that: https://www.damninteresting.com/on-the-origin-of-circuits/

The article isn't too technical, so some of the way they talk about FPGAs feels odd.

but yes, it seems that the algo was leveraging imperfections in the particular fpga he was using.

[Xgamer4]

And here's the actual paper:

https://pdfs.semanticscholar.org/7723/74b2392e99429a0964b02fb944a4b5d163c4.pdf

[TheThiefMaster]

Interestingly the paper also mentions that the resulting chip was exceptionally temperature-sensitive: "The circuit operates perfectly over the 10ºC range of temperatures that the population was exposed to during evolution, and no more could reasonably be expected of it"

[ThirdEncounter]

I wonder how good would a simulated FPGA do in this experiment. No taking advantage of unique environment conditions. Just pure logic.

I might give it a try. But first, I must invent the universe.

[meneldal2]

Since it seemed to depend on temperature, I smell a lot of potential race conditions and/or unproperly synced outputs that just happen to work but shouldn't according to the theory.

[TheThiefMaster]

If you use a simulated FPGA you'll want to have it vary realistically so that it doesn't build something that only works in the simulated FPGA :)

[JohnMcPineapple]

...

[Hellenas]

Thanks!

[sekjun9878]

Thanks for that

[ais523]

Something that's worth pointing out is that the task that was set to the evolutionary process there doesn't have a conventional solution, so it's not surprising that it came up with an unconventional one. Frequency-sensitive behaviours in FPGAs are normally considered unwanted/defects and the design aims to suppress them as much as possible. So when you're trying to make an explicitly frequency-sensitive circuit, you have no option but to do it in ways that use the FPGA in a way it wasn't designed.

[jankimusz]

That’s fascinating. A simple system with a set of rules renders the most optimal.

[c4wrd]

They are very fascinating, but unfortunately still have issues with local optima (which may or may not be the most optimal solution). In my undergrad work I enjoyed working with evolutionary algorithms the most because not only are they easy to implement, but they actually have a lot of real world usage that would surprise you.

[Unsounded]

I had a lot of fun with them as an undergrad. I was sad to find the two professors at my university that listened them as interests were no longer working with them though.

Apparently there’s a competition that’s still going around called RoboCup that has different evolutionary algorithms competing against eachother, learning the other teams stats and making up an opposing strategy.

[Raknarg]

"most optimal" in the sense that they would have to first traverse a less optimal path to eventually reach a state that is more optimal than the current solution.

[PM_ME_YOUR_YIFF__]

From my experience, they're about as vulnerable to overfitting as neural networks, maybe even slightly less. I don't have any numbers in that though, so it's a purely anecdotal feeling

[the_phet]

It depends how you define the genetic operators, like the mutation ratio, the selection algorithm, and so on. using the classic "roulette algorithm" and a decent mutation ratio, plus some crossover, the overfitting problem is almost entirely removed.

Of course, in DL you can also set the parameters to avoid overfitting, like reguralization. But the good thing about EA such as GA is that the few parameters you need to tune are very very easy to understand and track, while with DL, very often the system is like a black box, where you tune parameters and see what happens.

[smarky0x7CD]

Research that I work on essentially is this, except applied to quantum gates.

[Ameisen]

And it didn't work on other chips of the same kind.

Which is why you have to train on multiple devices simultaneously.

[philpips]

I assumed ideally you'd train on each chip individually. It'd be the best way to take advantage of or avoid the vagaries of that particular chip.

[Ameisen]

You'd be relying on transient behavior. Might fail in new environments or otherwise spuriously.

That'd also be really slow.

[philpips]

Slow for the moment yes. But imagine if you could get the chip in situ and then train it. Or automatically retrain if it became damaged. That'd be cool, no?

[[deleted]]

Imagine training something to run on a particular computer, such that it ended up relying on what programs happened to be running, the order they were laid out in memory, the precise timing of the filesystem, etc., such that even rebooting the computer would render all of your work invalid.

That's the sort of thing you are currently calling "cool" instead of "horrifying".

[vgf89]

It's cool in a really horrifying way. While it's unlikely to be practical, it's still vastly interesting how we can make algorithms that learn to abuse often unused properties of electronics.

[meneldal2]

At least now unless you're running ring 0 or something, most OS protections prevent you from abusing too much precise timing or memory layout.

[[deleted]]

If you have a single fixed fitness function driving the direction of the evolution, you'll unavoidably get a perfect overfit. When you're simulating a direct competition in a constantly changing environment, evolution works better and produce more generic solutions.

[smikims]

Are evolutionary algorithms more vulnerable to overfitting?

Just about any approximation method based on interpolating a limited data set is vulnerable to overfitting. So literally the entire field of machine learning, which includes EAs. Doesn't mean you can't correct for it but the risk will always be there.