title: PSO Solve N-Queen Problem
layout: page
categories: data analysis
PSO Solve 16-Queen Problem
The N-Queens problem is a classic problem in the field of computer science and combinatorial optimization. It involves placing N chess queens on an N×N chessboard so that no two queens threaten each other. In the 16-Queen Problem, we need to place 16 queens on a 16x16 chessboard without any queen attacking another queen.
Solution Encoding
The solution can be encoded as a list of integers where each index represents the column and the value at that index represents the row where the queen is placed. That is, we use a permutation array to represent a possible solution.
Objective Function and Constraint
The objective function is to minimize the number of pairs of queens that can attack each other. The constraint is that no two queens should be able to attack each other.
Models for PSO
- Particle representation: Each particle represents a potential solution to the problem.
- Position update: The position of each particle is updated based on its previous position, the best position it has achieved so far, and the best position achieved by any particle in the swarm.
- Velocity update: The velocity of each particle is updated to move towards the optimal solution.
Algorithm Design with Pseudo Code and Parameters
# PSO Algorithm for 16-Queen Problem
# Parameters
num_queens = 16
num_particles = 30
max_iter = 10000000
c1 = 2.0
c2 = 2.0
w = 0.7
# Initialize population and velocities
initialize_population()
initialize_velocities()
# Main PSO loop
for iter in range(max_iter):
for particle in particles:
# Update velocity
update_velocity(particle, c1, c2, w)
# Update position
update_position(particle)
# Evaluate fitness
fitness_value = evaluate_fitness(particle)
# Update personal best
update_personal_best(particle, fitness_value)
# Update global best
update_global_best(particle)
# Output the best solution
print("Best Solution:", global_best_position)
Result and Analysis
After running the PSO algorithm for the 16-Queen Problem, the best solution obtained is printed, indicating the positions of the queens on the chessboard.
Here I only show the last (optimal) output of the attatched program.
Optimal found!
global_best_fitness = 0
[15, 12, 9, 1, 5, 11, 2, 7, 13, 3, 0, 8, 14, 4, 6, 10]
More Discussions:
Additionally, we can explore the robustness of the PSO algorithm by conducting sensitivity analysis on the parameters. Comparisons with other metaheuristic algorithms such as Genetic Algorithms (GA) or Simulated Annealing (SA) can provide insights into the strengths and weaknesses of the PSO approach. Analyzing the convergence behavior and scalability of the algorithm for larger N-Queen problems can further deepen the understanding of its performance.
Code
import random
import numpy as np
import matplotlib.pyplot as plt
# Initialize parameters
num_queens = 16
num_particles = 300
max_iter = 1000000000
c1 = 2.0
c2 = 2.0
w = 0.7
# Initialize the population with random positions for each particle
particles = [[random.randint(0, num_queens - 1) for _ in range(num_queens)] for _ in range(num_particles)]
velocities = [[0] * num_queens for _ in range(num_particles)]
personal_best_positions = particles.copy()
personal_best_fitness = [float('inf')] * num_particles
global_best_position = None
global_best_fitness = float('inf')
# Visualization of the chessboard
def plot_solution(attack_pair):
if global_best_position is None:
return
print(global_best_position)
chessboard = np.zeros((num_queens, num_queens))
for col, row in enumerate(global_best_position):
chessboard[row][col] = 1
plt.figure(figsize=(6, 6))
plt.imshow(chessboard, cmap='binary')
plt.xticks([])
plt.yticks([])
plt.grid(color='black', linewidth=1)
plt.title(f'attack_pair = {attack_pair}')
plt.show()
# Display the chessboard with queen positions
plot_solution(global_best_fitness)
# Define the fitness function for the 16-Queen Problem
def evaluate_fitness(position):
attacking_pairs = 0
for i in range(num_queens):
for j in range(i + 1, num_queens):
if position[i] == position[j] or abs(i - j) == abs(position[i] - position[j]):
attacking_pairs += 1
return attacking_pairs
stop_flag = False
# Main PSO loop
for iter in range(max_iter):
if stop_flag is True:
break
for i, particle in enumerate(particles):
fitness_value = evaluate_fitness(particle)
if fitness_value < personal_best_fitness[i]:
personal_best_fitness[i] = fitness_value
personal_best_positions[i] = particle.copy()
if fitness_value < global_best_fitness:
global_best_fitness = fitness_value
global_best_position = particle.copy()
plot_solution(global_best_fitness)
if fitness_value == 0:
print("Optimal found!")
stop_flag = True
break
# Update velocity
for j in range(num_queens):
velocities[i][j] = (w * velocities[i][j] +
c1 * random.random() * (personal_best_positions[i][j] - particle[j]) +
c2 * random.random() * (global_best_position[j] - particle[j]))
# Update position
for j in range(num_queens):
particles[i][j] = (particles[i][j] + int(round(velocities[i][j]))) % num_queens
print(f"global_best_fitness = {global_best_fitness}")
# Display the chessboard with queen positions
plot_solution(global_best_fitness)
标签:global,Queen,num,Solve,fitness,position,Problem,best,queens
From: https://www.cnblogs.com/kion/p/17815179.html