Back to index

python-biopython  1.60
Tournament.py
Go to the documentation of this file.
00001 """Provide Tournament style selection.
00002 
00003 This implements selection based on a tournament style. In this model of
00004 selection, two individuals are randomly chosen from the population, and
00005 the organism with the higher fitness is considered the 'winner' and moves
00006 to the next generation.
00007 """
00008 # standard modules
00009 import random
00010 
00011 # local modules
00012 from Abstract import AbstractSelection
00013 
00014 class TournamentSelection(AbstractSelection):
00015     """Implement tournament style selection.
00016     """
00017     def __init__(self, mutator, crossover, repairer, num_competitors = 2):
00018         """Initialize the tournament selector.
00019 
00020         Arguments:
00021 
00022         o num_competitors-- The number of individiuals that should be
00023         involved in a selection round. By default we just have two
00024         individuals (head to head!).
00025 
00026         See AbstractSelection for a description of the arguments to
00027         the initializer.
00028         """
00029         AbstractSelection.__init__(self, mutator, crossover, repairer)
00030 
00031         if num_competitors < 2:
00032             raise ValueError("Must have at least 2 competitors!")
00033         
00034         self._num_competitors = num_competitors
00035 
00036     def select(self, population):
00037         """Perform selection on the population using the Tournament model.
00038 
00039         Arguments:
00040 
00041         o population -- A population of organisms on which we will perform
00042         selection. The individuals are assumed to have fitness values which
00043         are due to their current genome (ie. the fitness is up to date).
00044         """
00045         # we want to create a new population of the same size as the original
00046         new_population = []
00047 
00048         while len(new_population) < len(population):
00049             # select two individuals using tournament selection
00050             new_orgs = []
00051             # select for two individuals
00052             for round_num in range(2):
00053                 competitors = []
00054                 while len(competitors) < self._num_competitors:
00055                     new_org = random.choice(population)
00056                     if new_org not in competitors:
00057                         competitors.append(new_org)
00058                                     
00059                 # sort the competitors by fitness, this will put them
00060                 # from lowest to highest
00061                 competitors.sort(key = lambda org: org.fitness)
00062 
00063                 # get the best organism
00064                 new_orgs.append(competitors[-1])
00065 
00066             assert len(new_orgs) == 2, "Expected two organisms to be selected"
00067 
00068             # do mutation and crossover to get the new organisms
00069             new_org_1, new_org_2 = self.mutate_and_crossover(new_orgs[0],
00070                                                              new_orgs[1])
00071 
00072             new_population.extend([new_org_1, new_org_2])
00073 
00074         return new_population
00075