Introduction:

This is the first article of a series i'm going to present here.
The entire series will be dealing with the 8 queens problem,or more general the n-queens-problem.
I assume that all of you know what the problem is about.
If not just google it out, there are loads of resources. Also i will shortly explain what it's all about.

So why dedicate quite some articles to this problem?
Well at a first glance it's just a relativly easy scientific problem.
But if you look closer you'll notice that solutions to this problems can be generated in quite many ways. Not few of them offer interesting applications beyond the problem itself.
The n-queens-problem is very well suited for studying various algorithms.
It's very easy to comprehend thus you can focus on solving it efficiently.

This first article attacks the problem with a genetic algorithm. I thought it's probably the most interesting to start with and shows some general ideas.
Note that it is not proven that genetic algorithms perform particulary well.
It's just that they're related to what we all know from school that makes them so appealing.

Before we can start we need to make a few things clear.
First of all, the 8-queens-problem is all about chess.
You know chess don't you? If not, go buy a book on it and learn it.
It's definitely worth the time you spend.
The goal of the 8-queens-problem is to place 8 queens on a chess-board such that none of the queens are attacking each other.The generalization, the n-queens-problem thus formulates the goal
of placing n queens on an nxn chessboard in such a way that no queen is attacking another.

So what's all that genetic algorithm sort of thing?

It's foundations are actually quite easy to grasp and quickly explained. We model our problem in a way that allows us to apply evolutionary methods to quite a big extend.
In a genetic algorithm, GA for short, we deal with populations, chromosomes, mutation, fitness and selection. I'll explain all of this term shortly.

In a GA the problemset is represented as a set of chromosomes.
Each chromosome represents a particlar problemstate.
We now have formal tequniques to measure the fitness of each chromosome in
regard to the goal we're trying to reach.
Or in other words we can express numerically how well a specific chromosome solves a particular problem.
This numeric value is called the fitness of a chromosome.
Our goal is to let chromosomes with better fitness survive where chromosomes with lower fitness will die, eventually producing a chromosome that does indeed solve the problem.

So how do we actually make chromosomes reproduce themselves?

Well the same way every higher biological being does.
We crossover chromosomes. Crossing over means breaking two chromosomes apart, and glueing the pieces together in such a way that we get two new resulting chromosomes.

The general layout of a GA is as follows

Code Copy / Restore

procedure GA(problem) return solution    initial_generation := create_random_generation()    solution := false    while not solution      selected_chromosomes := select_chromosomes(initial_generation)      new_generation := crossover(selected_chromosomes)      solution := select_solution(new_generation)    end    return solution end Select what you want to copy and in doing so you will keep the formatting when pasting it. procedure GA(problem) return solution initial_generation := create_random_generation() solution := false while not solution selected_chromosomes := select_chromosomes(initial_generation) new_generation := crossover(selected_chromosomes) solution := select_solution(new_generation) end return solution end

How can we apply this to the n-queens-problem?

Chromsomes:
The first thing we have to do, is to model our chromosomes and thus our problemstates.
A straight forward model is a numeric array, where the index represents the column of the queen
and the value at a given index i represents the row of the queen.

A chromosome for a give state in the 8-queens-problem might look like this:

|3|6|1|8|3|4|7|2|

This array represents one possible problem-state where 8 queens are placed on the board.
You can get the actual positions by forming a set of pairs, like so:

Ps = { (1,2), (2,6), (3,1), (4,8), (5,3), (6,4), (7,7), (8,2) }

This type of chromsomes can efficiently be represented with any programming language.

The fitness:
Now that we know how to represent our chromsomes, the next step is to determine a
way to measure the fitness of a particular chromosome.
I choose to base the fitness on the number of non-attacking pairs in a chromosome.
A queen is attacking another queen if it is placed on the same row or on the same column.
It also does attack another queen if it sits on the same diagonal(s).
We can compute if a queen is attacking another queen if we thing of the row and column
as a point in a coordinate system. We can place the queens on this coordinate system
and see if they lay on the same straights. There are 4 of those straights that we
need to consider.

To get the maximum number of non-attacking pairs for a given n in the n-queens-problem
you can just compute it via (n * ( n - 1)) / 2.
So for the 8-queens-problem the maximum number of non-attacking pairs and thus a goal state
is 28.

We have two important points allready covered. We know how to represent our
chromosome and we know how we can compute how well it is suited to solve the given problem.

The fittest will survive:
Next we obviously need a way to use the information we have and bring some evolution
into play. We need a way to select chromsomes for crossover such that the fitter
the chromosome is, the more likely it will be selected for reproduction. As you all
know, only the fittest survive. This is actually a keypoint of GAs. In the literature
there are many methods discussed that lead to more or less usefull selction-rules for
a given problem. These methods are also known as selection-operators.

I choose the fitness-proportionate-selection or roulette-wheel-selection.
It's by far the most comprehensive one. As a sidenote, almost all of the selection-operators
work stochastically to determine the best chromosomes. So it's no surprise that the underlying
idea is often the same, but the actuall implementation vary in complexity and performance.
See for example tournament-selection or SUS (stochastic universal sampling).

How does this work?

Well, imagine you have a roulette-wheel. You can spin it and hopefully it halts on the color
or number you've previously chosen. Now suppose the numbers and colors aren't allready there. You'll have
to paint them on. The first thing you do is you calculate the fitness in percent of each
chromsome you have. Thus the "weaker" chromsomes get a smaller percentage whereas the stronger
(fitter) chromosomes get a greater percentage. Now based on these values assign each chromsome
a slice on the wheel so that the slice-size corresponds to the percentage-value.
Now that you painted the slices on the wheel, you can spin it and see on which slice it halts.
Bigger slices are more likely to be selected here, as they obviously occupie more space on the wheel.
This spinning is our way to select two chromosomes for reproduction.
Note that weaker chromosoms still have a small probability of being chosen.

Cross them over:
So now that we can fairly select chromsomes for reproduction, we need to actually perform the
crossover process. This is straight forward. We just choose a random index between 1 and n.
We cut our two chromosomes at this index in half. Now we have four pieces. These four pieces
we now glue together so that the head of the first chromosome gets the tail of the second
and the head of the second gets the tail of the first.
Suppose we have the following chromosomes:

Code Copy / Restore

c1 = |3|6|1|8|3|4|7|2|   c2 = |5|1|7|8|2|6|3|3|   Let our point for crossover be 3   i = 3   h1 = |3|6|1| t1 = |8|3|4|7|2|   h2 = |5|1|7| t2 = |8|2|6|3|3|   Now we join them:   h1t2 = |3|6|1|8|2|6|3|3|   h2t1 = |5|1|7|8|3|4|7|2| Select what you want to copy and in doing so you will keep the formatting when pasting it. c1 = |3|6|1|8|3|4|7|2| c2 = |5|1|7|8|2|6|3|3| Let our point for crossover be 3 i = 3 h1 = |3|6|1| t1 = |8|3|4|7|2| h2 = |5|1|7| t2 = |8|2|6|3|3| Now we join them: h1t2 = |3|6|1|8|2|6|3|3| h2t1 = |5|1|7|8|3|4|7|2|

We have our offspring. The idea behind this is that there are sequences of genes that
perform better. For example if |3|6|1|5 did not have a single queen that attacks another
this sequence does perform quite well. Suppose you have an 4-queens-problem it would actually
be a goal state. The hope of the GA is to combine those successful sequences so that even
better sequences are produced that solve the bigger problem. It's a kind of divide and conquer
but much more random.

Mutation:
In nature there is another mechanism that kicks in randomly. It's mutation.
Mutation randomly alters the chromomsomes. We model this by walking through the chromosome
and decide based on a certain delta (mutation-rate) if we do actually mutate the current gene.
The higher mutation-rate the more often this mutations will occure.
Also i choose to not stop mutation after i mutated a given gene in a chromosome, but instead
walk further and see if another gene shall be mutated.
You can easily replace this algorithm by the non-greedy one to see if it performs better or
worse.

So now that we have our now chromosomes we replace the parents and can thus form a new generation.
Hopefully this offspring has fitter individuals. If an individual is generated that solves the
problem we can abort the algorithm and return the solution.

Over and over again:
The GA repeats this cycles until a goal-state is reached or another break-condition arises.
Possibly quite many generations are needed to solve a problem.
And that's really all there is to it.

Note that this genetic algorithm isn't the fastest on earth but it is actually a good
one to study. It is able to solve the n-queens-problem for smaller ns in acceptable time.
For bigger ns you'll quickly notice that it doesn't find a solution or it takes much time.


Referenceimplementation: http://www.coderprofile.com/source-code/438/solving-the-n-queens-problem-pa...

Next up:
The next article will model the 8-queens-problem as a constraint satisfaction problem.
We'll be solving it by simple chronological backtracking first.
In a later article we'll use more advanced algorithms from linear programming to solve
the problem, like simulated annealing and hill-climbing. I'll even present you
a variation of the hill-climbing algorithm to solve the problem even for big ns in a short time.
This algorithm is known as random-restart hill-climbing.

Yet other articles will use straight uninformed search algorithms and other will
focus on informed search algorithms using heuristics like A*.

I hope you enjoy the articles and stay tuned. Don't expect me to pull them out too soon, as i don't have
that much time. But i'll try to make the breaks as short as possible.



References:
"Artificial Intelligence a Modern Approach" Second Edition by Russel and Norvig
Newcastle University EDC