Genetic Algorithms

Not exactly a question, FYI

I'm taking a course (outside of Treehouse) on complexity and complex systems, and I just finished the course on genetic algorithms (aka GA's). I was fascinated by the content, and so I decided to build a simple Python program to find "strategies" for playing a simple game.

I found it really interesting, and so I wanted to share my understanding of GA's with the community.

A genetic algorithm is a sort of machine-learning algorithm that "evolves" over time. For example, a long time ago, the ancient dinosaurs dominated the world. But eventually their species died out. More often, though, species over time better adapt the situation, thus "evolving." Computer scientists discovered that this could be applied to AI, too, so out sprang the idea of a "genetic algorithm."

In a genetic algorithm, there are bits of "DNA", or sequences of digits. (it could be letters, too, but let's stick to using digits.) The idea of a genetic algorithm is that two parents create offspring with a mix of their DNA with some minor tweaks added. Then those children have their own children... etc.

Imagine that you had each piece of DNA represent two "strategies" for a game. We have some method of encoding that strategy as a string of numbers 1-6:

Strategy 1:
2226626265146121152464546431123316346556662621534243246622241433666225431315254421251666521416222653

Strategy 2:
3112143224626663652355143323543331311511115344431641153654136665463312443223355454654135666631266152

Now imagine if you could somehow "mesh" those two strategies together to make a child. How would you do that? Well, you could split the sequences somehow, and recombine it:

New strategy:
2226626565146121152464546431123316346556662621534243246622241684633124432233554446541356666312661212

Notice that the first part of this strategy is somewhat like that of the first strategy, and the last bit looks somewhat like the last part of the second strategy. Also note that there are a few random tweaks in addition to that. Now, we can test this strategy and see if it is successful. If so, great! We came up with a new, working strategy!

Now imagine that we started with 1000 strategies. We could filter out the bad strategies, and pair up the good strategies randomly, and combine the strategies to produce new strategies, and then we could take those strategies, and repeat.

We continue to do this as many times as we want, then we can select the best strategy out of the remaining strategies, and that will be the final result! The computer can execute that strategy, and it may even outwit a human being!

Now, of course gameplay AI isn't the only thing a genetic algorithm can help make. It can even generate random music/art just by listening/looking at multiple pieces of art/music, and somehow combining them!

GA's are very fascinating and worth learning, and so I hope enjoyed this topic! Please leave comments below.

Happy coding! ~Alex