Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Genetic brainfuck programming

github.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Genetic brainfuck programming

#21

Post by Someone »

robert_tweed wrote: post #19
reitzensteinm wrote: post #2

It's been a decade since I have written a BF program, but if I'm not mistaken, the winning strand in the gif example has quite a bit of dead code, for example here: [[]+ +,] This entire loop must always be skipped, because if entered, the inner [] loop will also enter, and run indefinitely. It would be cool to run it through more iterations, to get to the local minimum of length, rather than just a correct program.

This appears to be GA rather than GP, but I did some experiments with GP a while ago and the most counterintuitive thing I discovered was how essential junk code turns out to be. First, for anyone unaware of the difference, in Genetic Algorithms (GA) you have fixed-length strings of instructions. Genetic Programming (GP) is a superset in which you have ASTs, which can get arbitrarily large (which can be a problem if…

"Once you get down into final generations you can start running optimisations [...] but DNA doesn't come with an optimiser."

It better not, as DNA isn't planning to "get down into final generations". The Borg would be long dead if it ever stopped adapting.

Re: Genetic brainfuck programming

#22

Post by ctdonath »

robert_tweed wrote: post #19
reitzensteinm wrote: post #2

It's been a decade since I have written a BF program, but if I'm not mistaken, the winning strand in the gif example has quite a bit of dead code, for example here: [[]+ +,] This entire loop must always be skipped, because if entered, the inner [] loop will also enter, and run indefinitely. It would be cool to run it through more iterations, to get to the local minimum of length, rather than just a correct program.

This appears to be GA rather than GP, but I did some experiments with GP a while ago and the most counterintuitive thing I discovered was how essential junk code turns out to be. First, for anyone unaware of the difference, in Genetic Algorithms (GA) you have fixed-length strings of instructions. Genetic Programming (GP) is a superset in which you have ASTs, which can get arbitrarily large (which can be a problem if…

I hope you've written this up somewhere for publication. You've solved the "junk DNA" issue with computer science.

Best post on HN ever.

Re: Genetic brainfuck programming

#23

Post by robert_tweed »

ctdonath wrote: post #22
robert_tweed wrote: post #19

Earlier quoted context omitted.

This appears to be GA rather than GP, but I did some experiments with GP a while ago and the most counterintuitive thing I discovered was how essential junk code turns out to be. First, for anyone unaware of the difference, in Genetic Algorithms (GA) you have fixed-length strings of instructions. Genetic Programming (GP) is a superset in which you have ASTs, which can get arbitrarily large (which can be a problem if…

I hope you've written this up somewhere for publication. You've solved the "junk DNA" issue with computer science. Best post on HN ever.

It's already documented. I just didn't pay much attention and was thus able to verify what others have observed. I highly recommend the book "A Field Guide to Genetic Programming", which covers this and other associated topics. It's one of the best CS books I've read in the last few years.

Re: Genetic brainfuck programming

#24

Post by nazka »

apl wrote: post #18
jostmey wrote: post #10

Earlier quoted context omitted.

I guess I was trying to draw a distinction between biological systems and man made machines. I find the difference striking. I can look at a car engine, and if I stare at it long enough, I can make sense of it. The engine makes sense to me not just because it was designed by another human but also because its design is non-random. When I stare at the protein KcsA, which is the biological system that I study, I cannot…

> The most striking characteristic of a randomly designed > system is that you cannot restart it. Once you shut it off > it dies permanently. I don't see how that is a consequence of the underlying design principle. There are many organisms that survive de-facto death through freezing etc. You could also engineer machines to not be restartable, and under certain circumstances that may be a desirable feature. There's…

Yes saying it is that random is like to expect nature to build a complex organism like us by only being like a monkey typing randomly on the keyboard of chemistry, physics etc... and be able to create that.

Even if it was the case then the earth would be full of defective cells to animals across the whole tree of life with only a few working well. It's not what we find when we mine the earth or what we have today.

But even still with a "keyboard" that complex.. You will need more than billions of years to accomplish something that complex randomly.

Re: Genetic brainfuck programming

#26

Post by LnxPrgr3 »

robert_tweed wrote: post #19
reitzensteinm wrote: post #2

It's been a decade since I have written a BF program, but if I'm not mistaken, the winning strand in the gif example has quite a bit of dead code, for example here: [[]+ +,] This entire loop must always be skipped, because if entered, the inner [] loop will also enter, and run indefinitely. It would be cool to run it through more iterations, to get to the local minimum of length, rather than just a correct program.

This appears to be GA rather than GP, but I did some experiments with GP a while ago and the most counterintuitive thing I discovered was how essential junk code turns out to be. First, for anyone unaware of the difference, in Genetic Algorithms (GA) you have fixed-length strings of instructions. Genetic Programming (GP) is a superset in which you have ASTs, which can get arbitrarily large (which can be a problem if…

Stanford researchers did something similar for superoptimization: http://cs.stanford.edu/people/eschkufz/research/asplos291-sc...

They separate the problem into two phases: the first is only worried about correctness, then the second deals with optimization while (eventually) preserving correctness.

Re: Genetic brainfuck programming

#27

Post by j42 »

jostmey wrote: post #8

As someone with a background in computer programming, I found biology quite frustrating. I wanted to see some underlying structure or meaning in the genetic code. It took me a long time to realize that it wasn't there. Biological systems and their genetic codes are the result of random trial and error filtered through Natural selection. Biological systems clearly have a design because you see the same "form" reappear…

So essentially, we are "shakespeare" produced unknowingly by the infinitum of proverbial (and literal) monkeys :)

Re: Genetic brainfuck programming

#28

Post by FranOntanaya »

jostmey wrote: post #8

As someone with a background in computer programming, I found biology quite frustrating. I wanted to see some underlying structure or meaning in the genetic code. It took me a long time to realize that it wasn't there. Biological systems and their genetic codes are the result of random trial and error filtered through Natural selection. Biological systems clearly have a design because you see the same "form" reappear…

You can see this with a sim called DarwinBots. Hand-crafted code is as clever as it can be. Code evolved from zero is a bunch of gibberish that just happens to hit the right spots here and there. The key is reverse engineering what effect the evolved code is actually going after.

Re: Genetic brainfuck programming

#30

Post by tripzilch »

kozlinov wrote: post #20
jostmey wrote: post #8

As someone with a background in computer programming, I found biology quite frustrating. I wanted to see some underlying structure or meaning in the genetic code. It took me a long time to realize that it wasn't there. Biological systems and their genetic codes are the result of random trial and error filtered through Natural selection. Biological systems clearly have a design because you see the same "form" reappear…

Ironically, the theoretically optimal programs for computers would not be sensible for human understanding as well, so it is probably not that different.

You sure? How do you know? Is this based on research or gut-feeling? (if it's the former I'd be real curious to read about it)
Post reply on HN