For this school year, I am taking a class called Honors Artificial Intelligence, and after finishing my current project, I decided to start posting about them.
The goal of this particular project is to solve the 8x8 queen's problem. Essentially you are given a chess board and you have to place 8 queens in a manner where none of them can attack each other. http://en.wikipedia.org/wiki/Eight_queens_puzzle
To accomplish this project, we have to use python and create a gui to use it.
To add some more fun to this project, I decided to use a genetic algorithm to solve this problem, as well as making it capable of handling NxN board size dimensions.
A genetic algorithm mimics life, where the fittest of them all survives:
http://en.wikipedia.org/wiki/Genetic_algorithm
The gist of this is basically a population is first generated, the fitness of each individual is calculates. The fittest mates with each other to form the next generation, mutations will also occur as the two individuals' "genes" are combined together.
Implementing this was interesting. What I basically have is a list of 8 numbers, the index representing the x coordinates, and then number at that index value representing the y coordinates of the queen. This represents the location of the 8 queens. A population of x is randomly generated, taking in to account the fact that queens cannot be in the same row or column. This increases the probability by quite a bit. Then the fitness of each individual is calculated by the number of queens that can attack each other. This means the lower the fitness, the better the solution, a fitness of 0 equating to the solution of the problem. Then all of the individuals mate with each other, except for the last individual, to form the next generation. To fill up the 2 empty spots, two more individuals are randomly generated to bring in diversity into the population. This is repeated until a solution is found.
Here is the code used! (PS, Tkinter is used for the GUI):
1: from Tkinter import *
2: from ttk import *
3: from random import choice, randint
4: import time
5: import queens
6: DEBUGGING = False
7: DELAY = 0
8: class window(Frame):
9: def __init__(self, parent):
10: self.rows = boardSize
11: self.columns = boardSize
12: self.size = squareSize
13: self.color1 = "white"
14: self.color2 = "black"
15: self.queens = []
16: self.pic = PhotoImage(file ="queen.gif")
17: canvas_width = self.columns * self.size
18: canvas_height = self.rows * self.size
19: Frame.__init__(self, parent)
20: self.canvas = Canvas(self, borderwidth=0, highlightthickness=0,
21: width=canvas_width, height=canvas_height, background="bisque")
22: self.canvas.pack(side="top", fill="both", expand=True, padx=2, pady=2)
23: self.parent = parent
24: self.initUI()
25: def initUI(self):
26: self.parent.title("Queens NxN Genetic Algorithm")
27: self.style = Style()
28: self.style.theme_use("default")
29: frame = Frame(self, relief=RAISED, borderwidth=1)
30: frame.pack(fill=BOTH, expand=1)
31: self.pack(fill=BOTH, expand=1)
32: quitButton = Button(self, text="QUIT", command=self.quit)
33: quitButton.pack(side=RIGHT, padx=10, pady=20)
34: findButton = Button(self, text="FIND", command=lambda : run(int(enterPopulation.get())))
35: findButton.pack(side=RIGHT, padx=10, pady=20)
36: enterPopulation = Entry(self)
37: enterPopulation.pack(side=RIGHT, padx=10)
38: scale = Scale(self, from_=0, to=100, command=self.onScale)
39: scale.pack(side=RIGHT, padx=10)
40: self.var = IntVar()
41: self.label = Label(self, text=0, textvariable=self.var)
42: self.label.pack(side=RIGHT)
43: color = self.color2
44: for row in range(self.rows):
45: color = self.color1 if color == self.color2 else self.color2
46: for col in range(self.columns):
47: x1 = (col * self.size)
48: y1 = (row * self.size)
49: x2 = x1 + self.size
50: y2 = y1 + self.size
51: self.canvas.create_rectangle(x1, y1, x2, y2, outline="black", fill=color, tags="square")
52: color = self.color1 if color == self.color2 else self.color2
53: def place(self, xcoord, ycoord):
54: x = (xcoord+1)*self.size
55: x -= (self.size/2)
56: y = (ycoord+1)*self.size
57: y -= (self.size/2)
58: self.queens.append(self.canvas.create_image(x, y, image = self.pic, anchor = CENTER))
59: def delete(self):
60: for queen in self.queens:
61: self.canvas.delete(queen)
62: self.queens = []
63: def add(self, individual):
64: self.delete()
65: for x in range(boardSize):
66: self.place(x, individual[x])
67: def onScale(self, val):
68: DELAY = int(float(val))
69: self.var.set(DELAY)
70: def main():
71: global boardSize
72: global squareSize
73: global app
74: squareSize = 64
75: boardSize = int(raw_input("input n for NxN grid \n"))
76: root = Tk()
77: root.geometry("%ix%i+%i+%i" % (boardSize*squareSize, boardSize*squareSize+68, root.winfo_screenwidth()/2-boardSize*squareSize/2, root.winfo_screenheight()/2-(boardSize*squareSize+68)/2))
78: root.resizable(0, 0)
79: app = window(root)
80: root.mainloop()
81: root.destroy()
82: def genetic1(population, fitness):
83: generations = 0
84: solution = []
85: while(not check(population)):
86: app.after(DELAY)
87: population = selection(population, fitness, generations)
88: temp = find(population, False)
89: print temp[0]
90: app.add(temp[0])
91: app.update()
92: generations += 1
93: temp = find(population, False)
94: solution = temp[0]
95: app.add(solution)
96: app.update()
97: return solution
98: def generate_population(size):
99: population = []
100: for i in range(size):
101: individual = outsider()
102: population.append(individual)
103: if DEBUGGING: print individual
104: return population
105: def outsider():
106: individual = []
107: options = range(boardSize)
108: for i in range(boardSize):
109: select = choice(options)
110: individual.append(select)
111: options.remove(select)
112: return individual
113: def check(population):
114: population = find(population, False)
115: if FITNESS_FN(population[0]) == 0:
116: if DEBUGGING:
117: print "FOUND"
118: print population[0]
119: return True
120: def find(population, debug):
121: temp = []
122: fitness_vals = dict()
123: index = 0
124: for i in population:
125: fitness_vals[index] = FITNESS_FN(i)
126: index+=1
127: fitness_vals_sorted = sorted(fitness_vals, key=fitness_vals.get, reverse = False)
128: if DEBUGGING and debug: print fitness_vals_sorted
129: for i in fitness_vals_sorted:
130: temp.append(population[i])
131: if DEBUGGING and debug: print population[i], fitness_vals[i]
132: return temp
133: def FITNESS_FN(individual):
134: fitness_val = 0
135: for i in range(boardSize):
136: if not individual.count(i) == 1:
137: fitness_val += individual.count(i)
138: for o in range(1, boardSize):
139: if abs(individual[i] - individual[o]) == abs(i - o) and not abs(i - o) == 0:
140: fitness_val += 1
141: return fitness_val
142: def mutate(individual, trigger):
143: individual[trigger] = randint(0, boardSize-1)
144: return individual
145: def reproduce(individualA, individualB, trigger):
146: combined = []
147: for i in range(trigger): combined.append(individualA[i])
148: for i in range(trigger, boardSize): combined.append(individualB[i])
149: return combined
150: def selection(population, fitness, generations):
151: temp = find(population, False)
152: population = []
153: for i in range(len(temp) - 2):
154: reproduced = reproduce(temp[i], temp[i+1], randint(2, boardSize-3))
155: mutated = mutate(reproduced, randint(0, boardSize-1))
156: population.append(mutated)
157: for i in range(2):
158: population.append(outsider())
159: population = find(population, True)
160: print "Generation: ", generations, "Smallest Fitness: ", FITNESS_FN(population[0])
161: return population
162: def size(population_size):
163: print "Population Size: ", population_size
164: time.sleep(1)
165: population = generate_population(population_size)
166: solution = genetic1(population, FITNESS_FN)
167: print "Found: ", solution
168: def run(*args):
169: size(args[0])
170: if __name__ == "__main__":
171: main()
No comments:
Post a Comment