Do you know the N-Queens problem? Its target is to put N queens on a NxN chessboard in such a way that doesn't exists a couple of queens attacking each other. I'm a student of computer engineering, and a teacher assigned me the task of solving this problem writing a genetic algorithm in python. I wrote this code, and it actually works fine for a low number (N < 12) of queens, but increasing that number (even if just a little, from 12 to 14 for example) my script takes too much time to return me a solution.
I'm going to post and comment my code, but first i'm going to say something about the genetic algorithm strategy, for those who don't know it:
A genetic algorithm takes inspiration from biology and evolution theory. It starts with a population of individuals, evaluates every individual "goodness" with a fitness function. Then, one or more individual are selected for reproduction according to their fitness values (best individuals have a higher probability to get chosen), and a child is generated by them. This child, with a certain probability, can also be subjected to genetic mutations. Once this is done, this child is evaluated with the fitness function. If it is fit enough, it can be accepted as a solution and returned from the algorithm; else, it will become an element of a new population, and so on.
You can see everything explained above in the code i'm going to post. Note that
a) every individual is a list of numbers from 0 to N-1. The i-th number represents the row position of the queen in the i-th column. Hence, the population is a list of lists.
i'm using a good heuristic according to which there cannot be 2 queens on the same row. Hence, every individual is a different permutation of che [0, ..., N-1] list.
c) the reproduction is asexual, and just switches some columns of the parent
d) the fitness function counts how many queens are in the same right diagonal of each queen.
e) i don't think anything else, so please ask me if you have anymore doubts :E
Here is the code:
import random import sys def random_selection(population, fitness_fn, goal_fit): selection = None current_amount = 0 fitness_total =  selection =  for i in range(len(population)): current_amount += fitness_fn(population[i], goal_fit) fitness_total.append(current_amount) prob = random.uniform(0, fitness_total[-1]) for i in range(len(population)): if fitness_total[i] > prob: return population[i] def mutation(child): return switch(1, child) def reproduce(x): return switch(2, x) def compute_goal_fit(n): goal_fit = 0 for i in range(n): goal_fit += i return goal_fit def switch(n, target): for i in range(n): j = random.randint(0, len(target)-1) k = random.randint(0, len(target)-1) target[j], target[k] = target[k], target[j] return target def gen_alg(population, fitness): nmax = 100000 n = nmax goal_fit = compute_goal_fit(len(random.choice(population))) print "\nproblem dimension: ", len(random.choice(population)), "x", len(random.choice(population)) #FIXME print "population size: ", len(population) #FIXME print "max generations: ", n #FIXME print "\nrunning..." #FIXME while n > 0: new_population =  for i in range(len(population)): x = random_selection(population, fitness_fn, goal_fit) child = reproduce(x) if random.uniform(0,1) < 1.0: child = mutation(child) if fitness(child, goal_fit) >= goal_fit: print "...done. \n\nresult ", child," found in ", nmax-n, " generations.\n" #FIXME return child new_population.append(child) population = new_population n -= 1 print "\nno solution found in ", nmax, " generations, try again.\n" #FIXME return None def fitness_fn(individual, goal_fit): fitness_value = goal_fit for i in range(len(individual)): j = 1 while j < len(individual)-i: if (individual[i] == individual[i+j]+j) or (individual[i] == individual[i+j]-j): fitness_value -= 1 j += 1 return fitness_value #---------------------------------------main--------------------------------------- n = 14 population =  base = range(n) for i in range(10): population.append(switch(5, base)) gen_alg(population, fitness_fn)
p.s. i know this code is written roughly, please don't get mad at me... my main trouble is to reduce complexity as best as it is possible, then i will make everything more elegant :E
Thank you all for the patience.