Ich beschloss, das N-Queen-Problem zu lösen (eine der Lösungen zu finden), um genetische Algorithmen zu untersuchen. Jede Programmiersprache war in Ordnung, aber ich habe mich für Python entschieden, weil es einfach zu schreiben ist.

N-Queen Problem

Das Problem, ein Muster zu finden, das N Schachköniginnen auf das NxN-Brett legt, damit sie nicht miteinander in Konflikt stehen. Queen kann sich ohne Einschränkungen vertikal, horizontal und naname bewegen. Ich wünschte wirklich, ich könnte alle Lösungen finden, aber dieses Mal werde ich versuchen, eine davon mithilfe eines genetischen Algorithmus zu finden. Um das Problem zu vereinfachen, betrachten Sie zuerst den Fall von N = 8 und versuchen Sie dann, ein beliebiges N aufzunehmen.

Anwendung genetischer Algorithmen

Definition von Genen

Zunächst einmal, wie man ein Gen darstellt. Es muss in der Lage sein, die endgültige Lösung auszudrücken. Daher wird ein Vektor erster Ordnung, der die Position der Königin auf dem Brett darstellt, als Gen angenommen. Die Queen-Position in jeder Spalte wird durch 0-7 dargestellt. Zum Beispiel. [0, 2, 3, 1, 4, 3, 6, 7] Bereiten Sie darauf basierend das ursprüngliche Gen vor. Dieses Mal werden wir vier verwenden. Jedes Element des Vektors wählt zufällig 0-7 aus.

`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

Anpassungsfähigkeit

Anpassungsfähigkeit ist ein Indikator dafür, wie nahe ein Gen an einem Ziel ist. Dieses Mal wird bei der Anordnung eines bestimmten Gens = Königin auf dem Brett die Anzahl der miteinander konkurrierenden Königinnen als Grad der Anpassungsfähigkeit genommen. Daher kann die endgültige Lösung gefunden werden, wenn die Anpassungsfähigkeit = 0 ist. Die Anpassungsfähigkeit wird berechnet, indem ein Quadrat in acht Richtungen von der Position einer Königin aus gesucht wird. Wenn eine andere Königin gefunden wird, wird die Anpassungsfähigkeit um +1 erhöht.

`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

Ein Beispiel für das Berechnungsergebnis ist unten dargestellt. [0, 1, 2, 3, 4, 5, 6, 7] => fitness = 56

Genetik

Beispielsweise werden die folgenden vier Gene als Eltern verwendet, um Kindergene zu erzeugen. 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

In aufsteigender Reihenfolge der Anpassungsfähigkeit anordnen. Der Rang ist Rang = 0 bis 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

Lassen Sie zuerst die ausgezeichneten Gene. Ersetzt das Gen mit der höchsten Anpassungsfähigkeit durch das Gen mit der niedrigsten Anpassungsfähigkeit. In diesem Fall überschreiben Sie den Wert von G0 mit dem Wert von 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]

Als nächstes überqueren. Crossover ist ein Verfahren zum Erzeugen eines Kindergens aus einem Elterngen. Dieses Mal werden wir eine einfache Frequenzweiche betrachten. Ersetzen Sie zunächst das k-te und die nachfolgenden Elemente des Gens rank = 0 und des Gens rank = 1. Dieses Mal werde ich die Elemente nach k = 5 ersetzen. G2' = [0, 2, 4, 6, 2, 2, 3, 3] G1' = [0, 0, 1, 1, 7, 5, 3, 1] Ersetzen Sie als nächstes das m-te und die nachfolgenden Elemente des Gens rank = 2 und des Gens rank = 3. Dieses Mal werde ich die Elemente nach m = 7 ersetzen. G3' = [1, 3, 5, 7, 0, 1, 3, 1] G0'' = [0, 2, 4, 6, 7, 5, 2, 3]

Aus dem Obigen haben die Nachkommen die folgenden vier Gene. 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]

Der Quellcode des genetischen Teils lautet wie folgt. gene_list ist eine Liste der elterlichen Gene. rank_list speichert den Index von gene_list in seinem Element mit seinem Index als Rang. Mit anderen Worten, im Fall dieses Beispiels ist das Bild 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

Durch Wiederholen des genetischen Verfahrens (Crossover) werden wir versuchen, hervorragende Gene zu hinterlassen. Wiederholte Überkreuzungen können jedoch zu lokalen Lösungen führen. Um ein Beispiel für eine lokale Lösung des 8-Queen-Problems zu geben, Anpassungsfähigkeit = 2, dh das verbleibende Queens-Paar kann in einem Zustand des Wettbewerbs miteinander stecken bleiben. Um diesen Zustand zu überwinden, ist eine Mutation erforderlich. Dieses Mal werde ich einfach alle vier genetischen Verfahren ein Element eines Gens durch einen Zufallswert von 0 bis 7 ersetzen.

`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

Zusammenfassung

Fügen Sie das Obige im Quellcode zusammen.

`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)

Bei der Ausführung wird die Anpassungsfähigkeit angezeigt, und wenn eine Lösung gefunden wird (Anpassungsfähigkeit = 0), werden die Anzahl der Schleifen und die Position der Königin auf dem Brett angezeigt.

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

Nächstes Mal wird versuchen, sich von N = 8 auf ein beliebiges N zu erstrecken.

[PYTHON] Suche nach einer Lösung für das N-Queen-Problem mit einem genetischen Algorithmus (1)

N-Queen Problem

Anwendung genetischer Algorithmen

Definition von Genen

python

Anpassungsfähigkeit

python

Genetik

python

Mutation

python

Zusammenfassung

8-queen.py

`python`

`python`

`python`

`python`

`8-queen.py`