人工智能
八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
算法解决流程图为：
源代码为：
importnumpyasnpimportrandomimporttimeimportoperator#遗传算法解决八皇后问题#八皇后初始化函数definit():cache={}m=np.zeros((8,8),dtype=int)foriinrange(0,8):temp=random.randrange(0,8)m[temp,i]=1cache["queen"+str(i)]=[temp,i]returnm,cache#计算一个八皇后状态的适应度,计算方法为皇后无碰撞数量deffitness_algorithm_single(coord_cache):weight=0foriinrange(0,8):row,column=coord_cache["queen"+str(i)]forjinrange(i+1,8):_row,_column=coord_cache["queen"+str(j)]if_row-row==j-ior_row-row==i-j:weight+=1if_row==row:weight+=1return28-weight#28表示最优解状态互不攻击的皇后数目，减去碰撞数目即为适应度#为一个种群计算适应度deffitness_algorithm_for_list(list):foriinlist:fitness=fitness_algorithm_single(i)i["fitness"]=[fitness]returnlist#根据适应度计算出每个样本被选择的概率defselect_probability(list):total_fitness=0specimen_list=listforiinspecimen_list:fitness=i["fitness"]total_fitness+=fitness[0]forjinspecimen_list:fitness=j["fitness"]j["select"]=[fitness[0]/total_fitness]returnspecimen_list#初始化种群函数，并依据适应度进行了排序definit_population(M):specimen_list=[]#种群列表foriinrange(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=lambdakeys:keys["fitness"],reverse=True)#降序specimen_list=select_probability(specimen_list)#计算被选为父母的概率returnspecimen_list#轮盘赌算法defroulette_algorithm(list):total_probability=0p=random.random()foriinlist:total_probability=total_probability+i["select"][0]iftotal_probability>p:breakreturni#运行两次轮盘赌得到父母基因,这两个样本应该不同defsa_roulette(list):#fix_bug#这段代码为了修复种群过小时，经过多代繁衍，所有种群收敛到趋近于一个值，比如10个种群全部适应度为27#导致轮盘赌算法陷入无限循环count=0temp=list[0]foriinlist:ifoperator.eq(temp,i):count+=1ifcount==len(list):mother=list[0]father=list[1]returnmother,father#*******************************************************************************************mother=roulette_algorithm(list)whileTrue:father=roulette_algorithm(list)ifoperator.ne(mother,father):breakreturnmother,father#繁衍算法，产生新的M个种群defcross_algorithm(origin_list,M):new_list=[]foriinrange(M):mother,father=sa_roulette(origin_list)son={}split_index=random.randrange(0,8)forjinrange(split_index):son["queen"+str(j)]=father["queen"+str(j)]forkinrange(split_index,8):son["queen"+str(k)]=mother["queen"+str(k)]new_list.append(son)returnnew_list#优秀的基因直接保留，适应度较低的样本按一定的概率淘汰defretain_and_eliminate(list,retain_prob,eliminate_prob):retain_list=[]length=len(list)#保留retain_prob百分比的样本retain_index=int(length*retain_prob)foriinrange(retain_index):retain_list.append(list[i])eliminate_index=int(length*eliminate_prob)#因为列表已经按照适应度排序，只需要计算出要淘汰的个数，直接将样本从列表尾部POP掉forjinrange(eliminate_index):list.pop()returnretain_list,list#基因变异函数,每个样本的皇后位置会根据mutation_prob的概率随机调整defmutation_algorithm(list,mutation_prob):foriinrange(len(list)):ifrandom.random()