Finding a solution to the N-Queen problem with a genetic algorithm (1)
I decided to solve the N-Queen problem (find one of the solutions) as a starting point for studying genetic algorithms. Any programming language was fine, but I decided to use python because it is easy to write.
N-Queen problem
The problem of finding a pattern in which N chess Queens are placed on the NxN board so that they do not conflict with each other. Queen can move vertically, horizontally, and naname without any restrictions. It would be nice if we could find all the solutions, but this time we will try to find one of the solutions using a genetic algorithm. To simplify the problem, let's first consider the case of N = 8 and then correspond to any N.
Application of genetic algorithm
Definition of genes
First of all, how to represent a gene. It needs to be able to express the final solution.
Therefore, a first-order vector representing the position of Queen on the board is adopted as a gene.
The Queen position in each column is represented by 0-7. For example.
[0, 2, 3, 1, 4, 3, 6, 7]
Based on this, prepare the initial gene. This time we will use four. Each element of the vector randomly selects 0-7.
python
def makeIniGene():
ini_gene = []
for cnt in range(0, 4):
line = []
for i in range(0, 8):
val = random.randint(0, 7)
line.append(val)
ini_gene.append(line)
return ini_gene
Fitness
Fitness is an indicator of how close a gene is to a goal. This time, in the arrangement of a certain gene = Queen on the board, the fitness is the number of Queens competing with each other. Therefore, the final solution can be found when fitness = 0. The fitness calculation is performed by searching one square in eight directions from the position of one queen, and when another queen is found, the fitness is incremented by +1.
python
gVec = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
def calcFitness(gene):
fitness = 0
board = []
line = []
for i in range(0, 8):
line = []
for j in range(0, 8):
if j == gene[i]:
line.append(1)
else:
line.append(0)
board.append(line)
for i in range(0, 8):
for j in range(0, 8):
val = getCell(board, (i,j), (0,0))
if val == 1:
for vec in gVec:
for k in range(1, 8):
valofst = getCell(board, (i,j), (vec[0]*k, vec[1]*k))
if valofst == 1:
fitness += 1
elif valofst == -1:
break
return fitness
def getCell(board, pos, ofst):
posx = pos[0] + ofst[0]
posy = pos[1] + ofst[1]
if posx >= 0 and posy >= 0 and posx < 8 and posy < 8:
val = board[posx][posy]
else:
val = -1
return val
An example of the calculation result is shown below. [0, 1, 2, 3, 4, 5, 6, 7] => fitness = 56
Heredity
As an example, the following four genes are used as parents to generate offspring genes. G0 = [0, 1, 2, 3, 4, 5, 6, 7] => fitness = 56 G1 = [0, 0, 1, 1, 2, 2, 3, 3] => fitness = 14 G2 = [0, 2, 4, 6, 7, 5, 3, 1] => fitness = 6 G3 = [1, 3, 5, 7, 0, 1, 2, 3] => fitness = 20
Arrange in ascending order of fitness. The rank is rank = 0 to 3. G2 = [0, 2, 4, 6, 7, 5, 3, 1] => rank = 0 G1 = [0, 0, 1, 1, 2, 2, 3, 3] => rank = 1 G3 = [1, 3, 5, 7, 0, 1, 2, 3] => rank = 2 G0 = [0, 1, 2, 3, 4, 5, 6, 7] => rank = 3
Leave the excellent genes first. Replaces the gene with the highest fitness with the gene with the lowest fitness. In this case, overwrite the value of G0 with the value of G2. G2 = [0, 2, 4, 6, 7, 5, 3, 1] G1 = [0, 0, 1, 1, 2, 2, 3, 3] G3 = [1, 3, 5, 7, 0, 1, 2, 3] G0' = [0, 2, 4, 6, 7, 5, 3, 1]
Next, cross over. Crossover is the process of generating a child gene from a parent gene. This time we will consider a simple crossover. First, replace the k-th and subsequent elements of the gene with rank = 0 and the gene with rank = 1. This time, I will replace the elements after k = 5th. G2' = [0, 2, 4, 6, 2, 2, 3, 3] G1' = [0, 0, 1, 1, 7, 5, 3, 1] Next, the elements after the mth of the gene with rank = 2 and the gene with rank = 3 are exchanged. This time, I will replace the elements after m = 7. G3' = [1, 3, 5, 7, 0, 1, 3, 1] G0'' = [0, 2, 4, 6, 7, 5, 2, 3]
From the above, the genes of the offspring are the following four. G2' = [0, 2, 4, 6, 2, 2, 3, 3] G1' = [0, 0, 1, 1, 7, 5, 3, 1] G3' = [1, 3, 5, 7, 0, 1, 3, 1] G0'' = [0, 2, 4, 6, 7, 5, 2, 3]
The source code of the genetic part is as follows. gene_list is a list of parent genes. rank_list has its index as rank and stores the index of gene_list in its element. In other words, in the case of this example, the image is rank_list = [2, 1, 3, 0].
python
gGaIdx = [4, 6]
def simpleGa(gene_list, rank_list):
new_gene_list = []
for i in range(0, gGeneCnt):
if i == rank_list[3]:
new_gene_list.append(gene_list[rank_list[0]])
else:
new_gene_list.append(gene_list[i])
updated_gene_list = []
line1 = []
line2 = []
for i in range(0, 8):
if i < gGaIdx[0]:
line1.append(new_gene_list[rank_list[0]][i])
line2.append(new_gene_list[rank_list[1]][i])
else:
line1.append(new_gene_list[rank_list[1]][i])
line2.append(new_gene_list[rank_list[0]][i])
updated_gene_list.append(line1)
updated_gene_list.append(line2)
line1 = []
line2 = []
for i in range(0, 8):
if i < gGaIdx[1]:
line1.append(new_gene_list[rank_list[2]][i])
line2.append(new_gene_list[rank_list[3]][i])
else:
line1.append(new_gene_list[rank_list[3]][i])
line2.append(new_gene_list[rank_list[2]][i])
updated_gene_list.append(line1)
updated_gene_list.append(line2)
return updated_gene_list
mutation
By repeating the genetic procedure (crossover), we will try to leave excellent genes. However, repeating crossovers may lead to local solutions. To give an example of a local solution to the 8-Queens problem, fitness = 2, that is, the remaining pair of Queens may be stuck in a state of competing with each other. In order to overcome this condition, it is necessary to make a mutation. This time, we will simply replace one element of one gene with a random value from 0 to 7 every four genetic procedures.
python
# mutation
if loop % 4 == 0:
geneidx = random.randint(0, 3)
posidx = random.randint(0, 7)
valrand = random.randint(0, 7)
gene_list[geneidx][posidx] = valrand
Summary
Put the above together in the source code.
8-queen.py
#! /usr/bin/env python
# encoding=utf-8
# 8 Queens Problem
import sys
import random
gGeneCnt = 4
gMutationSpan = 4
gRange = 0
gVec = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
gGaIdx = [4, 6]
def makeIniGene():
ini_gene = []
for cnt in range(0,gGeneCnt):
line = []
for i in range(0, 8):
val = random.randint(0, 7)
line.append(val)
ini_gene.append(line)
return ini_gene
def calcFitness(gene):
fitness = 0
board = []
line = []
for i in range(0, 8):
line = []
for j in range(0, 8):
if j == gene[i]:
line.append(1)
else:
line.append(0)
board.append(line)
for i in range(0, 8):
for j in range(0, 8):
val = getCell(board, (i,j), (0,0))
if val == 1:
for vec in gVec:
for k in range(1, 8):
valofst = getCell(board, (i,j), (vec[0]*k, vec[1]*k))
if valofst == 1:
fitness += 1
elif valofst == -1:
break
return fitness
def getCell(board, pos, ofst):
posx = pos[0] + ofst[0]
posy = pos[1] + ofst[1]
if posx >= 0 and posy >= 0 and posx < 8 and posy < 8:
val = board[posx][posy]
else:
val = -1
return val
def simpleGa(gene_list, rank_list):
new_gene_list = []
for i in range(0, gGeneCnt):
if i == rank_list[3]:
new_gene_list.append(gene_list[rank_list[0]])
else:
new_gene_list.append(gene_list[i])
updated_gene_list = []
line1 = []
line2 = []
for i in range(0, 8):
if i < gGaIdx[0]:
line1.append(new_gene_list[rank_list[0]][i])
line2.append(new_gene_list[rank_list[1]][i])
else:
line1.append(new_gene_list[rank_list[1]][i])
line2.append(new_gene_list[rank_list[0]][i])
updated_gene_list.append(line1)
updated_gene_list.append(line2)
line1 = []
line2 = []
for i in range(0, 8):
if i < gGaIdx[1]:
line1.append(new_gene_list[rank_list[2]][i])
line2.append(new_gene_list[rank_list[3]][i])
else:
line1.append(new_gene_list[rank_list[3]][i])
line2.append(new_gene_list[rank_list[2]][i])
updated_gene_list.append(line1)
updated_gene_list.append(line2)
return updated_gene_list
def printBoard(gene):
for i in range(0, len(gene)):
line = []
for j in range(0, len(gene)):
if j == gene[i]:
line.append(1)
else:
line.append(0)
print line
def main(argv):
gene_list = makeIniGene()
print "Initial gene = " + str(gene_list)
fitness = []
for i in range(0, gGeneCnt):
fitness.append(0)
loop = 0
while True :
loop += 1
idx = 0
max_fitness_idx = []
min_fitness_idx = []
# mutation
if loop % gMutationSpan == 0:
geneidx = random.randint(0, gGeneCnt-1)
posidx = random.randint(0, 7)
valrand = random.randint(0, 7)
gene_list[geneidx][posidx] = valrand
# compare fitness
for gene in gene_list:
fitness[idx] = calcFitness(gene)
if idx == 0:
max_fitness_idx = (fitness[0], 0)
min_fitness_idx = (fitness[0], 0)
if max_fitness_idx[0] < fitness[idx]:
max_fitness_idx = (fitness[idx], idx)
if min_fitness_idx[0] > fitness[idx]:
min_fitness_idx = (fitness[idx], idx)
print fitness[idx]
idx += 1
min_fitness = min(fitness)
if min_fitness <= gRange:
print "Loop end = " + str(loop) + ", Fitness = " + str(min_fitness)
printBoard(gene_list[min_fitness_idx[1]])
break
ranktemp = []
for i in range(0, gGeneCnt):
if i != max_fitness_idx[1] and i != min_fitness_idx[1]:
ranktemp.append(i)
if fitness[ranktemp[0]] > fitness[ranktemp[1]]:
rank_list = [ min_fitness_idx[1], ranktemp[1], ranktemp[0], max_fitness_idx[1] ]
else:
rank_list = [ min_fitness_idx[1], ranktemp[0], ranktemp[1], max_fitness_idx[1] ]
updated_gene_list = []
updated_gene_list = simpleGa(gene_list, rank_list)
gene_list = updated_gene_list
if __name__ == "__main__":
main(sys.argv)
When executed, the fitness is displayed with a dash, and when a solution is found (fitness = 0), the number of loops and the position of Queen on the board are shown.
$ ./8-queen.py
...
...
2
2
2
2
2
2
0
2
Loop end = 12964, Fitness = 0
[0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
Next time will try to extend from N = 8 to any N.
Recommended Posts