6 ms·

I did the same in Javascript a while ago with a genetic algorithm. http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hello-world/ http://www.puremango.co

by user24 15y ago

I did the same in Javascript a while ago with a genetic algorithm. http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hello-world/ http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hel... (HN discussion: http://news.ycombinator.com/item?id=2002673 http://news.ycombinator.com/item?id=2002673) Again just evolving a string not a full program. Mine hit the target significantly faster than OPs (around 70 generations rather than between 2 and 4 thousand). I'm trying to work out where he went wrong. First of all his 'mutate' function in the second example is actually performing both mutation and crossover. As far as the mutation goes it looks fine; almost identical to the way I mutate genes. I think the problem lies in the way he's doing his crossover (breeding), just trying to work it out. He's using one-point crossover, same as me. The selection method is a kind of hybrid elite method where fitter members are more likely to be selected than unfit members, which is reasonable. It might just be that his crossover and mutation probability is 100% and his population is only 20. But if you plug those figures into the interactive demo on my post (http://www.puremango.co.uk/genetic-hello-world.html http://www.puremango.co.uk/genetic-hello-world.html) then it gets as far as "Hbumr Xqnkd" by the 70th generation. Still looks like it's evolving faster than his code. Must be the way he's selecting parents...

pgroves 15y ago
I would agree. With a population size of only 20 the algorithm is closer to being hill-climbing with random restart. Crossover can't do much if there isn't a lot of diversity in the population, and a small population can't be very diverse. But it still worked.
- smoyer 15y ago
  And ... throwing away the least fit every time can lead you to climb the hill to a local maxima. In this case, the only way to leave a local maxima is to get lucky with a mutation, but if you cull the population randomly with a log probability that more fit parents will be kept, you could reach the goal in fewer generations. You could even eliminate mutations altogether if you have the proper character in each position in at least one member of the starting population.
- maercsrats 15y ago
  Right, I was thinking it was more of a random walk algorithm: http://en.wikipedia.org/wiki/Random_walk http://en.wikipedia.org/wiki/Random_walk There was too much randomness in his evolving. When I was evolving agents for my M.S., I used tournament selection (http://en.wikipedia.org/wiki/Tournament_selection http://en.wikipedia.org/wiki/Tournament_selection) with an 80% crossover rate for the top 2 winners and only a 5% mutation rate on the offspring. I also started off with a population of 500 individuals. This approach seemed to produce much better results.
  - user24 15y ago
    Yeah, I was taught roulette wheel at university but I think that tournament is a much better way of doing selection.
  - bermanoid 15y ago
    There was too much randomness in his evolving. When I was evolving agents for my M.S., I used tournament selection (http://en.wikipedia.org/wiki/Tournament_selection http://en.wikipedia.org/wiki/Tournament_selection) with an 80% crossover rate for the top 2 winners and only a 5% mutation rate on the offspring. I also started off with a population of 500 individuals. This approach seemed to produce much better results. I don't know about that - with a population size of 500, every generation is very expensive to test, so your runway is a lot shorter. I set up a test using your parameters, and it seemed to take an average of about 50 generations to evolve "Hello, World". That's a total of 50x500=25000 fitness evaluations (assuming you've cached results properly) to solve the problem. Whereas with a population size of 20, 100% crossover and mutation rates, the average is about 150 gens, for 150x20 = 3000 evaluations, beating your parameter set by a factor of 8. Which doesn't mean much, other than that this is not such a good problem to use evolutionary methods on.
bermanoid 15y ago
I just ran some tests, and actually, mutation and selection probabilities of near 100% are optimal, as is a very small population size, at least if you use the mutation and selection policies as given in this article (multiply two numbers on 0->1, multiply by population size, floor the result and select the candidate out of a fitness sorted array that has that index). When I say "optimal", you have to be sure to evaluate the population size multiplied by the number of generations to estimate how well the algorithm is doing, because a bigger population takes more work to evaluate even if it requires fewer gens. Honestly, I'm not sure why the OP's algorithm seems to take so long - with population of 20, and both crossover and mutation set at 100%, I'm seeing an average of about 190 generations needed to evolve a perfect "Hello, World" when started randomly (character codes between 32 and 127). This should be exactly the same setup as the OP has, though I haven't checked his code against mine in serious detail (mine is in JS). I just wrote my code up in a couple hours, so it's quite possible there's a mistake, but it seems unlikely that I coded a bug that made it perform better than it should... One difference I note is that the way he does crossover is actually two point crossover, in that he selects a start and end point randomly from a uniform distribution over the length. That's a little odd, but probably not a major problem: even when I disable crossover altogether in my code, and roll with mutation-only, I still end up with an average of 342 gens to reach the target, which is an order of magnitude under the 3100 that the OP claims it took for him. It's worth noting that the OP's first, "naive" algorithm, with a single member in the population, performed at roughly the same number of generations as the one with pop size of 20, mutation, selection, and crossover, according to his report. That's disturbing...I checked, and in my code the "naive" algo (mutate, then either accept or reject the mutation based on whether it's beneficial or not) performs at somewhere around 3000 generations to completion, which makes me suspicious that somewhere in OP's code there's a bug that's somehow missing out on the benefits (measured by gen count - see below) of having a higher population and crossover. FWIW, for this problem, at least the way the OP set it up, the "naive" algorithm is actually a very good way to go - when I increase the population size to 20, and set the mutation/selection/crossover policies OP used, I find that the average number of fitness checks required to hit "Hello, World" (about 3510) is actually higher than the number in the naive version (in the neighborhood of 3k, usually a bit under). Also, the real time taken is larger. Which means that adding "genetic" to the algorithm has actually hurt us... In fact, even with my full GA codebase in hand (not a substantial one, I wrote it in response to this post, but it's more flexible than the OP's), I couldn't find any situation where having a population size more than a few members helped - single member mutation (which is accepted/rejected if better/worse) always won. This is a good indication that this type of problem is vastly better suited to gradient descent than it is to a genetic algorithm. Of course, the reason for this is that the fitness landscape is very smooth, and the local gradient very accurately tells you where to go - an decent hill climber that knew how to work with integer parameters could solve this in probably ten or fifteen steps, max. Which reminds me, I keep meaning to write up an article on how to pick out problems where GAs are actually of some use. There are a few, but you almost never see them, and almost every demo I've seen on HN over the past few years would be better solved by gradient descent.

by user24 15y ago

pgroves 15y ago

I would agree. With a population size of only 20 the algorithm is closer to being hill-climbing with random restart. Crossover can't do much if there isn't a lot of diversity in the population, and a small population can't be very diverse. But it still worked.

smoyer 15y ago
And ... throwing away the least fit every time can lead you to climb the hill to a local maxima. In this case, the only way to leave a local maxima is to get lucky with a mutation, but if you cull the population randomly with a log probability that more fit parents will be kept, you could reach the goal in fewer generations. You could even eliminate mutations altogether if you have the proper character in each position in at least one member of the starting population.
maercsrats 15y ago
Right, I was thinking it was more of a random walk algorithm: http://en.wikipedia.org/wiki/Random_walk http://en.wikipedia.org/wiki/Random_walk There was too much randomness in his evolving. When I was evolving agents for my M.S., I used tournament selection (http://en.wikipedia.org/wiki/Tournament_selection http://en.wikipedia.org/wiki/Tournament_selection) with an 80% crossover rate for the top 2 winners and only a 5% mutation rate on the offspring. I also started off with a population of 500 individuals. This approach seemed to produce much better results.
- user24 15y ago
  Yeah, I was taught roulette wheel at university but I think that tournament is a much better way of doing selection.
- bermanoid 15y ago
  There was too much randomness in his evolving. When I was evolving agents for my M.S., I used tournament selection (http://en.wikipedia.org/wiki/Tournament_selection http://en.wikipedia.org/wiki/Tournament_selection) with an 80% crossover rate for the top 2 winners and only a 5% mutation rate on the offspring. I also started off with a population of 500 individuals. This approach seemed to produce much better results. I don't know about that - with a population size of 500, every generation is very expensive to test, so your runway is a lot shorter. I set up a test using your parameters, and it seemed to take an average of about 50 generations to evolve "Hello, World". That's a total of 50x500=25000 fitness evaluations (assuming you've cached results properly) to solve the problem. Whereas with a population size of 20, 100% crossover and mutation rates, the average is about 150 gens, for 150x20 = 3000 evaluations, beating your parameter set by a factor of 8. Which doesn't mean much, other than that this is not such a good problem to use evolutionary methods on.

bermanoid 15y ago

I just ran some tests, and actually, mutation and selection probabilities of near 100% are optimal, as is a very small population size, at least if you use the mutation and selection policies as given in this article (multiply two numbers on 0->1, multiply by population size, floor the result and select the candidate out of a fitness sorted array that has that index). When I say "optimal", you have to be sure to evaluate the population size multiplied by the number of generations to estimate how well the algorithm is doing, because a bigger population takes more work to evaluate even if it requires fewer gens. Honestly, I'm not sure why the OP's algorithm seems to take so long - with population of 20, and both crossover and mutation set at 100%, I'm seeing an average of about 190 generations needed to evolve a perfect "Hello, World" when started randomly (character codes between 32 and 127). This should be exactly the same setup as the OP has, though I haven't checked his code against mine in serious detail (mine is in JS). I just wrote my code up in a couple hours, so it's quite possible there's a mistake, but it seems unlikely that I coded a bug that made it perform better than it should... One difference I note is that the way he does crossover is actually two point crossover, in that he selects a start and end point randomly from a uniform distribution over the length. That's a little odd, but probably not a major problem: even when I disable crossover altogether in my code, and roll with mutation-only, I still end up with an average of 342 gens to reach the target, which is an order of magnitude under the 3100 that the OP claims it took for him. It's worth noting that the OP's first, "naive" algorithm, with a single member in the population, performed at roughly the same number of generations as the one with pop size of 20, mutation, selection, and crossover, according to his report. That's disturbing...I checked, and in my code the "naive" algo (mutate, then either accept or reject the mutation based on whether it's beneficial or not) performs at somewhere around 3000 generations to completion, which makes me suspicious that somewhere in OP's code there's a bug that's somehow missing out on the benefits (measured by gen count - see below) of having a higher population and crossover. FWIW, for this problem, at least the way the OP set it up, the "naive" algorithm is actually a very good way to go - when I increase the population size to 20, and set the mutation/selection/crossover policies OP used, I find that the average number of fitness checks required to hit "Hello, World" (about 3510) is actually higher than the number in the naive version (in the neighborhood of 3k, usually a bit under). Also, the real time taken is larger. Which means that adding "genetic" to the algorithm has actually hurt us... In fact, even with my full GA codebase in hand (not a substantial one, I wrote it in response to this post, but it's more flexible than the OP's), I couldn't find any situation where having a population size more than a few members helped - single member mutation (which is accepted/rejected if better/worse) always won. This is a good indication that this type of problem is vastly better suited to gradient descent than it is to a genetic algorithm. Of course, the reason for this is that the fitness landscape is very smooth, and the local gradient very accurately tells you where to go - an decent hill climber that knew how to work with integer parameters could solve this in probably ten or fifteen steps, max. Which reminds me, I keep meaning to write up an article on how to pick out problems where GAs are actually of some use. There are a few, but you almost never see them, and almost every demo I've seen on HN over the past few years would be better solved by gradient descent.