1.0 | Introduction & Motivation
The N-Queens problem, a well-known combinatorial challenge, involves placing N chess queens on an N×N board so that no two queens threaten each other. For small boards, brute-force methods suffice, but as N increases, these approaches become infeasible. My team tackled this challenge using evolutionary algorithms (EAs), a class of optimization techniques that mimic natural selection to explore large solution spaces efficiently.
2.0 | Why Evolutionary Algorithms?
EAs are particularly effective for problems with large, complex solution spaces due to their stochastic nature and ability to avoid local optima. For the N-Queens problem, each solution is represented as a 1D array to eliminate row and column conflicts, with a fitness function assessing diagonal threats. This representation reduces the search space from \(N^N\) to \(N!\), significantly improving computational feasibility.
Sample Array Representation: [6,3,5,8,1,4,2,7]
3.0 | Fitness Function
The fitness function selected for the algorithm is based on the number of conflicts counted in given a board state. The maximum number of possible conflicts can be calculated as follows.
- \(C_{max} = \binom{N}{2} = \frac{N(N-1)}{2}\)
Where N equals the board size N × N as well as the number of queens. Using this we normalize the counted number of conflicts in a state.
- \(fitness = 1 - \frac{C_{count}}{C_{max}}\)
A valid solution \(1\) represents no conflicts. A worst case \(0\) represents \(C_{max}\) conflicts.
3.0 | Experimentation & Strategies
We evaluated 2,000 configurations of genetic operators, dynamic rates, and evolutionary strategies to optimize performance. Each configuration was tested 10 times on the 8-Queens problem for statistical reliability.
3.1 Sampling Strategies
To explore the parameter space effectively, we used:
- Uniform Sampling: Evenly distributed but inefficient in high dimensions.
- Latin Hypercube Sampling (LHS): Balanced coverage and computational cost, ensuring diverse configurations.
- Sobol Sequences: Uniform and effective in higher dimensions, reducing clustering.
- Halton Sequences: Similar to Sobol but slightly less robust at higher dimensions.
LHS emerged as the best method, ensuring comprehensive exploration of the parameter space without redundant evaluations.
3.2 Dynamic Rates
Dynamic adjustments to mutation and recombination rates allowed the algorithm to adapt to different stages:
Mutation Rate: Started low (0.1) to preserve promising structures, increasing over generations to boost exploration.
Recombination Rate: Began high (0.9) to introduce variety, decreasing to focus on exploitation as convergence neared.
This approach balanced broad exploration with refined exploitation, enhancing performance.
3.3 Genetic Operators
We tested combinations of:
Selection: Tournament selection ensured diversity while favoring fitter individuals.
Recombination:
- Partially Mapped Crossover (PMX): Best performer, maintaining solution validity and diversity.
- Ordered Crossover: Effective but less robust than PMX.
- Even Cut-and-Crossfill: Weakest, often generating invalid solutions.
Mutation:
- Duplicate Replacement: Essential for maintaining valid solutions.
- Scramble and Inversion Mutations: Added randomness for exploration.
- Swap Mutation: Effective for fine-tuning solutions.
3.4 Genocide Operator
When populations stagnated, a genocide operator replaced a portion of the population with new candidates. This reinvigorated exploration and proved especially effective for higher dimensions, preventing the algorithm from getting stuck in local optima.
4.0 | Key Insights on Functional Dependency
During experimentation, we investigated whether there is a functional dependency between the best performing configurations and their parameters. Our results revealed a stochastic pattern, with no clear relationship observable in two-dimensional visualizations.
Possible reasons include:
Intrinsic Stochasticity: EAs inherently rely on random processes, which may obscure any underlying patterns.
Complex Dependencies: The relationship involves higher dimensions, making too complex to meaningfully visualize 2D representations.
Further analysis is required.
5.0 | Performance Comparison
Our final genetic algorithm (GA) setup significantly outperformed earlier versions:
Genome 8 (8-Queens): 30% fewer evaluations, with a 99% improvement in execution time.
Genome 12 (12-Queens): Time savings of 99.8%, showcasing excellent scalability.
The genocide operator and PMX recombination were pivotal in achieving these improvements.
6.0 | Balancing Exploration & Exploitation
Dynamic parameter tuning played a key role:
Early Exploration: High recombination rates and low mutation rates helped avoid local optima.
Late Exploitation: Increasing mutation rates refined solutions, ensuring convergence.
This adaptability was crucial for scaling the algorithm to larger board sizes.
7.0 | Future Directions
Potential areas for further exploration include:
Adaptive Algorithms: Dynamically adjusting operator selection based on age of individuals.
Comparative Studies: Benchmarking against optimization techniques like simulated annealing or particle swarm optimization.
8.0 | Conclusion
Our exploration of the N-Queens problem underscored the versatility and adaptability of evolutionary algorithms. By optimizing genetic operators, dynamically adjusting rates, and introducing novel strategies like genocide, we achieved a robust, scalable solution. The stochastic nature of the process, coupled with innovative strategies, made the project a rewarding learning experience.
For those interested in a more detailed breakdown of the methodology and results, you can download the full report here.