admin管理员组文章数量:1596416
问题描述：
八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 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"] 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=True) # 降序 specimen_list = select_probability(specimen_list) # 计算被选为父母的概率 return specimen_list # 轮盘赌算法 def roulette_algorithm(list): total_probability = 0 p = random.random() for i in list: total_probability = total_probability + i["select"][0] if total_probability > p: break return i # 运行两次轮盘赌得到父母基因,这两个样本应该不同 def sa_roulette(list): # fix_bug # 这段代码为了修复种群过小时，经过多代繁衍，所有种群收敛到趋近于一个值，比如10个种群全部适应度为27 # 导致轮盘赌算法陷入无限循环 count = 0 temp = list[0] for i in list: if operator.eq(temp, i): count += 1 if count == len(list): mother = list[0] father = list[1] return mother, father # ******************************************************************************************* mother = roulette_algorithm(list) while True: father = roulette_algorithm(list) if operator.ne(mother, father): break return mother, father # 繁衍算法，产生新的M个种群 def cross_algorithm(origin_list, M): new_list = [] for i in range(M): mother, father = sa_roulette(origin_list) son = {} split_index = random.randrange(0, 8) for j in range(split_index): son["queen" + str(j)] = father["queen" + str(j)] for k in range(split_index, 8): son["queen" + str(k)] = mother["queen" + str(k)] new_list.append(son) return new_list # 优秀的基因直接保留，适应度较低的样本按一定的概率淘汰 def retain_and_eliminate(list, retain_prob, eliminate_prob): retain_list = [] length = len(list) # 保留retain_prob百分比的样本 retain_index = int(length * retain_prob) for i in range(retain_index): retain_list.append(list[i]) eliminate_index = int(length * eliminate_prob) # 因为列表已经按照适应度排序，只需要计算出要淘汰的个数，直接将样本从列表尾部POP掉 for j in range(eliminate_index): list.pop() return retain_list, list # 基因变异函数,每个样本的皇后位置会根据mutation_prob的概率随机调整 def mutation_algorithm(list, mutation_prob): for i in range(len(list)): if random.random() < mutation_prob: row = random.randrange(0, 8) column = random.randrange(0, 8) list[i]["queen" + str(column)] = [row, column] return list # 判断种群中是否有满足条件的个体，即无碰撞数量为28 def screening_population(population_list): for i in population_list: if fitness_algorithm_single(i) == 28: return True return False def SA_algorithm(T=50, M=10, retain_prob=0.3, eliminate_prob=0.3, mutation_prob=0.1): """ :param T: 最大繁殖代数 :param M: 种群大小 :param retain_prob: 每一代中优良基因直接保留的百分比 :param eliminate_prob: 每一代中淘汰的百分比 :param mutation_prob: 变异百分比 :return:bool """ population_list = init_population(M) # 初始化种群，已经按适应度降序排列 print("初始种群的状态为：", ) for j in population_list: print(j) for i in range(T): if screening_population(population_list): return True print("当前种群的状态为：",) for j in population_list: print(j) retain_list, left_list = retain_and_eliminate(population_list, retain_prob, eliminate_prob) # 保留优良基因和淘汰适应度低的基因 print("直接保留的个体为：") for j in retain_list: print(j) print("淘汰之后剩余的个体") for j in left_list: print(j) cross_list = cross_algorithm(left_list, M - len(retain_list)) # 基因交叉,因为保留了一部分优良基因，这里产生的基因等于M-保留的基因数 print("交叉产生的新个体为:") for j in cross_list: print(j) population_list = mutation_algorithm(retain_list + cross_list, mutation_prob) # 基因变异 population_list = fitness_algorithm_for_list(population_list) population_list = select_probability(population_list) population_list = sorted(population_list, key=lambda keys: keys["fitness"], reverse=True) # 降序 print("变异后产生的种群为:") for j in population_list: print(j) return False def sa_algorithm_test(T, M, retain_prob, eliminate_prob, mutation_prob, num=1000): success_case = 0 fail_case = 0 tic = time.time() for i in range(num): if SA_algorithm(T, M, retain_prob, eliminate_prob, mutation_prob): success_case += 1 print("第{0}个例子发现最优解".format(i)) else: fail_case += 1 print("第{0}个例子失败".format(i)) toc = time.time() print("{0}个例子中成功解决的例子为：{1}".format(num, success_case)) print("{0}个例子成功解决的百分比为：{1}".format(num, success_case / num)) print("{0}个例子中失败的例子为：{1}".format(num, fail_case)) print("{0}个例子失败的百分比为：{1}".format(num, fail_case / num)) print("{0}个例子运行算法所需的时间为：{1}秒".format(num, toc - tic)) sa_algorithm_test(T=300, M=50, retain_prob=0.3, eliminate_prob=0.3, mutation_prob=0.3, num=1000)
在实验参数为：T=100,M=30, retain_prob=0.3, eliminate_prob=0.3, mutation_prob=0.3情况下，实验结果为：
版权声明：本文标题：人工智能-遗传算法解决八皇后问题-python源码 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728257538a1151190.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论