Contracts

Contracts are used to check the pre and post conditions of functions to make sure that the evolutionary algorithm remains constrained within the solution space.

All contracts used by all functions are listed here. It is highly recommended that similar functions that are implemented in the future implement similar contracts. This will be explained further as each contract is explaioned.

GA.py

The main GA driver has the following contracts. It is highly recommended that any GA implemented to maximize the fitness score should implement these contracts.

The main GA runner

Preconditions

1. kwargs should be supplied
2. kwargs is a dict mapping argument names (strings) to argument values
3. The maximum number of generations allowed is greater than 0

Postconditions

1. kwargs should not be changed

2. At least one of the following two conditions must hold

   1. the fitness of the fittest individual (being returned) is at least targetscore
   2. the current generation count is equal to the maximum number of generations allowed

3. the maximum number of generations allowed is greater than 0

Individual.py

The following contracts must be followed for any implementation of the Individual class

Individual.__hash__(self, other)

Preconditions

None

Postconditions

1. an int should be returned
2. self should not be changed

In addition to these, the current implementation has the following methods implemented:

Individual.__eq__(self, other)

Preconditions

1. other should be an instance of Individual

Postconditions

1. other should not be changed
2. self should not be changed

Individual.__len__(self)

Preconditions

None

Postconditions

1. self should not be changed

Individual.__setitem__(self, index, obj)

Preconditions

1. Exactly one of the following two conditions must be satisfied:

   1. 0 <= index <= len(self.chromosomes)
   2. len(self.chromosomes)*-1 >= index >= -1

Postconditions

1. The object at self.chromosomes[index] should be obj

Individual.__contains__(self, chromosome)

Preconditions

None

Postconditions

1. self should not be changed
2. chromosome should not be changed

Individual.__repr__(self)

Preconditions

None

Postconditions

1. self should not be changed

Individual.append(self, chrom)

Preconditions

None

Postconditions

1. The length of self.chromosomes should be increased by exactly 1
2. The last chromosome in self.chromosomes should be chrom

Individual.count(self, sub, chrom)

Preconditions

None

Postconditions

1. self should not be changed

population.py

The following contracts are applied to the functions in population.py

genPop(N, chromGenfuncs, chromGenParams)

Preconditions

1. N >= 0
2. chromGenfuncs is a list
3. Every entry in chromGenfuncs is a function
4. chromGenParamss is a list
5. The lengths of chromGenfuncs and chromGenParams are equal

Postconditions

1. The inputs are unchanged
2. Function returns a list
3. The length of the returned list is N
4. The returned list contains exactly 1 of each item i.e. no two items in the returned list are equal

genCharsChrom(l, chars)

Preconditions

1. l is an integer
2. chars is an instance of some class that implements __getitem__
3. chars is an instance of some class that implements __len__
4. len(chars) is greater than 0

Postconditions

1. The inputs are unchanged
2. Function returns a list
3. The length of the returned list is l
4. Every element in the returned list exists in chars

genTour(numCities)

Preconditions

1. numCities is an integer

Postconditions

1. The inputs are unchanged
2. Function returns a list
3. The length of the returned list is numCities
4. Every element in the returned list exists exactly once in the returned list.

score.py

score(p, scorefuncs, scorefuncparams, SCORES)

Preconditions

1. p is an instance of Individual
2. scorefuncs is a list of functions
3. scorefuncparams is a list of tuples
4. The lengths of scorefuncs and scorefuncparams are equal
5. SCORES is a dictionary

Postconditions

1. The inputs are unchanged

2. p is in SCORES

3. Exactly one of the following two conditions are met:

   1. p was in SCORES before this function was called and the number of entries in SCORES has not changed
   2. p was not in SCORES before this function was called and the number of entries in SCORES has increased by exactly 1

scoreOnes(p)

Preconditions

1. p is list
2. All elements in p are strings of length exactly 1
3. All elements in p are either ‘0’ or ‘1’

Postconditions

1. p is unchaged
2. An integer is returned
3. The value returned is at least 0

scoreTSP(tour, DIST)

post:

isinstance(__return__, float)

post[tour, DIST]:

__old__.tour == tour __old__.DIST == DIST

Preconditions

1. tour is a list
2. DIST is a dictionary
3. All elements in tour are integers
4. All keys in DIST are integers
5. All values in DIST are dictionaries
6. Every key in every value of DIST is an integer
7. Every value in every value of DIST is a float

Loop Invariant

1. answer (the value to be returned is at most 0 and monotonously decreases

Postconditions

1. The inputs are unchanged
2. The function returns a float

getRouletteWheel(pop, SCORES)

Preconditions

1. pop is a list of instances of Individual
2. SCORES is a dictionary
3. Every element in pop is a key in SCORES

Postconditions

1. The inputs are unchanged
2. A list of 3-tuples of type (Individual, float, float) is returned
3. The length of the returned list is equal to the length of pop
4. The first element of every tuple in the returned list exists in pop
5. The second float is smaller than the third float in every tuple in the returned list

rouletteWheelSelect(wheel, s=None)

Preconditions

1. wheel is a list of 3-tuples which satisfy all the following conditions

   1. The first element is an instance of Individual
   2. The last two elements are floats
   3. The first float is smaller than the second

2. Exactly one of the following two conditions are met:

   1. s is a float
   2. s is None

Postconditions:

1. The inputs are unchanged
2. An instance of Individual is returned

tournamentSelect(pop, T, w, n, scorefunc, scoreparams)

Preconditions

1. pop is a list of instances of Individual
2. T is an integer
3. w is an integer
4. n is an integer
5. w is at most n
6. n%w is exactly 0
7. n is at most T
8. scoreparams is a tuple

Postconditions

1. The inputs are unchanged
2. A list of n instances of Individual is returned

crossover.py

The following contracts are implemented for the crossover functions.

crossOnes(p1, p2, chrom)

Preconditions

1. p1 and p2 are instances of list

Postconditions

1. The inputs are unchaged

2. A tuple of two instances of list is returned

3. Each list in the return tuple satisfies the following conditions:

   1. each element in the list exists in either p1 or p2 or both.

injectionco(p1, p2, chrom)

Preconditions

1. p1 and p2 are instances of list
2. The length of p1 is exactly equal to the length of p2
3. p1 is a permutation of [0… len(p1)-1]
4. p2 is a permutation of [0… len(p2)-1]

Postconditions

1. The inputs are unchaged
2. A new object is returned of type list
3. The length of the returned list is exactly equal to the length of p1 (and therefore of p2 as well)
4. The function returns a permutation i.e. all elements in the returned list occur exactly once

twoChildCrossover(p1,p2, crossfuncs, crossparams)

Preconditions

1. p1 and p2 are instances of Individual
2. p1 and p2 are of exactly equal length
3. The number of elements in crossfuncs is exactly equal to the length of p1 (and therefore of p2)
4. The number of elements in crossfuncs is exactly equal to the number of elements in crossparams
5. Every element in crossparams is a tuple

Postconditions

1. The inputs are unchanged
2. A tuple of two elements of type Individual is returned
3. Each of the returned children has the same number of chromosomes as the parents
4. Each chromosome in each of the children has the same length as the corresponding chromosome of both parents

oneChildCrossover(p1,p2, crossfuncs, crossparams)

Preconditions

1. p1 and p2 are instances of Individual
2. p1 and p2 are of exactly equal length
3. The number of elements in crossfuncs is exactly equal to the length of p1 (and therefore of p2)
4. The number of elements in crossfuncs is exactly equal to the number of elements in crossparams
5. Every element in crossparams is a tuple

Postconditions

1. The inputs are unchanged
2. A tuple of one element of type Individual is returned
3. The returned child has the same number of chromosomes as the parents
4. Each chromosome in the child has the same length as the corresponding chromosome of both parents

muatation.py

mutateSingleAllele(p, chrom, chars)

Preconditions

1. p is an instance of Individual

2. chrom is an integer

3. The value of each gene in the chrom th chromosome of p exists in chars

4. Exactly one of the following two conditions must be satisfied:

   1. 0 <= index <= len(self.chromosomes)
   2. len(self.chromosomes)*-1 >= index >= -1

Postconditions

1. The inputs are unchanged
2. A new instance of Individual is returned
3. The chrom th chromosome of the returned individual is not equal to the chrom th chromosome of p
4. All other chromosomes of the returned individual are exactly the same as the corresponding chromosome of p

swapmut(p, chrom)

Preconditions

1. p is an instance of Individual

2. chrom is an integer

3. Exactly one of the following two conditions are satisfied:

   1. 0 <= chrom <= len(p.chromosomes)
   2. len(self.chromosomes)*-1 >= index >= -1

Postconditions

1. The inputs are unchaged
2. An instance of Individual is returned
3. All values in the chrom th chromosome of p are present in the chrom th chromosome of the output individual
4. The chrom th chromosomes of the output individual and p are not equal
5. There are exactly two genes in the chrom th chromome of p and the returned individual, whose values differ

revmut(p, chrom)

Preconditions

1. p is an instance of Individual

2. chrom is an integer

3. Exactly one of the following two conditions are satisfied:

   1. 0 <= chrom <= len(p.chromosomes)
   2. len(self.chromosomes)*-1 >= index >= -1

Postconditions

1. The inputs are unchaged
2. An instance of Individual is returned
3. All values in the chrom th chromosome of p are present in the `chrom th chromosome of the output individual
4. The chrom th chromosomes of the output individual and p are not equal

shufflemut(p, chrom)

post[p, chrom]:

__old__.p == p __old__.chrom == chrom isinstance(__return__, Individual) __return__.chromosomes[chrom] != p.chromosomes[chrom] forall(p.chromosomes[chrom], lambda e: e in __return__.chromosomes[chrom]) forall(__return__.chromosomes[chrom], lambda e: e in p.chromosomes[chrom])

Preconditions

1. p is an instance of Individual

2. chrom is an integer

3. Exactly one of the following two conditions are satisfied:

   1. 0 <= chrom <= len(p.chromosomes)
   2. len(self.chromosomes)*-1 >= index >= -1

Postconditions

1. The inputs are unchaged
2. An instance of Individual is returned
3. All values in the chrom th chromosome of p are present in the `chrom th chromosome of the output individual
4. The chrom th chromosomes of the output individual and p are not equal
5. The length of the chrom th chromosome of the returned individual is exactly equal to the length of the chrom th chromosome of p