Finding a solution to the N-Queen problem with a genetic algorithm (2)

Last time asked for one of the solutions to the N-Queen problem for the case of N = 8. This time we will extend it to any N.

policy

Basically, just replace 8 in Last time with any N. This time, I will write a program that finds a solution by specifying the value of N as an argument and executing it. The number of genes remains four. Last time, the crossing position was fixed, but this time it changes depending on N. Specifically, the N-4th and subsequent elements are replaced, and the N-2nd and subsequent elements are replaced.

Summary

I will wake it up in the source code immediately.

n-queen.py


#! /usr/bin/env python
# encoding=utf-8

# N 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)]

def makeIniGene(dim):
	ini_gene = []
	for cnt in range(0,gGeneCnt):
		line = []
		for i in range(0, dim):
			val = random.randint(0, dim-1)
			line.append(val)

		ini_gene.append(line)

	return ini_gene

def calcFitness(gene, dim):
	fitness = 0
	board = []
	line = []
	for i in range(0, dim):
		line = []
		for j in range(0, dim):
			if j == gene[i]:
				line.append(1)
			else:
				line.append(0)
		board.append(line)

	for i in range(0, dim):
		for j in range(0, dim):
			val = getCell(board, (i,j), (0,0), dim)
			if val == 1:
				for vec in gVec:
					for k in range(1, dim):
						valofst = getCell(board, (i,j), (vec[0]*k, vec[1]*k), dim)
						if valofst == 1:
							fitness += 1
						elif valofst == -1:
							break

	return fitness

def getCell(board, pos, ofst, dim):
	posx = pos[0] + ofst[0]
	posy = pos[1] + ofst[1]
	if posx >= 0 and posy >= 0 and posx < dim and posy < dim:
		val = board[posx][posy]
	else:
		val = -1
	
	return val

def simpleGa(gene_list, rank_list, dim):
	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])

	gaIdx = [dim-4, dim-2]
	updated_gene_list = []
	line1 = []
	line2 = []
	for i in range(0, dim):
		if i < gaIdx[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, dim):
		if i < gaIdx[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):
	dim = int(argv[1])
	gene_list = makeIniGene(dim)
	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,  dim-1)
			valrand = random.randint(0,  dim-1)
			gene_list[geneidx][posidx] = valrand

		# compare fitness
		for gene in gene_list:
			fitness[idx] = calcFitness(gene, dim)
			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, dim)
		gene_list = updated_gene_list


if __name__ == "__main__":
        main(sys.argv)

As an example, the execution result when N = 16 is shown.

$./n-queen.py 16
...
...
2
2
2
0
Loop end = 23420, Fitness = 0
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[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, 0, 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, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]

Convergence is slow. .. .. .. It seems that it is necessary to change the method of crossing to accelerate the convergence. At the end, it depends on the luck of mutation, so it may be necessary to think about a proper mutation method. This is a future issue.

reference

AI for the first time to learn while experiencing with Excel :: Noboru Asai

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)
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
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
Find the optimal value of a function with a genetic algorithm (Part 2)
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
Solving the Python knapsack problem with the greedy algorithm
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
Solving the traveling salesman problem with the genetic algorithm (GA) and its library (vcopt)
[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
How to create a submenu with the [Blender] plugin
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 memo on how to overcome the difficult problem of capturing FX with AI
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" ♬
How to make a command to read the configuration file with pyramid
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.
The NVM Checksum Is Not Valid, a solution to the problem that Intel's wired LAN is not recognized on Linux
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