人工智障-遗传算法解8皇后问题

发表于 | 更新于 | 阅读次数：

！！！WARNING！！！
此算法为欧皇专用，非酋请注意回避！！！

课上的遗传算法解n皇后问题
根据书上的代码写的，没怎么修改。
（目前只测试了10皇后，而且出解的速度随缘，纯粹看脸）
ps：存在1w皇后，32次演化出解，和5min内8皇后压根解不出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import random

def init(total_num,num):  # 初始化种群，前一个为皇后数量，后一个为初始种群数目
    goal_array = [0,]
    for x in range(0,num):
        init_array = [0,]
        for i in range(1,total_num+1):
            init_array.append(random.randint(1,total_num))
        init_array = fitness(init_array)
        goal_array[0]+=init_array[0]
        goal_array.append(init_array)
    return goal_array

def fitness(query):  # 计算适应度，适应度返回在query[0]中
    marked = 0
    num = len(query)
    
    for i in range(1,num):
       
        test = query[i]
       
        for x in range(i+1,num):
            
            if((query[x]==test+x-i)|(query[x]==test-x+i)|(query[x]==test)):
                marked += 2
    query[0] = marked
    return query

def mutate(query): # 模拟变异
    x = random.randint(1,100)
    if(x==1):
        postion = random.randint(1,len(query)-1)
        value = random.randint(1,len(query)-1)
        query[postion-1] = value
    query = fitness(query)
    return query

def cross(query1,query2):   #  杂交
   
    cut_pos = random.randint(1,len(query1)-1)
    cut_q1_f = query1[1:cut_pos+1]
    cut_q1_b = query1[cut_pos+1:]
   
    cut_q2_f = query2[1:cut_pos+1]
    cut_q2_b = query2[cut_pos+1:]

    query_mix = [0,]
    if(random.randint(0,1)):
        query_mix+=(cut_q1_f)
        query_mix+=(cut_q2_b)
       
    else:
        query_mix+=(cut_q2_f)
        query_mix+=(cut_q1_b)


    return mutate(query_mix)

def check(query):  # 检查适应度
    if(query[0]==0):
        return 1
    else:
        return 0


def choose(global_num):  # 根据概率选择父母样本
  
    per_sum = []
    sum = global_num[0]
    total_num = global_array[1:]
   
    for x in range(1,len(global_num)): # 获取概率
      
        if(global_num[x][0]==0):
            return global_num[x]
        per_sum.append(global_num[x][0]/sum) 
   
    ran = random.random()
    sum_ =0
   
    for num, r in zip(total_num, per_sum): # 根据概率选择
        sum_ += r
        if ran < sum_ :break

    return num


global_array = init(8,50)
total = 0
while True:
    for x in range(0,len(global_array)-1): # 一次演化
        father = choose(global_array)

        mother = choose(global_array)
     
        child = cross(father,mother)
        global_array[0] += child[0]
        global_array.append(child)

    sort_array = global_array[1:]

    sort_global = sorted(sort_array,key=(lambda x:x[0]))

    if(sort_global[0][0]==0):
        print("find!!!")
        print("-"*50)
        print(sort_global[0])
        print("-"*50)
        print(total)
        break

    global_array = [global_array[0],]

    global_array+=(sort_global)


    if(len(global_array)>400):  # 控制最大种群数量
        global_array = global_array[:400]

    total += 1
    print(total)

以上算法仅供参考。