进化算法的N皇后问题

Question

我正在尝试使用进化算法解决 NQueen 问题，但我无法获得图表所需的输出，

以下是我写的代码

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

我尝试改变人口规模，世代价值，但我仍然无法获得平滑的曲线 我的输出：我的输出

一代人的预期输出适应度： 预期产出曲线

如何使该曲线看起来平滑

Answer 1

为什么要对不同突变率（尤其是大突变率）的结果进行平均？如果你想要一条平滑的曲线，你需要有一个大的群体规模来减少统计噪音，并且你还想采取小步骤，所以有一个小的突变率，最后你不需要太多的代数就足以达到最大的适应度:

POP_SIZE = 1000  # Population size
GENERATIONS = 50  # Number of generations
MUTATION_PROBABILITIES = [0.001]  # Mutation probabilities