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] queen_example.jpg 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

Finding a solution to the N-Queen problem with a genetic algorithm (2)
Finding a solution to the N-Queen problem with a genetic algorithm (1)
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
Try to solve the traveling salesman problem with a genetic algorithm (execution result)
How to fix the initial population with a genetic algorithm using DEAP
The first algorithm to learn with Python: FizzBuzz problem
A story about how to deal with the CORS problem
I wanted to solve the ABC164 A ~ D problem with Python
Finding the optimum value of a function using a genetic algorithm (Part 1)
Search the maze with the python A * algorithm
I tried "Implementing a genetic algorithm (GA) in python to solve the traveling salesman problem (TSP)"
Try to solve the fizzbuzz problem with Keras
How to try the friends-of-friends algorithm with pyfof
Save the object to a file with pickle
A solution to the problem that the Python version in Conda cannot be changed
I failed to install django with pip, so a reminder of the solution
[Python] Solution to the problem that elements are linked when copying a list
Calculate the optimal solution to set a world record for decathlon with scipy.optimize
Try to solve the internship assignment problem with Python
Transit to the update screen with the Django a tag
I tried to solve the problem with Python Vol.1
A solution to the problem that files containing [and] are not listed in glob.glob ()
A solution to the problem that kernel restarting frequently occurs when running PyQt system with jupyter or Spyder IDE
Python sample to learn XOR with genetic algorithm with neural network
Probably the easiest way to create a pdf with Python3
[Python] Try optimizing FX systole parameters with a genetic algorithm
The first step to creating a serverless application with Zappa
I tried to solve a combination optimization problem with Qiskit
The usual way to add a Kernel with Jupyter Notebook
[Python] The first step to making a game with Pyxel
A memo that solves the knapsack problem by the greedy algorithm
Try to model a multimodal distribution using the EM algorithm
A person who wants to clear the D problem with ABC of AtCoder tried to scratch
The story of the algorithm drawing a ridiculous conclusion when trying to solve the traveling salesman problem properly
Let's write a program to solve the 4x4x4 Rubik's Cube! 2. Algorithm
[Introduction to Python] How to split a character string with the split function
[Introduction to StyleGAN] I played with "The Life of a Man" ♬
Try to solve the N Queens problem with SA of PyQUBO
Solving the Maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference-
Error with pip: There was a problem confirming the ssl certificate
Write a script to calculate the distance with Elasticsearch 5 system painless
Solve the Python knapsack problem with a branch and bound method
Solve the subset sum problem with a full search in Python
How to send a request to the DMM (FANZA) API with python
Create a REST API to operate dynamodb with the Django REST Framework
PhytoMine-I tried to get the genetic information of plants with Python
Finding the simplest mistakes with OpenCV
(Machine learning) I tried to understand the EM algorithm in a mixed Gaussian distribution carefully with implementation.
I want to solve the problem of memory leak when outputting a large number of images with Matplotlib
The 16th offline real-time how to write problem was solved with Python
A memo to simply use the illuminance sensor TSL2561 with Raspberry Pi 2
Calculate the shortest route of a graph with Dijkstra's algorithm and Python
Think about how to write a filter with the Shotgun API-Contact Versions
[Python] Explains how to use the range function with a concrete example
I tried to express sadness and joy with the stable marriage problem.
The 16th offline real-time how to write reference problem to solve with Python
[Django] I made a field to enter the date with 4 digit numbers
[Introduction to Python] How to sort the contents of a list efficiently with list sort
[Introduction to Python] How to write a character string with the format function
The 15th offline real-time how to write problem was solved with python