iJoshSmith

Introduction

In my previous post I explained the basics of genetic algorithms, and provided a very simple example written in Objective-C. In this post I will dive deeper into the fascinating world of genetic algorithms and show a more sophisticated solution to a more difficult problem, known as the 8 Queens puzzle.

The demo program can be downloaded from github here.

Debt of gratitude

My study of genetic algorithms has been largely based on reading blog posts written by other developers. The post I found most helpful, and which inspired me to tackle the 8 Queens puzzle, can be found on the HandCraftsman blog (a.k.a. Clinton’s Blog). He has posted two separate solutions to this puzzle, one written in C# and the other in some language called Go. The post I studied the most, and from which my algorithm’s gene encoding system is based, can be found here. My algorithm is heavily influenced by Clinton’s but different in several ways.

The 8 Queens Puzzle

Back in 1848 some chess guru named Max Bezzel posed the question of how can you arrange eight queens on a chessboard such that none of them can attack each other. Some seriously smart people, including the almighty Gauss himself, gave this problem a lot of thought and it soon became a well-known problem amongst mathematicians. These days it has become a common problem for Computer Science students to solve while learning about things like constraint programming, logic programming, or genetic algorithms.

Learn more about the 8 Queens puzzle here.

Not the fastest draw in the West

I should point out that genetic algorithms are not the fastest way to solve the 8 Queens puzzle. There are many other ways to solve it, some of which can find all ninety-two distinct solutions to the puzzle in less than one second. It took my algorithm just under an hour on a decent MacBook Pro to find all ninety-two distinct solutions.

I’m OK with that. I didn’t set out to write the fastest way to solve the 8 Queens puzzle. Instead, I used the 8 Queens puzzle as an interesting problem with which I could explore designing and implementing genetic algorithms.

From Hello World to 8 Queens

In my introductory post about genetic algorithms I reviewed a very simple example; an algorithm that evolves randomly generated strings to match a string typed in by the user. In that algorithm the genetic sequence stored in a chromosome has a direct, literal relationship with the problem domain. In other words, the characters/genes in the string/chromosome can be compared to the user input string to see if the chromosome is an exact match. In that contrived example the genes are not being used to encode information about a problem domain: they are that information.

In such a simple example it was not possible to create a genotype-phenotype distinction. A genetic algorithm that solves the 8 Queens puzzle, on the other hand, is a step up in complexity. Genes representing a possible solution to the 8 Queens puzzle will be meaningless by themselves. They must be projected, or, to stick with terms used in biology, translated, into information about the problem domain. This is similar to how nucleotides in DNA are translated into functional proteins within your cells.

Learning from my mistakes

Designing an appropriate genetic encoding system, and determining what information the genes should encode, is of crucial importance to creating a successful genetic algorithm. I know this from experience. My first attempt didn’t work out. I am going to explain my faulty reasoning, and what I learned from it, to better illustrate why the encoding system I eventually created works well.

My initial thought about how to encode information to solve the 8 Queens puzzle was to have a gene sequence consisting of sixty-four genes, since there are 8×8 squares on a chessboard. Each gene would represent one square of the chessboard and encode the binary state of a square (queen/no-queen). Each gene would be stored as a character in a string. The first gene would represent the top-left square on the chessboard, the ninth gene would represent the first square in the second row, the last gene would represent the bottom-right square, etc.

I started implementing a genetic algorithm using this encoding system, but soon ran into a problem indicative of a serious design flaw. My code needed to keep enforcing the rule that each chromosome must have exactly eight genes that represent a queen. This problem appeared when creating a new chromosome with randomly generated genes, and when combining the gene sequences of two mating chromosomes.

The problem around mating chromosomes and ensuring a child’s genes contained exactly eight “queen genes” was particularly troubling. Adding and removing queen genes willy-nilly from each new gene sequence meant introducing a lot more randomization into the algorithm. Genetic algorithms rely on randomness for both creating the initial population’s gene sequences and introducing mutations to subsequent generations, but those are highly controlled and intentional randomizations.

The algorithm’s crossover method, which is the fancy name for how it combines segments from two gene sequences to form a new one, should not introduce a high degree of randomness that significantly alters the combined gene sequence. Doing so renders the algorithm’s fitness function pointless. What’s the point in mating the fittest chromosomes if you always make a large number of random modifications to their children?

The fundamental problem with my initial encoding system was that it stored irrelevant information about the problem domain. It encoded the state of all sixty-four squares on the chessboard. Producing new gene sequences involved a lot of clean up work, which introduced inappropriate randomization. A well-designed encoding system would not include superfluous information about the chessboard.

Designing a proper encoding system

A solution to the 8 Queens puzzle can be expressed as a set of eight data points. Each data point represents a square of a chessboard on which a queen exists. Therefore, each chromosome used in a genetic algorithm that solves the 8 Queens puzzle should consist of eight genes, each of which identifies a square of a chessboard in which a queen exists. Rather than store the binary state of all sixty-four squares, the gene sequence should store only the locations of the queens.

My genetic algorithm represents the top-left square on the chessboard with the character zero (‘0’) and the bottom-right square with lowercase p (‘p’). This is a range of sixty-four characters, according to the ASCII character codes. In other words, ‘p’ – ‘0’ is equal to 64. My choice of using the character for zero as the initial character is mostly arbitrary, but I liked the idea of the first square being represented with a zero (as in, squares[0]).

In the demo program, there is a class that is used to store a solution to the 8 Queens puzzle and draw a diagram of it to the console. An example of its output is seen below:

. Q . . . . . . 
. . . . . Q . . 
. . . . . . . Q 
. . Q . . . . . 
Q . . . . . . . 
. . . Q . . . . 
. . . . . . Q . 
. . . . Q . . .

That class is named JAS8QueensSolution. It contains the following methods that draw the solution to the console window. This code shows how information from the problem domain (squares on a chessboard) can be translated via the genetic encoding system to check for the presence of a queen at a particular chessboard square.

The genetic encoding system is also used when evaluating the fitness of a chromosome’s gene sequence, which we will look at next.

Working out the fitness function

In my previous blog post about genetic algorithms the demo program’s fitness function was very simple. It took a chromosome (which simply wraps a string) and compared each character/gene against the corresponding character/gene from the target string. The greater the delta between the two characters/genes, the lower the chromosome’s fitness became. A chromosome with a fitness of zero meant it was an exact match to the target string; anything below zero meant the chromosome was not an exact match.

That simplicity is not possible when genes do not directly map to, or represent, the problem domain. A level of abstraction exists which allows a gene in the 8 Queens algorithm to encode information about a square of a chessboard on which a queen exists. As such, the fitness function for my 8 Queens genetic algorithm must translate each gene into information about the problem domain while evaluating a chromosome’s fitness.

An interesting quirk about the 8 Queens puzzle is that the other genes in a chromosome determine a given gene’s fitness. A gene represents the location of a queen, and a queen’s safety is contingent upon the locations of the other queens. It turns out that the fitness function can be significantly optimized due to this quirk. Instead of searching for queens occupying squares that are North, Northeast, East, Southeast, South, Southwest, West, and Northwest of a given queen, we only need to search half of those directions (the demo program searches North, Northeast, East, and Southeast.) For example, if a queen is South of another queen, searching North from both of those queens will cause the incompatible locations to be detected. There is no need to search South as well.

Here is the fitness property from JAS8QueensChromosome that calculates the chromosome’s fitness.

That property calculates the fitness of each gene and caches the sum. The result is cached to improve performance, since this property can be accessed multiple times for a chromosome. The helper method that calculates the fitness of a given gene is seen here:

This method searches in four directions, as discussed earlier, to look for other queens that are attacking the queen represented by the gene at the given index. Let’s take a look at the code that searches North and East for attacking queens. This code shows how the genetic encoding system is used to translate genes into information about the problem domain, namely, the squares in which queens exist.

The translation of genetic information to problem domain information occurs in the for() loops. The ‘threat’ variable in those loops identifies a chessboard square. A list of chessboard square identifiers is appended together and passed to the areEmptyThreats: method for analysis. That method checks to see if the chromosome’s gene sequence contains any of those chessboard square identifiers. If so, that means a queens exists on one or more of those squares.

Breeding the next generation

Because each chromosome contains exactly the information needed to represent a solution to the 8 Queens puzzle, the code to mate two chromosomes is very straightforward. All of the problems I faced with my original genetic encoding system, as described earlier, disappeared when I used the system seen above. Here is the code from JAS8QueensChromosome that mates one chromosome with another:

The chromosomes are mated after the algorithm has evaluated the fitness of every chromosome in the population to look for valid solutions to the 8 Queens puzzle. Below is the code from JAS8QueensAlgorithm that selects the best chromosomes from the population, along with a small number of the non-elite, and creates the next generation.

Wrapping up

There is a lot more going on in the demo program than what I’ve shown here, so I encourage you to grab it off github and take a look. One particular point of interest is how JAS8QueensChromosome overrides the hash and isEqual: methods to help the algorithm avoid adding equivalent chromosomes to the population.

The demo program can be downloaded from github here.

Thanks for stopping by!

Introduction

This article explores a simple genetic algorithm I wrote in Objective-C. The purpose of this article is to introduce the basics of genetic algorithms to someone new to the topic, as well as show a fully functional example of such an algorithm.

I am by no means an expert in the field of artificial intelligence. If you are looking for an authoritative voice on cutting-edge research in genetic algorithms, and this article’s title didn’t tip you off, please look elsewhere. If you’re looking for the “Hello, World!” of genetic algorithms written by a professional software developer, not an academic researcher, read on.

The demo program reviewed in this article is available on github.

The demo program

In this article we will review a genetic algorithm whose purpose is to construct a piece of text (i.e. a string) that you specify at run-time. Sounds simple, right? The tricky part is that the algorithm must start with nothing but randomly generated strings and somehow “evolve” them until one of the strings exactly matches the string you specified. The process of evolving the strings is where things get interesting. Here is a screenshot of the Cocoa desktop demo program I wrote to test out the algorithm.

This was my first time writing a Cocoa desktop program, so I’m sure I didn’t follow any Cocoa best practices. My bad!

Below is an abridged version of the output logged by the application while it evolved strings to match the input value of “Once upon a time there was a genetic algorithm”. Each line represents a generation, whose number is listed first, followed by the string in that generation closest to matching the input value.

#00: Rdne$cnfg"2L:ThDBA`awN!d`Z$f"xfsdgVo$Zx^V&oslq
#10: Rpdf!xppl!a tjle!sibs`"vbv#b!hgcbvje aimlumthl
#20: Onee!unoo"a"vhjd!tfese!var `"ffodtid"dlgrrishn
#30: Nnce!upon `"time#theqg wds a gfnduid#alfnritjm
#40: Once!upon a time!theqe!xas b henetid"algnqithm
#50: Once!upon a time!theqe was a genetid"algnrithm
#60: Once upoo a time shese was a genetic amgorjshm
#70: Once upoo a time theqe was a genetic!algorithm
#80: Once upoo a time these was a genetic algorithm
#86: Once upon a time there was a genetic algorithm

I designed and wrote this genetic algorithm, but only after reading many blog posts showing how other people attacked the same problem. My approach involves a couple of novel twists, such as the “population shuffling” that we’ll examine later on, but I’m definitely standing on the shoulders of giants here.

On the origin of genetic algorithms

The heady world of artificial intelligence and machine learning is a fascinating place. Many of the concepts are imported from other fields of research. For example, neural networks are programs that mimic aspects of the brain in order to get some tricky job done, such as recognizing letters and numbers in your handwriting.

Genetic algorithms are based on concepts from the field of biology. They take conceptual root in Darwinian evolution by natural selection. The name genetic algorithm makes sense because these algorithms emulate the mechanisms by which heritable traits are transmitted from parent to offspring, namely the genes found in DNA.

Don’t take the “evolution by natural selection” analogy too seriously. Your code can do things that don’t happen in nature, without causing your algorithm to somehow be wrong or invalid. Genetic algorithms were inspired by what is observed in the natural world, but they do not need to precisely imitate it. If one took the analogy too seriously, and learned how these algorithms actually work, one would have to conclude that the biological world is a huge, non-stop, rampant orgy of incestual mutants. That’s not an accurate description of the world we live in (I hope!).

Components of a genetic algorithm

For our purposes in this article the following quick summary of how genetic algorithms work will suffice. In the next section I provide some other sites to check out if you want a more comprehensive conceptual background.

• Gene – A unit of information that encodes part of a potential solution to the problem being solved. In the demo program a gene is stored as a character in a string.
• Chromosome – A sequence of genes that might be a good solution to the problem being solved. Some people refer to this as an “individual” instead of “chromosome.” In the demo program a chromosome is represented as a JASChromosome object, which uses an NSMutableString to store its gene sequence.
• Population – All of the chromosomes processed by the genetic algorithm. The algorithm mates chromosomes from the population to produce a new generation of chromosomes, which are added to the population.
• Fitness function – Some logic that evaluates a chromosome and returns a numeric value indicating the “fitness” of the chromosome’s genes for solving whatever problem is being solved.
• Selection method – Some logic that figures out which chromosomes should mate in order to create the next generation of chromosomes. In the demo program the chromosomes are rather lazy and will mate with whoever happens to live next door.
• Crossover method – Some logic that determines how to combine the genes from each chromosome while they are mating. In the demo program the fitness of the genes at the same gene sequence index from both parents are compared, and the fitter gene is given to the child. This is an example of my algorithm performing an optimization that doesn’t happen in nature, but who cares?
• Mutation method – Some procedure that randomly changes a chromosome’s gene sequence once in a while. In the demo program, mutations occur for about 20% of the chromosomes immediately after they’re born.

The hard part is figuring out a good fitness function, selection method, crossover method, and mutation method for the problem your algorithm is supposed to solve. The rest is just scaffolding and housekeeping.

Learn (a lot) more

If you want to learn more about the theory of genetic algorithms, you’re in luck. There’s a ton of great material on the Web. It seems like standard operating procedure these days to check what Wikipedia has to say on the topic, but I found this blog post much more digestible and useful.

If you prefer to see a C# implementation be sure to check out this blog post, which is part of an excellent series about genetic algorithms.

Another approachable, and rather hilarious, introduction to the topic with an example in Python can be found here.

How my algorithm works

I split the algorithm into two classes: JASGeneticAlgo and JASChromosome. The JASGeneticAlgo class creates, breeds, and analyzes a collection of JASChromosome objects. Each chromosome is capable of mating with other chromosomes, and determining how its fitness compares to another chromosome’s fitness. Here is the interface from JASChromosome.h:

Now let’s turn our attention back to the JASGeneticAlgo class. After you instantiate that class, and provide it with the target sequence (the string typed in by the user), you send it the execute message to begin running the algorithm. The execute method from JASGeneticAlgo.m, and its two direct dependencies, are shown below.

The populate method adds a bunch of chromosomes to the population array. Each chromosome has the same number of genes as the target sequence. In other words, each JASChromosome object has a string of random characters the same length as the user-defined input value. Here is the code from JASChromosome.m that shows how a chromosome is initialized.

As seen above, the run method of JASGeneticAlgo has been decomposed into three methods: breedNextGeneration, shufflePopulation, and analyzePopulation. Those three methods from JASGeneticAlgo.m are shown below.

Note: In the full demo program source code, the analyzePopulation method logs information about the fittest chromosome from the current generation, which is why that method doesn’t just search for a chromosome whose gene sequence exactly matches the target sequence. I removed that logging code before taking a screenshot of the method, so that the code would visually fit on my blog.

My algorithm’s “selection method” can be found in the loop of the breedNextGeneration method and also in the shufflePopulation method. The selection method used here is to mate each chromosome with its neighbor, and then replace the less fit parent with the child chromosome. To avoid some of the horrific side effects of rampant incest, the shufflePopulation method moves the last chromosome in the array to the beginning of the array. This allows each chromosome to mate with both of its neighbors on an alternating basis. What a life…

The algorithm’s fitness function is exposed by JASChromosome as the isFitterThanChromosome:forTargetSequence: method. That logic is shown below. The basic idea is that each character in the string is compared to the corresponding character in the target string. The numeric difference between the two characters is normalized to a negative number, where zero represents an exact match (perfect fitness). The fitness of each gene is aggregated into an overall fitness for the chromosome. Those overall fitness values can then be compared to each other, where a higher number is considered to be a chromosome with a better fitness. In this context, a fitness value of zero indicates that a chromosome’s gene sequence is an exact match of the target sequence.

Next up is the mating ritual. This method in JASChromosome is responsible for creating a new chromosome based on two parent chromosomes. It contains the “crossover method” component of the genetic algorithm, which determines what genes to give to an offspring.

The crossover method makes an optimization that is specific to the particular problem being solved. It compares the parents’ genes and gives their child the better gene of the two. In more complicated problem spaces, where the genes themselves do not directly correspond to a potential solution but are only used to encode a more complicated solution, this optimization would usually not make any sense.

Lastly, we need to see how random mutations occur. As seen toward the end of the mateWithChromosome: method above, once in a while a new chromosome’s gene sequence is mutated. This adds more variety into the gene pool, which is usually necessary to arrive at a correct or optimal solution. Here is how mutations occur in a JASChromosome object.

If you are interested in diving into this code deeper, feel free to grab a copy off github here.

Summary

Genetic algorithms are an interesting and powerful way to find the solution to certain types of problems. They are great for finding something that you know how to look for, which is what the fitness function is all about. If a fitness function cannot be created to evaluate potential solutions to a problem, genetic algorithms won’t be much help in solving that problem.

The algorithm reviewed in this article has a very simple problem to solve. The genes in a chromosome directly map to a solution to the problem (i.e. characters of a string). When applied to more complicated problems, the genes in a chromosome become decoupled from the problem space and are used purely as a means of encoding information. To learn more about this fascinating step up in complexity, visit my next blog post about solving the 8 Queens puzzle.

Thanks for stopping by!