526互联

PSO Solve N-Queen Problem

发布时间 2023-11-07 15:51:01作者: K1øN
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]
image-20231104191807575

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)