Проблема N Queen с эволюционным алгоритмом ⇐ Python

[Anonymous]

Я пытаюсь решить задачу N Queen с помощью эволюционного алгоритма, но не могу получить желаемый результат моего графика.
Ниже приведен код, который я написал

Код: Выделить всё

import matplotlib.pyplot as plt
import random
import numpy as np

# Constants
N = 8  # Size of the N-Queens problem
POP_SIZE = 100  # Population size
GENERATIONS = 1000  # Number of generations
MUTATION_PROBABILITIES = [0.6, 0.8, 1.0]  # Mutation probabilities

# Fitness function to maximize non-attacking pairs
def fitness(solution):
non_attacking_pairs = 0
for i in range(N):
for j in range(i + 1, N):
if solution[i] != solution[j] and abs(i - j) != abs(solution[i] - solution[j]):
non_attacking_pairs += 1
return non_attacking_pairs  # Return the number of non-attacking pairs

def generate_population():
return [random.sample(range(N), N) for _ in range(POP_SIZE)]

def select_parents(population):
# Tournament selection for parents
tournament = random.sample(population, 5)
parent = max(tournament, key=fitness)  # Maximizing fitness
return parent

def crossover(parent1, parent2):
point = random.randint(1, N - 1)
child1 = parent1[:point] + [x for x in parent2 if x not in parent1[:point]]
child2 = parent2[:point] + [x for x in parent1 if x not in parent2[:point]]
return child1, child2

def mutate(solution, mutation_rate):
if random.random() < mutation_rate:
i, j = random.sample(range(N), 2)
solution[i], solution[j] = solution[j], solution[i]
return solution

def next_generation(population, mutation_rate):
new_population = []

# Sort the population by fitness in descending order
sorted_population = sorted(population, key=fitness, reverse=True)

# Select parents and create the new population
while len(new_population) <  POP_SIZE:
parent1 = select_parents(sorted_population)
parent2 = select_parents(sorted_population)
child1, child2 = crossover(parent1, parent2)

# Mutate the children
new_population.append(mutate(child1, mutation_rate))
new_population.append(mutate(child2, mutation_rate))

return new_population

# Evolutionary Algorithm with tracking of fitness values
def evolutionary_algorithm(mutation_rate):
population = generate_population()
best_fitness_values = []
average_fitness_values = []

for generation in range(GENERATIONS):
# Evaluate fitness of current population
fitness_values = [fitness(individual) for individual in population]
best_fitness = max(fitness_values)  # Maximization
average_fitness = np.mean(fitness_values)

# Record best and average fitness
best_fitness_values.append(float(best_fitness))  # Keep as float
average_fitness_values.append(float(average_fitness))  # Keep as float

# Generate the next generation
population = next_generation(population, mutation_rate)

return best_fitness_values, average_fitness_values

# Store average fitness values across mutation rates
overall_average_fitness = np.zeros(GENERATIONS)

# Run the evolutionary algorithm for each mutation probability
for mutation_rate in MUTATION_PROBABILITIES:
best_fitness, average_fitness = evolutionary_algorithm(mutation_rate)

# Accumulate average fitness values
overall_average_fitness += np.array(average_fitness)

# Calculate the overall average fitness across mutation rates
overall_average_fitness /= len(MUTATION_PROBABILITIES)

# overall_average_fitness = np.round(overall_average_fitness)

# Plotting the results
plt.figure(figsize=(12, 6))
plt.plot(range(GENERATIONS), overall_average_fitness, label='Overall Average Fitness', color='blue')
plt.title('Overall Average Non-Attacking Pairs Fitness Over Generations')
plt.xlabel('Generation')
plt.ylabel('Fitness (Number of Non-Attacking Pairs)')
plt.xticks(ticks=np.arange(0, GENERATIONS + 1, 100))  # Set x-axis ticks at intervals of 10
plt.grid()
plt.axhline(y=N * (N - 1) / 2 + 0.001, color='black', linewidth=0.1, linestyle='--', label='Max Non-Attacking Pairs')  # Max pairs line
plt.legend()
plt.show()

Я пытался изменить размер популяции и значение генерации, но мне все еще не удалось получить плавную кривую.
Мой результат: мой результат
Ожидаемый Согласованность результатов в зависимости от поколения:
Кривая ожидаемого результата
Как сделать эту кривую гладкой

Подробнее здесь: https://stackoverflow.com/questions/790 ... -algorithm