Back to index

python-biopython  1.60
Classes | Functions | Variables
test_GAQueens Namespace Reference

Classes

class  QueensAlphabet
class  QueensRepair
class  QueensCrossover
class  QueensMutation

Functions

def main
def display_board
def queens_solved
def queens_fitness

Variables

int VERBOSE = 0
int num_queens = 5

Function Documentation

def test_GAQueens.display_board (   genome)
Display a genome in the N-queens problem.

Inspired by the display function in the queens.py solution to the N-queens
problem in the Python demo scripts.

Definition at line 78 of file test_GAQueens.py.

00078 
00079 def display_board(genome):
00080     """Display a genome in the N-queens problem.
00081 
00082     Inspired by the display function in the queens.py solution to the N-queens
00083     problem in the Python demo scripts.
00084     """
00085     print '+-' + '--'*len(genome) + '+'
00086 
00087     for row in range(len(genome)):
00088         print '|',
00089         for genome_item in genome:
00090             if genome_item == row:
00091                 print 'Q',
00092             else:
00093                 print '.',
00094         print '|'
00095 
00096     print '+-' + '--'*len(genome) + '+'

Here is the caller graph for this function:

def test_GAQueens.main (   num_queens)

Definition at line 40 of file test_GAQueens.py.

00040 
00041 def main(num_queens):
00042 
00043     print "Calculating for %s queens..." % num_queens
00044 
00045     num_orgs = 1000
00046     print "Generating an initial population of %s organisms..." % num_orgs
00047     queen_alphabet = QueensAlphabet(num_queens)
00048 
00049     start_population = Organism.random_population(queen_alphabet, num_queens,
00050                                                   num_orgs, queens_fitness)
00051 
00052     print "Evolving the population and searching for a solution..."
00053 
00054     mutator = QueensMutation(mutation_rate = 0.05)
00055     crossover = QueensCrossover(queens_fitness, crossover_prob = .2,
00056                                 max_crossover_size = 4)
00057     repair = QueensRepair()
00058     # rw_selector = RouletteWheelSelection(mutator, crossover, repair)
00059     t_selector = TournamentSelection(mutator, crossover, repair, 5)
00060 
00061     start_time = time.ctime(time.time())
00062     evolver = GenerationEvolver(start_population, t_selector)
00063     evolved_pop = evolver.evolve(queens_solved)
00064     end_time = time.ctime(time.time())
00065 
00066     unique_solutions = []
00067     for organism in evolved_pop:
00068         if organism.fitness == num_queens:
00069             if organism not in unique_solutions:
00070                 unique_solutions.append(organism)
00071 
00072     if VERBOSE:
00073         print "Search started at %s and ended at %s" % (start_time, end_time)
00074         for organism in unique_solutions:
00075             print "We did it!", organism
00076             display_board(organism.genome)
00077         

Here is the call graph for this function:

def test_GAQueens.queens_fitness (   genome)
Calculate the fitness of an organization of queens on the chessboard.

Arguments:

o genome -- A MutableSeq object specifying an organism genome.

The number returned is the number of unattacked queens on the board.

Definition at line 111 of file test_GAQueens.py.

00111 
00112 def queens_fitness(genome):
00113     """Calculate the fitness of an organization of queens on the chessboard.
00114 
00115     Arguments:
00116 
00117     o genome -- A MutableSeq object specifying an organism genome.
00118 
00119     The number returned is the number of unattacked queens on the board.
00120     """
00121     fitness = 0
00122 
00123     # check each queen on the board
00124     for check_queen_col in range(len(genome)):
00125         is_attacked = 0
00126         # check against all other queens on the board
00127         for other_queen_col in range(len(genome)):
00128             # only check a queen if it isn't exactly the same queen
00129             if check_queen_col != other_queen_col:
00130                 # get the row for the two queens we are comparing
00131                 check_queen_row = int(genome[check_queen_col])
00132                 other_queen_row = int(genome[other_queen_col])
00133                 
00134                 # a queen is attacked if it is in a row with another queen
00135                 if check_queen_row == other_queen_row:
00136                     is_attacked = 1
00137                     break
00138                 # or it is attacked if it is diaganol to another queen
00139                 elif (abs(check_queen_row - other_queen_row) ==
00140                       abs(check_queen_col - other_queen_col)):
00141                     is_attacked = 1
00142                     break
00143 
00144         if not(is_attacked):
00145             fitness += 1
00146 
00147     return fitness

def test_GAQueens.queens_solved (   organisms)
Determine if we have solved the problem.

We just search through the population for an organism that has a
fitness that is equal to the number of queens in the population.
If so, we have a solution, otherwise we need to keep looking.

Definition at line 97 of file test_GAQueens.py.

00097 
00098 def queens_solved(organisms):
00099     """Determine if we have solved the problem.
00100 
00101     We just search through the population for an organism that has a
00102     fitness that is equal to the number of queens in the population.
00103     If so, we have a solution, otherwise we need to keep looking.
00104     """
00105     for org in organisms:
00106         if org.fitness == len(org.genome):
00107             return 1
00108 
00109     # if we got here we didn't do it
00110     return 0
     

Variable Documentation

Definition at line 384 of file test_GAQueens.py.

Definition at line 37 of file test_GAQueens.py.