Queens Problem Genetic Algorithm - Evolutionary Approach

A genetic algorithm (GA) is a metaheuristic search algorithm inspired by natural evolution. It maintains a population of candidate solutions, evaluates each by a fitness function, selects the fittest for reproduction via crossover, and introduces variation via mutation. Over many generations, the population converges toward high-quality solutions.

GAs are part of the broader field of evolutionary computation and are covered in AI courses alongside classical search methods. The N queens problem is a standard GA benchmark because:

• The solution space is a set of permutations — a well-studied GA domain.
• The fitness function (counting non-attacking pairs) is easy to compute.
• There are 92 known optimal solutions for n=8, making verification straightforward.

For a comparison with other AI approaches (hill climbing, simulated annealing, CSP), see the 8 Queens in AI guide. For classical exact solutions, see the backtracking algorithm guide.

The choice of representation (chromosome encoding) is critical for GA performance. For N queens, the permutation representation is the best choice:

• A chromosome is a permutation of [0, 1, ..., n-1].
• chromosome[row] = col means the queen in row row is in column col.
• Because each column value appears exactly once, column conflicts are eliminated by design.

This reduces the problem to eliminating only diagonal conflicts, which are encoded in the fitness function. A random permutation like [2, 4, 6, 0, 3, 1, 7, 5] is a valid chromosome even if it has diagonal conflicts — the GA's job is to evolve toward zero-conflict permutations.

Alternative encodings and why they are worse:

• Binary (each bit = one cell): Chromosome length n² = 64 for n=8. Most bit strings are invalid (wrong number of queens per row). Repair operators add complexity.
• Integer per row (0..n-1, no uniqueness): Allows column conflicts, requiring the fitness function to penalize them. Larger search space.

The fitness function measures how good a chromosome is. For N queens, the natural metric is the number of non-attacking queen pairs:

fitness = n*(n-1)/2 - conflicts

Where n*(n-1)/2 is the maximum possible non-attacking pairs (when no queen attacks any other), and conflicts is the number of attacking pairs.

For n=8: maximum fitness = 8×7/2 = 28. A valid solution has fitness = 28 (zero conflicts). A random permutation typically has fitness around 22–25.

We only need to count diagonal conflicts (column conflicts are impossible with permutation encoding):

def fitness(chrom):
    n = len(chrom)
    max_pairs = n * (n - 1) // 2
    conflicts = sum(
        1 for i in range(n) for j in range(i + 1, n)
        if abs(chrom[i] - chrom[j]) == abs(i - j)
    )
    return max_pairs - conflicts

The maximum fitness (28 for n=8) signals a valid solution and terminates the GA.

Selection determines which chromosomes reproduce. Tournament selection is the most common and robust method for permutation GAs:

1. Randomly pick k individuals from the population (tournament size k, typically 2–5).
2. The individual with the highest fitness wins and is selected as a parent.
3. Repeat to select a second parent.

Tournament selection has desirable properties: it maintains selection pressure without over-selecting the best individual (which would reduce diversity), it is O(k) per selection, and it is easy to implement.

Alternatives considered:

• Roulette wheel (fitness-proportionate): Problematic when fitness values have different scales; can cause premature convergence.
• Rank-based: More robust than roulette but slower to compute.
• Elitism: Always carry the best individual to the next generation unchanged — commonly combined with tournament selection.

Standard crossover operators (one-point, two-point) do not preserve permutation validity — they can produce offspring with duplicate or missing values. PMX (Partially Mapped Crossover) is the standard crossover for permutation chromosomes.

PMX procedure:

1. Select a random crossover segment [start, end].
2. Copy the segment from parent P1 to child C1.
3. For positions outside the segment, copy from P2 if the value is not already in C1, otherwise follow the mapping chain to find a valid replacement.

Example for n=8:

P1: [2, 4 | 6, 0, 3 | 1, 7, 5]   segment = indices 2-4
P2: [5, 3 | 1, 7, 4 | 0, 2, 6]

C1: [_, _ | 6, 0, 3 | _, _, _]  (copy segment from P1)
    Fill remaining positions from P2 using mapping:
    1→6, 7→0, 4→3 (mapping derived from segment swap)
C1: [5, 1 | 6, 0, 3 | 7, 2, 4]  (valid permutation!)

PMX guarantees the offspring is a valid permutation, making it essential for permutation-encoded GAs.

Mutation introduces small random changes to maintain population diversity and escape local optima. For permutation chromosomes, swap mutation is the simplest valid operator:

1. With probability mutation_rate (typically 0.01–0.05), select two random positions i and j.
2. Swap chromosome[i] and chromosome[j].

Swapping preserves permutation validity automatically (two values exchange positions, so all values remain present exactly once).

Other permutation mutation operators:

• Insertion mutation: Remove one element and reinsert it at a random position. Produces minimal disruption — good for fine-tuning near-optimal solutions.
• Scramble mutation: Randomly shuffle a sub-segment of the chromosome. More disruptive — useful for escaping local optima.
• Inversion mutation: Reverse a sub-segment. Effective for routing problems; less naturally suited to queens.

For the queens problem, swap mutation is usually sufficient because the search landscape is relatively smooth.

The following complete Python implementation runs a genetic algorithm to solve the N queens problem. It uses tournament selection, PMX crossover, and swap mutation:

How does the genetic algorithm compare to backtracking for the N queens problem?

When to use a genetic algorithm for queens:

• When studying evolutionary computation and need a concrete example.
• When the problem has additional constraints beyond standard queens (e.g., fixed queen positions, weighted boards) that make backtracking unwieldy.
• When you want to demonstrate GA properties: selection pressure, diversity, crossover effectiveness.

When NOT to use a genetic algorithm:

• When you need all solutions — use backtracking.
• When you need guaranteed correctness — GAs are stochastic and can fail.
• When n ≤ 20 — backtracking is faster and simpler.

For single-solution large-n problems, the min-conflicts heuristic outperforms GAs in both speed and simplicity.