[PYTHON] Trouver une solution au problème N-Queen avec un algorithme génétique (1)
J'ai décidé de résoudre le problème N-Queen (trouver l'une des solutions) comme point de départ pour étudier les algorithmes génétiques. Tout langage de programmation allait bien, mais j'ai décidé d'utiliser python car il est facile à écrire.
Problème N-Queen
Le problème de trouver un modèle qui place N reines d'échecs sur le plateau NxN afin qu'elles ne soient pas en conflit les unes avec les autres. Queen peut se déplacer verticalement, horizontalement et naname sans aucune restriction. J'aimerais vraiment pouvoir trouver toutes les solutions, mais cette fois je vais essayer d'en trouver une en utilisant un algorithme génétique. Pour simplifier le problème, considérons d'abord le cas de N = 8, puis essayez d'accommoder tout N.
Application d'algorithmes génétiques
Définition des gènes
Tout d'abord, comment représenter un gène. Il doit pouvoir exprimer la solution finale.
Par conséquent, un vecteur de premier ordre représentant la position de la reine sur le plateau est adopté comme gène.
La position de la reine dans chaque colonne est représentée par 0-7. Par exemple.
[0, 2, 3, 1, 4, 3, 6, 7]
Sur cette base, préparez le gène initial. Cette fois, nous en utiliserons quatre. Chaque élément du vecteur sélectionne au hasard 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
Adaptabilité
L'adaptabilité est un indicateur de la proximité d'un gène avec une cible. Cette fois, dans l'arrangement d'un certain gène = Reine sur le plateau, le nombre de reines en compétition les unes avec les autres est considéré comme le degré d'adaptabilité. Par conséquent, la solution finale peut être trouvée lorsque l'adaptabilité = 0. L'adaptabilité est calculée en recherchant un carré dans huit directions à partir de la position d'une reine, et lorsqu'une autre reine est trouvée, l'adaptabilité est incrémentée de +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
Un exemple du résultat du calcul est présenté ci-dessous. [0, 1, 2, 3, 4, 5, 6, 7] => fitness = 56
La génétique
À titre d'exemple, les quatre gènes suivants sont utilisés comme parents pour générer des gènes enfants. 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
Disposez par ordre croissant d'adaptabilité. Le rang est le rang = 0 à 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
Laissez d'abord les excellents gènes. Remplace le gène avec la plus grande adaptabilité par le gène avec la plus faible adaptabilité. Dans ce cas, remplacez la valeur de G0 par la valeur de 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]
Ensuite, traversez. Le crossover est une procédure pour générer un gène enfant à partir d'un gène parent. Cette fois, nous considérerons un simple crossover. Tout d'abord, remplacez le k-ème et les éléments suivants du gène rank = 0 et le gène rank = 1. Cette fois, je remplacerai les éléments après k = 5e. G2' = [0, 2, 4, 6, 2, 2, 3, 3] G1' = [0, 0, 1, 1, 7, 5, 3, 1] Ensuite, remplacez le m-ème et les éléments suivants du gène rank = 2 et le gène rank = 3. Cette fois, je remplacerai les éléments après m = 7. G3' = [1, 3, 5, 7, 0, 1, 3, 1] G0'' = [0, 2, 4, 6, 7, 5, 2, 3]
D'après ce qui précède, la progéniture a les quatre gènes suivants. 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]
Le code source de la partie génétique est le suivant. gene_list est une liste de gènes parentaux. rank_list stocke l'index de gene_list dans son élément avec son index comme rang. En d'autres termes, dans le cas de cet exemple, l'image est 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
En répétant la procédure génétique (crossover), nous essaierons de laisser d'excellents gènes. Cependant, la répétition des croisements peut conduire à des solutions locales. Pour donner un exemple de solution locale au problème des 8-Queen, adaptabilité = 2, c'est-à-dire que la paire de reines restante peut être bloquée dans un état de concurrence les unes avec les autres. Pour surmonter cette situation, il est nécessaire de faire une mutation. Cette fois, je remplacerai simplement un élément d'un gène par une valeur aléatoire de 0 à 7 toutes les quatre procédures génétiques.
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
Résumé
Mettez ce qui précède dans le code source.
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)
Lorsqu'elle est exécutée, l'adaptabilité est affichée, et lorsqu'une solution est trouvée (adaptivité = 0), le nombre de boucles et la position de Queen sur le plateau sont affichés.
$ ./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]
La prochaine fois essaiera d'étendre de N = 8 à n'importe quel N.
Recommended Posts