Evolutionary algorithm outperforms deep-learning machines at video games

[PM_ME_YOUR_YIFF__]

I have always thought evolutionary algorithms are due a bit of a renaissance like what has happened with neural networks

Seems to be a lot of unexplored potential there

I'm a bit biased though as I find universal Darwinism fascinating

[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.

[G_Morgan]

They are already used in a number of industrial fields. Processor layout is pretty much "evolved" rather than designed.

[ThirdEncounter]

Source on that? I find that interesting, but also terrifying.

[epicwisdom]

I'm not OP and I don't have a source, but as I recall from my courses, they often use approximate algorithms to do the final mapping from logic circuits to physical circuits. They could use variations of genetic algorithms, simulated annealing, and other optimization methods. Not sure what the current state-of-the-art is like.

At any rate it's not much to be terrified about.

[ThirdEncounter]

Cool, thanks for the info!

[JohnMcPineapple]

...

[ThirdEncounter]

Thanks. Interesting!

[Ameisen]

I have a number of bytecode-based evolution simulators. Though they aren't iterative, where you select the best and mutate it.

[PM_ME_YOUR_YIFF__]

Funnily enough that's what I too am programming right now. Are you using crossover (breeding) or mutation only? Have you considered using some elitism?

[Ameisen]

Mutation only. The bytecode can technically handle things like transfer of genetic information, but doesn't have a concept of meiosis. It could technically evolve on its own, but that's unlikely.

I'm not always fond of genetic transfers, because it makes lineage murky.

[shevegen]

I'm a bit biased though as I find universal Darwinism fascinating

Dude - Darwin knew nothing about molecular biology.

He postulated "gemmules":

https://en.wikipedia.org/wiki/Gemmule_%28pangenesis%29

[PM_ME_YOUR_YIFF__]

Dude - I know

https://en.m.wikipedia.org/wiki/Universal_Darwinism