CS345, Machine Learning, GA Example: n queens

CS345, Machine Learning
Prof. Alvarez
GA Example: The Nonattacking Chess Queens Problem

The nonattacking chess queens problem consists of finding positions for n queens on an nxn square board so that no two of the queens are attacking one another according to the usual rules of chess. Specifically, no two queens can share a row, a column, or a diagonal. This problem is also known simply as the n queens problem. Here I comment on the use of genetic algorithms (GA) to find solutions to the n queens problem.

Combinatorial Complexity

In case you haven't thought about the n queens problem before, notice that an exhaustive search for solutions among all possible positions of the n queens is extremely complicated because the number of different positions grows very rapidly as a function of the board size n. Each queen could potentially be associated with any of the nxn board positions, producing a total of (nxn)ⁿ possible assignments of the n queens. We can cut this number down a bit by taking into account that no two queens can share the same position, which now yields (nxn)! (the factorial of nxn) different configurations. Going further, we remember that there can only be one queen per row, so that there are n possible positions for each queen within its row. This still leaves a total of nⁿ (n to the power n) different combinations that must be considered. For n=4, this number is 256. For n=8 (the usual chess board size), the number of positions is already over 16 million. This combinatorial complexity motivates the use of methods other than exhaustive search for this problem.

GA Representation

I implemented a GA for the n queens problem based on the simple representation described here. Some examples of the results obtained appear below.

Population

The simplest approach is to represent each board configuration by the sequence of positions of the n queens. We wire in the constraint that there should be only one queen per row by allowing each queen to move only sideways across columns, not up and down across rows. Each individual of the population corresponds to a board configuration.

Fitness Function

The fitness of a given individual in this context measured on a scale of 0 to 1 can be obtained as the ratio of the number of nonattacking pairs of queens in the board configuration corresponding to the individual relative to the total number of different pairs that can be formed among n queens. Two queens can be determined to be attacking each other if they are either in the same column or if their column numbers differ by the same number (in absolute value) as their row numbers; the row numbers are guaranteed to be different for different queens by construction.

Learning

The basic selection, crossover, mutation, and evaluation steps are iterated as discussed in class. These genetic operators are briefly described below. The process of evolutionary adaptation proceeds until the fitness function reaches 1 for some individual, at which point a solution to the n-queens problem has been found.

Genetic Operators

The population for each generation is selected probabilistically with a distribution proportional to the fitness of the various individuals. Crossover is then applied to a fraction of the population. Crossover involves combining two configurations (individuals); the simplest version of crossover simply pairs the first k rows from one individual with the last n-k rows from the other. Finally, we apply pointwise mutation to a portion of the population; pointwise mutation changes the column of one of the queens in the selected individual (configuration).

Sample Runs

Below are the initial and final configurations for two sample runs for the 8-queens problem. Board configurations are represented in terms of the queen positions, with a "Q" for each queen, drawn at a vertical offset proportional to the row number and a vertical offset proportional to the column number.

Run 1

For this first run I used a population of 5 individuals. The number of generations required to find a solution was about 75000 for this particular run, which is equivalent to trying 5x75000 = 375000 different configurations (since the population size was 5). This is less than 1/2 of 1 percent of the total of over 16,000,000 different positions for the 8-queens problem.

After 0 generations:
Best GA is 0
Max fitness of 0.7857142857142857
Best configuration: 
(0,4) (1,6) (2,2) (3,5) (4,0) (5,0) (6,5) (7,1) 
        Q
            Q
    Q
          Q
Q
Q
          Q
  Q


After 74680 generations:
Best GA is 1
Max fitness of 1.0
Best configuration: 
(0,0) (1,6) (2,4) (3,7) (4,1) (5,3) (6,5) (7,2) 
Q
            Q
        Q
              Q
  Q
      Q
          Q
    Q

Run 2

The results of a second run follow. This time I used a population of 100 individuals. Learning succeeded in finding a solution after 21 generations, corresponding to trying only 2100 board configurations, a fraction of merely 1/8000 of the full hypothesis space.

After 0 generations:
Best GA is 0
Max fitness of 0.7142857142857143
Best configuration: 
(0,2) (1,2) (2,7) (3,2) (4,4) (5,5) (6,3) (7,7) 
    Q
    Q
              Q
    Q
        Q
          Q
      Q
              Q


After 21 generations:
Best GA is 89
Max fitness of 1.0
Best configuration: 
(0,4) (1,2) (2,0) (3,5) (4,7) (5,1) (6,3) (7,6) 
        Q
    Q
Q
          Q
              Q
  Q
      Q
            Q

However, take the above sweet results with a grain of salt, as a more sophisticated representation would be needed in order to make the GA results competitive with, say, depth-first search with backtracking. A few comments on the GA ingredients that are at work behind the scenes here are given below.

Crossover Only

If no mutations can occur, it is easy for the search to get stuck. Informally, the absence of mutation prevents the creation of additional genetic diversity. Therefore, unless a solution can be assembled by combining parts of different individuals in the population using the allowed crossover operator(s), a solution will never be found. Here is an example of an n queens run that is going nowhere.

Crossing individuals 2 and 1 at position 0
Crossing individuals 1 and 2 at position 1
Crossing individuals 3 and 2 at position 3

After 11442 generations:
Best GA is 0
Max fitness of 0.5
Best configuration: 
(0,0) (1,3) (2,0) (3,1) 
Q
      Q
Q
  Q


Individual GA configurations:
individual 0:

(0,0) (1,3) (2,0) (3,1) 
Q
      Q
Q
  Q

individual 1:

(0,2) (1,1) (2,1) (3,0) 
    Q
  Q
  Q
Q

individual 2:

(0,1) (1,2) (2,3) (3,3) 
  Q
    Q
      Q
      Q

individual 3:

(0,2) (1,2) (2,2) (3,0) 
    Q
    Q
    Q
Q

individual 4:

(0,1) (1,1) (2,1) (3,0) 
  Q
  Q
  Q
Q

Crossover Only: Lucky Initial Conditions

Below is an example where crossover alone actually works. Note that the bottom half of configuration 3 is combined with the top half of configuration 4 to produce a full solution to the n queens problem in this case. However, such a good result is rather atypical and was made possible here largely by good luck in the pseudorandom initial choice of configurations for the population.

Individual GA configurations:
individual 0:

(0,3) (1,2) (2,1) (3,1) 
      Q
    Q
  Q
  Q

individual 1:

(0,3) (1,3) (2,3) (3,1) 
      Q
      Q
      Q
  Q

individual 2:

(0,3) (1,2) (2,1) (3,1) 
      Q
    Q
  Q
  Q

individual 3:

(0,3) (1,3) (2,3) (3,1) 
      Q
      Q
      Q
  Q

individual 4:

(0,2) (1,0) (2,0) (3,3) 
    Q
Q
Q
      Q

Selecting individual 0 (becomes 0)
Selecting individual 4 (becomes 1)
Selecting individual 3 (becomes 2)
Crossing individuals 4 and 3 at position 2
Crossing individuals 3 and 0 at position 2

After 2 generations:
Best GA is 4
Max fitness of 1.0
Best configuration: 
(0,2) (1,0) (2,3) (3,1) 
    Q
Q
      Q
  Q

Mutation Only

If no crossover is used, there is still a good chance that a solution will be found. This is because random mutations will eventually explore all regions of the hypothesis space. In the example shown below, the solution was found when the bits corresponding to the position of the queen in the bottom row were mutated starting from the configuration shown here:

(0,1) (1,3) (2,0) (3,3) 
  Q
      Q
Q
      Q

...
Mutating individual 4 at position 3

After 31 generations:
Best GA is 4
Max fitness of 1.0
Best configuration: 
(0,1) (1,3) (2,0) (3,2) 
  Q
      Q
Q
    Q


Individual GA configurations:
individual 0:

(0,1) (1,2) (2,0) (3,1) 
  Q
    Q
Q
  Q

individual 1:

(0,1) (1,3) (2,0) (3,3) 
  Q
      Q
Q
      Q

individual 2:

(0,1) (1,3) (2,2) (3,0) 
  Q
      Q
    Q
Q

individual 3:

(0,0) (1,3) (2,0) (3,3) 
Q
      Q
Q
      Q

individual 4:

(0,1) (1,3) (2,0) (3,2) 
  Q
      Q
Q
    Q

Crossover and Mutation

Combining both types of genetic operator has the potential to speed up the discovery of a solution as compared with using mutation alone. Crossover has the effect of globalizing the search for a solution. The following is an example of a situation in which a combination of crossover and mutation finds a solution in one generation, whereas at least two mutations would have been needed to achieve the same result. I used a population of 5 individuals and crossover and mutation rates of 0.5 and 0.5.

After 1145 generations:
Best GA is 2
Max fitness of 0.8
Best configuration: 
(0,2) (1,0) (2,2) (3,4) (4,0) (5,3) 
    Q
Q
    Q
        Q
Q
      Q

Selecting individual 2 (becomes 0)
Selecting individual 4 (becomes 1)
Selecting individual 1 (becomes 2)
Crossing individuals 2 and 0 at position 3
Crossing individuals 0 and 2 at position 2
Mutating individual 0 at position 1
Mutating individual 1 at position 1

After 1146 generations:
Best GA is 0
Max fitness of 1.0
Best configuration: 
(0,2) (1,5) (2,1) (3,4) (4,0) (5,3) 
    Q
          Q
  Q
        Q
Q
      Q

CS345, Machine Learning Prof. Alvarez GA Example: The Nonattacking Chess Queens Problem