人工智能-遗传算法解决八皇后问题-python源码.pdf

⼈⼯智能-遗传算法解决⼋皇后问题-python源码 问问题题描描述述 ：： ⼋皇后问题，⼀个古⽼⽽著名的问题，是回 算法的典型案例。该问题由国际西洋棋棋⼿马克斯 ·贝瑟尔于 1848 年提出：在 8 ×8 格的国际象棋上摆放⼋个皇后，使其不能互相攻击，即任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上，问有多少种摆 法。 算法解决流程图为 ： 源代码为 ： import numpy as np import random import time import operator # 遗传算法解决⼋皇后问题 # ⼋皇后初始化函数 def init() : cache = {} m = np.zeros((8, 8), dtype=int) for i in range(0, 8) : temp = random.randrange(0, 8) m temp, i] = 1 cache "queen" + str(i)] = temp, i] return m, cache # 计算⼀个⼋皇后状态的适应度,计算⽅法为皇后⽆碰撞数量 def fitness_algorithm_single(coord_cache) : weight = 0 for i in range(0, 8) : row, column = coord_cache "queen" + str(i)] for j in range(i + 1, 8) : _ row, _column = coord_cache "queen" + str(j)] if _ row - row == j - i or _ row - row == i - j : weight += 1 if _ row == row : weight += 1 return 28 - weight # 28表⽰最优解状态互不攻击的皇后数 ⽬，减去碰撞数 ⽬即为适应度 # 为⼀个种群计算适应度 def fitness_algorithm_for_ list(list) : for i in list : fitness = fitness_algorithm_single(i) i "fitness"] = fitness] return list # 根据适应度计算出每个样本被选择的概率 def select_ probability(list) : total_fitness = 0 specimen_ list = list for i in specimen_ list : fitness = i "fitness"] fitness = i "fitness"] total_fitness += fitness 0] for j in specimen_ list : fitness = j "fitness"] j "select"] = fitness 0] / total_fitness] return specimen_ list # 初始化种群函数，并依据适应度进⾏了排序 def init_ population(M) : specimen_ list = ] # 种群列表 for i in range(M) : m, coord_cache = init() specimen_ list.append(coord_cache) specimen_ list = fitness_algorithm_for_ list(specimen_ list) # 对适应度进⾏排序 specimen_ list的结构为 {"queen0": row,column] "weight": weight]}] specimen_ list = sorted(specimen_ list, key=lambda keys: keys "fitness"], reverse=T