Genetic Algorithms
Well, as I mentioned earlier, one of my favorite things from University was Artificial Intelligence. And one of my favorite things in AI was something I never actually did in class, which is Genetic Algorithms. There were two Artificial Intelligence classes and I couldn't fit the second one which covered neural nets and genetic algorithms into my schedule so I looked up the course topics on the professors website and learned about them on my own time.
To this day I think Genetic Algorithms are by far my favorite type of Artificial Intelligence construct. They can be complicated to setup, but if designed well they have the most flexibility. Neural nets from what I've seen have results which are very much tied to the design. I never got very far in researching them, but it didn't seem like there was a lot you could toy with once you got into a design. Certain weights could be changed, but not much else. I'll assume at this point that I could be drastically wrong. But the point is simply, that from what I've seen GA's are easier to implement, easier to understand and easier to tweak.
So, the point of all of this? One of the things I wanted to do was incorporate AI into data structures as well as using it to solve obscure problems. So I went in search of a challenge today. I wanted to find something small but interesting to model as a GA. The answer came in the form of doing something someone else had already done without looking at their code. The idea was a "Hello World!" application for Genetic Algorithms. Basically, start with a population of randomly generated strings and evolve them until they spell "Hello World!".
Original link was here. For my day #1 approach I kept to his "cheat" that we only generate populations with string lengths equal to the target string length, but made mine more complicated :) what I loved about GA's was implementing survival of the fittest into a computer algorithm and watching the weakest get eliminated, so I added a plethora of variables that affected the outcome. I have a variable to choose the percentage of the population that "lives" to reproduce, I have a variable to control the odds of a strong gene mixing with a weak gene to vary up the results. You can control the potential litter size and the minimum and maximum population sizes during a given generation.
First attempt worked out splendidly. Next task I think will be to try different modifications to my fitness calculation and to remove the limit on the length of the string. Honestly, I think it should be simple for the strings to eventually "evolve" to the correct length; in fact this should be as easy as making the penalty for the amount of characters a candidate is off of the target to a substantially large number (one larger than the largest penalty possible for a single character being wrong should suffice).
With the way I implemented the "mating" process such that one parent is chosen starting from the top of the survivors and the second chosen from the bottom, the quickest way to get to the best solution at the moment is to kill off a large part of the population :) the other variables seem to have a bit of impact. It is worth noting that when I start by choosing both parents from the top of the survivors it was SLOWWWWW, in fact no combination ever resulted in anything but a rare chance of finding the solution in less than a thousand generations. After a few generations, the top candidates were always so similar that not enough change was occurring without increasing the rate of mutation which would simply make the virtual evolution closer to random rather than "genetic" and organic seeming. Perhaps tweaking my fitness calculation will resolve this... and perhaps not.
Anyway... I know it was nerdy... but that was a fun day.
To this day I think Genetic Algorithms are by far my favorite type of Artificial Intelligence construct. They can be complicated to setup, but if designed well they have the most flexibility. Neural nets from what I've seen have results which are very much tied to the design. I never got very far in researching them, but it didn't seem like there was a lot you could toy with once you got into a design. Certain weights could be changed, but not much else. I'll assume at this point that I could be drastically wrong. But the point is simply, that from what I've seen GA's are easier to implement, easier to understand and easier to tweak.
So, the point of all of this? One of the things I wanted to do was incorporate AI into data structures as well as using it to solve obscure problems. So I went in search of a challenge today. I wanted to find something small but interesting to model as a GA. The answer came in the form of doing something someone else had already done without looking at their code. The idea was a "Hello World!" application for Genetic Algorithms. Basically, start with a population of randomly generated strings and evolve them until they spell "Hello World!".
Original link was here. For my day #1 approach I kept to his "cheat" that we only generate populations with string lengths equal to the target string length, but made mine more complicated :) what I loved about GA's was implementing survival of the fittest into a computer algorithm and watching the weakest get eliminated, so I added a plethora of variables that affected the outcome. I have a variable to choose the percentage of the population that "lives" to reproduce, I have a variable to control the odds of a strong gene mixing with a weak gene to vary up the results. You can control the potential litter size and the minimum and maximum population sizes during a given generation.
First attempt worked out splendidly. Next task I think will be to try different modifications to my fitness calculation and to remove the limit on the length of the string. Honestly, I think it should be simple for the strings to eventually "evolve" to the correct length; in fact this should be as easy as making the penalty for the amount of characters a candidate is off of the target to a substantially large number (one larger than the largest penalty possible for a single character being wrong should suffice).
With the way I implemented the "mating" process such that one parent is chosen starting from the top of the survivors and the second chosen from the bottom, the quickest way to get to the best solution at the moment is to kill off a large part of the population :) the other variables seem to have a bit of impact. It is worth noting that when I start by choosing both parents from the top of the survivors it was SLOWWWWW, in fact no combination ever resulted in anything but a rare chance of finding the solution in less than a thousand generations. After a few generations, the top candidates were always so similar that not enough change was occurring without increasing the rate of mutation which would simply make the virtual evolution closer to random rather than "genetic" and organic seeming. Perhaps tweaking my fitness calculation will resolve this... and perhaps not.
Anyway... I know it was nerdy... but that was a fun day.
Comments
Post a Comment