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

Genetic Algorithm Walkers

rednuht.org

Post reply on HN
Print view View original

41–50 of 75 posts

Re: Genetic Algorithm Walkers

#41

Post by fivedogit »

lukev wrote: post #36

One interesting thing is that progress very much happens by fits and starts, as it waits for the "lucky mutation" that will enable evolution to continue. For example, 0 Bedaaa Ceeici 6.07 1 Bocodo Bidobo 105.93 3 Aibebe Docoeo 107.74 7 Diaebe Eocoeu 107.88 10 Ciaabe Eocoeo 107.95 25 Diaebe Facodu 108.19 28 Biaebe Eocoeo 108.20 30 Biaeae Eacoeo 108.47 35 Beaebi Fucieo 109.88 36 Biaebi Eucici 203.60 42 Biaibi Fuceci 20…

This is called punctuated equilibrium. Evolution happens in fits and starts after periods of relative non-change.

http://en.wikipedia.org/wiki/Punctuated_equilibrium

Re: Genetic Algorithm Walkers

#43

Post by Houshalter »

saganus wrote: post #40

A bit OT, but I remember a very cool Quake2 mod that basically built a neural network so that bots could learn how to play. The useful part was that you could save the NN to a file, and so you could let Q2 run for hours (mostly I left it at night so it wouldn't prevent me from playing :) ) and the hext day I would save the progress. After about a week of doing this everynight, the bots evolved from just jumping aroun…

Someone made a GA evolve a hello world program in brainfuck. It's definitely possible, but incredibly inefficient.

Re: Genetic Algorithm Walkers

#45

Post by shkkmo »

You seem to have some bugs with the copying of champions and/or the identical reproduction of walks at the very short simulation length. Without having adjusted simulation parameters I no longer have my highest scoring walker saved as a champion.

Re: Genetic Algorithm Walkers

#46

Post by saganus »

nhzmju wrote: post #4

I was just about to give up at 70th generation, when the walkers suddenly evolved from 1 to 4 steps in 5 generations. Currently at generation 120 with 7 steps, looks like it is "evolving" in bursts, with long periods of nothing. Well it is stuck at 9 steps at gen 400+. 327 aibobe baeado 948.93 >> 548 aibobe baeado 1058.76 I wonder if the author got any further. I would say this is close to the limit.

It's interesting how I got:

0 Cicebi Bicedi 206.20

1 Cibebi Dibodi 208.03

4 Cobebi Bibedi 208.54

6 Cobebi Bobedi 208.68

8 Cocebi Boaedi 209.53

14 Cocibi Boaedi 310.47

20 Cocebi Boaedi 312.73

36 Cocebi Boaedi 312.85

38 Cocebi Biaedi 312.89

40 Cocebi Bobedi 314.06

58 Cocebi Bobedi 417.71

119 Cicebi Bibodi 522.37

331 Cicebi Bibuei 624.26

And at ~500 generations the champions are still the same 3. I have fiddled with the parameters several times to no avail. I've tried very little mutation probability (1-5%) with low mutation amount (1-10%) but also 75-100 mut. prob with 1-5% mutation amount and any figures in between and nothing seems to make it go out of the local minima.

Is there any way to get out of this? or when this happens in nature the species simply goes extinct or gets eaten by everyone else?

Re: Genetic Algorithm Walkers

#48

Post by saganus »

saganus wrote: post #46
nhzmju wrote: post #4

I was just about to give up at 70th generation, when the walkers suddenly evolved from 1 to 4 steps in 5 generations. Currently at generation 120 with 7 steps, looks like it is "evolving" in bursts, with long periods of nothing. Well it is stuck at 9 steps at gen 400+. 327 aibobe baeado 948.93 >> 548 aibobe baeado 1058.76 I wonder if the author got any further. I would say this is close to the limit.

It's interesting how I got: 0 Cicebi Bicedi 206.20 1 Cibebi Dibodi 208.03 4 Cobebi Bibedi 208.54 6 Cobebi Bobedi 208.68 8 Cocebi Boaedi 209.53 14 Cocibi Boaedi 310.47 20 Cocebi Boaedi 312.73 36 Cocebi Boaedi 312.85 38 Cocebi Biaedi 312.89 40 Cocebi Bobedi 314.06 58 Cocebi Bobedi 417.71 119 Cicebi Bibodi 522.37 331 Cicebi Bibuei 624.26 And at ~500 generations the champions are still the same 3. I have fiddled with the…

Ah.. seems like I finally got out of it at gen ~530 by changing the amount of champions to copy to increase the amount of gene variation in the pool.

I guess it kinda stuck into an inbreeding sort of loop.

Re: Genetic Algorithm Walkers

#49

Post by deong »

saganus wrote: post #40

A bit OT, but I remember a very cool Quake2 mod that basically built a neural network so that bots could learn how to play. The useful part was that you could save the NN to a file, and so you could let Q2 run for hours (mostly I left it at night so it wouldn't prevent me from playing :) ) and the hext day I would save the progress. After about a week of doing this everynight, the bots evolved from just jumping aroun…

There are branches of evolutionary computation that aim to evolve programs. The best known examples are Genetic Programming (GP) and Evolutionary Programming (EP). GP is by far the most popular today, and involves evolving source code, generally in Lisp-like languages where programmatically manipulating source code is a bit easier, but there are also GP approaches that use stack-based languages like Forth or Factor. I'm not aware of anyone trying to evolve code in languages like C++ or Java, but I suppose someone out there has probably experimented with it.

EP is about evolving finite state machines, and from there, you could presumably infer a program in the conventional way, although it might not be particularly nice for humans to read. Neither are the programs learned by GP though, for that matter.

Re: Genetic Algorithm Walkers

#50

Post by saganus »

Houshalter wrote: post #43
saganus wrote: post #40

A bit OT, but I remember a very cool Quake2 mod that basically built a neural network so that bots could learn how to play. The useful part was that you could save the NN to a file, and so you could let Q2 run for hours (mostly I left it at night so it wouldn't prevent me from playing :) ) and the hext day I would save the progress. After about a week of doing this everynight, the bots evolved from just jumping aroun…

Someone made a GA evolve a hello world program in brainfuck. It's definitely possible, but incredibly inefficient.

Wow. That does sound inefficient.
Post reply on HN