Been playing around with genetic adaption, but couldnt find a nice tutorial with code to guide me through the process. So here it is.

introduction

The whole idea of genetic adaptation is optimized random search, searching for the optimal solution.

But to search, we need to first be able encode and represent our solution in some manner, then have the ability to evaluate the fitness of the solution.

For me, the hardest part of using this genetic adaptation method is probably the part where you have to come up with the representation of the solution. When we explore other problems later on, there will be more complicated structures such as decision trees.

But for a start, we will be going with the rather straight-forward and classical travelling salesman problem.

the problem

The travelling salesman problem is a classical algorithm problem. Given a few towns, find the shortest path (or lowest cost) to traverse these towns.

Here, we are gonna solve the problem in its most minimal form. We will generate nodes randomly in a 1000x1000 grid for the poor salesman to wander to.

I will be omitting most of the algorithm explanations, the ideas aren’t too difficult to understand, just refer to the code if needed.

writing the code (step-by-step)

this is the part where you will be guided step by step towards building the whole script.

I used matplotlib to display the nodes and paths, but that is optional (if you trust the math enough). Plus, it pretty cool to visualize what you have done, so i will advise you to set it up anyways.

generating the nodes

Here, we will be scaffolding the code, generating the nodes and displaying it out.

fitness of solution

The first step is to figure out how to encode a possible solution in a form readable by the computer. And the easiest way to do this for the travelling salesman problem is to store the actual sequence of the path.

And the “fitness” of solution, it is basically to figure out how long it will take to traverse the nodes in that order, traversing each nodes one by one, summing up the Eucliean distance.

fitness (line 10)

genesis

So before we are able to do any genetic adaptation magic, we need the first population to work on. And here is where we define our adam and eve.

This first population will include 2 default paths, from which the genetic adaptation process will work on. Here, we will just include the two most direct path, one from the first to n-th node, the second travelling backwards from the n-th node to the first.

main (line 37)

making them mate

The idea of mating is to induce genetic crossover such that two solutions generate a valid offspring solution. This is the part where we will have to tickle our brain a little and ask ourselves: “given the current representation of our solutions (the paths), how do we take some part of the first, some part of the second to form a third path?”

If you are a little confused, this is what we are talking about, here is what we implemented here, you can alter this in anyway you want, so long as the child produced is valid.

We copy a section of the first solution, then traverse through the second solution, copying all those nodes not visited one by one.

crossover (line 23), main (line 63)

go forth and copulate

Now that we have the crossover function, we can start the population by creating new offsprings to fill the population.

Here, we are gonna evaluate the fitness of each member of the population and print it out for logging purposes.

populate (line 46), main (line 74)

Survival of the fittest

If we keep generating new offsprings, our population will get bigger and bigger. Well, since we want to have a local minimum distance, it will be sufficient to keep only a number of members (in this case 50, try and experiment).

So what we are going to do here is to cull the population and keep only the top performing members (survival of the fittest).

cull (line 54), main (line 80)

Freaks of nature

Mutations, while not always pleasant (think 3 nostrils, 1 ear), can sometimes produce a much more efficient solution. Generally, the mutate function exist to jumble up parts of the current member to generate a new solution or in genetic terms, offspring.

In this travelling salesman problem, mutation is simply just randomly swapping 2 nodes of an existing solution.

note However, we shouldnt really do this too often. If we keep swapping nodes around, wont it just become a case where you randomly generate possible solutions to find the best one? Whats the use of this genetic adaptation idea then?

mutate (line 47), populate (line 63)

let time do its thing

Now the thing to do is to run the simulation and let the population mate, mutate and die off. This will be one run of the simulation, and we will just keep repeating this process, generate one population then the next, until we finally get the best of the population and print it out (making changes to our showGraph function).

Another thing we could do here is to store the results of the test in a pickle so that we can explore it later on when we need to.

note small little change i made here. Previously my fitness function didn’t really do a round trip (going back to the original town). So here i updated it, and of course, the showGraph now draws a complete loop too.

main (line 103)

end

A little thing here is that it is quite a chore getting matplotlib to update itself, if we do that, the result will flash past too quickly. So another way of storing the results will be to use plt.savefig to store all the graphs and view it after the script have finished running.

So here is an implementation of the genetic adaptation for the travelling saleman problem. And these are the steps to apply the genetic adapation (optimized random search) process on most problems.

things to figure out

• whats the problem
• how to know a solution is better (fitness)
• how to encode your possible solutions
• whats your first population (genesis)
• how do they crossover
• how do they mutate
• how to cull the population

Once you know all these steps, just work through them one step at a time, and your script will practically write itself.