Back to index

python-biopython  1.60
test_GACrossover.py
Go to the documentation of this file.
00001 #!/usr/bin/env python
00002 """Tests different Genetic Algorithm crossover classes.
00003 """
00004 # standard library
00005 import unittest
00006 
00007 # biopython
00008 from Bio.Seq import MutableSeq
00009 from Bio.Alphabet import SingleLetterAlphabet
00010 
00011 # local stuff
00012 from Bio.GA.Organism import Organism
00013 from Bio.GA.Crossover.General import SafeFitnessCrossover
00014 from Bio.GA.Crossover.GeneralPoint import GeneralPointCrossover
00015 from Bio.GA.Crossover.GeneralPoint import InterleaveCrossover
00016 from Bio.GA.Crossover.TwoPoint import TwoPointCrossover
00017 from Bio.GA.Crossover.Point import SinglePointCrossover
00018 from Bio.GA.Crossover.Uniform import UniformCrossover
00019 
00020 
00021 class TestAlphabet(SingleLetterAlphabet):
00022     """Simple test alphabet.
00023     """
00024     letters = ["1", "2", "3"]
00025 
00026     def contains(self, oalpha):
00027         return True
00028 
00029 def test_fitness(genome):
00030     """Simple class for calculating fitnesses.
00031     """
00032     seq_genome = genome.toseq()
00033     return int(seq_genome.tostring())
00034 
00035 class SinglePointTest(unittest.TestCase):
00036     """Test simple point crossovers.
00037     """
00038     def setUp(self):
00039         self.alphabet = TestAlphabet()
00040         genome_1 = MutableSeq("11111", self.alphabet)
00041         self.org_1 = Organism(genome_1, test_fitness)
00042 
00043         genome_2 = MutableSeq("22222", self.alphabet)
00044         self.org_2 = Organism(genome_2, test_fitness)
00045         
00046         self.crossover  = SinglePointCrossover(1.0)
00047 
00048     def test_basic_crossover(self):
00049         """Test basic point crossover functionality.
00050         """
00051         start_genome_1 = self.org_1.genome[:]
00052         start_genome_2 = self.org_2.genome[:]
00053         
00054         new_org_1, new_org_2 = self.crossover.do_crossover(self.org_1,
00055                                                            self.org_2)
00056         self.assertNotEqual(str(new_org_1.genome), str(start_genome_1),
00057                             "Did not perform a crossover when expected.")
00058         self.assertNotEqual(str(new_org_2.genome), str(start_genome_2),
00059                             "Did not perform a crossover when expected.")
00060         
00061         self.assertNotEqual(str(new_org_1), str(self.org_1),
00062                             "Returned an exact copy of the original organism.")
00063         self.assertNotEqual(str(new_org_2), str(self.org_2),
00064                             "Returned an exact copy of the original organism.")
00065 
00066 class UniformTest(unittest.TestCase):
00067     """Test simple point crossovers.
00068     """
00069     def setUp(self):
00070         self.alphabet = TestAlphabet()
00071         genome_1 = MutableSeq("11111111", self.alphabet)
00072         self.org_1 = Organism(genome_1, test_fitness)
00073 
00074         genome_2 = MutableSeq("22222222", self.alphabet)
00075         self.org_2 = Organism(genome_2, test_fitness)
00076         
00077         genome_3 = MutableSeq("333", self.alphabet)
00078         self.org_3 = Organism(genome_3, test_fitness)
00079 
00080         self.crossover = UniformCrossover(1.0, 0.8)
00081 
00082     def test_basic_crossover(self):
00083         """Test basic uniform crossover functionality.
00084         """
00085         start_genome_1 = self.org_1.genome[:]
00086         start_genome_2 = self.org_2.genome[:]
00087         
00088         new_org_1, new_org_2 = self.crossover.do_crossover(self.org_1,
00089                                                            self.org_2)
00090 
00091         self.assertNotEqual(str(new_org_1.genome), str(start_genome_1),
00092                             "Did not perform a crossover when expected.")
00093         self.assertNotEqual(str(new_org_2.genome), str(start_genome_2),
00094                             "Did not perform a crossover when expected.")
00095     
00096         self.assertNotEqual(str(new_org_1), str(self.org_1),
00097                             "Returned an exact copy of the original organism.")
00098         self.assertNotEqual(str(new_org_2), str(self.org_2),
00099                             "Returned an exact copy of the original organism.")
00100 
00101     def test_ds_prop_uniform_crossover(self):
00102         """Test properties of differing genome length, uniform crossovers.
00103         """
00104         new_org_1, new_org_2 = self.crossover.do_crossover(self.org_1,
00105                                                            self.org_3)
00106 
00107 
00108         self.assertTrue(len(new_org_1.genome) > len(new_org_2.genome),
00109                      "Strings are of wrong sizes after uniform crossover.")
00110 
00111         self.assertEqual(new_org_2.genome.tostring().count("1"),
00112                          new_org_1.genome.tostring().count("3"),
00113                          "There should be equal distributions of the smaller string")
00114 
00115         self.assertEqual(str(self.org_1.genome[len(new_org_2.genome):]),
00116                          str(new_org_1.genome[len(new_org_2.genome):]),
00117                          "Uniform should not touch non-overlapping elements of genome")
00118     
00119     def test_ss_prop_uniform_crossover(self):
00120         """Test properties of equal genome length, uniform crossovers.
00121         """
00122         new_org_1, new_org_2 = self.crossover.do_crossover(self.org_1,
00123                                                            self.org_2)
00124 
00125         self.assertEqual(len(new_org_1.genome), len(new_org_2.genome),
00126                          "Strings are of different sizes after uniform crossover.")
00127 
00128         self.assertEqual(new_org_1.genome.tostring().count("1"),
00129                          new_org_2.genome.tostring().count("2"),
00130                          "There should be equal, inverse distributions")
00131         self.assertEqual(new_org_1.genome.tostring().count("2") ,
00132                          new_org_2.genome.tostring().count("1"),
00133                          "There should be equal, inverse distributions")
00134 
00135 
00136 class InterleaveTest(unittest.TestCase):
00137     """Test 'simple' 4-point crossovers.
00138     """
00139     def setUp(self):
00140         self.alphabet = TestAlphabet()
00141         genome_1 = MutableSeq("11111", self.alphabet)
00142         self.org_1 = Organism(genome_1, test_fitness)
00143 
00144         genome_2 = MutableSeq("22222", self.alphabet)
00145         self.org_2 = Organism(genome_2, test_fitness)
00146         
00147         genome_3 = MutableSeq("333333333", self.alphabet)
00148         self.org_3 = Organism(genome_3, test_fitness)
00149         
00150         self._crossover  = InterleaveCrossover(1.0)
00151 
00152     def test_basic_crossover(self):
00153         """Test basic interleave crossover functionality.
00154         """
00155         start_genome_1 = self.org_1.genome[:]
00156         start_genome_2 = self.org_2.genome[:]
00157         
00158         new_org_1, new_org_2 = self._crossover.do_crossover(self.org_1,
00159                                                             self.org_2)
00160 
00161         self.assertNotEqual(str(new_org_1.genome), str(start_genome_1),
00162                             "Did not perform a crossover when expected.")
00163         self.assertNotEqual(str(new_org_2.genome), str(start_genome_2),
00164                             "Did not perform a crossover when expected.")
00165 
00166         self.assertNotEqual(str(new_org_1), str(self.org_1),
00167                             "Returned an exact copy of the original organism.")
00168         self.assertNotEqual(str(new_org_2), str(self.org_2),
00169                             "Returned an exact copy of the original organism.")
00170        
00171     def test_prop_sym_crossover(self):
00172         """Test properties of interleave point crossover."""
00173         new_org_1, new_org_2 = self._crossover.do_crossover(self.org_1,
00174                                                             self.org_2)
00175 
00176         self.assertEqual(len(new_org_1.genome), len(new_org_2.genome),
00177             "Strings are of different sizes after interleave point crossover.")
00178 
00179         self.assertEqual(new_org_1.genome.tostring().count("1"),
00180                          new_org_2.genome.tostring().count("2"),
00181                          "There should be equal, inverse distributions")
00182         self.assertEqual(new_org_1.genome.tostring().count("2") ,
00183                          new_org_2.genome.tostring().count("1"),
00184                          "There should be equal, inverse distributions")
00185        
00186         self.assertEqual(new_org_1.genome.tostring(), "12121",
00187                          "Did not interleave.")
00188         self.assertEqual(new_org_2.genome.tostring(), "21212",
00189                          "Did not interleave.")
00190 
00191     def test_prop_asym_crossover(self):
00192         """Test basic interleave crossover with asymmetric genomes."""
00193         start_genome_1 = self.org_1.genome[:]
00194         start_genome_3 = self.org_3.genome[:]
00195 
00196         new_org_1, new_org_3 = self._crossover.do_crossover(self.org_1,
00197                                                             self.org_3)
00198 
00199         self.assertNotEqual(str(new_org_1.genome), str(start_genome_1),
00200                             "Did not perform a crossover when expected.")
00201         self.assertNotEqual(str(new_org_3.genome), str(start_genome_3),
00202                             "Did not perform a crossover when expected.")
00203 
00204         self.assertNotEqual(str(new_org_1), str(self.org_1),
00205                             "Returned an exact copy of the original organism.")
00206         self.assertNotEqual(str(new_org_3), str(self.org_3),
00207                             "Returned an exact copy of the original organism.")
00208 
00209         self.assertEqual(new_org_1.genome.tostring(), "13131",
00210                          "Did not interleave with growth.")
00211         self.assertEqual(new_org_3.genome.tostring(), "31313333",
00212                          "Did not interleave with growth.")
00213     
00214 class FourPointTest(unittest.TestCase):
00215     """Test 'simple' 4-point crossovers.
00216     """
00217     def setUp(self):
00218         self.alphabet = TestAlphabet()
00219         genome_1 = MutableSeq("11111", self.alphabet)
00220         self.org_1 = Organism(genome_1, test_fitness)
00221 
00222         genome_2 = MutableSeq("22222", self.alphabet)
00223         self.org_2 = Organism(genome_2, test_fitness)
00224         
00225         self.sym_crossover = GeneralPointCrossover(3,1.0)
00226         self.asym_crossover = GeneralPointCrossover(4,1.0)
00227 
00228     def test_basic_crossover(self):
00229         """Test basic 4-point crossover functionality.
00230         """
00231         start_genome_1 = self.org_1.genome[:]
00232         start_genome_2 = self.org_2.genome[:]
00233         
00234         new_org_1, new_org_2 = self.sym_crossover.do_crossover(self.org_1,
00235                                                                self.org_2)
00236 
00237         self.assertNotEqual(str(new_org_1.genome), str(start_genome_1),
00238                             "Did not perform a crossover when expected.")
00239         self.assertNotEqual(str(new_org_2.genome), str(start_genome_2),
00240                             "Did not perform a crossover when expected.")
00241 
00242         self.assertNotEqual(str(new_org_1), str(self.org_1),
00243                             "Returned an exact copy of the original organism.")
00244         self.assertNotEqual(str(new_org_2), str(self.org_2),
00245                             "Returned an exact copy of the original organism.")
00246                
00247     def test_prop_sym_crossover(self):
00248         """Test properties of symmetric 4-point crossover.
00249         """
00250         new_org_1, new_org_2 = self.sym_crossover.do_crossover(self.org_1,
00251                                                                self.org_2)
00252 
00253         self.assertEqual(len(new_org_1.genome), len(new_org_2.genome),
00254                          "Strings are of different sizes after symmetric crossover.")
00255 
00256         self.assertEqual(new_org_1.genome.tostring().count("1"),
00257                          new_org_2.genome.tostring().count("2"),
00258                          "There should be equal, inverse distributions")
00259         self.assertEqual(new_org_1.genome.tostring().count("2") ,
00260                          new_org_2.genome.tostring().count("1"),
00261                          "There should be equal, inverse distributions")
00262     
00263     def test_basic_asym_crossover(self):
00264         """Test basic asymmetric 2-point crossover functionality.
00265         """
00266         start_genome_1 = self.org_1.genome[:]
00267         start_genome_2 = self.org_2.genome[:]
00268         
00269         new_org_1, new_org_2 = self.asym_crossover.do_crossover(self.org_1,
00270                                                                 self.org_2)
00271 
00272         self.assertNotEqual(str(new_org_1.genome), str(start_genome_1),
00273                             "Did not perform a crossover when expected.")
00274         self.assertNotEqual(str(new_org_2.genome), str(start_genome_2),
00275                             "Did not perform a crossover when expected.")
00276 
00277         self.assertNotEqual(str(new_org_1), str(self.org_1),
00278                             "Returned an exact copy of the original organism.")
00279         self.assertNotEqual(str(new_org_2), str(self.org_2),
00280                             "Returned an exact copy of the original organism.")
00281     
00282     
00283 class TwoPointTest(unittest.TestCase):
00284     """Test simple 2-point crossovers.
00285     """
00286     def setUp(self):
00287         self.alphabet = TestAlphabet()
00288         genome_1 = MutableSeq("11111111", self.alphabet)
00289         self.org_1 = Organism(genome_1, test_fitness)
00290 
00291         genome_2 = MutableSeq("22222222", self.alphabet)
00292         self.org_2 = Organism(genome_2, test_fitness)
00293         
00294         self.asym_crossover = TwoPointCrossover(1.0)
00295 
00296     def test_basic_asym_crossover(self):
00297         """Test basic asymmetric 2-point crossover functionality.
00298         """
00299         start_genome_1 = self.org_1.genome[:]
00300         start_genome_2 = self.org_2.genome[:]
00301         
00302         new_org_1, new_org_2 = self.asym_crossover.do_crossover(self.org_1,
00303                                                                 self.org_2)
00304 
00305         self.assertNotEqual(str(new_org_1.genome), str(start_genome_1),
00306                             "Did not perform a crossover when expected.")
00307         self.assertNotEqual(str(new_org_2.genome), str(start_genome_2),
00308                             "Did not perform a crossover when expected.")
00309 
00310         self.assertNotEqual(str(new_org_1), str(self.org_1),
00311                             "Returned an exact copy of the original organism.")
00312         self.assertNotEqual(str(new_org_2), str(self.org_2),
00313                             "Returned an exact copy of the original organism.")
00314 
00315     
00316 class TestCrossover:
00317     """Provide basic crossover functionality for testing SafeFitness.
00318     """
00319     def __init__(self):
00320         # whether or not to produce new organisms with lower fitness
00321         # higher fitness, or the same organism
00322         self.type = "lower"
00323 
00324     def do_crossover(self, org_1, org_2):
00325         seq_org1 = org_1.genome.toseq()
00326         seq_org2 = org_2.genome.toseq()
00327         org1_genome = seq_org1.tostring()
00328         org2_genome = seq_org2.tostring()
00329 
00330         new_org_1 = org_1.copy()
00331         new_org_2 = org_2.copy()
00332         
00333         if self.type == "same":
00334             return new_org_1, new_org_2
00335         elif self.type == "lower":
00336             new_org1_genome = str(int(org1_genome) - 1)
00337             new_org2_genome = str(int(org2_genome) - 1)
00338 
00339             new_org_1.genome = MutableSeq(new_org1_genome,
00340                                           org_1.genome.alphabet)
00341             new_org_2.genome = MutableSeq(new_org2_genome,
00342                                           org_2.genome.alphabet)
00343         elif self.type == "higher":
00344             new_org1_genome = str(int(org1_genome) + 1)
00345             new_org2_genome = str(int(org2_genome) + 1)
00346         else:
00347             raise ValueError("Got type %s" % self.type)
00348 
00349         new_org_1.genome = MutableSeq(new_org1_genome,
00350                                       org_1.genome.alphabet)
00351         new_org_2.genome = MutableSeq(new_org2_genome,
00352                                       org_2.genome.alphabet)
00353 
00354         return new_org_1, new_org_2
00355                 
00356 class SafeFitnessTest(unittest.TestCase):
00357     """Tests for crossovers which do not reduce fitness.
00358     """
00359     def setUp(self):
00360         self.alphabet = TestAlphabet()
00361         genome_1 = MutableSeq("2", self.alphabet)
00362         self.org_1 = Organism(genome_1, test_fitness)
00363 
00364         genome_2 = MutableSeq("2", self.alphabet)
00365         self.org_2 = Organism(genome_2, test_fitness)
00366 
00367         self.test_crossover = TestCrossover()
00368 
00369     def test_keep_higher(self):
00370         """Make sure we always keep higher fitness when specified.
00371         """
00372         crossover = SafeFitnessCrossover(self.test_crossover)
00373 
00374         self.test_crossover.type = "same"
00375         new_org_1, new_org_2 = crossover.do_crossover(self.org_1, self.org_2)
00376 
00377         self.assertEqual(str(new_org_1), str(self.org_1),
00378                          "Did not retain organism for same fitness.")
00379         self.assertEqual(str(new_org_2), str(self.org_2),
00380                          "Did not retain organism for same fitness.")
00381 
00382         self.test_crossover.type = "lower"
00383         new_org_1, new_org_2 = crossover.do_crossover(self.org_1, self.org_2)
00384 
00385         self.assertEqual(str(new_org_1), str(self.org_1),
00386                          "Did not retain organism when crossover had lower fitness.")
00387         self.assertEqual(str(new_org_2), str(self.org_2),
00388                          "Did not retain organism when crossover had lower fitness.")
00389 
00390         self.test_crossover.type = "higher"
00391         new_org_1, new_org_2 = crossover.do_crossover(self.org_1, self.org_2)
00392 
00393         self.assertTrue(new_org_1.fitness > self.org_1.fitness and \
00394                      new_org_2.fitness > self.org_2.fitness,
00395                      "Did not get new organism when it had higher fitness.")
00396 
00397     def test_keep_lower(self):
00398         """Make sure we do normal crossover functionality when specified.
00399         """
00400         crossover = SafeFitnessCrossover(self.test_crossover, 1.0)
00401 
00402         self.test_crossover.type = "same"
00403         new_org_1, new_org_2 = crossover.do_crossover(self.org_1, self.org_2)
00404 
00405         self.assertEqual(str(new_org_1), str(self.org_1),
00406                          "Did not retain organism for same fitness.")
00407         self.assertEqual(str(new_org_2), str(self.org_2),
00408                          "Did not retain organism for same fitness.")
00409 
00410         self.test_crossover.type = "lower"
00411         new_org_1, new_org_2 = crossover.do_crossover(self.org_1, self.org_2)
00412 
00413         self.assertNotEqual(str(new_org_1), str(self.org_1),
00414                          "Retained lower fitness organism in crossover.")
00415         self.assertNotEqual(str(new_org_2), str(self.org_2),
00416                          "Retained lower fitness organism in crossover.")
00417         
00418         self.test_crossover.type = "higher"
00419         new_org_1, new_org_2 = crossover.do_crossover(self.org_1, self.org_2)
00420 
00421         self.assertTrue(new_org_1.fitness > self.org_1.fitness and \
00422                      new_org_2.fitness > self.org_2.fitness,
00423                      "Did not get new organism under higher fitness conditions.")
00424 
00425 if __name__ == "__main__":
00426     runner = unittest.TextTestRunner(verbosity = 2)
00427     unittest.main(testRunner=runner)