Published on 3/22/2015
The term "genetic algorithm" has an aura of mystery surrounding it, so I decided to dive in and see what all the fuss is about. When you boil them down and look at the essentials, genetic algorithms aren't that complicated - and they can help you find an optimal solution to complex combinatorial problems.
The big idea at the heart of GAs is this: randomly create a "population" of possible solutions to your problem, combine and modify those solutions in different ways to create new solutions, evaluate the new solutions to see how effective the are, and then rise and repeat.
Genetic algorithms have five main parts:
GAs manipulate possible solutions to our problem, which means that we need to devise a way to format our solutions in such a way that an algorithm can process them. Throughout this post, I'm going to use the Traveling Salesman Problem (TSP) as an example. Suppose we have a salesman that needs to visit 10 different cities. We know the distances between each of the cities, and we want to find the shortest round-trip route for the salesman that will take him to each of the cities only once.
In this example, the solution to our problem will take the form of a path - an ordered list of cities that the salesman will visit. We can represent each city with an integer, and use a vector to make our list of stops. Assuming that we have 10 cities to visit, a possible solution would look like this:
[3 5 4 6 2 7 8 1 9 0]The solution above means the salesman would start in city 3, travel to city 5, then city 4, etc (you get the idea) and finally return to city 3.
In my opinion, encoding is the most difficult part of creating a GA. While it may seem obvious for the TSP, the method of encoding is going to be different for most problem domains and you may have to get pretty creative.
In Clojure, creating a random population is pretty easy:
The end goal of our GA is to find the optimal solution to our problem, so we need to give our GA the ability to determine how effective a given solution is. This measure of a solution is know as its fitness score.
For our example, we want to find the shortest path that the salesman can take - that means that our fitness score would simply be the total distance the salesman must travel. Let's define our data and a helper function to get the distance between two cities.
Our distance data is contained in a 2d vector, but you can think of it like a table:
|City 1||City 2||City 3||...|
With our data in this format, we can define a function that will calculate the fitness score for a given solution.
The meat of a GA is in the crossover function, but before we get to that, we need to determine which solutions in our population will be paired up in the crossover. This process is often called selection, and there are many different approaches to explore. I'm going to cover two possible selection processes - tournament selection and roulette selection. The outcome of these selection processes is going to be a vector that places mates next to each other:
[a1 a2, b1 b2, c1 c2]
In tournament selection, we randomly select n number of participants from our population, and the "winner" of the tournament is the participant with the best fitness score. Remember that the lower the score, the better (at least in our example).
Roulette selection gives solutions with a better fitness score a higher chance of being selected. My implementation is a bit...odd. Here's the basic idea: we want to create a "roulette wheel" that we can spin to find a random solution. The better the solution's fitness score, the bigger its slice on the roulette wheel.
To create the roulette wheel, I create a vector of cumulative fitness scores...sort of. Because the lower fitness scores are better, we have to transform them a bit. I picked a number (700) that is larger than the fitness score of any solution (I just guessed here). Then, we can subtract our actually fitness score from 700, and now our bigger scores are better. Using the bigger-is-better scores, I create a vector of cumulative scores, and that's the roulette wheel.
Now that we have our wheel, we need to spin it once for every solution of the population. To do so, we'll choose a random number between 0 and the last element of the roulette wheel vector. We then find the first element in the vector that is greater than our random value, and the index of that value is the index of the solution in the population vector that we picked.
You know what? Let's just step through it. Assume we have this population:
[[0 1 2 3] [2 3 1 0] [4 2 3 1]]To build our roulette wheel, we want to subtract each score from 700. Our scores are now 500, 300, and 200 respectively. The higher scores are now better. Now, let's create our roulette wheel - remember that it's a vector of cumulative scores:
with fitness scores of:
[200 400 500]
0 + 500 = 500 500 + 300 = 800 800 + 200 = 1000
which results in:
[500 800 1000]
Hopefully you can see how we're assigning a bigger slice of the roulette wheel to the solutions with better fitness scores. My implementation of this process in Clojure is below.
(I also added a 'fitness multiplier' to help tune the results of roulette selection)
Now that we've selected which solutions in our population will be crossed-over (bred), we can finally get into the good stuff. Just like selection, there are a number of different methods to perform crossover. The method with which you encoded your solutions may dictate which method of crossover works best. In our example, I'm going to use cycle crossover. Cycle crossover will prevent the creation of invalid solutions. Remember that we must visit every city, and we can only visit each city once. Therefore, the solution below is invalid because we visit city 1 twice, and because we don't visit city 9:
[7 6 5 1 8 3 2 4 1]
The cycle crossover finds subsets of values in two solutions that occupy the same set of indices. These subsets are called cycles. Let's look at the example below.
Notice the highlighted cells - the subset of values (8 and 0) occupy the same subset of indices (0 and 9) in both solutions. This means they can safely be switched between the solutions, and the resulting solutions will still be valid!
Awesome! But...given a pair of solutions, how do we go about finding a cycle? My implementation is below, but there's probably a better way!
We can then apply the crossover to the entire population with the functions below:
Mutation causes the values at random indices in a given solution to switch places. Mutation should only occur in a small percentage of the population. This helps keep the population from settling into a local optimum. To perform a mutation, we simply randomly choose two indices and swap their values. In the example below, the random indices that were chosen are 0 and 6.
In my implementation below, 15% of the population will undergo mutation, and we actually swap two sets of indices.
Now that we have all of the steps in the process of the algorithm complete, we can piece everything together.
In the code above, you'll notice the references to 'draw-chan' - in the full version of this experiment, I've included a visualization component using Quil.
You can find the full code on Github here.
Thanks for stopping by!
Published on 6/28/2014
When I downloaded Monument Valley, I knew I was in for a treat.
Sometimes when you just look at screenshots of a game, you can tell that the developers and designers put a lot of thought and hard work into their creation - and that's definitely the case with MV. It's so very true that every level in the game is a work of art. In fact, you can easily purchase prints of any screenshots you take in-game. The low-poly, geometric, brightly colored architecture that's the focal point of MV is a breath of fresh air, coming from the all-too-common pixel art style that many games are adopting, especially in the mobile market. On top of that, you get the intricately layered, often mind-boggling level design, which really makes for some unique perpective shifts throughout the game.
Last week, I finally had a chance to download the game, brew a cup of coffee, and sit down on the couch with my iPad to dive into this beautiful world.
My first interaction with MV was beautifully orchestrated by the developers. My objective was clearly marked on the screen as a target-like set of concentric squares on the ground, a visual queue that was obvious but didn't seem out of place. Of course, the path to my objective was blocked, so I reached for the clearly defined interaction point - a knob - and with one small motion, the perspective shift clicked into place for the first time...and I was hooked.
As the game progressed, the puzzles were layered with additional mechanics - moving obstructions, buttons that open new paths, a general disregard for gravity, and even a companion. The different mechanics always kept me thinking, and they interacted in interesting ways. Can't get past that enemy? You have to flip the platform upside-down to get around - that sort of thing.
I have to admit, the main storyline in MV was lost on me. I get the gist - I'm a princess, I took some geometric stuff, I had to give it back, there were some graves, we're all pretty birds now - but it just didn't do anything for me. Maybe my expectations were unrealstic, or maybe the story was just shallow, it's hard to say, but either way I was disappointed.
That said, I still really enjoyed playing MV. And I love that Totem to death! Who knew that a pillar with an eye could be so adorable?
If you've got an extra $3.99 and an iPad, I would definitely recommend that you pick up MV - not sure how it looks on a smaller iPhone screen, but on the iPad it's a work of art!
Published on 6/27/2014
It's been about 2 years since I first started this blog, and I've made < 10 total posts. It's time for something new.
Originally I built this blog using WordPress because it was easy to install, easy to customize, and easy to update. While CMS platforms can be a really great tool for those that are not tech-savvy, I always found WordPress to be clunky and annoying. I've been wanting to experiment with a static site generator for quite some time now, and this seems like the perfect opportunity. I looked in Jekyll and Ghost, but I ended up taking ~2 hours to just roll my own static site generator using Node.js....and it was super easy to do.
The whole idea behind a static site generator is that you don't have to worry about a database (or any of the associated attack vectors), but you don't have to maintain the entire codebase by hand - the generator will take care of paging, links, etc.
I've decided not to publish my site generator through an official repo, but you can grab the main script here. It should help you understand my thought process and will point you in the right direction if you're itching to make your own static site generator. I'm just happy to be rid of WordPress!