关于遗传算法解决八皇后问题的简单代码的疑问
import timeimport numpy as np
import random
start = time.time()
seqs = [
for i in range(1, 9)
for j in range(1, 9)
for k in range(1, 9)
for l in range(1, 9)
for m in range(1, 9)
for n in range(1, 9)
for o in range(1, 9)
for p in range(1, 9)
if all([i != j, i != k, i != l, i != m, i != n, i != o, i != p,
j != k, j != l, j != m, j != n, j != o, j != p,
k != l, k != m, k != n, k != o, k != p,
l != m, l != n, l != o, l != p,
m != n, m != o, m != p,
n != o, n != p,
o != p])]# 筛选出【每行与每列都只有一个皇后】的序列
print('有' + str(len(seqs)) + '个可能的序列')
def calculate_fitness(s):
"""
计算个体的适应度，大小设为【攻击的皇后对数n】，0<=n<=28
最优解要满足【攻击的皇后对数n为0】
"""
a = np.array( * 81)# 在开始时创建一个有81个0的一维数组
a = a.reshape(9, 9)# 改为9*9二维数组。为方便后面使用，只用后八行和后八列的8*8部分，作为一个空白棋盘
n = 0# 适应度大小初始化为0
for i in range(1, 9):
a] = 1# 根据【个体】，即序列从第一列到最后一列的顺序，在对应位置放一个皇后，生成当前序列对应的棋盘
for i in range(1, 9):# 检查当前序列的八个皇后在各自的行及两条对角线上是否有其他皇后，不需判断同列是否有其他皇后，因为编码方式决定了同一列有且只有一个皇后
for k in list(range(1, i)) + list(range(i + 1, 9)):# 检查每个皇后各自所在的行上是否有其他皇后
if a] == 1:# 有其他皇后
n += 1
t1 = t2 = s
for j in range(i - 1, 0, -1):# 看左半段的两条对角线
if t1 != 1:
t1 -= 1
if a == 1:
n += 1# 正对角线左半段上还有其他皇后
if t2 != 8:
t2 += 1
if a == 1:
n += 1# 次对角线左半段上还有其他皇后
t1 = t2 = s# 继续检查右半段的两条对角线
for j in range(i + 1, 9):# 看右半段的两条对角线
if t1 != 1:
t1 -= 1
if a == 1:
n += 1# 正对角线右半段上还有其他皇后
if t2 != 8:
t2 += 1
if a == 1:
n += 1# 次对角线右半段上还有其他皇后
return int(n/2)# 返回n/2，因为A攻击B也意味着B攻击A，因此返回n的一半
def selection(populations, percents):
"""
对种群populations进行遗传算法的“选择”操作
使用轮盘赌法
"""
temp = 0
for i in range(len(populations)):# 累计百分数
temp += percents
percents = temp
percents.insert(0, 0)# 在开头插入一个零，方便后续比较
new_populations = []# 存放选择后的种群
for i in range(len(populations)):# 产生n个随机数，其中n为种群规模；根据随机数落在百分数列表中的位置去选择相应个体（轮盘赌）
a = random.random()
for pos in range(len(populations)):
if percents <= a < percents:
new_populations.append(populations)# 存放选择到的个体
break# 找到a所在的范围就退出循环，测试下一个随机数
return new_populations# 返回新一代种群
def crossover(populations):
"""
对种群populations进行“交叉”操作
随机将种群中的个体分为两组，然后将两个组中对应位置的个体两两交叉，从每个个体的第5个数开始做交叉
如第一组的第一个个体的后4个数和第二组的第一个个体的后4个数做交叉，第一组的第二个个体的后4个数和第二组的第二个个体的后4个数做交叉，以此类推
"""
temp1 = []
temp2 = []
new_populations = []# 存放交叉后的种群
n = len(populations)
for i in range(n):
tmp = random.choice(populations)
populations.remove(tmp)# 移除已选到的个体，避免选到相同个体
if i < n / 2:# 随机选择种群中的个体，分成两组
temp1.append(tmp)# temp1保存前一半随机选到的个体
continue
temp2.append(tmp)# temp2保存后一半随机选到的个体
temp1 = temp1 + temp2# 将两个列表合成为一个列表；这是一种技巧，方便后续交叉
temp2 = temp1[::-1]# 为temp1的倒序输出
for i in range(n):# 交叉
new_populations.append(temp1[:4] + temp2)
return new_populations
def mutation(populations):
""""
对种群populations进行“变异”操作
检查种群中的每个个体，看是否有重复的数字，因为重复的数字意味着在某一行有多于或等于2个皇后存在，故此个体不符合要求，需要变异
如个体12746737有三个7，意味着第七行有三个皇后，不符合要求
此时仅保留最后一个i，再用个体中在1到8中未出现的数字替换重复的数字
如上面的12746737缺少58，故将58【随机地】放在前两个7的位置，如可以将8放在第3个位置（第一个7的位置），5放在第6个位置（第二个7的位置），得到12846537
"""
new_populations = []# 存放变异后的种群
for item in populations:
tmp = list({1, 2, 3, 4, 5, 6, 7, 8} - set(item))# 找出个体中在1到8中未出现的数字，用来在后面代替重复的数字
for i in range(1, 9):# 检查数字i出现次数a是否为1，如果次数a>1，则找出前a-1个数字i的位置，用个体在1到8中未出现的数字【随机】进行替换
a = item.count(i)
if a > 1:
for k in range(a - 1):# 如果数字i出现的次数a大于1，就替换前a-1个的数字，仅留一个数字i
a = random.choice(tmp)
tmp.remove(a)
item = a
new_populations.append(item)
return new_populations
populations = []# 存放初始种群及后代种群
n = 100# 种群规模为n
iterations = 10# 设置迭代次数，避免无限循环
for i in range(n):
tmp = random.choice(seqs)
populations.append(tmp)# 保存每次随机选到的“个体”（这里是一个序列）
seqs.remove(tmp)# 移除已选到的个体，避免选到相同个体
print('第0代（初始）种群中的前几个个体如下：')# 只输出前几个个体，全部输出就太多了，不好看
print(', '.join(str(seq) for seq in populations[:5]))
for iteration in range(iterations + 1):# 加上初始种群（第0代），最多到iterations+1代种群
fitness = []# 存放种群中每个个体的适应度
good = []# 保存满足条件的个体
for item in populations:
a = calculate_fitness(item)
fitness.append(a)
if a == 0:# 若当前种群存在适应度为0的个体，则此个体为满足条件的一个解
good.append(item)
if good:# 若good不为空时，代表当前代种群中有满足条件的解
print('经过计算以及多次迭代，当前代，也就是第' + str(iteration) + '代种群中存在满足条件的个体。')
print('当前代种群由下列个体组成（只输出前几项）：\n' + ', '.join(str(p) for p in populations[:5]) + '\n满足条件的个体为：')
print(', '.join(str(g) for g in good))
break
print('经过计算，第' + str(iteration)+'代不行')
sum_of_fitness = sum(fitness)
percents = /sum_of_fitness) for i in range(n)]
populations = mutation(crossover(selection(populations, percents)))# 依次进行选择、交叉、变异操作
此程序运行代数越多，越不准确，有人说是适应度函数出问题，写反了，但是我只学了4周不到，看不出来，有大佬指一下哪里有问题吗，应该如何修改中间的适应度函数呢？
学了四周不到的 Python 自己写八皇后真的是超级厉害 {:10_333:}{:10_333:}
页:
[1]