Untitled

import random
import multiprocessing
import numpy as np

N = 180
N_POPULATION = 100
MAX_GENERATIONS = 1000000
TOURNAMENT_SIZE = 5
ELITE_SIZE = 10
NO_IMPROVEMENT_LIMIT = 3  # Number of generations to wait before increasing population size

def generate_random_matrix():
    return np.random.randint(0, N, size=N)

def print_matrix(matrix):
    for row in range(N):
        line = ['.'] * N
        if row in matrix:
            line[matrix[row]] = 'Q'
        print(' '.join(line))

def count_conflicts(matrix, col):
    conflicts = 0
    row = matrix[col]
    for i in range(N):
        if i == col:
            continue
        if matrix[i] == row or abs(i - col) == abs(matrix[i] - row):
            conflicts += 1
    return conflicts

def get_fitness_score(matrix):
    return sum(count_conflicts(matrix, col) for col in range(N))

def crossover(matrix1, matrix2):
    crossover_point = random.randint(0, N - 1)
    return np.concatenate((matrix1[:crossover_point], matrix2[crossover_point:]))

def mutate(matrix):
    col = random.randint(0, N - 1)
    matrix[col] = random.randint(0, N - 1)
    return matrix

def tournament_selection(population, fitness_scores):
    tournament = random.sample(list(zip(population, fitness_scores)), TOURNAMENT_SIZE)
    tournament.sort(key=lambda x: x[1])
    return tournament[0][0]

def evaluate_population(population):
    with multiprocessing.Pool() as pool:
        fitness_scores = pool.map(get_fitness_score, population)
    return fitness_scores

def main():
    population = [generate_random_matrix() for _ in range(N_POPULATION)]
    best_fitness = float('inf')
    generations_since_improvement = 0

    for generation in range(MAX_GENERATIONS):
        fitness_scores = evaluate_population(population)
        sorted_indices = np.argsort(fitness_scores)
        population = [population[i] for i in sorted_indices]
        fitness_scores = [fitness_scores[i] for i in sorted_indices]
        current_best_fitness = fitness_scores[0]
        print(f'Generation: {generation}, Best fitness: {current_best_fitness}, Population size: {len(population)}')
        
        if current_best_fitness == 0:
            print('Solution found!')
            print_matrix(population[0])
            break

        if current_best_fitness < best_fitness:
            best_fitness = current_best_fitness
            generations_since_improvement = 0
            if len(population) > N_POPULATION:
                population = population[:N_POPULATION]  # Decrease population size
        else:
            generations_since_improvement += 1
            if generations_since_improvement >= NO_IMPROVEMENT_LIMIT:
                population.extend([generate_random_matrix() for _ in range(len(population))])
                generations_since_improvement = 0

        new_population = population[:ELITE_SIZE]
        while len(new_population) < len(population):
            parent1 = tournament_selection(population, fitness_scores)
            parent2 = tournament_selection(population, fitness_scores)
            child = crossover(parent1, parent2)
            if random.random() < 0.1:  # Mutation rate
                child = mutate(child)
            new_population.append(child)

        population = new_population

if __name__ == '__main__':
    main()