# Untitled

unknown
plain_text
11 days ago
3.4 kB
6
Indexable
Never
```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])

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()
```