遗传算法之:八皇后问题_遗传算法解决八皇后

八皇后问题:

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。正确的解有很多个,遗传算法并不直接计算一共有多少个解,而是寻找满足条件的解,从一种状态进化到一种满足8皇后不能互相攻击的状态.

Q . . . . . . .
. . . . Q . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
. . . . . . . Q
. . . . . . . .
. . Q . . . . .
1
2
3
4
5
6
7
8

用matplotlib简单可视化棋盘

import random
import numpy as np
import matplotlib.pyplot as plt
1
2
3
'
运行
运行

def display_chessboard(coordinates):
    plt.figure(figsize=(7, 7))
    for i in range(9):
        plt.axhline(y=i,c='black')
    for i in range(9):
        plt.axvline(x=i,c='black')
    for x,y in coordinates:
        plt.text(x+0.35,y+0.35,'Q',size=20,color='blue')
    plt.xlim(0,8)
    plt.ylim(0,8)
1
2
3
4
5
6
7
8
9
10
'
运行
运行

这是一个满足条件的状态

# 这是一个正确的摆法
coordinates = [(2, 0),(4, 1),(7, 2),(3, 3),(0, 4),(6, 5),(1, 6),(5, 7)] 
display_chessboard(coordinates)
1
2
3

遗传算法求解8皇后问题

1. 随机初始化和变异
2. 加入部分约束条件
3. 下面是遗传算法实现过程

1. 随机状态初始化

# 随机生成初始状态
def generate_initinal_state(length,constraint=False):
    geneSet = list(range(length))
    # 不同行不同列约束
    if constraint:
        coordinate_xs = random.sample(geneSet,length)
        coordinate_ys = random.sample(geneSet,length)
        coordinates = [(x,y) for x,y in zip(coordinate_xs, coordinate_ys)]
    else:
        coordinate_xs = [random.sample(geneSet,1)[0] for i in range(length)]
        coordinate_ys = [random.sample(geneSet,1)[0] for i in range(length)]
        coordinates = [(x,y) for x,y in zip(coordinate_xs, coordinate_ys)]
    return coordinates
1
2
3
4
5
6
7
8
9
10
11
12
13
'
运行
运行

coordinates_1 = generate_initinal_state(8)
coordinates_2 = generate_initinal_state(8, True)
1
2

##### 随机初始,只有一个queen满足条件
display_chessboard(coordinates_1)
1
2

这个是没有约束的随机初始化

##### 增加行列约束后,有两个queen满足条件
display_chessboard(coordinates_2)
1
2

增加了行列约束的

2.适应度的计算

需要一个合适的适应度函数来量化当前棋盘的状态,便于跟其他状态进行比较.

1. 逐个计算每个Queen的状态,满足条件+1,bestFitness = 8
2. 通过Queen的坐标计算当前棋盘状态,bestFitness = 0

方案1:比较简单,就是遍历Queens,检测前后左右,对角线有无其他Queen,详细说下方案2:

1. Queen横坐标集合,x_set
2. Queen纵坐标集合.y_set
3. 以棋盘左下角为原点,计算Queens坐标和(x+y)的集合,a_set
4. 以棋盘右下角为原点,计算Queens坐标和(x+y)的集合,b_set
5. $fitness=8\times 4-(len(x_{set})+len(y_{set})+len(a_{set})+len(b_{set}))$

• 步骤1: x_set的长度就是不同列Queens的数量
• 步骤2: y_set的长度就是不同行Queens的数量
• 步骤3,4: 就是判断以Queen为中心,左右对角线有无Queen,如下图:
• 步骤5: 32是指8个不同x坐标,8个不同的y坐标,8个不同左右对角线,$8\times 4=32$,所以要满足不能相互攻击的条件:
  $$len(x_{set})+len(y_{set})+len(a_{set})+len(b_{set})=32$$
  所以在8皇后问题中,fitness = 0时最好的.

发现没有,如果Queen在同一对角线的话,坐标和是相等的,如果8个Queen的坐标和是不同的8个数字,那就满足了条件的25%了

2.1适应度函数

def get_fitness(coordinates):
    x_s = [coordinate[0] for coordinate in coordinates]
    y_s = [coordinate[1] for coordinate in coordinates]
    x_set = set(x_s)
    y_set = set(y_s)
    # 左对角线
    a_set = set([sum(coordinate) for coordinate in  coordinates])
    # 右对角线(反转x轴)
    b_set = set([8 - coordinate[0]+coordinate[1] for coordinate in coordinates])
    fitness = 32 -len(x_set)-len(y_set)-len(a_set)-len(b_set)
    return fitness
1
2
3
4
5
6
7
8
9
10
11
'
运行
运行

计算一个状态的适应度

random_state = generate_initinal_state(length=8)
display_chessboard(random_state)
print('random_state fitness : ',get_fitness(random_state))
1
2
3

random_state fitness :  10
1

3.变异方法

1. 无约束随机
   这个地方可以加入一些约束,加速,但是复杂的约束会影响效率

def mutate(coordinates, coordinateSet):
    index = np.random.randint(8)
    new_coordinates = coordinates.copy()
    picked_gene = coordinates[index]
    new_gene, alternative = random.sample(coordinateSet, 2)
    if picked_gene == new_gene:
        new_coordinates[index] = alternative
    else:
        new_coordinates[index] = new_gene
    return new_coordinates
1
2
3
4
5
6
7
8
9
10
'
运行
运行

从随机初始状态进化的过程

init_state = generate_initinal_state(length=8,constraint=True) 
display_chessboard(init_state)
1
2

初始状态是加入了约束的,开局的状态比较理想.

print('init state fitness : ',get_fitness(init_state))
1

init state fitness :  4
1

coordinateSet = [(x,y) for x in range(8) for y in range(8)]
1
'
运行
运行

state_logs = []
fines_logs = []
bestState = init_state
bestFitness = get_fitness(init_state)
state_logs.append(bestState)
fines_logs.append(bestFitness)
while True:
    childState = mutate(bestState,coordinateSet)
    childFitness = get_fitness(childState)
    state_logs.append(childState)
    fines_logs.append(childFitness)
    if childFitness > bestFitness:
        continue
    print('childState Fitness :',childFitness)
    if childFitness == 0:
        display_chessboard(childState)
        break
    bestState = childState
    bestFitness = childFitness
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

childState Fitness : 4
childState Fitness : 4
childState Fitness : 4
childState Fitness : 4
childState Fitness : 4
childState Fitness : 3
childState Fitness : 3
childState Fitness : 3
childState Fitness : 3
childState Fitness : 3
childState Fitness : 2
childState Fitness : 2
childState Fitness : 2
childState Fitness : 2
childState Fitness : 2
childState Fitness : 2
childState Fitness : 2
childState Fitness : 2
childState Fitness : 2
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 1
childState Fitness : 0
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

适应度的变化

进化的过程我做成了短视频,会放到公众号: 唐牛才是食神
常驻作者: 今晚打老虎, 懂王就是懂, 唐牛才是食神
安利一下公众号: