Solving Problems with Genetic Algorithms
Category : Uncategorized
Talk about an all-around STEM topic! If you’re interested in exploring genetics through modeling, Genetic Algorithms are a great start! I followed Chapter 9 in Dan Shiffman’s excellent book The Nature of Code (you can order it or read it for free here), where he creates a population of organisms to work out a target phrase:
target = "wherefore art thou romeo"
In Python, I created an Organism class so each organism would have a set of “genes,” or randomly generated letters to guess the target string.
characters = 'abcdefghijklmnopqrstuvwxyz ' class Organism(object): def __init__(self): self.score = 0 self.genes = '' for i in range(len(target)): self.genes += choice(characters)
Each organism would get a score based on matched letters divided by the length of the target phrase. The score would be multiplied by 100 so it would be a whole number and that number of copies of the organism would be added to a mating pool to reproduce.
“Reproduction” would consist of splicing together two organisms’ genes at a random point so the result would still be the length of the target phrase. A certain number of the child’s genes would be replaced by random characters according to a mutation rate. Then the child organism would take one parent’s place in the population. Repeat for the next generation, and the next and the next…
It doesn’t sound particularly promising with all the randomness factored in. We kept track of the best fit phrase among the organisms and it didn’t start off well:
But in a few dozen generations there was success:
This may not be so miraculous, since we knew the target phrase, but just imagine applying this method to a problem where we don’t know the answer. In the Traveling Salesperson’s Problem (TSP), for example, you don’t know the shortest path between the cities but you can score the attempts by length and use the genetic algorithm to evolve a pretty good approximation!