6 ms·
Show HN: A Genetic Algorithm I wrote in JavaScript to evolve "Hello World"
- user24 16y agoThe code's fairly messy, but I hope the blog post and online demo will be enough to give the absolute beginner a good idea of how GAs work. One day I hope to apply machine learning to the art of predicting real-life events. This is one small step towards that project, and I'd love to hear your feedback! - But it's 1AM now so I'll be offline for the next few hours. Here's hoping I wake up to a million upvotes! :)
- anathem 16y agoRelated: * http://www.jurisgalang.com/2010/10/13/breeding-images/ * http://www.jurisgalang.com/2009/02/01/breeding-strings/
- yters 16y agoUnfortunately there is something called the no free lunch theorem. Puts a significant constraint on using machine learning for real-life prediction.
- Groxx 16y agoTo that end, I propose a new acronym: The TISATATTANSTAAFLT (pronounced: "tiz-a tat tan staa fult") The "There Is Such A Thing As The There Ain't No Such Thing As A Free Lunch" Theorem.
- tel 16y agoThen again, all ML eventually is used for real-life prediction, so you ought to be able to buy a lunch if you really want one. The GA here is a fun start that'll introduce a training algorithm; there are plenty of gradient-aligned steps forward.
- yters 16y agoSure, I'm just saying ML, just like its forebear AI, doesn't live up to the hype. Lunch is very expensive.
- tel 16y agoProbably true. I'm not a big fan of the term ML due to the hype associated with it. Statistics however, which is pretty near the same thing most of the time, has proven itself quite often.
- user24 16y agoYou never know until you try ;)
- yters 16y agoVery true. I try jumping off of cliffs all the time cuz this time I might just fly!
- user24 16y agoRight. I'll just give up then. It's a good job no-one wasted time trying to apply machine learning to speech recognition, cuz there's no free lunch you know. Or handwriting recognition. Or housing prices. Or game strategies. Thanks for letting us know that there's no point searching for a solution via ML. Phew!
- deleted 16y ago[deleted]
- IsaacL 16y agoAren't genetic algorithms and machine learning distinct? I'm far from an expert, but my understanding is that with ML you're either trying to find a function (supervised) or clusters (unsupervised), whereas GA are a generic optimisation technique. Maybe you could generate a bunch of different versions of an ML algo (say, ANN with different numbers of hidden nodes and starting weights), and use GA to evolve the best one. Doesn't seem like the best technique, though.
- user24 16y agoYeah, I've heard of using GA to find good weights for an ANN. GAs are general optimisation techniques, but 'evolutionary computing' is very closely linked to AI and ML.
- kurin 16y agoGeez. Tried to do this myself. 10k generations in and still not a recognizable string.
- kurin 16y agoOkay. It helps if you sort your fitness correctly. Also it looks like if you keep mutations too low, you'll get stuck in a local maximum.
- jerf 16y agoI don't think there's a local optima here. The gradient with respect to the individual characters always points you at the solution, from all states. Pathologically so, even. But it makes for a good learning problem since the problem space actually fits in human heads and you can clearly see what the GA is doing. When you fire a GA at a real problem you won't have that luxury.
- SeanLuke 16y ago> I don't think there's a local optima here. The gradient always points you directly at the solution, at all times, in all states. Well, there are no local optima but plenty of global optima other than the correct answer, I think: "Hello, World!" and "!dlroW ,olleH" have the same fitness for example. So no, the gradient won't necessarily lead you to the solution. Now, suppose we defined the fitness function instead as the number of correct characters plus the number of characters in the right place, then we'd have local optima and a better chance of getting to the optimum.
- abhikshah 16y agoThe fitness function does take char location into account. In python, it'd be -1*sum(abs(x-y) for x,y in zip(chromosome,target)). The gradient here is continuous and smooth. Problems where GA is an appropriate solution have fitness landscapes that are much more pathological.
- tassl 16y ago
- cgs1019 16y agoThe author clearly put a lot of work into both the implementation and the presentation as well as the accompanying blog post (I love the quotes interspersed; reminds me of my college Abstract Algebra text by Gallian). However, I must say I was hoping for a GA that evolved a /program/ to print "Hello, world". Maybe in a follow-up post? :D [EDIT: s/GE/GA/ ... not sure why I got that wrong...]
- Vivtek 16y agoI almost made this same comment before noticing yours.
- user24 16y ago:D Thanks for your positive comments! > I love the quotes interspersed You've no idea how hard it is to find good quotes about mutation! (I did try to find a good TMNT quote at first...) > I was hoping for a GA that evolved a /program/ That would be very cool. I think my next project is going to be a neural network script. But I may revisit genetic algorithms again too, and at that point I'll probably look into genetic programming.
- Groxx 16y agoIn my artificial neural networks class, we had a guy who attempted to do just this... in bash... to generate C code... using temp files to pass data around. They didn't get far, but did actually manage to get something to print after a few hours, though it never seemed to get closer to "hello world" after that point. We figured it was just that the GA was a bit overly proud of its accomplishment, and wasn't interested in improvement. This is with random strings inside a main() wrapper with stdio, and nothing else. I forget what their fitness function was, but I'm fairly certain it wasn't too simple, and I think that shot them in the foot near the end. I still boggle at the attempt; I built a maze solver in Ruby that handled changing mazes by ant-trail-like solving (I forget the term...) that only took me a handful of hours. Then I spent another 10 to make modifying the maze as simple as possible, and I made a dozen or so wildly different mazes with moving walls, transporters, etc while doing my presentation to demonstrate that it worked. I think that may have won me more points than the functioning code; lots of people's barely worked, and nobody else had anything they could run in reasonable times during a presentation.
- StavrosK 16y agoThe term is Ant Colony Optimization: http://en.wikipedia.org/wiki/Ant_colony_optimization http://en.wikipedia.org/wiki/Ant_colony_optimization
- Groxx 16y agoThat's the one, thanks! And ooh, I hadn't thought of setting it up for a traveling salesman problem... that does seem like a good application. Never knew that was one of the first uses; the moment I grasped the principles, maze-solving seemed a logical use.
- StavrosK 16y agoI did try that once, the results were very good, though not optimal. It did converge very quickly to a good solution, however.
- user24 16y ago
- icefox 16y agoA few years ago I made up this [generic] genetic algorithm page in javascript. http://icefox.github.com/javascript_genetic_algorithm/?program=JavaScript%2520Genetic%2520Algorithm http://icefox.github.com/javascript_genetic_algorithm/?progr... The neat part about it was that you could put in your own problem and have it solve it. I took a minute and slapped together the Hello World! version of this problem. You can copy it into the text box and play with the parameters (and resulting graph output. The output isn't a pretty as the link and it runs slower, but still neat. function salesman() { this.target = "hello world!"; this.points = [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '!', ' ' ]; this.fitness = function(chromosome) { // higher fitness is better var f = 0; // start at 0; the best fitness for(var i=0, c=this.target.length; i<c ; i++) { f -= Math.abs(this.target.charCodeAt(i) - this.points[chromosome[i]].charCodeAt(0)); } return Math.abs(f); }; // the size of values that should be passed to fitness this.numberOfArgs = function() { return this.target.length; }; // the max value needed for the arguments this.maxArg = function() { return this.points.length; }; // convert the current chromosome value which can have a maxValue // into something fitness can use. this.getArg = function(value, maxValue) { return Math.round(value * (this.points.length - 1) / maxValue); }; // Paint the solution onto bestimage this.paint = function(values) { var canvas = document.getElementById('bestimage'); if (canvas.getContext){ var w = canvas.width; var h = canvas.height; var canvasContext = canvas.getContext('2d'); canvasContext.clearRect(0, 0, w, h); canvasContext.font = "italic 200 12px/2 Unknown Font, sans-serif"; canvasContext.strokeStyle = "blue"; for (var i = 0; i < values.length; ++i){ canvasContext.strokeText(this.points[values[i]], i*10, 10); } } } } salesman;
- JohnIdol 16y agoNice. I did something similar in javascript --> https://github.com/JohnIdol/WasDarwinWrong https://github.com/JohnIdol/WasDarwinWrong ... and C# --> https://github.com/JohnIdol/typingmonkey https://github.com/JohnIdol/typingmonkey
- agnt666 16y agoRecently, I also wrote (C#) a string evolver using a GA: https://github.com/dreasgrech/StringEvolver https://github.com/dreasgrech/StringEvolver I tried 3 different types of fitness functions: Per-Character error summation, Levenshtein Distance and Hamming Distance. I found that Hamming Distance produced the quickest convergences. The code for my project is "fully OOP" so you can switch implementations for crossover, mutation and selection operators and also for the fitness functions. Go ahead, fork me ;-)