-
Notifications
You must be signed in to change notification settings - Fork 0
/
nQueensGA.py
123 lines (105 loc) · 5.01 KB
/
nQueensGA.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
__author__ = 'rsimpson'
import random
from geneticAlgorithm import *
# The number of chromosomes in each generation
POPULATION_SIZE = 10
# This value is used to determine the size of the board when doing an n-queens problem
GRIDSIZE = 5
# This is a list of lists - where each sub-list contains the indices that are in the
# same column.
NQUEENS_COLUMNS = []
# This is a list of lists - where each sub-list contains the indices that are in the
# same diagonal.
NQUEENS_DIAGONALS = []
def createNQueensGlobals():
# get access to global variables
global GRIDSIZE
global NQUEENS_COLUMNS
global NQUEENS_DIAGONALS
# each list within this list will contain all the indexes for
# a single column of the board
NQUEENS_COLUMNS = []
# loop through all the columns in the board
for col in range(0, GRIDSIZE):
# each column has gridSize elements, each separated by gridSize items
NQUEENS_COLUMNS.append(range(col, GRIDSIZE*GRIDSIZE, GRIDSIZE))
# each list within this list contains all the indexes for
# a single diagonal on the board
NQUEENS_DIAGONALS = []
for index in range(0, GRIDSIZE):
# diagonals starting in upper left corner and going to middle of grid
NQUEENS_DIAGONALS.append(range(index, index * GRIDSIZE + 1, GRIDSIZE - 1))
# diagonals starting in upper right corner and going to lower right corner
NQUEENS_DIAGONALS.append(range((index+1) * GRIDSIZE - 1, GRIDSIZE * GRIDSIZE - 1, GRIDSIZE - 1))
# diagonals starting in upper left corner and going to upper right corner
NQUEENS_DIAGONALS.append(range(index, GRIDSIZE * (GRIDSIZE - index), GRIDSIZE + 1))
# diagonals starting in upper left corner and going to lower left corner
NQUEENS_DIAGONALS.append(range(index * GRIDSIZE, GRIDSIZE * GRIDSIZE, GRIDSIZE + 1))
class NQueensGene(Gene):
'''
Each gene represents a state. The value for each gene is the column (within a row) where the queen is positioned.
'''
def __init__(self, _row):
# domain for each gene is the set of grid cells within the row represented by the gene
# if GRIDSIZE = 5, we have a 5x5 grid, and rows are 0..4, 5..9, 10..14, 15..19, 20..24
domain = range(_row * GRIDSIZE, _row * GRIDSIZE + GRIDSIZE)
# call the parent constructor
Gene.__init__(self, str(_row), domain)
class NQueensChromosome(Chromosome):
'''
A chromosome is a location assignment for each building. The chromosome stores a list of gene objects in
self.genes
'''
def __init__(self):
# create a gene object for each row in the grid
# start with an empty list for the genes...
lstGenes = []
# for each state name...
for row in range(0, GRIDSIZE):
# create a new gene object and add it to the list of genes
lstGenes.append(NQueensGene(row))
# call the parent constructor with a list of gene objects
Chromosome.__init__(self, lstGenes)
def countViolations(self, gene0, gene1):
"""
returns true if constraint is satisfied and false if it is not
"""
global NQUEENS_DIAGONALS, NQUEENS_COLUMNS
# start accumulator at zero
violationCount = 0
# loop through the list of column lists
for columnList in NQUEENS_COLUMNS:
# if both genes are assigned and in the same column
if ((gene0.value in columnList) and (gene1.value in columnList)):
# then increment the violation count
violationCount += 1
# loop through the list of diagonal lists
for diagonalList in NQUEENS_DIAGONALS:
# if both features are in the same diagonal
if ((gene0.value in diagonalList) and (gene1.value in diagonalList)):
# then increment the violation count
violationCount += 1
# return the square of the number of violation counts
# (to create more separation between fitness scores)
return violationCount * violationCount
def fitness(self):
"""
Calculate the 'fitness' of each chromosome, which represents how
close the chromosome is to a valid solution
"""
# start accumulator at zero
fitness = 0
# check whether the queen represented by this gene
for gene1 in range(0, len(self.genes)-1):
# violates any constraints with the queen represented by all the other genes
for gene2 in range(gene1 + 1, len(self.genes)):
# add up the number of constraint violations
fitness += self.countViolations(self.genes[gene1], self.genes[gene2])
# return the total fitness
return fitness
class NQueensPopulation(Population):
def __init__(self, _populationSize, _chromosomeClass):
# call the parent constructor and pass it a chromosome object to use as a template
Population.__init__(self, _populationSize, _chromosomeClass)
createNQueensGlobals()
geneticAlgorithm(NQueensPopulation(POPULATION_SIZE, NQueensChromosome))