Back to index

python-biopython  1.60
Diversity.py
Go to the documentation of this file.
00001 """Select individuals into a new population trying to maintain diversity.
00002 
00003 This selection mechanism seeks to try and get both high fitness levels
00004 and high diversity levels in the population.
00005 """
00006 # standard modules
00007 import random
00008 import math
00009 
00010 # biopython
00011 from Bio.Seq import MutableSeq
00012 
00013 # local modules
00014 from Abstract import AbstractSelection
00015 from Tournament import TournamentSelection
00016 
00017 class DiversitySelection(AbstractSelection):
00018     """Implement diversity selection.
00019 
00020     Diversity selection is performed by trying to select individuals
00021     from the population that aren't already in the new_population. A group
00022     of selected individuals is then subjected to selection using
00023     a passed selection routine.
00024 
00025     If new individuals can not be selected, new individuals will be
00026     randomly generated and inserted into the population.
00027     """
00028     def __init__(self, internal_selector, genome_generator):
00029         """Initialize a diversity selector.
00030 
00031         Arguments:
00032 
00033         o internal_selector - A selection object that will be used to select
00034         individuals based on fitness, perform crossover, mutation and repair.
00035 
00036         o genome_generator - A function that, when called, will return a
00037         genome to be used for a new organism. The genome returned must
00038         be a MutableSeq() object.
00039         """
00040         self._internal_selector = internal_selector
00041         self._genome_generator = genome_generator
00042 
00043         self.sub_pop_percent = .1
00044         self.random_tries = 10
00045 
00046     def _get_new_organism(self, new_pop, old_pop):
00047         """Get a new organism from old_pop that isn't in new_pop.
00048 
00049         This attempts to select an organism from old_pop that isn't in
00050         new_pop. If we can't do this in the number of tries specified
00051         by the class attribute random_tries, we generate a new random
00052         organism and return that.
00053         """
00054         # try to pick an organism that isn't in the population
00055         new_org = None
00056         num_tries = 0
00057         while new_org is None and num_tries < self.random_tries:
00058             chance_org = random.choice(old_pop)
00059 
00060             if chance_org not in new_pop:
00061                 new_org = chance_org
00062 
00063             num_tries += 1
00064 
00065         # if we don't get an organism, generate a random one
00066         if new_org is None:
00067             new_org = old_pop[0].copy()
00068             random_genome = self._genome_generator()
00069             new_org.genome = random_genome
00070             new_org.recalculate_fitness()
00071 
00072         return new_org
00073     
00074     def select(self, population):
00075         """Perform selection on the current population, encouraging diversity.
00076         """
00077         new_population = []
00078 
00079         while len(new_population) < len(population):
00080             # generate a sub population
00081             sub_pop_size = int(math.ceil(len(population) *
00082                                          self.sub_pop_percent))
00083             sub_pop = []
00084             for individual in range(sub_pop_size):
00085                 new_org = self._get_new_organism(new_population, population)
00086                 sub_pop.append(new_org)
00087 
00088             # put the new sub population through selection, mutation
00089             # and all of that good stuff
00090             new_sub_pop = self._internal_selector.select(sub_pop)
00091 
00092             new_population.extend(new_sub_pop)
00093 
00094         # return the new population, which should have the same number
00095         # of individuals we started with.
00096         return new_population[:len(population)]
00097             
00098