Trouver une solution au problème N-Queen avec un algorithme génétique (2)

La dernière fois a cherché l'une des solutions au problème N-Queen pour le cas de N = 8. Cette fois, nous l'étendrons à tout N.

politique

En gros, remplacez simplement 8 dans Dernière fois par n'importe quel N. Cette fois, écrivez un programme qui trouve une solution en spécifiant la valeur de N comme argument et en l'exécutant. Le nombre de gènes reste quatre. La dernière fois, la position de croisement a été fixée, mais cette fois elle est modifiée par N. Plus précisément, le N-4e et les éléments suivants sont remplacés, et le N-2e et les éléments suivants sont remplacés.

Résumé

Je vais le réveiller immédiatement dans le code source.

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)

A titre d'exemple, le résultat de l'exécution lorsque N = 16 est affiché.

$./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]

La convergence est lente. .. .. .. Il semble qu'il soit nécessaire de changer la méthode de croisement pour accélérer la convergence. À la fin, cela dépend de la chance de la mutation, il peut donc être nécessaire de réfléchir à une méthode de mutation appropriée. C'est un problème futur.

référence

AI pour la première fois à apprendre tout en utilisant Excel :: par Noboru Asai

Recommended Posts

Trouver une solution au problème N-Queen avec un algorithme génétique (2)
Trouver une solution au problème N-Queen avec un algorithme génétique (1)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (théorie)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (code Python)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)
Résolution du problème d'horaire des infirmières (optimisation des équipes) avec un algorithme génétique
Comment réparer la population initiale avec un algorithme génétique utilisant DEAP
Une histoire sur la façon de traiter le problème CORS
Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 2)
Je voulais résoudre le problème ABC164 A ~ D avec Python
Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 1)
Rechercher le labyrinthe avec l'algorithme python A *
J'ai essayé "Implémentation d'un algorithme génétique (GA) en python pour résoudre le problème du voyageur de commerce (TSP)"
Essayez de résoudre le problème du fizzbuzz avec Keras
Comment essayer l'algorithme des amis d'amis avec pyfof
Enregistrer l'objet dans un fichier avec pickle
Résolvez le problème du sac à dos Python avec l'algorithme glouton
Notez la solution car django n'a pas pu s'installer avec pip
Résolution du problème du voyageur de commerce avec l'algorithme génétique (GA) et sa bibliothèque (vcopt)
[Python] Solution au problème que les éléments sont liés lors de la copie d'une liste
Calculez la solution optimale pour établir un record du monde pour dix types de compétition avec scipy.optimize
Comment créer un sous-menu avec le plug-in [Blender]
Essayez de résoudre le problème d'affectation du médecin de formation avec Python
Transition vers l'écran de mise à jour avec le Django a tag
J'ai essayé de résoudre le problème avec Python Vol.1
Un mémo sur la façon de surmonter le problème difficile de la capture d'effets avec l'IA
Une solution au problème que les fichiers contenant [et] ne sont pas répertoriés dans glob.glob ()
Comment résoudre le problème de redémarrage du noyau lors de l'exécution du système PyQt avec jupyter ou Spyder IDE
Un exemple de python pour apprendre XOR avec un algorithme génétique sur un réseau neuronal
Probablement le moyen le plus simple de créer un pdf avec Python 3
[Python] Essayez d'optimiser les paramètres de systole FX avec un algorithme génétique
La première étape de la création d'une application sans serveur avec Zappa
J'ai essayé de résoudre le problème d'optimisation des combinaisons avec Qiskit
La façon habituelle d'ajouter un noyau avec Jupyter Notebook
Un mémo qui a résolu le problème du sac à dos par la méthode gourmande
Essayez de modéliser une distribution multimodale à l'aide de l'algorithme EM
Une personne qui veut résoudre le problème D avec ABC d'AtCoder a essayé de gratter
Une histoire dans laquelle l'algorithme est arrivé à une conclusion ridicule en essayant de résoudre correctement le problème du voyageur de commerce
Écrivez un programme pour résoudre le Rubik Cube 4x4x4! 2. Algorithme
[Introduction à Python] Comment fractionner une chaîne de caractères avec la fonction split
[Introduction à StyleGAN] J'ai joué avec "The Life of a Man" ♬
Comment faire une commande pour lire le fichier de paramètres avec pyramide
Essayez de résoudre le problème N Queen avec SA de PyQUBO
Résolution du labyrinthe avec Python-Supplément au chapitre 6 de la référence rapide de l'algorithme-
Erreur avec pip: un problème est survenu lors de la confirmation du certificat SSL
Écrivez un script pour calculer la distance avec le système Elasticsearch 5 sans douleur
Résolvez le problème du sac à dos Python avec la méthode de branche et liée
Résolvez les problèmes de somme partielle avec une recherche complète en Python
Comment envoyer une requête à l'API DMM (FANZA) avec python
Créer une API REST pour faire fonctionner dynamodb avec le Framework Django REST
PhytoMine-I a essayé d'obtenir les informations génétiques de la plante avec Python
Trouver les erreurs les plus simples avec OpenCV
(Apprentissage automatique) J'ai essayé de comprendre attentivement l'algorithme EM dans la distribution gaussienne mixte avec l'implémentation.
La somme de contrôle NVM n'est pas valide, une solution au problème que le LAN câblé d'Intel ne reconnaît pas sous Linux.
Je souhaite résoudre le problème de fuite de mémoire lors de la sortie d'un grand nombre d'images avec Matplotlib
Le 16ème problème d'écriture en temps réel hors ligne a été résolu avec Python
Un mémo pour utiliser simplement le capteur d'éclairement TSL2561 avec Raspberry Pi 2
Calculer l'itinéraire le plus court d'un graphe avec la méthode Dyxtra et Python