遗传算法实现八皇后问题python

以下是遗传算法实现八皇后问题的Python代码：

import random

# 棋盘大小
BOARD_SIZE = 8

# 种群大小
POPULATION_SIZE = 100

# 繁殖代数
GENERATIONS = 1000

# 交叉概率
CROSSOVER_RATE = 0.8

# 变异概率
MUTATION_RATE = 0.2

# 定义一个个体类
class Individual:
    def __init__(self, chromosome):
        self.chromosome = chromosome
        self.fitness = self.calculate_fitness()

    # 计算个体适应度
    def calculate_fitness(self):
        clashes = 0
        for i in range(len(self.chromosome)):
            for j in range(i + 1, len(self.chromosome)):
                if abs(self.chromosome[i] - self.chromosome[j]) == j - i:
                    clashes += 1
        return 1 / (clashes + 1)

# 初始化种群
def init_population():
    population = []
    for i in range(POPULATION_SIZE):
        chromosome = random.sample(range(BOARD_SIZE), BOARD_SIZE)
        population.append(Individual(chromosome))
    return population

# 遗传算法
def genetic_algorithm():
    # 初始化种群
    population = init_population()
    # 进化
    for generation in range(GENERATIONS):
        # 对种群进行排序
        population = sorted(population, key=lambda x: x.fitness, reverse=True)
        # 输出最优解
        print("Generation:", generation, "Best fitness:", population[0].fitness)
        # 如果找到最优解，则退出循环
        if population[0].fitness == 1:
            break
        # 选择
        selected_parents = selection(population)
        # 交叉
        offspring_crossover = crossover(selected_parents)
        # 变异
        offspring_mutation = mutation(offspring_crossover)
        # 更新种群
        population = selected_parents + offspring_mutation
    # 对最终种群进行排序
    population = sorted(population, key=lambda x: x.fitness, reverse=True)
    # 输出最优解
    print("Generation:", generation + 1, "Best fitness:", population[0].fitness)
    print("Solution:", population[0].chromosome)

# 选择
def selection(population):
    selected_parents = []
    # 选择最优的前N个个体作为父母
    for i in range(int(POPULATION_SIZE / 2)):
        # 选择两个随机个体
        parents = random.sample(population[:int(POPULATION_SIZE / 2)], 2)
        # 选择适应度更高的个体作为父母
        selected_parents.append(max(parents, key=lambda x: x.fitness))
    return selected_parents

# 交叉
def crossover(selected_parents):
    offspring_crossover = []
    for i in range(int(POPULATION_SIZE / 2)):
        # 如果随机数小于交叉概率，则进行交叉
        if random.random() < CROSSOVER_RATE:
            # 随机选择两个父母
            parents = random.sample(selected_parents, 2)
            # 随机选择交叉点
            crossover_point = random.randint(1, BOARD_SIZE - 2)
            # 交叉生成两个后代
            offspring1 = parents[0].chromosome[:crossover_point] + parents[1].chromosome[crossover_point:]
            offspring2 = parents[1].chromosome[:crossover_point] + parents[0].chromosome[crossover_point:]
            # 将后代加入到新种群中
            offspring_crossover.append(Individual(offspring1))
            offspring_crossover.append(Individual(offspring2))
        else:
            # 如果随机数大于交叉概率，则直接将父母加入到新种群中
            offspring_crossover.append(selected_parents[i])
            offspring_crossover.append(selected_parents[i + 1])
    return offspring_crossover

# 变异
def mutation(offspring_crossover):
    offspring_mutation = []
    for i in range(len(offspring_crossover)):
        # 如果随机数小于变异概率，则进行变异
        if random.random() < MUTATION_RATE:
            # 随机选择一个基因进行变异
            mutation_point = random.randint(0, BOARD_SIZE - 1)
            # 随机生成一个新的基因
            mutation_gene = random.randint(0, BOARD_SIZE - 1)
            # 将基因替换为新的基因
            offspring_crossover[i].chromosome[mutation_point] = mutation_gene
        offspring_mutation.append(offspring_crossover[i])
    return offspring_mutation

# 运行遗传算法
genetic_algorithm()

该程序使用遗传算法来解决八皇后问题。其中，个体适应度的计算方式为：将所有冲突的皇后对数加1，然后取其倒数作为适应度。种群初始化时，每个个体的染色体都是一个随机排列的数列，表示每个皇后所在的列数。在每一代的进化过程中，先对种群进行排序，然后选择适应度更高的个体作为父母进行繁殖。选择时，每次随机选择两个个体，然后选择其中适应度更高的个体作为父母。交叉时，每次随机选择两个父母，然后随机选择一个交叉点，将交叉点之前的基因从一个父母继承，交叉点之后的基因从另一个父母继承，生成两个后代。变异时，每次随机选择一个个体，然后随机选择一个基因进行变异，将其替换为一个随机生成的新基因。最后，输出最优解并结束程序。