[von Rainer]

Hello everybody, i've just got registered here and i'm pleased to meet you.
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.

[Motoma]

Preface: I wrote a genetic algorithm for this problem from scratch to see if I encountered the same problem. I didn't, and this post is a result of my observations.

I think you will see a large improvement if you alter your fitness function to select the top performers. Cache this result. Iterate through these top performers and use them to create the next population. Be careful with your mutation function, you will need to make a deepcopy() if you are going to mutate a chromosome twice.

There is a careful balance to choosing your population size, too small and your algorithm will spend most of its time breeding, too large and it will spend most of its time on picking the top performers. My code solves an 18x18 it 5 quicker when I increase the population from 10 to 100.

You can realize a performance gain if you pre-seed the new generation with the top performers from the previous generation. My quickest solution comes from a main loop like this:

best_suited = alphas(genesis_population)
while fitness(best_suited[0]) != SPARTAN_SCORE:
    new_generation = []

    for chromo in best_suited:
        new_generation.append(chromo)
        new_generation.append(mutate(deepcopy(chromo)))

    best_suited = alphas(new_generation)

However, there is an increased potential when doing this that you will never solve the problem due to a local optima.

This post has been edited by Motoma: 10 February 2012 - 12:17 PM

[von Rainer]

Thank you very much for your reply. I'm thinking about it and i'll write you back as soon as my brain processes something worthy :E

[von Rainer]

Motoma, on 10 February 2012 - 12:15 PM, said:

I think you will see a large improvement if you alter your fitness function to select the top performers. Cache this result. Iterate through these top performers and use them to create the next population.

This is a good advice, but unfortunately i can't accept it. As you said at the bottom of your reply, a strategy like this has a high chance to get stuck in a local optimum. But genetic algorithms are methods of GLOBAL optimization, created with the purpose of avoiding such a problem. That's why in the random selection of the candidates for reproduction, the better individual's fitness value, the higher probability of being chosen, but there still have to be a chance for the less fitted individuals, to guarantee genetic variety.
The random selection function i posted within my code, was provided by Peter Norvig himself, author of the Artificial Intelligence book that my teacher took as a reference for his course. I think i just can rely to it
You gave me the idea of using a dictionary to save each child's fitness value once calculated after its birth, so the algorithm won't calculate again the same fitness values to select the candidates for reproduction. Now i'm trying to figure out how make this possible for the very first iteration, when no child is yet been generated.

Motoma, on 10 February 2012 - 12:15 PM, said:

There is a careful balance to choosing your population size, too small and your algorithm will spend most of its time breeding, too large and it will spend most of its time on picking the top performers. My code solves an 18x18 it 5 quicker when I increase the population from 10 to 100.

You're smart an article i read about said
"Initially, we ran our experiments with pool sizes usual in the case of classical GAs, and as N was increased, we increased the pool size as well in order to keep up with the increase of the search space, even if not in a proportional way. Afterwards we started to investigate the effect of the pool size on the performance of the crossover function. Interestingly, we found that the average number of generations needed to find a solution decreases as the pool size was increased up to 25, but increasing the pool size further had almost no effect. This can be explained on the basis of the reported analytical descriptions of the density of the solutions of the N-queens problem, indicating that the larger N is, the more likely it is that by consecutive repairs of an individual a solution can be gained."

Motoma, on 10 February 2012 - 12:15 PM, said:

You can realize a performance gain if you pre-seed the new generation with the top performers from the previous generation. My quickest solution comes from a main loop like this:

best_suited = alphas(genesis_population)
while fitness(best_suited[0]) != SPARTAN_SCORE:
    new_generation = []

    for chromo in best_suited:
        new_generation.append(chromo)
        new_generation.append(mutate(deepcopy(chromo)))

    best_suited = alphas(new_generation)

I'm sorry but i can't understand what you really mean. What do you mean with "pre-seed"? And, what is the purpose of the alphas function?

[von Rainer]

Thanks to your suggestion on using deepcopy() function to switch individual's genes, algorithm performances are way better. Nevertheless, it still fails on solving problems as dimension increases. I've used matplotlib to graphically see how average and maximum fitness values of new generations vary during the execution, and this is what i found out:



This plot is related to a 15x15 problem. As you can see, the population's goodness increases very rapidly in the first few generations, but then keeps fluctuating around a "sort of good" fitness value without increasing to reach the goal.

Do you see something i can't spot?


Here's the code if you want to browse it:

import random
import copy
import matplotlib.pyplot as plt

def random_selection(population, fitness_values):
	selection = None
	runningtotal = 0
	fitness_total = []
	for i in range(len(population)):
		runningtotal += fitness_values[i]
		fitness_total.append(runningtotal)
	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(1, 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)))
	averages = []
	maximums = []
	print "\nproblem dimension: ", len(random.choice(population)), "x", len(random.choice(population)) #NOTE
	print "population size: ", len(population) #NOTE
	print "max generations: ", n #NOTE
	print "fitness goal value: ", goal_fit
	print "\nrunning..." #NOTE
	fitness_values = {}
	for i in range(len(population)):
		fitness_values[i] = fitness_fn(population[i], goal_fit)
	while n > 0: 
		new_population = []
		new_fitness_values = {}
		a, m = info_fitness(fitness_values) #NOTE
		averages.append(a) #NOTE
		maximums.append(m) #NOTE
		for i in range(len(population)):
			x = random_selection(population, fitness_values)
			child = reproduce(x)
			if random.uniform(0,1) < 0.2:
				child = mutation(copy.deepcopy(child))
			child_fitness = fitness_fn(child, goal_fit)
			if child_fitness >= goal_fit:
				print "...done. \n\nresult ", child," found in ", nmax-n, " generations.\n" #NOTE
				plot(averages, maximums, goal_fit, nmax-n)
				return child
			new_fitness_values[i] = child_fitness
			new_population.append(child)
		population = new_population
		fitness_values = new_fitness_values
		n -= 1
	print "\nno solution found in ", nmax, " generations, try again.\n" #NOTE
	plot(averages, maximums, goal_fit, nmax)
	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



def info_fitness(d): #NOTE
	n = len(d)
	total = 0
	for i in range(n):
		total += d[i]
	a = total/n
	m = max(d.values())
	#print "avg :", a
	#print "max :", m
	return a, m	


def plot(averages, maximums, goal_fit, generations):
	plt.plot([goal_fit]*(generations+1), 'g-')
	plt.plot(averages, 'b-')
	plt.plot(maximums, 'r-')
	plt.axis([0, generations+1, goal_fit*0.5, goal_fit*1.2])
	plt.ylabel('avg (blue), max (red), goal (green)')
	plt.xlabel('generations')
	plt.show()

#---------------------------------------main---------------------------------------

n = 15
population = []
base = range(n)
for i in range(25):
	population.append(switch(5, copy.deepcopy(base)))
gen_alg(population, fitness_fn)

Thanks again for your advices.

[Motoma]

von Rainer, on 13 February 2012 - 04:57 AM, said:

The random selection function i posted within my code, was provided by Peter Norvig himself, author of the Artificial Intelligence book that my teacher took as a reference for his course. I think i just can rely to it

Did you copy it correctly? I made a minor modification to it to print the deltas between the fitness totals:

def random_selection(population, fitness_values):
        selection = None
        runningtotal = 0
        fitness_total = []
        for i in range(len(population)):
                runningtotal += fitness_values[i]
                fitness_total.append(runningtotal)
        prob = random.uniform(0, fitness_total[-1])

        weights = []
        for i in range(len(fitness_total)):
                if i == 0: weights.append(fitness_total[i])
                else: weights.append(fitness_total[i] - fitness_total[i-1])
        print weights

        for i in range(len(population)):
                if fitness_total[i] > prob:
                        return population[i]

The results seemed uniformly distributed, which wouldn't provide a very good fitness function:

...
[100, 98, 95, 93, 89, 92, 92, 91, 95, 98, 93, 97, 94, 98, 93, 97, 97, 98, 93, 94, 94, 95, 95, 96, 96]
[91, 91, 97, 97, 97, 98, 96, 96, 100, 91, 97, 99, 96, 94, 94, 100, 92, 98, 99, 89, 100, 98, 96, 97, 96]
[97, 96, 92, 99, 95, 97, 98, 99, 96, 98, 100, 97, 100, 102, 100, 94, 92, 95, 98, 94, 97, 95, 96, 89, 92]
...

I have a feeling that this fitness function is the main source of your problem here; with smaller boards, the influence of your random mutations can easily overcome this, however, as you problem size increases, the percentage of mutation is dwarfed by the fact your random_selection isn't weighted.

von Rainer, on 13 February 2012 - 04:57 AM, said:

Motoma, on 10 February 2012 - 12:15 PM, said:

You can realize a performance gain if you pre-seed the new generation with the top performers from the previous generation. My quickest solution comes from a main loop like this:

best_suited = alphas(genesis_population)
while fitness(best_suited[0]) != SPARTAN_SCORE:
    new_generation = []

    for chromo in best_suited:
        new_generation.append(chromo)
        new_generation.append(mutate(deepcopy(chromo)))

    best_suited = alphas(new_generation)

I'm sorry but i can't understand what you really mean. What do you mean with "pre-seed"? And, what is the purpose of the alphas function?

My alphas function returns the top 50% of the population. This code shows me keeping those in the next generations, repopulating the missing 50% with their offspring.

This post has been edited by Motoma: 13 February 2012 - 12:47 PM
Reason for edit:: Code was in terrible shape.

[von Rainer]

Motoma, on 13 February 2012 - 09:30 AM, said:

I have a feeling that this fitness function is the main source of your problem here; with smaller boards, the influence of your random mutations can easily overcome this, however, as you problem size increases, the percentage of mutation is dwarfed by the fact your random_selection isn't weighted.

I agree with you, but for the fact that the random_selection IS actually weighted

Here's the original function with the creator's comment

def random_weighted_selection(seq, n, weight_fn):
    """Pick n elements of seq, weighted according to weight_fn.
    That is, apply weight_fn to each element of seq, add up the total.
    Then choose an element e with probability weight[e]/total.
    Repeat n times, with replacement. """
    totals = []; runningtotal = 0
    for item in seq:
        runningtotal += weight_fn(item)
        totals.append(runningtotal)
    selections = []
    for s in range(n):
        r = random.uniform(0, totals[-1])
        for i in range(len(seq)):
            if totals[i] > r:
                selections.append(seq[i])
                break
    return selections

Notice it matches this explanation (from wikipedia):

Selection is the stage of a genetic algorithm in which individual genomes are chosen from a population for later breeding (recombination or crossover).
A generic selection procedure may be implemented as follows:

• The fitness function is evaluated for each individual, providing fitness values, which are then normalized. Normalization means dividing the fitness value of each individual by the sum of all fitness values, so that the sum of all resulting fitness values equals 1.
  
  
• The population is sorted by descending fitness values.
  
  
• Accumulated normalized fitness values are computed (the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals). The accumulated fitness of the last individual should be 1 (otherwise something went wrong in the normalization step).
  
  
• A random number R between 0 and 1 is chosen.
  
  
• The selected individual is the first one whose accumulated normalized value is greater than R.

The only difference is in the population sorting. I'm gonna try this variation.

Motoma, on 13 February 2012 - 09:30 AM, said:

My alphas function returns the top 50% of the population. This code shows me keeping those in the next generations, repopulating the missing 50% with their offspring.

Got it, thanks. It's a truncation selection


Now i'd say we could take a break. Thank you very much for your help.

What do you tell me about your performance evaluation? At a guess, what do you think could be a good execution time to solve the 10-50-100-1000 queens problem?

This post has been edited by Motoma: 15 February 2012 - 08:28 AM

[Motoma]

von Rainer, on 15 February 2012 - 10:13 AM, said:

I agree with you, but for the fact that the random_selection IS actually weighted

Then your weight function doesn't play well with your selection function. Correct me if I am wrong, but those deltas are pretty telling.

von Rainer, on 15 February 2012 - 10:13 AM, said:

What do you tell me about your performance evaluation? At a guess, what do you think could be a good execution time to solve the 10-50-100-1000 queens problem?

I can't give insight into "good" runtimes, but I can tell you my code's performance:
10: sub-second
50: 6 second median, range in 3-10 seconds.
100: 42 second median, range in 32-140 seconds.
1000: 45 minutes and counting...

[von Rainer]

Motoma, on 15 February 2012 - 09:25 AM, said:

von Rainer, on 15 February 2012 - 10:13 AM, said:

I agree with you, but for the fact that the random_selection IS actually weighted

Then your weight function doesn't play well with your selection function. Correct me if I am wrong, but those deltas are pretty telling.

Plausible. Actually i think the problem is in the reproduction: it's just too much random, so after a few generation when the population is refined to a good fitness value, finding a solution is nothing but a matter of luck, due to reproduction and random mutations. That's why sometimes the solution comes in about 500 generations, and sometimes 100000 generations are not enough.