Back to index

python-biopython  1.60
Public Member Functions | Private Member Functions | Private Attributes
test_GAQueens.QueensCrossover Class Reference

List of all members.

Public Member Functions

def __init__
def do_crossover

Private Member Functions

def _find_best_region

Private Attributes

 _crossover_prob
 _fitness_calc
 _max_crossover_size

Detailed Description

Crossover operation to help in solving the N-Queens problem.

This tries to perform smarter crossovers by picking out regions of
the genome that have high fitness.

It scans through both genomes in the crossover with a window half the
size of the genome, and finds the region with the highest fitness in
both genomes. It then recombines these high fitness windows to form
the new genome that is returned.

Definition at line 236 of file test_GAQueens.py.


Constructor & Destructor Documentation

def test_GAQueens.QueensCrossover.__init__ (   self,
  fitness_func,
  crossover_prob = .1,
  max_crossover_size = 4 
)
Initialize to do N-Queens optimized crossover.

Arguments:

o fitness_func -- A function that can calculate the fitness of
a genome.

o crossover_prob -- The probability of having a crossover
between two passed in organisms.

o max_crossover_size -- The maximum crossover size of the 'best' region
to search for.

Definition at line 248 of file test_GAQueens.py.

00248 
00249                  max_crossover_size = 4):
00250         """Initialize to do N-Queens optimized crossover.
00251 
00252         Arguments:
00253 
00254         o fitness_func -- A function that can calculate the fitness of
00255         a genome.
00256 
00257         o crossover_prob -- The probability of having a crossover
00258         between two passed in organisms.
00259 
00260         o max_crossover_size -- The maximum crossover size of the 'best' region
00261         to search for.
00262         """
00263         self._crossover_prob = crossover_prob
00264         self._fitness_calc = fitness_func
00265         self._max_crossover_size = max_crossover_size


Member Function Documentation

def test_GAQueens.QueensCrossover._find_best_region (   self,
  genome,
  make_best_larger = 1 
) [private]
Find the best region in the given genome.

Arguments:

o genome -- A MutableSeq object specifying the genome of an organism

o make_best_larger -- A flag to determine whether the best region
we should search for should be the larger region of the split
caused by crossover or the smaller region. This makes it easy
to split two genomes, recombine them, and get a solution that
makes sense.

Returns:
o Two MutableSeq objects. They are both half of the size of the passed
genome. The first is the highest fitness region of the genome and the
second is the rest of the genome.

Definition at line 289 of file test_GAQueens.py.

00289 
00290     def _find_best_region(self, genome, make_best_larger = 1):
00291         """Find the best region in the given genome.
00292 
00293         Arguments:
00294 
00295         o genome -- A MutableSeq object specifying the genome of an organism
00296 
00297         o make_best_larger -- A flag to determine whether the best region
00298         we should search for should be the larger region of the split
00299         caused by crossover or the smaller region. This makes it easy
00300         to split two genomes, recombine them, and get a solution that
00301         makes sense.
00302 
00303         Returns:
00304         o Two MutableSeq objects. They are both half of the size of the passed
00305         genome. The first is the highest fitness region of the genome and the
00306         second is the rest of the genome.
00307         """
00308         first_region = max(len(genome) / 2, self._max_crossover_size)
00309         second_region = len(genome) - first_region
00310         
00311         if make_best_larger:
00312             region_size = max(first_region, second_region)
00313         else:
00314             region_size = min(first_region, second_region)
00315 
00316         # loop through all of the segments and find the best fitness segment
00317         
00318         # represent best_fitness as a three tuple with the coordinates of
00319         # the start and end as the first two elements, and the fitness of
00320         # the region as the last element. Start with a value that
00321         # will overridden right away
00322         best_fitness = [0, 0, -1]
00323         for start_index in range(len(genome) - region_size):
00324             region_fitness = \
00325              self._fitness_calc(genome[start_index: start_index + region_size])
00326 
00327             if region_fitness > best_fitness[2]:
00328                 best_fitness = [start_index, start_index + region_size,
00329                                 region_fitness]
00330 
00331         # get the the two regions and return 'em
00332         best_region = genome[best_fitness[0]:best_fitness[1]]
00333         rest_region = genome[0:best_fitness[0]] + genome[best_fitness[1]:]
00334 
00335         return best_region, rest_region
00336             

Here is the caller graph for this function:

def test_GAQueens.QueensCrossover.do_crossover (   self,
  org_1,
  org_2 
)
Perform a crossover between two organisms.

Definition at line 266 of file test_GAQueens.py.

00266 
00267     def do_crossover(self, org_1, org_2):
00268         """Perform a crossover between two organisms.
00269         """
00270         new_org_1 = org_1.copy()
00271         new_org_2 = org_2.copy()
00272         
00273         # determine if we have a crossover
00274         crossover_chance = random.random()
00275         if crossover_chance <= self._crossover_prob:
00276             # find the region of highest probability in both orgs
00277             best_1, rest_1 = self._find_best_region(new_org_1.genome,
00278                                                     make_best_larger = 1)
00279             best_2, rest_2 = self._find_best_region(new_org_2.genome,
00280                                                     make_best_larger = 0)
00281 
00282             assert len(best_1) + len(best_2) == len(rest_1) + len(rest_2), \
00283                    "Did not preserve genome length!"
00284             
00285             new_org_1.genome = best_1 + best_2
00286             new_org_2.genome = rest_1 + rest_2
00287 
00288         return new_org_1, new_org_2

Here is the call graph for this function:


Member Data Documentation

Definition at line 262 of file test_GAQueens.py.

Definition at line 263 of file test_GAQueens.py.

Definition at line 264 of file test_GAQueens.py.


The documentation for this class was generated from the following file: